Modular exponentiation with Integer#pow(exponent, modulo) is slow

[jzakiya]

v20.0.0 has an inexplicable performance issue for this code compared to J|Ruby.

https://rosettacode.org/wiki/Long_primes#Ruby

[eregon]

On the first program TruffleRuby seems much faster:

Time: 24.653815    # Ruby 2.7.1 
Time: 27.365734    # JRuby 9.2.11.1
Time: 4.496        # Truffleruby 20.0.0

On the second program there is no mention of Ruby implementations:

(same output with previous version, but longer time elapse)

Time: 1599.787375

So I guess you mean the last output "Translation of: Crystal of Sidef. Faster version."?

Time: 0.322962684 secs  # Ruby 2.7.1
Time: 0.856769 secs     # JRuby 9.2.11.1
Time: 20.954 secs       # Truffleruby 20.0.0

[eregon]

Using the CPUSampler clearly shows the bottleneck:

$ ruby --cpusampler --cpusampler.Mode=roots --experimental-options --cpusampler.SampleInternal longprimes.rb
...
---------------------------------------------------------------------------------------------------------------------------------------
Sampling Histogram. Recorded 6832 samples with period 1ms.
  Self Time: Time spent on the top of the stack.
  Total Time: Time spent somewhere on the stack.
  Opt %: Percent of time spent in compiled and therefore non-interpreted code.
---------------------------------------------------------------------------------------------------------------------------------------
 Thread: Thread[main,5,main]
 Name                                            |      Total Time     |  Opt % ||       Self Time     |  Opt % | Location             
---------------------------------------------------------------------------------------------------------------------------------------
 Integer#**                                      |       6341ms  92.8% |  99.7% ||       6341ms  92.8% |  99.7% | resource:/truffleruby/core/integer.rb~45-60:2119-2523 
 Integer#%                                       |        252ms   3.7% |  98.4% ||        252ms   3.7% |  98.4% | (core)~1:0 
 block in Enumerable#count                       |       6802ms  99.6% |  92.6% ||         32ms   0.5% |  12.5% | resource:/truffleruby/core/enumerable.rb~118:4184-4222 
 Object#prime?                                   |         43ms   0.6% |   4.7% ||         24ms   0.4% |   4.2% | longprimes.rb~1-10:0-432 
 Object#long_prime?                              |       6763ms  99.0% |  94.2% ||         23ms   0.3% |   8.7% | longprimes.rb~20-24:731-863 
 Integer#pow                                     |       6614ms  96.8% |  99.6% ||         21ms   0.3% |  61.9% | resource:/truffleruby/core/integer.rb~123-127:3646-3871 
 block in Object#divisors                        |         24ms   0.4% |  50.0% ||         20ms   0.3% |  55.0% | longprimes.rb~14:506-592 
...

Which shows that the call to 10.pow(d, p) is currently not taking advantage of the second argument to do modular exponentiation:

truffleruby/src/main/ruby/truffleruby/core/integer.rb

Line 126 in 71f0d83

(self ** e) % m

[eregon]

JRuby has an implementation of it: https://github.com/jruby/jruby/blob/9.2.8.0/core/src/main/java/org/jruby/RubyInteger.java#L799-L851

[eregon]

That seems quite complicated though, I'd rather just have a primitive converting everything to BigInteger and calling BigInteger#modPow.

[eregon]

This is much better since #2006, now I see:

$ time ruby longprimes.rb
Long primes ≤ 500:
7 17 19 23 29 47 59 61 97 109 113 131 149 167 179 181 193 223 229 233 257 263 269 313 337 367 379 383 389 419 433 461 487 491 499 
Number of long primes ≤ 500: 35
Number of long primes ≤ 1000: 60
Number of long primes ≤ 2000: 116
Number of long primes ≤ 4000: 218
Number of long primes ≤ 8000: 390
Number of long primes ≤ 16000: 716
Number of long primes ≤ 32000: 1300
Number of long primes ≤ 64000: 2430

Time: 0.558 secs

Integer#pow is now 46.1% of the time, vs 92.8% before.

We could go further by having optimized logic for Fixnum-range modulo for Integer#pow, by porting MRI's logic for that (int_pow_tmp1/int_pow_tmp2) and cleaning it up, potentially writing some of it in Ruby.

I think for now this is enough, but PRs welcome if someone wants to optimize Integer#pow(e, m) further.