[erlang-questions] Writing a Concurrent Binary Search Tree Data Structure in Erlang

[Fuad Tabba]

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:-

http://www.cs.auckland.ac.nz/~fuad/pbst.erl

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?

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.

Thanks,
/Fuad

On Fri, Jun 27, 2008 at 8:54 AM, Fuad Tabba <fuad@REDACTED> wrote:

> Cool, that's matches my understanding of Hynek's suggestion as well. Thanks
> Kevin.
>
> 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.
>
> 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.
>
> Thanks again!
>
> Cheers,
> /Fuad
>
> On Fri, Jun 27, 2008 at 8:22 AM, Kevin Scaldeferri <kevin@REDACTED>
> wrote:
>
>>
>> On Jun 25, 2008, at 3:10 PM, Fuad Tabba wrote:
>>
>>  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...
>>>
>>>
>>> On Wed, Jun 25, 2008 at 9:40 PM, Hynek Vychodil <
>>> vychodil.hynek@REDACTED> wrote:
>>> 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.
>>> I know, it sounds weird, but may be help you :-)
>>>
>>
>>
>>
>> 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.
>>
>>
>> -kevin
>>
>> %%%%%%%%%%%%%%%%%%%%%%%%%
>>
>> -module(cbst).
>> -export([new/1, exists/2, insert/2, delete/2]).
>>
>> -record(node, {key,
>>               left=null,
>>               right=null}).
>>
>> %%
>> %% public API
>> %%
>>
>> new(Key) ->
>>    spawn(fun() -> create(Key) end).
>>
>> exists(Node, Key) ->
>>    Node ! {exists, Key, self()},
>>    receive
>>        true -> true;
>>        false -> false
>>    end.
>>
>> insert(Node, Key) ->
>>    Node ! {insert, Key}.
>>
>> delete(Node, Key) ->
>>    Node ! {delete, Key}.
>>
>>
>> %%
>> %% private functions
>> %%
>>
>> create(Key) ->
>>    Node = #node{key=Key},
>>    loop(Node).
>>
>> loop(Node) ->
>>    receive
>>        {exists, Key, Caller}=Q ->
>>            case Node#node.key of
>>                Key ->
>>                    Caller ! true;
>>                This when Key < This, Node#node.left =/= null ->
>>                    Node#node.left ! Q;
>>                This when Key > This, Node#node.right =/= null ->
>>                    Node#node.right ! Q;
>>                _ ->
>>                    Caller ! false
>>            end,
>>            loop(Node);
>>        {insert, Key} ->
>>            case Node#node.key of
>>                Key ->
>>                    loop(Node); % already in tree
>>                This when Key < This ->
>>                    case Node#node.left of
>>                        null ->
>>                            Left = new(Key),
>>                            loop(Node#node{left=Left});
>>                        Left ->
>>                            Left ! {insert, Key},
>>                            loop(Node)
>>                    end;
>>                This when Key > This ->
>>                    case Node#node.right of
>>                        null ->
>>                            Right = new(Key),
>>                            loop(Node#node{right=Right});
>>                        Right ->
>>                            Right ! {insert, Key},
>>                            loop(Node)
>>                    end
>>            end;
>>        {delete, Key} ->
>>            % left as an exercise for the reader
>>            loop(Node)
>>    end.
>>
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://erlang.org/pipermail/erlang-questions/attachments/20080630/8713558f/attachment.htm>