MonthFebruary 2011

More Red-Black Tree, but a little Ruby Benchmarking

After hearing a bit about the improvements in the Rubinius ruby interpreter, I decided to test a handful of the interpreters against the Red-Black tree insertion script I last posted about.

As a forward, this is completely out of idle curiosity, and with no deep intentions. The results had distinct winners and losers, and for more rich benchmark, this would need to include multiple iterations and some other aspects as well. All that to say, this is not an all encompassing benchmark.
The results are the length (in seconds) of time for the execution.

So using the rbtree.rb, that I last blogged about, using rvm, I have just run it through the following ruby interpreters:

  • ruby 1.9.1p430 (2010-08-16 revision 28998) [x86_64-linux]
  • rubinius 1.3.0dev (1.8.7 5bd938b5 xxxx-xx-xx JI) [x86_64-unknown-linux-gnu]
  • rubinius 1.2.0 (1.8.7 release 2010-12-21 JI) [x86_64-unknown-linux-gnu]
  • jruby 1.5.3 (ruby 1.8.7 patchlevel 249) (2010-09-28 7ca06d7) (Java HotSpot(TM) 64-Bit Server VM 1.6.0_23) [amd64-java]
  • ruby 1.8.7 (2010-12-23 patchlevel 330) [x86_64-linux], MBARI 0x6770, Ruby Enterprise Edition 2011.01
  • ruby 1.9.3dev (2011-02-14 trunk 30873) [x86_64-linux]

From an early look at it, the Rubinius interpreter is on to something good. For this example at least, their current release branch (1.2) is smoking, compared to anything else.
To look at the values, that make up the graph above, here is the spreadsheet

Take care,
vb

Kick off of playing with trees

As I have stated before, I enjoy the speed at which I can prototype an idea in Ruby. Even if ultimately that idea runs better on another language. For the sake of my academics, it provides a super learning playground.

Earlier, this past week, I began reading up on papers and documentation of trees. All in an effort to differentiate the various implementations of trees, including their benefits and drawbacks. Finding AVL trees, B trees, 2-3 node, 2-3-4 node and RB trees. I decided to kick off the events with a Red-Black tree. Some of the papers I found are the generally available by Google searching.

After a lot of learning, and a little massage, I have the first of a an “academic” implementation of an RB tree (http://hashbangbash.com/~vbatts/rbtree.rb). I gravitated towards this tree first because of the type searches I am needing. While the population of this slows as it grows, the searches are ridiculously fast. I’ll get around to generating some instrumentation to graph it. For now I have the run_loop() to return @results of the populating trees. The sets are [ , , , ]

The insertion graphed was an O(N) climb. For doubling the number of nodes to be inserted (of random unique numbers), the time increase was just a tad more than double. The @results for run_loop(1,000,000) was
=> [[1000000, 43.4912700653076, 24, 16], [500000, 20.5859882831573, 20, 15], [250000, 9.5372850894928, 20, 14], [125000, 4.50037479400635, 21, 13], [62500, 2.01573848724365, 16, 12], [31250, 0.941669225692749, 14, 11], [15625, 0.435366868972778, 14, 11], [7812, 0.252951860427856, 13, 10], [3906, 0.0940215587615967, 11, 9], [1953, 0.043536901473999, 13, 8], [976, 0.0200107097625732, 9, 8], [488, 0.00921034812927246, 9, 6], [244, 0.00417494773864746, 10, 5], [122, 0.00190210342407227, 6, 5], [61, 0.000821590423583984, 5, 4], [30, 0.000351667404174805, 4, 3], [15, 0.000170707702636719, 4, 2], [7, 6.03199005126953e-05, 2, 1], [3, 2.57492065429688e-05, 1, 1]]
which resulted in a time climb of


Another interesting observation was the logarithmic oscillations of the depth of the left most leg.

At any rate, enjoy and feel free to send your thoughts.
Take care,
vb