Need for speed - array operations

Ruby
1

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[i]]
rgb[(i3)+1] = lookup_values[1][pixels[i]]
rgb[(i3)+2] = lookup_values[2][pixels[i]]
end

2

On 04/29/2011 10:54 AM, Chris L. wrote:

rgb = Array.new(pixels.length*3)

The PALETTE transformation algorithm:

pixels.each_index do |i|
rgb[i*3] = lookup_values[0][pixels[i]]
rgb[(i3)+1] = lookup_values[1][pixels[i]]
rgb[(i3)+2] = lookup_values[2][pixels[i]]
end

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

ralf

3

On Fri, Apr 29, 2011 at 1:05 PM, Ralf M. [email protected]
wrote:

the question out here and see if any of you more experienced Rubyists
lookup_values<< Array.new(256, 2)
You might try narray: http://narray.rubyforge.org/. It’s available as a gem.
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)

Kind regards

robert

4

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

5

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:
Extremely slow NArray element access · Issue #8 · masa16/narray · GitHub.

6

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[i] instead
of pix.

Still a happy ending though!

Chris

7

On 05/17/2011 01:26 PM, Pirogov Eugene wrote:

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:
Extremely slow NArray element access · Issue #8 · masa16/narray · GitHub.

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…