From: Eleanor McHugh <eleanor@...>
Date: 2008-06-27T10:00:08+09:00
Subject: Re: Performance improvement possible?

On 26 Jun 2008, at 22:51, Philip Rhoades wrote:
> Eleanor McHugh wrote:
>> When I did the profile, the array processing was the biggest hit -  
>> when I got rid of the array, I almost halved the time!  Ruby arrays  
>> are pretty cool but I think you pay for the convenience . .

I'm surprised at the behaviour you're seeing so I ran a quick  
benchmark on what I believe to be an equivalent array handling problem  
with my laptop (OS X, Ruby 1.8.6-p111, Core 2 Duo 2GHz, 2GB RAM):

require 'benchmark'
include Benchmark
bm(6) do |y|
    y.report("appending") { x = []; (1..20000000).each { |i| x << i } }
    y.report("nested creation") { x = Array.new(1000)  
{ Array.new(1000) { Array.new(20, 0) } } }
    y.report("unrolling") { x.flatten.flatten.length }
end

             			user     system      total        real
appending		7.350000   0.100000   7.450000 (  7.685458)
nested creation	0.850000   0.000000   0.850000 (  0.851341)
unrolling		15.240000   0.280000  15.520000 ( 20.927189)

which in each case is manipulating an array of 20,000,000 elements.  
This would be equivalent to processing 32000 files where each  
contained 625 occurrences of the 'k=' tag.

>>> and the file writing output of:
>>> File.open(output_filename, "a") do |file| file.sync = false  
>>> file.puts *stats file.fsync end
>>> looks interesting - why should that be faster?
>> Doing the file write this way offloads making it efficient to the
>> Ruby runtime. The file.fsync call will cost you in terms of runtime
>> performance, but it ensures that the data is flushed to disk before
>> moving on to the next file which for a large data processing job is
>> often desirable.
>
> See my other note but it didn't make much difference.

Regardless of what the profiler says, any program that's opening 32000  
files and writing to them is a prime candidate for IO optimisation...

Assuming I want to write 625 single-digit numbers to 32000 files the  
difference with file.puts *stats compared to individual writes is  
noticeable on my setup and would more than outweigh the cost of  
appending these numbers to an array. A slower processor might behave  
differently, as might a system with a higher-performance drive than my  
laptop's 5400RPM SATA HDD.

x = Array.new(675, 1)
bm(6) do |y|
   y.report("direct") { 32000.times { File.open("test.dat", "a") { | 
file| file.puts *x } } }
   y.report("enumerated") { 32000.times { File.open("test.dat", "a")  
{ |file| x.each { |i| file.puts i } } } }
   y.report("direct+fsync") { 32000.times { File.open("test.dat", "a")  
{ |file| file.sync = false; file.puts *x; file.fsync } } }
   y.report("enum+fsync") { 32000.times { File.open("test.dat", "a")  
{ |file| file.sync = false; x.each { |i| file.puts i }; file.fsync } } }

end
             			user     system      total        real
direct		25.160000   2.100000  27.260000 ( 38.775792)
enumerated	34.200000   2.170000  36.370000 ( 55.614969)
direct+fsync	25.300000   2.250000  27.550000 ( 60.225069)
enum+fsync	34.520000   2.420000  36.940000 ( 98.627757)

I'd be interested in equivalent benchmarking figures for your  
configuration and also an estimate of how close to the actual case  
this 32000x625 assumption is to your actual use case as it would help  
me make sense of the doubled execution time you're seeing with my  
array modification.


>> The cubic array was just a direct translation of the C pointer  
>> setup I had - basically it is a rectangular grid of sub-populations  
>> each with an array of allele lengths.

One option is to use a Hash as a Sparse Matrix by using Arrays as keys  
for indexing:

	stats = Hash.new(0)
	lines.each |line|
		...
		v = stats06
		stats[[x,y]] = v if v != 0
		...
	end
	File.open(output_filename, "a") do |file|
		file.puts *stats.values
	end

which should pay off if the number of interesting results is much less  
than the cubic search space. Obviously if you need the values to keep  
a specific ordering you'd need additional logic...


Ellie

Eleanor McHugh
Games With Brains
http://slides.games-with-brains.net
----
raise ArgumentError unless @reality.responds_to? :reason