Thanks for everyone's replies. I finished writing the concurrent implementation of a bst, including delete. I think it's correct, but I haven't done any extensive testing, just some tests and some reasoning (which doesn't even begin to be enough, I know). I wanted to see what you think about this implementation:-<br>
<br><a href="http://www.cs.auckland.ac.nz/~fuad/pbst.erl">http://www.cs.auckland.ac.nz/~fuad/pbst.erl</a><br><br>The functions that perform insert or delete don't have any feedback mechanism, which I don't think is necessary since any later call to any other function should be ordered properly, but this is making benchmarking a bit of a challenge. I can't think of a way to measure how well this performs without implementing an acknowledgement mechanism. Any ideas?<br>
<br>I'm also not too happy with the process overhead per node; it's not a big deal if each node stores a lot of data, but it is quite significant for small nodes.<br><br>Thanks,<br>/Fuad
<br><br><div class="gmail_quote">On Fri, Jun 27, 2008 at 8:54 AM, Fuad Tabba <<a href="mailto:fuad@cs.auckland.ac.nz" target="_blank">fuad@cs.auckland.ac.nz</a>> wrote:<br><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
Cool, that's matches my understanding of Hynek's suggestion as well. Thanks Kevin.<br><br>I'm actually writing code along similar lines to test out the idea. It seems rather simple and elegant; what I don't like though is the added overhead of a process per node - I know that Erlang processes are light, but if I recall correctly from reading in Joe's book, each process has memory overhead in the order of 100 bytes. If the the data per node is large then it's not a big deal, but if the amount of data stored per node is small then that could be some serious overhead.<br>
<br>Implementing delete() is going to be a bit tricky, need to be wary of deadlocks; but this isn't an Erlang issue, this is a general issue with writing a concurrent and shared data structure.<br><br>Thanks again!<br clear="all">
<br>Cheers,<br><font color="#888888">/Fuad
<br></font><div><div></div><div><br><div class="gmail_quote">On Fri, Jun 27, 2008 at 8:22 AM, Kevin Scaldeferri <<a href="mailto:kevin@scaldeferri.com" target="_blank">kevin@scaldeferri.com</a>> wrote:<br>
<blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
<div><br>
On Jun 25, 2008, at 3:10 PM, Fuad Tabba wrote:<br>
<br>
</div><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;"><div>
I think I understand what you're saying here; but I still can't wrap my head around putting that into code. Is there similar code that you know of available online? The structure doesn't have to be a BST, just anything that demonstrates the idea of having a structure that stores lots persistent data to be viewed/modified by many processes and is scalable...<br>
<br>
<br></div><div>
On Wed, Jun 25, 2008 at 9:40 PM, Hynek Vychodil <<a href="mailto:vychodil.hynek@gmail.com" target="_blank">vychodil.hynek@gmail.com</a>> wrote:<br>
Because there is no shared state between processes in Erlang, I would start think about process per tree node, not process per action as usual in classic shared memory (for example C) implementations.<br>
I know, it sounds weird, but may be help you :-)<br>
</div></blockquote>
<br>
<br>
<br>
Here's a basic outline of this idea, if I understand it right. delete() is not implemented, and it has some other deficiencies, but I hope it at least starts to demonstrate the idea of a recursive data structure represented as a collection of processes.<br>
<br>
<br>
-kevin<br>
<br>
%%%%%%%%%%%%%%%%%%%%%%%%%<br>
<br>
-module(cbst).<br>
-export([new/1, exists/2, insert/2, delete/2]).<br>
<br>
-record(node, {key,<br>
left=null,<br>
right=null}).<br>
<br>
%%<br>
%% public API<br>
%%<br>
<br>
new(Key) -><br>
spawn(fun() -> create(Key) end).<br>
<br>
exists(Node, Key) -><br>
Node ! {exists, Key, self()},<br>
receive<br>
true -> true;<br>
false -> false<br>
end.<br>
<br>
insert(Node, Key) -><br>
Node ! {insert, Key}.<br>
<br>
delete(Node, Key) -><br>
Node ! {delete, Key}.<br>
<br>
<br>
%%<br>
%% private functions<br>
%%<br>
<br>
create(Key) -><br>
Node = #node{key=Key},<br>
loop(Node).<br>
<br>
loop(Node) -><br>
receive<br>
{exists, Key, Caller}=Q -><br>
case Node#node.key of<br>
Key -><br>
Caller ! true;<br>
This when Key < This, Node#node.left =/= null -><br>
Node#node.left ! Q;<br>
This when Key > This, Node#node.right =/= null -><br>
Node#node.right ! Q;<br>
_ -><br>
Caller ! false<br>
end,<br>
loop(Node);<br>
{insert, Key} -><br>
case Node#node.key of<br>
Key -><br>
loop(Node); % already in tree<br>
This when Key < This -><br>
case Node#node.left of<br>
null -><br>
Left = new(Key),<br>
loop(Node#node{left=Left});<br>
Left -><br>
Left ! {insert, Key},<br>
loop(Node)<br>
end;<br>
This when Key > This -><br>
case Node#node.right of<br>
null -><br>
Right = new(Key),<br>
loop(Node#node{right=Right});<br>
Right -><br>
Right ! {insert, Key},<br>
loop(Node)<br>
end<br>
end;<br>
{delete, Key} -><br>
% left as an exercise for the reader<br>
loop(Node)<br>
end.<br>
<br>
</blockquote></div><br>
</div></div></blockquote></div><br>