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...<br>
<br>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.<br>
<br>/Fuad
<br><br><div class="gmail_quote">On Tue, Jul 8, 2008 at 11:20 AM, Fuad Tabba <<a href="mailto:fuad@cs.auckland.ac.nz">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;">
Thanks Robert and Hynek.<br><br>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.<br>
<br>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 (<a href="http://www.cs.auckland.ac.nz/%7Efuad/cbst.erl" target="_blank">http://www.cs.auckland.ac.nz/~fuad/cbst.erl</a>), 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.<br>
<br>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.<br>
<br clear="all">Thanks again,<br><font color="#888888">/Fuad
<br></font><div><div></div><div class="Wj3C7c"><br><div class="gmail_quote">On Mon, Jul 7, 2008 at 9:58 PM, Robert Raschke <<a href="mailto:rtrlists@googlemail.com" target="_blank">rtrlists@googlemail.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;">
Hi Fuad,<br>
<div><br>
On 7/7/08, Fuad Tabba <<a href="mailto:fuad@cs.auckland.ac.nz" target="_blank">fuad@cs.auckland.ac.nz</a>> wrote:<br>
> Thanks Robert,<br>
><br>
> Yes I am familiar with Amdahl's law. That said, it's not true that all<br>
> writes need to be serialized; it's a binary tree, and unless the<br>
> modifications happen to be to the same node, there's no reason why they need<br>
> to be serialized.<br>
><br>
> A database would solve the problem kinda; but that's like using a<br>
> steamroller to crack a nut. What I'm looking for a lightweight option that<br>
> could temporarily store data shared between threads, and would scale well as<br>
> the number of threads accessing/modifying this structure increases. I know<br>
> how to solve this problem in C (writing a concurrent binary search tree that<br>
> scales well), but since I'm new to Erlang I was unsuccessful trying to solve<br>
> this problem in Erlang.<br>
<br>
</div>OK, I see.<br>
<br>
So, if I read your code correctly, your rpcInserts() and rpcDeletes()<br>
return quick, because your request is trickling down the tree on its<br>
own. Its the rpcContains() that need to wait for a proper result.<br>
<br>
It might be interesting to test the individual operations on their<br>
own, and then combinations thereof. That might give a quicker insight<br>
into what is causing the lack of speedup. My (uneducated) hunch is<br>
that the rpcContains() calls are where your "threads" are getting<br>
stuck (due in part to all the inserts and deletes clogging up the<br>
tree).<br>
<br>
Very unscientific, sorry.<br>
<div><div></div><div><br>
Robby<br>
_______________________________________________<br>
erlang-questions mailing list<br>
<a href="mailto:erlang-questions@erlang.org" target="_blank">erlang-questions@erlang.org</a><br>
<a href="http://www.erlang.org/mailman/listinfo/erlang-questions" target="_blank">http://www.erlang.org/mailman/listinfo/erlang-questions</a><br>
</div></div></blockquote></div><br>
</div></div></blockquote></div><br>