From: "Mauricio Fernández" <batsman.geo@...>
Date: 2003-05-12T16:10:04+09:00
Subject: Re: efficiency advice needed

On Mon, May 12, 2003 at 08:31:58AM +0900, Ryan Pavlik wrote:
> On Mon, 12 May 2003 06:56:27 +0900
> "meinrad.recheis" <my.name.here@gmx.at> wrote:
> 
> <snip> 
> > data = ''
> > (width*height).times{
> >   data += rgb.read( 3) + alpha.read( 1)
> > }

 += strikes as extremely inefficient, as it is creating new increasingly big String
objects on each iteration!! Ruby will spend quite some time just
duplicating the string (ie copying data) and then GC'ing, in fact that'd
be O(N^2). Although nearly as bad (making heavy use of realloc), using
#<< should give a significant speedup, and you cannot get it much easier
than s/+=/<</ ;-)


See:

batsman@tux-chan:/tmp$ cat ae.rb

rgb = File.new "rgbfile", 'rb'

alpha = File.new "alphafile", 'rb'

width = height = ARGV[0].to_i

data = ''
(width*height).times{
        data << rgb.read(3) + alpha.read( 1)
}
p data.size

batsman@tux-chan:/tmp$ cat ae1.rb

rgb = File.new "rgbfile", 'rb'

alpha = File.new "alphafile", 'rb'

width = height = ARGV[0].to_i

data = ''
(width*height).times{
        data += rgb.read(3) + alpha.read( 1)
}
p data.size


batsman@tux-chan:/tmp$ time ruby ae.rb 100
40000

real    0m0.071s
user    0m0.070s
sys     0m0.000s
batsman@tux-chan:/tmp$ time ruby ae.rb 200
160000

real    0m0.483s
user    0m0.460s
sys     0m0.010s
batsman@tux-chan:/tmp$ time ruby ae.rb 300
360000

real    0m2.067s
user    0m2.060s
sys     0m0.010s
batsman@tux-chan:/tmp$ time ruby ae1.rb 100
40000

real    0m0.555s
user    0m0.530s
sys     0m0.020s
batsman@tux-chan:/tmp$ time ruby ae1.rb 200
160000

real    0m9.316s
user    0m8.420s
sys     0m0.730s
batsman@tux-chan:/tmp$ time ruby ae1.rb 300
360000

real    1m3.309s
user    0m51.880s
sys     0m10.480s


You can see that ae.rb's execution time still grows faster than
linearly... A better solution is 

batsman@tux-chan:/tmp$ cat ae2.rb

rgb = File.new "rgbfile", 'rb'

alpha = File.new "alphafile", 'rb'

width = height = ARGV[0].to_i
data = String.new(" " * 4*width*height)
# this sucks, would like to create a String w/ a given capa,
# IRC that was considered for/possible in 1.8, but not sure

(width*height).times{ |idx|
        data[idx*4, 4] = rgb.read(3) + alpha.read( 1)
}

p data.size

Now:

batsman@tux-chan:/tmp$ time ruby ae2.rb 100
40000

real    0m0.053s
user    0m0.050s
sys     0m0.000s
batsman@tux-chan:/tmp$ time ruby ae2.rb 200
160000

real    0m0.186s
user    0m0.170s
sys     0m0.010s
batsman@tux-chan:/tmp$ time ruby ae2.rb 300
360000

real    0m0.391s
user    0m0.370s
sys     0m0.010s

batsman@tux-chan:/tmp$ ruby -v
ruby 1.6.8 (2003-02-28) [i386-linux]

Not bad, a >150-fold speedup from your original script :-)

You might consider using Inline for this stuff, that'd be pretty neat.

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

I did this 'cause Linux gives me a woody.  It doesn't generate revenue.
	-- Dave '-ddt->` Taylor, announcing DOOM for Linux