From: John Miller <jfmiller28@...>
Date: 2007-08-23T04:03:23+09:00
Subject: Rope Data Structures

Greetings All,

I have been plugging away a a parser for ruby Endo's DNA from this years
International Functional Programming Completion.
(http://www.icfpcontest.org/)  Most teems who have put up there reviews
have talked about having to switch programming languages to something
faster.  Most did this before trying to change algorithms.  Many of the
successful teems ended up using the 'rope' from the C++ Standard
Template Library.

please see:

http://en.wikipedia.org/wiki/Rope_(computer_science)
http://www.sgi.com/tech/stl/ropeimpl.html
http://www.cs.ubc.ca/local/reading/proceedings/spe91-95/spe/vol25/issue12/spe986.pdf

I tried writing a rope library in ruby and got an order of magnitude
better performance when compared to a String implementation (6.5 to 48.5
iterations per second -- to successfully solve the problem I estimated I
would need ~2000 iterations per second)

I learned several things from this attempt:
 * Avoid creating edge cases they are bad for business and my poor rope
implementation had way too many of them.
 * Working with long strings is a slow process (endo's dna is a string
~7.5M chars long)
 * For long running programs calling GC.start at points where the number
of living object is at a minimum will save time and Hard Drive actuator
motors.
 * The folks who wrote the ruby-prof gem deserve an award for making an
excelent tool.

One thing that got me thinking however was that even my poorly
implemented pure Ruby version of ropes gave me an order of magnitude
extra speed.  It made me wonder: How hard would it be to implement ropes
as a compiled binary library for ruby, and how much would using such a
library (even a pure ruby version) speed up rails, which does a lot of
string concatenation?
-- 
Posted via http://www.ruby-forum.com/.