[toronto-lisp] April meeting minutes available on the website

[doug at hcsw.org]

Hi Vish,

On Mon, Apr 13, 2009 at 10:57:12PM -0400 or thereabouts, Vishvajit Singh wrote:
> Rich Hickey's ant simulation is a good case study for Clojure
> concurrency in action. You may find it interesting to read through:

I briefly looked at this program and it seems to me that it creates
49 threads, each of which represent an ant. The ants then walk around
a 2D grid subject to conditions like food and pheromones. The threads
use transactional memory to synchronise access to the grid.

Let's apply The System.

Step 0: What is the reason for using threads (pre-emptively scheduled,
shared memory processes) in this program? To multiplex IO? No. To
coordinate access to multiple disks? No. To take advantage of multiple
CPUs for speed reasons? Possibly. Let's assume for now that this is
the reason.

Step 1: Make this program use 1 thread for all the ants. This will
give the following performance benefits (remember, we are concerned
about speed):

* Reduced context switching. Unless you have 49 or more CPUs in
  your machine, threads will be pre-empted frequently (or will
  waste much of their time sleeping).

* Reduce the memory and cache pressure of having 49 active threads.

* Eliminate the overhead of transactional memory (it's not free).

* You can now use mutable data-structures for performance reasons
  (remember we care about speed).

It will also give the following correctness benefits (we are always
concerned about correctness):

* How an ant moves will no longer be affected by artifacts
  of your system's thread scheduler. Instead, ants will move
  according to time as defined by your simulation.

* Eliminate possibility of deadlocks and livelocks.

Step 2: Since we are concerned about speed we will want to run
this simulation many times with different initial conditions
and/or PRNG seeds (otherwise we wouldn't care about speed).

Build a manager/worker system that fork()s N worker processes
(where N is the number of CPUs in your machine). Each worker
accepts messages over a socket. These messages contain initial
conditions and PRNG seeds. The worker then runs the simulation
and returns the pertinent statistics to the manager.

An advantage of this is that when you need to compute huge
simulations (the only situation where you would be concerned about
speed) you can spawn worker processes on separate physical machines
and have them connect to the manager over an internet socket. This
is because we have divided the concurrent tasks along the most
natural and effective concurrency boundary, the process.

Note: There is one use case for threads that The System doesn't
cover: testing or benchmarking threading implementations.
I have a feeling that this is the real purpose of the ant program.

> It will take me some time to fully work through your arguments, as I
> haven't worked very much with concurrency myself.

I see. Having created many concurrent programs, some of which are
multi-threaded, my advice is to avoid threads altogether. Only
once you have acquired significant experience with concurrency
will you be able to recognise the very rare situations where
threading is actually warranted. At this point you will no
longer need The System.

> How do you feel your
> opinions hold up on the issue of simple convenience for the
> programmer? I mean, using select() for IO, fork() for concurrency, and
> Berkeley DB for transactions throughout your programs takes extra
> effort as compared to using the built-in language mechanisms.

Aha! But remember that in lisp having something built-in to the
language is only a defmacro away.

Hope this helps,

Doug
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 195 bytes
Desc: not available
URL: <https://mailman.common-lisp.net/pipermail/toronto-lisp/attachments/20090414/6dd0d357/attachment.sig>