From: "Mauricio Fernández" <batsman.geo@...>
Date: 2003-01-12T19:50:33+09:00
Subject: Re: Why is the performance of list_append O(n**2)?

On Sun, Jan 12, 2003 at 05:47:02AM +0900, Phil Tomson wrote:
> 
> It certainly seems that the O(n**2) performace for appending an item to 
Make it O(n) for each item; as there's n items, it's O(n**2) for the
creation of the whole array.

My first thought on this was using Marshal; as the format is fixed it
should be parsed faster. So here's my first take:

batsman@kodos:/tmp$ ruby -e 'print "a=["; 999.times{ |i| print "#{i},"}; print "999];"' > tst.rb
batsman@kodos:/tmp$ time ruby tst.rb

real    0m0.025s
user    0m0.020s
sys     0m0.000s
batsman@kodos:/tmp$ cp tst.rb marshaller.rb
batsman@kodos:/tmp$ cat >> marshaller.rb
File.open("tst2.rb", "w") { |f|
        f.puts( "a = Marshal.load(#{Marshal.dump(a).inspect})" )
}
batsman@kodos:/tmp$ ruby marshaller.rb
time ruby tst2.rb

real    0m0.044s
user    0m0.040s
sys     0m0.000s

It's a little bit slower but it should scale better when the size grows
(unless it is badly implemented). However:
batsman@kodos:/tmp$ ruby -e 'print "a=["; 9999.times{ |i| print "#{i},
"}; print "9999];"' > tst.rb
batsman@kodos:/tmp$ time ruby tst.rb

real    0m3.849s
user    0m3.710s
sys     0m0.000s
batsman@kodos:/tmp$ cp tst.rb marshaller.rb
batsman@kodos:/tmp$ cat >> marshaller.rb
File.open("tst2.rb", "w") { |f|
        f.puts( "a = Marshal.load(#{Marshal.dump(a).inspect})" )
}
batsman@kodos:/tmp$ ruby marshaller.rb
batsman@kodos:/tmp$ time ruby tst2.rb
tst2.rb:1:in `load': dump format error(0x24) (ArgumentError)
        from tst2.rb:1

real    0m0.066s
user    0m0.040s
sys     0m0.010s

This approach fails, so I'll try with an intermediate file:
batsman@kodos:/tmp$ cp tst.rb marshaller.rb
batsman@kodos:/tmp$ cat >> marshaller.rb
File.open("tst.dump", "w") { |f|
        Marshal.dump(a,f)
}

batsman@kodos:/tmp$ time ruby marshaller.rb

real    0m3.409s
user    0m3.390s
sys     0m0.000s
batsman@kodos:/tmp$ cat tst2.rb
a= nil
File.open("tst.dump", "r") { |f| a = Marshal.load(f) }
batsman@kodos:/tmp$ time ruby tst2.rb

real    0m0.080s
user    0m0.020s
sys     0m0.010s

And now comes the important thing: it should be quite easy to build an
extension (in C) that performs essentially the same thing as
Marshal.dump for such simple (although long) arrays. You could even
build a hash of arrays and dump it all at the same time.
Take a look at w_object in marshal.c.
Another possibility would be playing with _dump and _load, using your
own format, either by defining them in Array or by subclassing. You
could implement these either in C or in Ruby; in the latter case,
although somewhat slower than in C, you'd be able to code quickly and
avoid O(N**2) problems (I'd bet a O(N) alg. in Ruby would beat
hands-down a O(N**2) in C with those sizes)

I have another idea to hack the Ruby parser, too. Gotta test it.

-- 
 _           _                             
| |__   __ _| |_ ___ _ __ ___   __ _ _ __  
| '_ \ / _` | __/ __| '_ ` _ \ / _` | '_ \ 
| |_) | (_| | |_\__ \ | | | | | (_| | | | |
|_.__/ \__,_|\__|___/_| |_| |_|\__,_|_| |_|
	Running Debian GNU/Linux Sid (unstable)
batsman dot geo at yahoo dot com

    if (argc > 1 && strcmp(argv[1], "-advice") == 0) {
	printf("Don't Panic!\n");
	exit(42);
    }
	-- Arnold Robbins in the LJ of February '95, describing RCS