[erlang-questions] Re: Shared/Hybrid Heap

Richard O'Keefe ok@REDACTED
Thu Oct 14 03:05:30 CEST 2010

I came across an example where a shared heap would help recently.

There is a rectangular grid of processes.
Each process wants to be able to send messages to other
processes, based on their coordinates.

The simplest setup that would occur to me is
	- create the processes
	- build a data structure mapping (row,col) to pid
	- send it to each process
But this results in O(N**2) space for N processes.

With a shared heap, it would be O(N) space.

The second simplest setup is to have a single process
hold the data structure, and all the others ask it to
relay messages.  But this serialises all communication
through a single chokepoint.

The student who wrote the program did something that
would never have occurred to me.  He used the
registry, doing

	Pid = whereis(list_to_atom([Row,Col])),
	Pid ! Message

I don't know exactly what goes on in the emulator to
make list_to_atom/1 and whereis/1 work; maybe they are
lock-free and maybe they aren't.

Of course there are intermediate approaches that work,
like having a master (row,col)->pid server ("DNS") and
having each of the processes in the grid keep a cache
of the last k processes it talked to, which would work
well in the problem at hand.

More information about the erlang-questions mailing list