From: Eric Wong <normalperson@...>
Date: 2013-08-26T19:57:23+00:00
Subject: [ruby-core:56811] Re: [ruby-trunk - Feature #8820][Open] Speed up Array#index

"trans (Thomas Sawyer)" <redmine@ruby-lang.org> wrote:
>     def main
>       n = 10000000  # ten million
>       a = randPerm(100)
> 
>       t0 = Time.now
> 
>       n.times do |i|
>         a.index(i)
>       end
> 
>       puts "%.5f" % [Time.now - t0]
>     end
> 
>     def randPerm(n)
>       (0...n).sort_by{rand}
>     end

The performance of your code varies between runs because the
ordering is always different and index is O(n) _worst_ case.
call srand(0) before any rand calls to get a consistent seed.

I suspect your Go code has the same flaw (but I don't know Go)

> The result
> 
>   Ruby: 71.08961 secs
>     Go: 2.61975 secs
> 
> That's pretty huge difference (and worse I was told my Go index
> function was "crazily inefficient" too, though personally I don't see
> how it can be any better). So, I thought I'd mention it. Maybe it
> would be possible to speed up

From what I can tell, rb_ary_index in array.c doesn't use the optimized
== definition in insns.def (which inlines some common comparisions) to
avoid rb_funcall overhead.

Maybe that can help this case...

Otoh, I would never use anything like Array#index on large arrays and/or
hot code in the first place.  After all these years of Ruby, I've hardly
ever used Array#index.  The only time in recent memory I used it was on
a 5-element array of short strings.