https://bugs.ruby-lang.org/https://bugs.ruby-lang.org/favicon.ico?17097754782013-08-27T04:59:15ZRuby Issue Tracking SystemRuby master - Feature #8820: Speed up Array#indexhttps://bugs.ruby-lang.org/issues/8820?journal_id=413512013-08-27T04:59:15Znormalperson (Eric Wong)normalperson@yhbt.net
<ul></ul><p>"trans (Thomas Sawyer)" <a href="mailto:redmine@ruby-lang.org" class="email">redmine@ruby-lang.org</a> wrote:</p>
<blockquote>
<pre><code>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
</code></pre>
</blockquote>
<p>The performance of your code varies between runs because the<br>
ordering is always different and index is O(n) <em>worst</em> case.<br>
call srand(0) before any rand calls to get a consistent seed.</p>
<p>I suspect your Go code has the same flaw (but I don't know Go)</p>
<blockquote>
<p>The result</p>
<p>Ruby: 71.08961 secs<br>
Go: 2.61975 secs</p>
<p>That's pretty huge difference (and worse I was told my Go index<br>
function was "crazily inefficient" too, though personally I don't see<br>
how it can be any better). So, I thought I'd mention it. Maybe it<br>
would be possible to speed up</p>
</blockquote>
<p>From what I can tell, rb_ary_index in array.c doesn't use the optimized<br>
== definition in insns.def (which inlines some common comparisions) to<br>
avoid rb_funcall overhead.</p>
<p>Maybe that can help this case...</p>
<p>Otoh, I would never use anything like Array#index on large arrays and/or<br>
hot code in the first place. After all these years of Ruby, I've hardly<br>
ever used Array#index. The only time in recent memory I used it was on<br>
a 5-element array of short strings.</p> Ruby master - Feature #8820: Speed up Array#indexhttps://bugs.ruby-lang.org/issues/8820?journal_id=413532013-08-27T05:23:18ZAnonymous
<ul></ul><p>On 08/26/2013 12:57 PM, Eric Wong wrote:</p>
<blockquote>
<p>"trans (Thomas Sawyer)" <a href="mailto:redmine@ruby-lang.org" class="email">redmine@ruby-lang.org</a> wrote:</p>
<blockquote>
<pre><code> 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
</code></pre>
</blockquote>
<p>The performance of your code varies between runs because the<br>
ordering is always different and index is O(n) <em>worst</em> case.<br>
call srand(0) before any rand calls to get a consistent seed.</p>
</blockquote>
<p>The running time of this code won't vary much at all. The n=10000000<br>
setting is much higher than a.size, so most #index calls will return<br>
nil. The entire array is searched for almost all iterations.</p>
<p>Maybe the intent was for each iteration step to do this</p>
<pre><code>a.index(i%n)
</code></pre>
<p>?</p> Ruby master - Feature #8820: Speed up Array#indexhttps://bugs.ruby-lang.org/issues/8820?journal_id=413552013-08-27T06:59:29Znormalperson (Eric Wong)normalperson@yhbt.net
<ul></ul><p>Joel VanderWerf <a href="mailto:joelvanderwerf@gmail.com" class="email">joelvanderwerf@gmail.com</a> wrote:</p>
<blockquote>
<p>On 08/26/2013 12:57 PM, Eric Wong wrote:</p>
<blockquote>
<p>The performance of your code varies between runs because the<br>
ordering is always different and index is O(n) <em>worst</em> case.<br>
call srand(0) before any rand calls to get a consistent seed.</p>
</blockquote>
<p>The running time of this code won't vary much at all. The n=10000000<br>
setting is much higher than a.size, so most #index calls will return<br>
nil. The entire array is searched for almost all iterations.</p>
</blockquote>
<p>I think you're right. I was on a new machine (Haswell) and enabled a<br>
bunch kernel options I normally don't use (Hyper-threading,<br>
full tickless, full preempt, automatic process group scheduling).<br>
Lots of variables even when the system isn't loaded :o</p> Ruby master - Feature #8820: Speed up Array#indexhttps://bugs.ruby-lang.org/issues/8820?journal_id=413572013-08-27T08:19:46Ztrans (Thomas Sawyer)
<ul></ul><p>Yes, sorry. I meant to use a random index with each iteration, not <code>i</code>. But per the suggestion, I think <code>i % 100</code> would be better.</p>
<p>I changed and reran the benchmarks. But even so the comparison still comes out about the same ratio:</p>
<p>Ruby: 35.66597<br>
Go: 1.39305</p> Ruby master - Feature #8820: Speed up Array#indexhttps://bugs.ruby-lang.org/issues/8820?journal_id=413642013-08-27T16:46:11Znobu (Nobuyoshi Nakada)nobu@ruby-lang.org
<ul><li><strong>Status</strong> changed from <i>Open</i> to <i>Closed</i></li><li><strong>% Done</strong> changed from <i>0</i> to <i>100</i></li></ul><p>This issue was solved with changeset r42704.<br>
Thomas, thank you for reporting this issue.<br>
Your contribution to Ruby is greatly appreciated.<br>
May Ruby be with you.</p>
<hr>
<p>array.c: optimized equality</p>
<ul>
<li>array.c (rb_ary_index, rb_ary_rindex): use optimized equality to<br>
improve performance. [Feature <a class="issue tracker-2 status-5 priority-4 priority-default closed" title="Feature: Speed up Array#index (Closed)" href="https://bugs.ruby-lang.org/issues/8820">#8820</a>]</li>
<li>vm_insnhelper.c (rb_equal_opt): optimized equality function.</li>
</ul>