Need for speed - array operations

[Chris Lervag]

Hi,

Im working on a library to decode medical image files, and some of these
files are encoded as 'PALETTE COLOR', which means you have a lookup
table for red, green and blue pixel values. The final RGB pixel array is
constructed by hitting the lookup table with the original pixel values.
In my implementation I am using an iterator, and it is kinda slow. I
cant spot an obvious way to improve on it though, so I thought I'd put
the question out here and see if any of you more experienced Rubyists
can suggest a more efficient way of doing this.

Thanks,
Chris

Example code:
# Set up example arrays to test the algorithm:
lookup_values = Array.new
lookup_values << Array.new(256, 0)
lookup_values << Array.new(256, 1)
lookup_values << Array.new(256, 2)
pixels = Array.new(258000, rand(256))
rgb = Array.new(pixels.length*3)

# The PALETTE transformation algorithm:
pixels.each_index do |i|
rgb[i*3] = lookup_values[0][pixels]
rgb[(i*3)+1] = lookup_values[1][pixels]
rgb[(i*3)+2] = lookup_values[2][pixels]
end

 

[Ralf Mueller]

Hi,

Im working on a library to decode medical image files, and some of these
files are encoded as 'PALETTE COLOR', which means you have a lookup
table for red, green and blue pixel values. The final RGB pixel array is
constructed by hitting the lookup table with the original pixel values.
In my implementation I am using an iterator, and it is kinda slow. I
cant spot an obvious way to improve on it though, so I thought I'd put
the question out here and see if any of you more experienced Rubyists
can suggest a more efficient way of doing this.

Thanks,
Chris

Example code:
# Set up example arrays to test the algorithm:
lookup_values = Array.new
lookup_values<< Array.new(256, 0)
lookup_values<< Array.new(256, 1)
lookup_values<< Array.new(256, 2)
pixels = Array.new(258000, rand(256))
rgb = Array.new(pixels.length*3)

# The PALETTE transformation algorithm:
pixels.each_index do |i|
rgb[i*3] = lookup_values[0][pixels]
rgb[(i*3)+1] = lookup_values[1][pixels]
rgb[(i*3)+2] = lookup_values[2][pixels]
end

You might try narray: http://narray.rubyforge.org/. It's available as a gem.

ralf

 

[Robert Klemme]

Hi,

Im working on a library to decode medical image files, and some of these
files are encoded as 'PALETTE COLOR', which means you have a lookup
table for red, green and blue pixel values. The final RGB pixel array is
constructed by hitting the lookup table with the original pixel values.
In my implementation I am using an iterator, and it is kinda slow. I
cant spot an obvious way to improve on it though, so I thought I'd put
the question out here and see if any of you more experienced Rubyists
can suggest a more efficient way of doing this.

Thanks,
Chris

Example code:
# Set up example arrays to test the algorithm:
lookup_values =3D Array.new
lookup_values<< =A0Array.new(256, 0)
lookup_values<< =A0Array.new(256, 1)
lookup_values<< =A0Array.new(256, 2)
pixels =3D Array.new(258000, rand(256))
rgb =3D Array.new(pixels.length*3)

# The PALETTE transformation algorithm:
pixels.each_index do |i|
=A0 rgb[i*3] =3D lookup_values[0][pixels]
=A0 rgb[(i*3)+1] =3D lookup_values[1][pixels]
=A0 rgb[(i*3)+2] =3D lookup_values[2][pixels]
end

You might try narray: http://narray.rubyforge.org/. It's available as a g=

em.

Not so fast. There is room for optimization even in this
implementation. We can shave off over 12% with a pure Ruby solution:

13:18:20 Temp$ ruby19 lv.rb
user system total real
old prep 0.000000 0.000000 0.000000 ( 0.000000)
old 1.812000 0.000000 1.812000 ( 1.806000)
new prep 0.000000 0.000000 0.000000 ( 0.001000)
new 1.016000 0.047000 1.063000 ( 1.060000)

https://gist.github.com/948178

Kind regards

robert


--=20
remember.guy do |as, often| as.you_can - without end
http://blog.rubybestpractices.com/

 

[Chris Lervag]

Robert,
I've implemented your tweaked solution and indeed it runs significantly
faster! In retrospect it looks so obvious, almost embarrasing!

Thanks a million, your effort is appreciated!

Ralf,
yes I am aware of NArray, and probably that will be the optimal
solution. At some stage I will probably use it, however, at least for
now, I want to avoid external dependencies and just go with a pure Ruby
solution.

Thanks,
Chris

 

[Chris Lervag]

Just a bit of an update:
Turns out the each_with_index iterator is INSANELY slow on ruby1.8 on
large arrays, so I had to use each_index instead and pixels instead
of pix.

Still a happy ending though!

Chris

 

[Pirogov Eugene]

I'm experience the loss of speed in NArrays. Did you guys tried benching
a simple access to an element in NArray?

My benches show dramatical slowdown comparing to a Ruby built-in Array.
I already filled an issue here:
https://github.com/masa16/narray/issues/8.

 

[Joel VanderWerf]

I'm experience the loss of speed in NArrays. Did you guys tried benching
a simple access to an element in NArray?

My benches show dramatical slowdown comparing to a Ruby built-in Array.
I already filled an issue here:
https://github.com/masa16/narray/issues/8.

It's too simple a benchmark to demonstrate the efficiency of narray.
What it's measuring is access time from ruby. For the first two cases,
the number in the ruby array is a fixnum (shifted by one bit and or-ed
with 0x01) that can simply be returned with no modification, as a 32 or
64 bit VALUE (ruby's basic data type). In the third case, the number is
stored as an 8 bit signed int, which has to be converted to VALUE by
sign extending, shifting, and or-ing.

As soon as you start measuring operations whose inputs and outputs are
both NArrays (especially large ones), you'll see the speed...