[erlang-questions] Re: Shared/Hybrid Heap
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
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