HashSet removal question

Newbie & Debugging Questions
#1

I have an object called Cursor. It has a value in it that gets incremented.
I have a HashSet called Cursors. When the Cursor reaches a target, I want to delete it from the HashSet. But I’m running into Concurrency errors.
The code fragment below (a “for” loop) runs repeatedly in yet another encasing loop.

First try


for (Cursor c : cursors)
{
    newValue = c.increment();
    if (newValue > target) cursors.remove(c);
}

Second try, I made a second HashSet called “removalSet”


for (Cursor c : cursors)
{
    newValue = c.increment();
    if (newValue > target) removalSet.add(c);
}
for (Cursor c : removalSet)
{
    cursors.remove(c);
}
removalSet.clear();

I am fairly confident this second version is fine, but I did get one concurrency exception in about 40 playbacks, at the first “for” loop. There was another error also made in that run that maybe could have been the real cause of the exception.

Should #2 be OK? Is there a better way to do this? Perhaps another collection option? I see that there is a ConcurrentHashMap, but I don’t think I should have to add the complication of dealing with keys & values.

#2

You’re getting ConcurrentModificationExceptions, which means you’re modifying the set at the same you’re iterating it. That is different than the concurrency solved by ConcurrentHashMap. That is why #2 works, because you don’t remove while iterating the same set.

You should use the set’s iterator:


Iterator<Cursor> it = cursors.iterator();
while(it.hasNext()) {
   Cursor c = it.next();
   newValue = c.increment();

   if (newValue > target)
      it.remove();
}

Your first for-loop actually used an iterator under the hood, but didn’t expose it, so you couldn’t call Iterator.remove() to properly remove it from the underlying collection.

#3

Perfect! Thank you. I thought there was a better way.

#4

Yeah, even if a quick for-loop (for(Cursor c : cursors){ … }) is easier to read and faster (or so I’ve heard) it makes it impossible to modify the actual list, set or array you’re iterating over, as you don’t know the index of each cursor or have access to the iterator.

#5

The iterator work for the “removes” but [doh!] I forgot I also have add() ops happening, as a second, totally asynchronous input to this set. Putting a lock around the entire iteration seems like it might be overkill.

“Java Concurrency in Practice” (Goetz) suggests (pg. 83) cloning the list before iterating. The collection is small (good), but the frequency of cloning will be high.

Still testing…

#6

If you genuinely do have multiple threads accessing one collection, then either put a mutex around it, or look into the concurrent collections. Taking a clone before iterating is (basically) what those collections do so you’ll just be reinventing it, probably with more bugs and slower. :slight_smile:

#7

I’m not sure how efficient it is but I tend to use .toArray(), then iterate through the array and remove dead objects from the collection as required.

#8

Yes, truly concurrent. The iteration is in its own thread. It is for playing back some sound data multiple times, overlapping. The calling code will usually be from the GUI. See the Audio thread: “AudioMixer”, the post on “ClipTrack”. I’m trying to design a more efficient and useful alternative to the JavaSound Clip.

Here is a simplified version of a “mutex” solution that seems to work well:


public play()
{
	Cursor c = new Cursor();
	synchronized(lock)
	{
		cursors.add(c);
	}
}

//...from within the runnable...

                        while (playing)
                        {
				// ...do some initialization stuff...
				synchronized(lock)
				{
					cursorsClone = (HashSet<Cursor>) cursors.clone();
				}
				for (Cursor c : cursorsClone)
				{	
					// ...do some stuff with the Cursor...
					
					// advance cursor, and delete if finished
					c.idx += c.incr;
					if (c.idx > clipLastRead)
					{
						synchronized(lock)
						{
							cursors.remove(c);
						}
					}
				}
			}

The simplest concurrent collection is a HashMap, yes? That wouldn’t be much help, I don’t think. But if the implementation of the concurrent collections is to make a clone, then I’m feeling more reassured that the above is fine. The number of iterations in the HashSet will always be small, so cloning should be quick.

#9

Acquiring a lock can be expensive if there’s contention. It might be better to lock once for the pre-iteration copy, build up a collection of items to remove inside the loop, and then lock again after the loop has finished to do a removeAll.

#10

+1 +1 +1!!! :slight_smile: Phil, I know you’ve seen this article before (http://www.rossbencina.com/code/real-time-audio-programming-101-time-waits-for-nothing), but it pays reiterating - try and keep locks out of your audio thread.

Ideally, as I suggested in your other (forum!) thread, make it so that play() can only be called from within your audio thread. If you really want to allow play() to be called from the GUI thread, then maybe consider something along these lines -


public void play() {
  if (AudioMixer.isAudioThread()) {
    playImpl();
  } else {
    AudioMixer.invokeLater(new Runnable() {
      public void run() {playImpl();}
    });
  }
}

Also, think about optimizing the majority of times this code runs. In most cases, you’ll not be adding or removing cursors, so the need to clone the HashSet is adding much extra overhead. In fact, you don’t really need a Set at all, as it’s all private you don’t need the extra overhead of enforcing the semantics of Set. Maybe consider using a plain Cursor[]. Copy this from a field into a local variable each time you iterate through the cursors, then you can change the field to point to a different array if you need to add or remove cursors.


private Cursor[] cursors;

...
while(playing) {
  Cursor[] localCursors = cursors;
  for (Cursor c : localCursors) { ... }
}

private void add(Cursor c) {cursors = ListenerUtils.add(cursors, c);} 
private void remove(Cursor c) {cursors = ListenerUtils.remove(cursors, c);}

I’ve got a class here http://code.google.com/p/praxis/source/browse/praxis.impl/src/net/neilcsmith/praxis/impl/ListenerUtils.java that does the array copy - as you know you’re working with Cursor, you wouldn’t need to use reflection to create the new array. This approach is somewhat similar to CopyOnWriteArrayList, but without the synchronization overhead.

#11

I am reading the article cited by nsigma.

Question:

    Cursor c = new Cursor();
    synchronized(lock)
    {
        cursors.add(c);
    }

In this code, “cursors” is a HashSet. The ONLY thing in the mutex is a single command, which as far as I know amounts to putting an address in a list. It is the HashSet.add() method. Is there a danger of “priority inversion” in such a small piece of code? In other words, if a thread from the GUI results in a Cursor being added to the ClipTrack, can this thread be paused by the JVM during the execution of this single command?

It should be possible to use the remove() via the iterator example given by lkhbob, since they are on the same thread. Maybe I can put the actual HashSet add() within the same while loop but outside of the cursor iteration. Then, neither the mutex nor the clone() wouldn’t be needed (for the HashSet itself). Will try tomorrow.

The article on “time-waits-for-nothing”: [quote]But wait you say, how am I supposed to communicate between a GUI and the audio callback if I can’t do these things? How can I do file or network i/o? There are a few options, which I will explain in more detail in future posts, but for now I’ll just say that the best practice is to use lock-free FIFO queues to communicate commands and data between real-time and non-real-time contexts
[/quote]
So, if I understand correctly, the above is kind of what I came up with for the RTESmoother (RealTimeEventSmoother) I wrote about earlier. I’m guessing I can make another variant of that for the GUI to thread to interact with the sound thread.

#12

Actually, this method does a little more than add an address to a list - it has to create a Map.Entry object for a start - HashSet is actually backed by HashMap. It’s still not much to do though …

In theory, yes, though it’s OS specific, and probably not much of a problem. Reason #3 in not to use locks is probably most relevant. Simply put, you want to try and stop your audio thread being descheduled in the middle of processing a buffer of audio, because the cost of the context shift and rescheduling is an unknown.

This model gets worse as a library evolves. What starts as a single back-and-forth context shift becomes multiple as more methods are added in that require a mutex lock. Better to start with a single-threaded model to start with.

Coupled with that, as I’ve mentioned before, your current mutex model doesn’t allow you to play multiple sounds (add multiple cursors) in a single operation at a single moment in time - calling play() twice in succession may or may not get the sounds to start at the same time.

So, if I understand correctly, the above is kind of what I came up with for the RTESmoother (RealTimeEventSmoother) I wrote about earlier. I’m guessing I can make another variant of that for the GUI to thread to interact with the sound thread.
[/quote]
The simplest (though far from only) way to do this would be to post Runnables to a ConcurrentLinkedQueue.

#13

I just found and tested “CopyOnWriteArraySet”.

Works great! I can ditch ALL the synchronizers, and no need to clone or copy the set for iteration.

It seems to be ideally suited for this situation.
The adds and removes are many orders of magnitude less frequent than the iterations.
The iterating set is small.

It also seems like it will be useful, along with “CopyOnWriteArrayList”, for GUI to sound thread communication, in general.

http://download.oracle.com/javase/7/docs/api/java/util/concurrent/CopyOnWriteArrayList.html

[quote]public class CopyOnWriteArrayList
extends Object
implements List, RandomAccess, Cloneable, SerializableA thread-safe variant of ArrayList in which all mutative operations (add, set, and so on) are implemented by making a fresh copy of the underlying array.
This is ordinarily too costly, but may be more efficient than alternatives when traversal operations vastly outnumber mutations, and is useful when you cannot or don’t want to synchronize traversals, yet need to preclude interference among concurrent threads. The “snapshot” style iterator method uses a reference to the state of the array at the point that the iterator was created. This array never changes during the lifetime of the iterator, so interference is impossible and the iterator is guaranteed not to throw ConcurrentModificationException. The iterator will not reflect additions, removals, or changes to the list since the iterator was created. Element-changing operations on iterators themselves (remove, set, and add) are not supported. These methods throw UnsupportedOperationException.

All elements are permitted, including null.

Memory consistency effects: As with other concurrent collections, actions in a thread prior to placing an object into a CopyOnWriteArrayList happen-before actions subsequent to the access or removal of that element from the CopyOnWriteArrayList in another thread.

This class is a member of the Java Collections Framework.
[/quote]

#14

Hi Phil,

As I mentioned above, CopyOnWriteArrayList is much better because it removes all the unnecessary cloning. However, it’s not perfect. Be aware that you’re not removing the locking issue - it still uses a lock internally, so you’re not really ditching the synchronization.

Best wishes, Neil

#15

Hi Neil, I see in your reply #9 where you mentioned CopyOnWriteArrayList. Indeed!

I also liked the idea of CopyOnWriteArraySet, as I do not need to order the Cursors. But the specifications indicate that it uses CopyOnWriteArrayList. So, since the latter can handle the few requirements, why not!

The ConcurrentLinkedQueue looks very useful, too. But these Cursors should not be FIFO. The design of the Cursors is that they can operate at different rates, and overtake one another. ConcurrentHashMap looks good, but I can’t imagine writing efficient code to handle keys.

Now, as far as I can tell from the description, the blocking that occurs with the CopyOnWriteArrayList is NOT during iteration. Therefore, are you sure the audio thread is going to be blocked? If anything, it seems to me that if there is going to be a block, it will be the GUI thread. Maybe I am misreading the description, or have a fundamental misunderstanding about the internals.

I very much appreciate your advice and hope you remain patient with me and continue to give it, even if I am slow to take in everything you have to say!! I only started teaching myself Java two years ago.

Was ListenerUtils meant to be a class that could be used for the question here, or, as an example of an array copy? I couldn’t tell what the purpose of ListenerUtils is. Maybe just intimidated.

I wish the article on avoiding blocks pointed to examples written in Java. Most everything referenced that I could find was in C++. And some of the links at the end which seemed to be about this thread’s question have gone cold or only go to general discussions. Perhaps I did not hunt through there carefully enough.

Reason #3 (Time waits for nothing) went quite over my head. :frowning:

#16

It might be better if we pushed all this discussion into your AudioMixer forum thread - this is getting a little confusing in two places now! :slight_smile: However, I’ll respond to the points you raised above here first.

I meant using ConcurrentLinkedQueue in combination with moving all control calls onto the audio thread, not for Cursors - see my reply in AudioMixer.

Always worth downloading the code and having a look what’s actually going on! You’re right that COWAL does not block during either creating the iterator or iteration. However, you will get blocking with remove() - and also note that the iterator doesn’t seem to support remove() so you’ll have to call it on the list itself. Now, I guess add() and remove() aren’t called that often so there’s going to be a lot less thread contention.

To be honest, right now I’m using LinkedBlockingQueue rather than ConcurrentLinkedQueue in Praxis, which potentially can lock in certain circumstances, and I’ve not noticed a huge issue (which doesn’t mean fixing it is not on my ‘to do’ list at some point!) The important thing is that the Praxis API would allow this change without breaking anything.

No, it’s literally just for array copying - nothing complicated! :slight_smile: It’s for use in association with keeping a Cursor[] field in your ClipTrack (see the code above the link, which I’ve edited to clarify).

Simply put, steer clear of threads and locks! :wink: Slightly less simply, when your audio thread encounters a lock with another thread, the OS thread scheduler has to switch back and forth between them. You have little or no control over how efficiently this happens, and it can be different between OS’s, between different versions of the same OS, and even different systems.