Ants: Good Java solution?

[Andreas Wenger]

Hi,

for seminar talk at my university I have to prepare a demo program
showing Clojure's concurrency features. I stumbled upon the ants demo
presented in Rich Hickey's "Clojure Concurrency" talk ( http://blip.tv/file/812787
) which I like very much. I began to port the program to Java to
demonstrate how difficult it is to do the same job in Java.

Rich already said that is very hard to do that. For example, he states
that you need to lock the whole world (all cells and ants) if you want
to create a report with a consistent view of the program's state in a
certain point of time. What does that mean in Java? Do we need a
"global lock" for that? But then, I have to use the same global lock
on all writing operations, too? This results in destroying all
concurrency.

So my question is: Has anybody tried to port the ants demo to Java?
Any experiences?

Thanks,

Andi

[ianp]

> … if you want

> to create a report with a consistent view of the program's state in a
> certain point of time. What does that mean in Java? Do we need a
> "global lock" for that? But then, I have to use the same global lock
> on all writing operations, too? This results in destroying all
> concurrency.

Yes, exactly. This is the problem with a Java based version (at least
with one that uses the standard collections libraries). At the very
least your reporting function would have to make a complete copy of
the world state while holding the lock, it could then go in to process
this and produce the report on another thread after releasing the
lock.

This is why persistent data structures are so cool: you gain the
ability to look at consistent snapshots of the world for free.

Cheers,
Ian.

[Raoul Duke]

> This is why persistent data structures are so cool: you gain the
> ability to look at consistent snapshots of the world for free.

it is not impossible to use persistent data structures with plain old
java, by the way :-)

[Krukow]

On Jan 2, 4:03 pm, ianp <ian.phill...@gmail.com> wrote:
<snip>

> Yes, exactly. This is the problem with a Java based version (at least
> with one that uses the standard collections libraries). At the very
> least your reporting function would have to make a complete copy of
> the world state while holding the lock, it could then go in to process
> this and produce the report on another thread after releasing the
> lock.
>
> This is why persistent data structures are so cool: you gain the
> ability to look at consistent snapshots of the world for free.
>
> Cheers,
> Ian.

In this particular case, the STM system is more important than the
fact that it uses persistent data structures. A Java solution that
didn't have persistent data structures but still had an equivalent STM
could use copy-on-write: it would certainly be slower, but I think it
would work just fine (the data structures are quite small).

I think the hardest part for a traditional Java solution would be to
see a consistent snapshot of the ant world without impeding all other
threads. Having a global lock would certainly work, but implies
impeding all threads to draw the ant world (or to update any edge in
the graph).

You don't necessarily need a global lock, but the alternative would be
to stripe the lock into several locks: at the extreme to have a read-
write lock for every place in the ant-world. Then always acquire those
locks in the same order (to avoid deadlock). The UI thread would then
have to acquire all the locks to see a consistent world (hence
impeding all threads). Now to increase concurrency you might want to
keep some history around for the UI thread... :-) Step-by-step you are
"Greenspunning" Clojure's STM inside your Java ants demo...

In fact, I think a neat demonstration for your talk would be to start
with a naive Java solution with a global lock. Then introduce a read-
write lock. Then stripe it in say 4 locks, then 8, then one for each
"ref". Then start adding history to avoid stopping the world. You
should probably stop before having implemented the STM ;-) End up the
demo explaining what Clojure's STM does and the interplay between
persistent data structures and STM (e.g. the price of keeping
history).

/Karl

[ianp]

True, true, but it's not (yet?) common and there are no persistent
data structures that ship with the JDK.

[ianp]

> In this particular case, the STM system is more important than the
> fact that it uses persistent data structures. A Java solution that
> didn't have persistent data structures but still had an equivalent STM
> could use copy-on-write: it would certainly be slower, but I think it
> would work just fine (the data structures are quite small).

If the DS are small then using j.u.cconcurrent.CopyOnWriteArrayList
may be an option, but since the program is fairly write intensive this
would be a lot of overhead.

Since the data structures are small you could have a timer or similar
(this would also allow you to set a target frame rate) that takes
snapshots of the state and uses that to update the UI. Something like
this:

final ExecutorService drawService = Executors.newSingleThreadExecutor
();

Runnable drawTask = new Runnable() {
private List stateSnapshot;
public void run() {
if (stateSnapshot == null) {
assert !EventQueue.isDispatchThread();
acquireGlobalLock();
stateSnapshot = copyStateOfTheWorld(world);
releaseGlobalLock();
EventQueue.invokeLater(this);
} else {
assert EventQueue.isDispatchThread();
updateUI();
stateSnapshot = null;
drawService.submit(this);
}
}
};

> In fact, I think a neat demonstration for your talk would be to start
> with a naive Java solution with a global lock. Then introduce a read-
> write lock. Then stripe it in say 4 locks, then 8, then one for each

Something that discusses a few different approaches in Java before
moving on the the Clojure version would make for a pretty interesting
talk I think.