Re: [Datadraw-user] Red-black trees beat treaps
Brought to you by:
smilindog2000
Menu
▾
▴
Re: [Datadraw-user] Red-black trees beat treaps
|
From: <dat...@li...> - 2008-05-23 16:32:21
|
Hi there :) it would be interesting to inspect the assembly-code of #define and the static code. I guess the #define really gets inlined and the static is an extra function call.... inspecting code is rather easy in visual studio, but I know you're working in a unix-environment. Optimising code is always a great challenge. But nowadays optimising memory-layout is much better than optimising only functions (ok, ok, using the right algorithm for the problem is the best ;) so congratulations for you fast routines! I'm really impressed. kai ----- original Nachricht -------- Betreff: Re: [Datadraw-user] Red-black trees beat treaps Gesendet: Do, 22. Mai 2008 Von: dat...@li... > Hi, Kai. > > For some reason, every compiler I've tested has trouble optimizing when > using inline functions instead of #defines. That's why #defines are > still in use in datadraw, though for debugging, we undefine most of them > and provide real functions instead. > > I tested multiset from stdcxx. You'll be happy to know it beats the STL > library. For 5 million nodes, my random insert/remove benchmark takes > 30 seconds, while STL takes 31. However, DataDraw does it in 8, while > doing more work (it inserts real objects with key values, rather than > just ints), and uses only about 60% as much memory on my 64-bit machine. > I've attached the files I used to do the benchmark. The DataDraw > benchmarks are signed in under trunk/examples/redblack_benchmarks > > I just love winning speed benchmarks :-) > > Best regards, > Bill > > On Thu, 2008-05-22 at 13:42 -0400, dat...@li... > wrote: > > I am surprise about the static versus #define because I though static > > could be interpreted as inline by the optimizer. > > > > Great to know. > > > > Regards > > > > On Thu, May 22, 2008 at 12:38 PM, > > <dat...@li...> wrote: > > Hi, Kai. > > > > Thanks for the link. I've downloaded it and hope to compare > > to stdcxx > > soon. In the meantime, I compared DataDraw ordered_lists to > > the g++ STL > > multiset. With just integers, the STL code takes 33 seconds > > for 5 > > million creates, 5 million random insert delete pairs, and 5 > > million > > deletes. We use to run in 45 seconds... I found out why we > > were slower, > > and fixed it. DataDraw now runs in 8 seconds! > > > > Best regards, > > Bill > > > > P.S. The reason the datadraw implementation was slow is a bit > > scary. > > Static inline functions DO NOT run as fast as #defines! I > > converted the > > compare function to #define base, and the speed when from 43 > > seconds to > > 8! > > > > On Thu, 2008-05-22 at 11:59 +0200, > > dat...@li... > > > > wrote: > > > Hi Guys, > > > > > > I've heard that the stdcxx-code should be really fast, but > > I've not measured the performance against the > > wikipedia-entry.... what I've done is to measure the > > performance of the stl-, crisscross-implementation and some > > other and found that the stdcxx was the fastest for me. you > > can find the code here: http://stdcxx.apache.org/ > > > > > > regards and happy coding :) > > > kai > > > > > > ----- original Nachricht -------- > > > > > > Betreff: Re: [Datadraw-user] Red-black trees beat treaps > > > Gesendet: Mi, 21. Mai 2008 > > > Von: dat...@li... > > > > > > > It's done. We now have red-black tree implementations for > > ordered_list > > > > relationships. This is the fastest code I've found on the > > Internet for > > > > ordered lists after both Richard and I did a fairly > > lengthy search. > > > > Thanks for the help, Richard! > > > > > > > > Bill > > > > > > > > On Wed, 2008-05-21 at 14:43 -0400, > > dat...@li... > > > > wrote: > > > > > ?Hi. > > > > > > > > > > I hand-coded both treap and black-red tree benchmarks. > > The red-black > > > > > code I used is the code from the wikipedia.org page. > > For random insert > > > > > and delete of 10 million nodes, treaps took 63 seconds, > > while red-black > > > > > took 43 seconds. Treaps actually trounced red-black > > trees when used as > > > > > a fifo (deleting only smallest, inserting only largest), > > but I think > > > > > random is the more important case for ordered lists. > > > > > > > > > > I'm going to convert over to wikipedia style red-black > > trees if there > > > > > are no objections. You can find my benchmarks in > > > > > examples/treap_benchark and examples/redblack_benchmark. > > > > > > > > > > Regards, > > > > > Bill > > > > > > > > > > > > > > > > > > ------------------------------------------------------------------------- > > > > > This SF.net email is sponsored by: Microsoft > > > > > Defy all challenges. Microsoft(R) Visual Studio 2008. > > > > > http://clk.atdmt.com/MRT/go/vse0120000070mrt/direct/01/ > > > > > _______________________________________________ > > > > > Datadraw-user mailing list > > > > > Dat...@li... > > > > > > > https://lists.sourceforge.net/lists/listinfo/datadraw-user > > > > > > > > > > > > > > > ------------------------------------------------------------------------- > > > > This SF.net email is sponsored by: Microsoft > > > > Defy all challenges. Microsoft(R) Visual Studio 2008. > > > > http://clk.atdmt.com/MRT/go/vse0120000070mrt/direct/01/ > > > > _______________________________________________ > > > > Datadraw-user mailing list > > > > Dat...@li... > > > > https://lists.sourceforge.net/lists/listinfo/datadraw-user > > > > > > > > > > --- original Nachricht Ende ---- > > > > > > > > > > > > ------------------------------------------------------------------------- > > > This SF.net email is sponsored by: Microsoft > > > Defy all challenges. Microsoft(R) Visual Studio 2008. > > > http://clk.atdmt.com/MRT/go/vse0120000070mrt/direct/01/ > > > _______________________________________________ > > > Datadraw-user mailing list > > > Dat...@li... > > > https://lists.sourceforge.net/lists/listinfo/datadraw-user > > > > > > > ------------------------------------------------------------------------- > > This SF.net email is sponsored by: Microsoft > > Defy all challenges. Microsoft(R) Visual Studio 2008. > > http://clk.atdmt.com/MRT/go/vse0120000070mrt/direct/01/ > > _______________________________________________ > > Datadraw-user mailing list > > Dat...@li... > > https://lists.sourceforge.net/lists/listinfo/datadraw-user > > > > > > > > > > -- > > +1 514-518-8172 > > ------------------------------------------------------------------------- > > This SF.net email is sponsored by: Microsoft > > Defy all challenges. Microsoft(R) Visual Studio 2008. > > http://clk.atdmt.com/MRT/go/vse0120000070mrt/direct/01/ > > _______________________________________________ Datadraw-user mailing list > Dat...@li... > https://lists.sourceforge.net/lists/listinfo/datadraw-user > --- original Nachricht Ende ---- |
