[erlang-questions] Problems Writing a Scalable Shared Data Structure

[Fuad Tabba]

Adding some observations; I've tried disabling smp all together (on the 8
core machine), and ironically the tests run more than twice as fast with smp
disabled. It's probably a cache-locality thing, since the tests are small
therefore all the data could easily fit in one processor's cache. The thing
is though, I do not get the same effect using +S 1, performance doesn't vary
all that much...

Another thing I've tried is I created a base for the tree; what I mean is
that there's a known root, a known node to the left of the root and a known
node that's to the right of the root. These nodes are always there. Whenever
the insert/delete/contains functions are called, rather than send the
request to the Root, they send it to one of those three depending on the
value of the key. To make a long story short, this didn't help either (even
going from 1 to 2 threads), which might imply that contention at the root
isn't the bottleneck in my case.

/Fuad

On Tue, Jul 8, 2008 at 11:20 AM, Fuad Tabba <fuad@REDACTED> wrote:

> Thanks Robert and Hynek.
>
> Hynek; playing around with the number of scheduler threads (+S) or
> asynchronous threads (surprisingly) does not significantly alter the
> results. As for the tree size, on average it should be around 500 nodes,
> assuming it's balanced this gives us a bst that's roughly 8 nodes deep. A
> tree this big should scale well with 8 processors. Moreover, I'd expect a
> tree this big to  scale almost perfectly going from 1 to 2 processors;
> especially if the ratio of lookups (contains()), that don't modify the data
> structure, is high. However, all I'm seeing is minor improvements. Moreover,
> increasing the size of the tree from 1000 to 10000 does improve scalability
> a bit, but not by all that much either.
>
> Robert; I think you're referring to an earlier version of my code, where I
> don't wait for the results of an insert or a delete. The lastest one (
> http://www.cs.auckland.ac.nz/~fuad/cbst.erl<http://www.cs.auckland.ac.nz/%7Efuad/cbst.erl>),
> the final node inserted/deleted does inform the client whether the operation
> was successful or not. I can't confirm, but on a big enough tree stacking
> shouldn't be an issue since each node will probably only relay its request.
> But then again you're right, deeper analyses seems to be in order before I
> could make such statements with any kind of certainty.
>
> That said, I feel that this solution doesn't seem to be the best one. I'm
> sure other Erlang programmers must have had to solve a similar problem,
> maintaining shared data between different threads in a scalable way.
>
> Thanks again,
> /Fuad
>
> On Mon, Jul 7, 2008 at 9:58 PM, Robert Raschke <rtrlists@REDACTED>
> wrote:
>
>> Hi Fuad,
>>
>> On 7/7/08, Fuad Tabba <fuad@REDACTED> wrote:
>> > Thanks Robert,
>> >
>> > Yes I am familiar with Amdahl's law. That said, it's not true that all
>> > writes need to be serialized; it's a binary tree, and unless the
>> > modifications happen to be to the same node, there's no reason why they
>> need
>> > to be serialized.
>> >
>> > A database would solve the problem kinda; but that's like using a
>> > steamroller to crack a nut. What I'm looking for a lightweight option
>> that
>> > could temporarily store data shared between threads, and would scale
>> well as
>> > the number of threads accessing/modifying this structure increases. I
>> know
>> > how to solve this problem in C (writing a concurrent binary search tree
>> that
>> > scales well), but since I'm new to Erlang I was unsuccessful trying to
>> solve
>> > this problem in Erlang.
>>
>> OK, I see.
>>
>> So, if I read your code correctly, your rpcInserts() and rpcDeletes()
>> return quick, because your request is trickling down the tree on its
>> own. Its the rpcContains() that need to wait for a proper result.
>>
>> It might be interesting to test the individual operations on their
>> own, and then combinations thereof. That might give a quicker insight
>> into what is causing the lack of speedup. My (uneducated) hunch is
>> that the rpcContains() calls are where your "threads" are getting
>> stuck (due in part to all the inserts and deletes clogging up the
>> tree).
>>
>> Very unscientific, sorry.
>>
>> Robby
>> _______________________________________________
>> erlang-questions mailing list
>> erlang-questions@REDACTED
>> http://www.erlang.org/mailman/listinfo/erlang-questions
>>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://erlang.org/pipermail/erlang-questions/attachments/20080708/350eb781/attachment.htm>