[erlang-questions] MPI based BST and AVL

Rujia Liu rujia.liu@REDACTED
Sun Nov 7 02:31:44 CET 2010


What is your main concern? The simplicity or the performance?
you mentioned "If a concurrent BST/AVL is build in message passing
style, the solution will be simpler, even if it will not give a better
performance." so I assume simplicity is more important.

Then what's wrong with the following straight-forward solution that
comes to my mind?
1. employ a BST-controller process which receives commands, then
execute them one at a time, just like normal serial case.
2. clients (process that needs to do insertions and deletions) send
messages to the controller process.

Maybe I misunderstood you, so could you please mention some details of
the use case of your concurrent BST? The size of the BST, the
amount/speed of tree operations, how well you want to scale. For
example, if your BST is too big, you need to do something like:

1. dynamically create and destroy erlang nodes (don't do this if the
size of your tree does not change drastically during execution)
2. operations happen at different parts of the tree goes to different
erlang nodes
3. schedule some rebalances of the tree, by moving subtrees between
erlang nodes (ps: I don't think keeping strict balance, like AVL, is a
good idea to build concurrent BSTs)

I have never implemented these idea, but if your BST is really huge,
even the simpliest use of these ideas will be a lot better than the
previous straight-forward solution I mentioned above.

BTW: You may also consider external balanced trees like B trees/B+
trees. The tree nodes are easier to distribute between erlang nodes.

Good luck!

- Rujia

On Sat, Nov 6, 2010 at 11:45 PM, Jiansen He <jiansenhe@REDACTED> wrote:
> BST is a common data structure.  In some cases, the speed of producing data
> might be faster than the speed of inserting data.  Or, many users might want
> to do operations(inserting, deleting, etc.) at the same time, if the tree is
> shared by many users.
>
> It is practical to do tree (both BST and AVL) operations concurrently based
> on locks and (software transactional memory) STM.  I wonder if it is
> practical  to build concurrent BST/AVL in message passing style.
>
> In a locks/STM based concurrent BST/AVL, it is parent node's job to check
> the accessibility of child nodes before performing an operation.  This
> increase the complexity  of programming.  A beauty of message passing style
> is that the sender does not need to worry about the status of receivers.
> If a concurrent BST/AVL is build in message passing style, the solution will
> be simpler, even if it will not give a better performance.
>
> Please let me know if the problem is not clear.
>
> I plan to build such a tree if I have time.  A design for concurrent BST has
> in my mind for a while, but it might be difficulty to build a lock free
> concurrent AVL.
>
> In the mean time, I wounder if someone else has implemented this idea, or it
> might be in library.
>
>
> Jiansen
>
>
> On Fri, Nov 5, 2010 at 11:24 PM, Francis Stephens <francisstephens@REDACTED
>> wrote:
>
>> Jiansen,
>>
>> I am interested in your problem.  However, I don't think I fully understand
>> what you are asking.  Are you able to spell out more clearly what problem
>> you are trying to solve?
>>
>> Francis
>>
>


More information about the erlang-questions mailing list