I’ve noticed (and have done this myself) that people tend to rely on ArrayLists for game dev. However, it seems that this is potentially a BAD idea for multithreaded applications since they are not synchronized/thread safe. Now… that being said, I’m looking into other potentials and would like to hear other peoples thoughts.
Since I tend to do lookups against member values, HashTable was a thought… but I’m a bit shaky on the pitfalls of changing the approach from from using ArrayLists.
I know this is a very basic question… but since the data is volatile I’m interested in getting every bit of input I can from those who know.
EDIT: It may be worth mentioning that lookups against these lists are/can be/will be initiated from multiple threads while another thread could potentially be modifying the data or the data could change for some unforeseen reason (i.e. A client could crash, the world could come to an end, etc),… Anyways… enough said.
Raw answer: Learn java.util.concurrent… or don’t do threading. 
Hashtable is a hugely wasteful class. ConcurrentHashMap is 10000000000 times better in pretty much all cases (which is in the java.util.concurrent package). (I’d have to contrive some really strange example to have Hashtable be better.)
If you read often and write little, CopyOnWriteArrayList is a thread safe alternative to ArrayList that is just as fast. It’s also nice because it can be modified within an iterator.
The thing is… I’d be interested to know more about the actual problem because it sounds bad just on description. If you say “lookups” then I think ConcurrentHashMap… not lists at all. Multi-threaded “lookups” in “lists” seem to imply a synchronization nightmare.
2 Likes
[java]package com.fortresswars.util;
import java.util.ArrayList;
import java.util.List;
/**
- Manages instances that can be used by multiple threads, allowing to retrieve random instances that are not busy.<br/>
- <br/>
- It does not control how many parallel instances can exist.
- What it does control is how many <strong>free</strong> instances can co-exist at the same time.<br/>
- To change how many free instances can exist at the same time, take a look at {@link #setLimit(int)}.
*
-
@author Shirkit
*/
public abstract class GroupController<O> {
/**
- Maximum number of unbusy objects that can exist at the same time.<br/>
- <br/>
- <strong>Default value:</strong> 20
*/
protected int limit = 20;
/**
- The {@link List} that will contain all the unbusy objects.
*/
private List<O> free = new ArrayList<O>(limit);
/**
- Sets an instance to not busy, allowing other threads to use it.
- After using an object, this method should be called to add the object back to the list of unbusy objects.
*
-
@param object the object to be unbusied.
*/
public synchronized void unbusy(O object) {
if (free.size() < limit) {
free.add(object);
}
}
/**
- Try to retrive an object that is not busy and mark it as busy.
- If there is no object free to use, creates a new instance of that object.
- <br/><br/>
- When the object is free again, it should be added back with the {@link #unbusy(java.lang.Object) }.
*
-
@return an instance of a object that is not busy.
*/
public synchronized O getFirst() {
if (!free.isEmpty()) {
return free.remove(free.size() - 1);
} else {
return newObject();
}
}
/**
- Generates a new instance of the object.
- Sub-classes must implement this to apply everything
- needed to generate a new instance of the object.<br/>
- <br/>
- A new instance of the object must <strong>not</strong> be added on the {@link #free} list of objects.
*
-
@return a new instance of the object.
*/
protected abstract O newObject();
/**
- Sets the maximum amount of unbusy ojects that can exist exist at the same time.
- When this limit is reached, extra unbusy objects will be removed from this {@link GroupController}.
*
-
@param limit the maximum amount of instances.
*/
public void setLimit(int limit) {
this.limit = limit;
List<O> temp = free;
free = new ArrayList<O>(limit);
for (O obj : temp)
unbusy(obj);
}
/**
- Retrieves the current limit of unbusy objects that can exist at the same time.
*
-
@return the maximum amount of instances.
*/
public int getLimit() {
return limit;
}
// ---- Inherited Methods ---- //
@Override
public String toString() {
return “limit=” + limit + “,” + free.toString();
}
}
[/java]
They are not a BAD idea for multithreading, they can be quite fast. It only depends how you use them. The jME core has an implementation of an SafeArrayList, it’s really worth to check that out. Also, check this implementation I have created 2 years ago. It’s really interesting (at least for my problem) depending on your case.
But for synchronizing threads, any collection can be tricky. The problem is that the threading safe collections may cause a huge overhead, because each one of them work in a specific way that causes more overhead if your application has a specific behavior. The good thing about ArrayLists is that they have a similar behavior in any situation, which isn’t the case for most of the thread safe collections.
Also, remember that the thread safe collections do the synchronization also! How they do it it’s a whole new history, but if you choose not to do your synch, remember that someone is doing, and that is not by magic (it’s interesting that people often forget about this). So, overheads will happen in one way or another.
@shirkit said:
They are not a BAD idea for multithreading, they can be quite fast. It only depends how you use them. The jME core has an implementation of an SafeArrayList, it's really worth to check that out. Also, check this implementation I have created 2 years ago. It's really interesting (at least for my problem) depending on your case.
But for synchronizing threads, any collection can be tricky. The problem is that the threading safe collections may cause a huge overhead, because each one of them work in a specific way that causes more overhead if your application has a specific behavior. The good thing about ArrayLists is that they have a similar behavior in any situation, which isn't the case for most of the thread safe collections.
Also, remember that the thread safe collections do the synchronization also! How they do it it's a whole new history, but if you choose not to do your synch, remember that someone is doing, and that is not by magic (it's interesting that people often forget about this). So, overheads will happen in one way or another.
java.util.concurrent avoids "synchronized" at all costs. "Synchronized" is the sledge hammer of multi-threading.
Note: SafeArrayList is not multithreaded. It is a single threaded version of CopyOnWriteArrayList that directly exposes the internal array for speed. It's useful for cases where iteration may alter the list.
1 Like
@shirkit said:
[java]package com.fortresswars.util;
import java.util.ArrayList;
import java.util.List;
/**
* Manages instances that can be used by multiple threads, allowing to retrieve random instances that are not busy.<br/>
* <br/>
* It does not control how many parallel instances can exist.
* What it does control is how many <strong>free</strong> instances can co-exist at the same time.<br/>
* To change how many free instances can exist at the same time, take a look at {@link #setLimit(int)}.
*
* @author Shirkit
*/
public abstract class GroupController<O> {
/**
* Maximum number of unbusy objects that can exist at the same time.<br/>
* <br/>
* <strong>Default value:</strong> 20
*/
protected int limit = 20;
/**
* The {@link List} that will contain all the unbusy objects.
*/
private List<O> free = new ArrayList<O>(limit);
/**
* Sets an instance to not busy, allowing other threads to use it.
* After using an object, this method should be called to add the object back to the list of unbusy objects.
*
* @param object the object to be unbusied.
*/
public synchronized void unbusy(O object) {
if (free.size() < limit) {
free.add(object);
}
}
/**
* Try to retrive an object that is not busy and mark it as busy.
* If there is no object free to use, creates a new instance of that object.
* <br/><br/>
* When the object is free again, it should be added back with the {@link #unbusy(java.lang.Object) }.
*
* @return an instance of a object that is not busy.
*/
public synchronized O getFirst() {
if (!free.isEmpty()) {
return free.remove(free.size() - 1);
} else {
return newObject();
}
}
/**
* Generates a new instance of the object.
* Sub-classes must implement this to apply everything
* needed to generate a new instance of the object.<br/>
* <br/>
* A new instance of the object must <strong>not</strong> be added on the {@link #free} list of objects.
*
* @return a new instance of the object.
*/
protected abstract O newObject();
/**
* Sets the maximum amount of unbusy ojects that can exist exist at the same time.
* When this limit is reached, extra unbusy objects will be removed from this {@link GroupController}.
*
* @param limit the maximum amount of instances.
*/
public void setLimit(int limit) {
this.limit = limit;
List<O> temp = free;
free = new ArrayList<O>(limit);
for (O obj : temp)
unbusy(obj);
}
/**
* Retrieves the current limit of unbusy objects that can exist at the same time.
*
* @return the maximum amount of instances.
*/
public int getLimit() {
return limit;
}
// ---- Inherited Methods ---- //
@Override
public String toString() {
return "limit=" + limit + "," + free.toString();
}
}
[/java]
This class looks like it would be better served with a ConcurrentLinkedQueue internally and get rid of the performance sledge hammers, I mean "synchronized" statements. Or if you want a fixed size then you can use an ArrayBlockingQueue and get the added benefit of being able to block until an item is available.
@pspeed said:
The thing is... I'd be interested to know more about the actual problem because it sounds bad just on description. If you say "lookups" then I think ConcurrentHashMap... not lists at all. Multi-threaded "lookups" in "lists" seem to imply a synchronization nightmare.
Fortunately, at this point... the problem is nothing more than a "potential" problem... that will become a "real" problem at some point in the future. I knew this was going to be the case, however, how you store and manage data (if implemented in a well thought out manner) can be changed with little to no impact of application logic (more in the "no impact" arena should be your target :) ). Sooooo... instead of spending a lot of time up front considering these issues, I worked on game logic knowing that how I am "managing" the data would change at some time in the future. It will literally take me an hour or so to make all necessary changes to both the server and client once I determine the proper way of handling this.
And... that's a huge yes in terms of synchronization nightmare. So... it is time to bury myself in exploring java.util.concurrent seeing as it should contain all the answers I am looking for! ConcurrentHashMap (in particular) is exactly what I was looking for in this case. What I find amazing is that I'm searching the web, reading through discussions, javadocs, etc, etc concerning this subject and not once did I see a reference to ConcurrentHashMap. /boggle
Thanks a ton for pointing me in the right direction... as I thought that the concurrent package contained nothing more than the executor, callables and futures. Guess there is quite a bit more to it >.<
By do the synchronizing I mean do the things that are required for allowing it to be accessed by various threads.
You’ve been reading the wrong places, then. java.util.concurrent was like a beacon from the heavens when it was added. Any of us who had been following Doug Lea’s writing on Java threading did a little dance for joy when this stuff was added. They are very tricky classes. It’s almost like fully understanding them will drive you mad… but I still try.
There have been numerous articles and stuff dissecting these classes down to the minute detail of the volatiles usage, lock ordering, etc… Fascinating stuff. You kind of have already had to come fully through Cthulhu-like madness from “understanding why double-checked locking is bad” before it makes sense why some stuff is the way it is.
@shirkit said:
By do the synchronizing I mean do the things that are required for allowing it to be accessed by various threads.
Yeah, I wondered if that's what you meant... posted class not withstanding.
I put the note regarding the class way before the code 
Btw, you think it’s better suited with ConcurrentLinkedQueue? I did some benchmarking on my end between my implementation and CopyOnWrite, and I got some really good results for mine.
@shirkit said:
I put the note regarding the class way before the code :P Btw, you think it's better suited with ConcurrentLinkedQueue? I did some benchmarking on my end between my implementation and CopyOnWrite, and I got some really good results for mine.
ConcurrentLinkedQueue is perfect for the way you've implemented your pool. It's essentially a queue anyway: first object to be released is the first to be returned.
ArrayList will be the fastest if you've preallocated its size but then you don't need a list at all and a plain array would be even faster. Now we are really to the level of microoptimization.
The real issue is all of the synchronized calls. You make threads wait that potentially didn't have to and that makes them lose an entire rest of their time slice, potentially. Nevermind the monitor setup overhead of a synchronized in the first place.
P.S.: And CopyOnWriteArrayList is exactly the wrong thing in your case since you write exactly as often as you read… it’s easily the worst possible approach in that case.
@shirkit said:
public void setLimit(int limit) {
this.limit = limit;
List<O> temp = free;
free = new ArrayList<O>(limit);
for (O obj : temp)
unbusy(obj);
}
[/java]
Also, while I'm rambling... a note on this method. This method may cause strange behavior on multicore machines if you change the limit will threads are actually using the data structure. The strange behavior is probably more predictably strange on single core machines... but reordering can make it problematic either way. If you continue using this class and call setLimit() while running then you should make the method synchronized.
@pspeed said:
You kind of have already had to come fully through Cthulhu-like madness from "understanding why double-checked locking is bad" before it makes sense why some stuff is the way it is.
Have I actually found another person who actually reads Lovecraft? At the Mountains of Madness... absolute FAVORITE book ever. I have heard rumor that Guillermo del Toro has been trying to get funding for making this into a true-to-the-book movie for years... but so many people have HACKED Lovecraft's stories into BAD b-movies that it has been next to impossible for him to find anyone willing to invest in it. :(
@t0neg0d said:
Have I actually found another person who actually reads Lovecraft? At the Mountains of Madness... absolute FAVORITE book ever. I have heard rumor that Guillermo del Toro has been trying to get funding for making this into a true-to-the-book movie for years... but so many people have HACKED Lovecraft's stories into BAD b-movies that it has been next to impossible for him to find anyone willing to invest in it. :(
Sorry... I have not read the books but I've been around enough people who have that I understand a bit about the mythos. :) del Toro could probably do a decent job if they let him.
P.S.: I found it interesting that firefox's spell checker could help me properly spell Cthulhu. :)
@pspeed said:
Sorry... I have not read the books but I've been around enough people who have that I understand a bit about the mythos. :) del Toro could probably do a decent job if they let him.
P.S.: I found it interesting that firefox's spell checker could help me properly spell Cthulhu. :)
One of the reasons I love his stuff (aside from his writing style) is everything was (semi)short stories... which is about the amount of time I have to dedicate towards reading (when I do).
@t0neg0d said:
One of the reasons I love his stuff (aside from his writing style) is everything was (semi)short stories... which is about the amount of time I have to dedicate towards reading (when I do).
Yeah, I haven't had time for fiction in a while. I have a stack of art books that I'm working through trying to resurrect my nascent art training.
I think the last book I read was Alchemy of Stone... which is told from the perspective of a Steampunk-style android. Kind of interesting, though... and dangerously off topic. :)
@pspeed said:
Yeah, I haven't had time for fiction in a while. I have a stack of art books that I'm working through trying to resurrect my nascent art training.
I think the last book I read was Alchemy of Stone... which is told from the perspective of a Steampunk-style android. Kind of interesting, though... and dangerously off topic. :)
No issues there... you answered the question I had already :) Will see if I can find a copy of that book... sounds interesting!
@pspeed Yeah, I never called that setLimit actually, I didn’t even see that it wasn’t sync (it should be). Also, the actual sync blocks should be inside the methods, and using THIS as the paremeter. I just noticed that this is the old class, the actual class has something like this:
[java]
public void unbusy(O object) {
if (free.size() < limit) {
synchronized (this) {
free.add(object);
}
}
}
public O getFirst() {
if (!free.isEmpty()) {
synchronized (this) {
return free.remove(free.size() - 1);
}
} else {
return newObject();
}
}
[/java]
@shirkit said:
@pspeed Yeah, I never called that setLimit actually, I didn't even see that it wasn't sync (it should be). Also, the actual sync blocks should be inside the methods, and using THIS as the paremeter. I just noticed that this is the old class, the actual class has something like this:
[java]
public void unbusy(O object) {
if (free.size() < limit) {
synchronized (this) {
free.add(object);
}
}
}
public O getFirst() {
if (!free.isEmpty()) {
synchronized (this) {
return free.remove(free.size() - 1);
}
} else {
return newObject();
}
}
[/java]
This methods may allow a caller to avoid the limit or even worse... remove an element that is no longer there. getFirst() being the most dangerous since another thread could snatch the one free item before the sync block gets to run and try to remove one from an empty list.
Trying to get clever with threading can be dangerous. There was no real reason to move in the synchronized inside the methods and as we see... several bad ones.