Should Truffleruby be slower than JRuby for this?

[jzakiya]

Tested this code against 4 Ruby VMs and noticed TR slower than JRuby, which is usually not the case.

truffleruby 24.1.1, like ruby 3.2.4, Oracle GraalVM Native [x86_64-linux] (via rvm)

Except for 2nd|3rd test values, which JRuby significantly underperforms, in many cases it's faster than TR.
For most computationally intense highly numerical code like this it's been faster for me.
Is this an issue with the GraalVM, or is JRuby just mostly faster for this code?

Test Code

module Primes
  module Utils

    # Miller-Rabin prime test in Ruby
    # From: http://en.wikipedia.org/wiki/Miller-Rabin_primality_test
    # Ruby Rosetta Code: http://rosettacode.org/wiki/Miller-Rabin_primality_test
    # I modified the Rosetta Code, as shown below

    def primemr2?(k=5)  # increase k for more reliability
      return self >= 2 if self <= 3 
      return false unless 6.gcd(self) == 1
      neg_one_mod = n = d = self - 1      # these are even as self is always odd
      s = 0
      (d >>= 1; s += 1) while d.even?
      k.times do
        a = 2 + rand(self-4)
        y = a.pow(d,self)                 # y = (a**d) mod self
        next if y == 1 or y == neg_one_mod
        (s-1).times do
          y = y.pow(2, self)              # y = (y**2) mod self
          return false if y == 1
          break if y == neg_one_mod
        end
        return false unless y == neg_one_mod
      end
      true                                # n is prime (with high probability)
    end
    
    def primemr3?(k=5)  # increase k for more reliability
      return self >= 2 if self <= 3
      return false unless 6.gcd(self) == 1
      neg_one_mod = n = d = self - 1      # these are even as self is always odd
      d >>= 2 while (d & 0b11) == 0; d >>= (d & 1)^1  # make d odd number
      k.times do
        a = 2 + rand(self-4)
        y = a.pow(d, self)                # y = (a**d) mod self
        next if y == 1 or y == self-1
        until y == 1 || y == neg_one_mod || d == n
	      y = y.pow(2, self)              # y = (y**2) mod self
          d <<= 1
        end
        return false unless y == neg_one_mod
      end
      true                                # n is prime (with high probability)
    end

    # Returns true if +self+ is a prime number, else returns false.
    def primemr?(k = 5)
      wits = WITNESS_RANGES.find { |range, wits| range > self }
      witnesses = wits ? wits[1] : k.times.map{ rand(self - 4) + 2 }
      witnesses.each { |p| return false unless miller_rabin_test(p) }
      true
    end

    def primemr1?(k = 5)             # k is default number of random bases
      return PRIMES.include? self if self <= PRIMES.last
      return false if MODPN.gcd(self) != 1
      #return true  if self < PRIMES.last**2
      neg_one_mod = n = d = self - 1 # these are even as self is always odd
      d >>= 2 while (d & 0b11) == 0; d >>= (d & 1)^1  # make d odd number
      # wits = [range, [wit_prms]] or nil
      wits = WITNESS_RANGES.find { |range, wits| range > self }
      witnesses = wits ? wits[1] : k.times.map{ rand(self - 4) + 2 }
      witnesses.each do |b|
        next if (b % self).zero?     # **skip base if a multiple of input**
        y = b.pow(d, self)           # y = (b**d) mod self
        s = d
        until y == 1 || y == neg_one_mod || s == n
          y = y.pow(2, self)         # y = (y**2) mod self
          s <<= 1
        end
        return false unless y == neg_one_mod || s.odd?
      end
      true
    end

    private

    WITNESS_RANGES = {
      341_531 => [9345883071009581737],
      1_050_535_501 => [336781006125, 9639812373923155],
      350_269_456_337 => [4230279247111683200, 14694767155120705706, 16641139526367750375],
      55_245_642_489_451 => [2, 141889084524735, 1199124725622454117, 11096072698276303650],
      7_999_252_175_582_851 => [2, 4130806001517, 149795463772692060, 186635894390467037, 3967304179347715805],
      585_226_005_592_931_977 => [2, 123635709730000, 9233062284813009, 43835965440333360, 761179012939631437, 1263739024124850375],
      18_446_744_073_709_551_615 => [2, 325, 9375, 28178, 450775, 9780504, 1795265022],
      #318_665_857_834_031_151_167_461   => [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37],
      #3_317_044_064_679_887_385_961_981 => [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41]
    }

    MODPN  = 232862364358497360900063316880507363070 # 101# (101 primorial) is largest for u128
    PRIMES = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103]

    # Returns true if +self+ passes Miller-Rabin Test on +b+
    def miller_rabin_test(b)             # b is a witness to test with
      return self >= 2 if self <= 3 
      return false unless 6.gcd(self) == 1
      n = d = self - 1
      d >>= 2 while (d & 0b11) == 0; d >>= (d & 1)^1  # make d odd number
      return if (b % self).zero?         # **skip base if a multiple of input**
      y = b.pow(d, self)                 # y = (b**d) mod self
      until y == 1 || y == n || d == n
	    y = y.pow(2, self)               # x = (x**2) mod self
        d <<= 1
      end
      y == n || d.odd?
    end
  end
end

class Integer; include Primes::Utils end
  
def tm; s=Time.now; yield; Time.now-s end

# Perform primality tests with Miler-Rabin methods

def primes_tests(n)
  puts "test value #{n} is prime?: #{n.primemr1?}"
  puts "time for n.primemr?  is #{tm{ (10**4).times{ n.primemr?  } } }"
  puts "time for n.primemr1? is #{tm{ (10**4).times{ n.primemr1? } } }"
  puts "time for n.primemr2? is #{tm{ (10**4).times{ n.primemr2? } } }"
  puts "time for n.primemr3? is #{tm{ (10**4).times{ n.primemr3? } } }"
  puts
end

For these tests:

n = 100000000000000000000000000000000000000000000000000000000000000000000000001309503
primes_tests(n)

n = 303_371_455_241                              # lo prime pair for gap of 500
primes_tests(n)

n = 8446744073709551627
primes_tests(n)

n = 8446744073709551556
primes_tests(n)

n = 18446744073709551556
primes_tests(n)

n = 18446744073709551557                         # largest 64-bit prime
primes_tests(n)

n = 18446744073709551615                         # 2**64 - 1, largest 64-bits
primes_tests(n)

n = 18446744073709551629                         # next prime > 64-bits
primes_tests(n)

n = 340282366920938463463374607431768211296      # 1 < largest 128-bit prime
primes_tests(n)

n = 340282366920938463463374607431768211297      # largest 128-bit prime
primes_tests(n)

n = 340282366920938463463374607431768211455      # 2**128 - 1, largest 128-bits
primes_tests(n)

JRuby 9.4.9.0

test value 100000000000000000000000000000000000000000000000000000000000000000000000001309503 is prime?: true
time for n.primemr?  is 0.873514
time for n.primemr1? is 0.754906
time for n.primemr2? is 0.733884
time for n.primemr3? is 0.692394

test value 303371455241 is prime?: true
time for n.primemr?  is 8.858697000000001
time for n.primemr1? is 8.801776
time for n.primemr2? is 14.792952
time for n.primemr3? is 15.211563

test value 8446744073709551627 is prime?: false
time for n.primemr?  is 4.929926
time for n.primemr1? is 4.843951000000001
time for n.primemr2? is 5.052339999999999
time for n.primemr3? is 5.02239

test value 8446744073709551556 is prime?: false
➜  miller-rabin ruby miller-rabintest1.rb
test value 100000000000000000000000000000000000000000000000000000000000000000000000001309503 is prime?: true
time for n.primemr?  is 0.836465
time for n.primemr1? is 0.749006
time for n.primemr2? is 0.715312
time for n.primemr3? is 0.703027

test value 303371455241 is prime?: true
time for n.primemr?  is 8.743595
time for n.primemr1? is 8.502458
time for n.primemr2? is 14.66437
time for n.primemr3? is 14.517415000000002

test value 8446744073709551627 is prime?: false
time for n.primemr?  is 4.941791
time for n.primemr1? is 4.80778
time for n.primemr2? is 5.038014
time for n.primemr3? is 5.132918

test value 8446744073709551556 is prime?: false
time for n.primemr?  is 0.016883000000000002
time for n.primemr1? is 0.009792
time for n.primemr2? is 0.005158
time for n.primemr3? is 0.002415

test value 18446744073709551556 is prime?: false
time for n.primemr?  is 0.021440999999999998
time for n.primemr1? is 0.00723
time for n.primemr2? is 0.010395999999999999
time for n.primemr3? is 0.006878

test value 18446744073709551557 is prime?: true
time for n.primemr?  is 0.164283
time for n.primemr1? is 0.106833
time for n.primemr2? is 0.091131
time for n.primemr3? is 0.076461

test value 18446744073709551615 is prime?: false
time for n.primemr?  is 0.019133999999999998
time for n.primemr1? is 0.004553
time for n.primemr2? is 0.0025
time for n.primemr3? is 0.002422

test value 18446744073709551629 is prime?: true
time for n.primemr?  is 0.117601
time for n.primemr1? is 0.11476800000000001
time for n.primemr2? is 0.098049
time for n.primemr3? is 0.09081299999999999

test value 340282366920938463463374607431768211296 is prime?: false
time for n.primemr?  is 0.022298
time for n.primemr1? is 0.009453999999999999
time for n.primemr2? is 0.000998
time for n.primemr3? is 0.000956

test value 340282366920938463463374607431768211297 is prime?: true
time for n.primemr?  is 0.260003
time for n.primemr1? is 0.258279
time for n.primemr2? is 0.24645899999999998
time for n.primemr3? is 0.205179

test value 340282366920938463463374607431768211455 is prime?: false
time for n.primemr?  is 0.021006
time for n.primemr1? is 0.009675999999999999
time for n.primemr2? is 0.001349
time for n.primemr3? is 0.001433

TruffleRuby 24.1.1

test value 100000000000000000000000000000000000000000000000000000000000000000000000001309503 is prime?: true
time for n.primemr?  is 2.037394
time for n.primemr1? is 2.044762
time for n.primemr2? is 2.023177
time for n.primemr3? is 2.030676

test value 303371455241 is prime?: true
time for n.primemr?  is 0.130453
time for n.primemr1? is 0.083802
time for n.primemr2? is 0.13637000000000002
time for n.primemr3? is 0.10047499999999998

test value 8446744073709551627 is prime?: false
time for n.primemr?  is 0.074172
time for n.primemr1? is 0.09076000000000001
time for n.primemr2? is 0.05860000000000001
time for n.primemr3? is 0.05164800000000001

test value 8446744073709551556 is prime?: false
time for n.primemr?  is 0.03371
time for n.primemr1? is 0.008634
time for n.primemr2? is 0.002139
time for n.primemr3? is 0.002048

test value 18446744073709551556 is prime?: false
time for n.primemr?  is 0.027187
time for n.primemr1? is 0.013865
time for n.primemr2? is 0.00269
time for n.primemr3? is 0.001435

test value 18446744073709551557 is prime?: true
time for n.primemr?  is 0.268511
time for n.primemr1? is 0.27220300000000003
time for n.primemr2? is 0.207252
time for n.primemr3? is 0.204208

test value 18446744073709551615 is prime?: false
time for n.primemr?  is 0.046696
time for n.primemr1? is 0.003036
time for n.primemr2? is 0.001324
time for n.primemr3? is 0.001558

test value 18446744073709551629 is prime?: true
time for n.primemr?  is 0.34620700000000004
time for n.primemr1? is 0.2535529999999999
time for n.primemr2? is 0.190887
time for n.primemr3? is 0.256318

test value 340282366920938463463374607431768211296 is prime?: false
time for n.primemr?  is 0.050591
time for n.primemr1? is 0.028317
time for n.primemr2? is 0.000678
time for n.primemr3? is 0.000937

test value 340282366920938463463374607431768211297 is prime?: true
time for n.primemr?  is 0.678474
time for n.primemr1? is 0.63026
time for n.primemr2? is 0.5384709999999999
time for n.primemr3? is 0.534702

test value 340282366920938463463374607431768211455 is prime?: false
time for n.primemr?  is 0.03755
time for n.primemr1? is 0.028116
time for n.primemr2? is 0.000501
time for n.primemr3? is 0.001292

Ruby 3.3.6

est value 100000000000000000000000000000000000000000000000000000000000000000000000001309503 is prime?: true
time for n.primemr?  is 0.61845201
time for n.primemr1? is 0.600007099
time for n.primemr2? is 0.579011867
time for n.primemr3? is 0.579763807

test value 303371455241 is prime?: true
time for n.primemr?  is 0.019405872
time for n.primemr1? is 0.018532674
time for n.primemr2? is 0.022467344
time for n.primemr3? is 0.017704992

test value 8446744073709551627 is prime?: false
time for n.primemr?  is 0.023057941
time for n.primemr1? is 0.02498252
time for n.primemr2? is 0.013945913
time for n.primemr3? is 0.026167141

test value 8446744073709551556 is prime?: false
➜  miller-rabin ruby miller-rabintest1.rb
test value 100000000000000000000000000000000000000000000000000000000000000000000000001309503 is prime?: true
time for n.primemr?  is 0.632514411
time for n.primemr1? is 0.617031376
time for n.primemr2? is 0.584806694
time for n.primemr3? is 0.591961562

test value 303371455241 is prime?: true
time for n.primemr?  is 0.020221291
time for n.primemr1? is 0.018887651
time for n.primemr2? is 0.022730917
time for n.primemr3? is 0.017800883

test value 8446744073709551627 is prime?: false
time for n.primemr?  is 0.023692471
time for n.primemr1? is 0.024016789
time for n.primemr2? is 0.013324277
time for n.primemr3? is 0.019741071

test value 8446744073709551556 is prime?: false
time for n.primemr?  is 0.00981716
time for n.primemr1? is 0.002083217
time for n.primemr2? is 0.001528687
time for n.primemr3? is 0.001532383

test value 18446744073709551556 is prime?: false
time for n.primemr?  is 0.009846595
time for n.primemr1? is 0.002255851
time for n.primemr2? is 0.001545298
time for n.primemr3? is 0.001540399

test value 18446744073709551557 is prime?: true
time for n.primemr?  is 0.098092364
time for n.primemr1? is 0.074849837
time for n.primemr2? is 0.057987474
time for n.primemr3? is 0.050729434

test value 18446744073709551615 is prime?: false
time for n.primemr?  is 0.032238006
time for n.primemr1? is 0.002349256
time for n.primemr2? is 0.001806658
time for n.primemr3? is 0.001847625

test value 18446744073709551629 is prime?: true
time for n.primemr?  is 0.103820035
time for n.primemr1? is 0.085631054
time for n.primemr2? is 0.065799875
time for n.primemr3? is 0.062917339

test value 340282366920938463463374607431768211296 is prime?: false
time for n.primemr?  is 0.034392627
time for n.primemr1? is 0.003315758
time for n.primemr2? is 0.001747036
time for n.primemr3? is 0.001703224

test value 340282366920938463463374607431768211297 is prime?: true
time for n.primemr?  is 0.21347393
time for n.primemr1? is 0.191538654
time for n.primemr2? is 0.165191455
time for n.primemr3? is 0.130311444

test value 340282366920938463463374607431768211455 is prime?: false
time for n.primemr?  is 0.034583705
time for n.primemr1? is 0.003264902
time for n.primemr2? is 0.001701821
time for n.primemr3? is 0.001677576

Ruby 3.4-preview1

est value 100000000000000000000000000000000000000000000000000000000000000000000000001309503 is prime?: true
time for n.primemr?  is 0.635770087
time for n.primemr1? is 0.638503523
time for n.primemr2? is 0.595368691
time for n.primemr3? is 0.598772634

test value 303371455241 is prime?: true
time for n.primemr?  is 0.020588841
time for n.primemr1? is 0.019819027
time for n.primemr2? is 0.022277577
time for n.primemr3? is 0.017595767

test value 8446744073709551627 is prime?: false
time for n.primemr?  is 0.024912559
time for n.primemr1? is 0.027428728
time for n.primemr2? is 0.014424921
time for n.primemr3? is 0.025096815

test value 8446744073709551556 is prime?: false
time for n.primemr?  is 0.011165799
time for n.primemr1? is 0.002304622
time for n.primemr2? is 0.001619867
time for n.primemr3? is 0.001628684

test value 18446744073709551556 is prime?: false
time for n.primemr?  is 0.012746023
time for n.primemr1? is 0.003037716
time for n.primemr2? is 0.002829116
time for n.primemr3? is 0.001748089

test value 18446744073709551557 is prime?: true
time for n.primemr?  is 0.099865469
time for n.primemr1? is 0.077873137
time for n.primemr2? is 0.059939405
time for n.primemr3? is 0.055619184

test value 18446744073709551615 is prime?: false
time for n.primemr?  is 0.035954957
time for n.primemr1? is 0.002472667
time for n.primemr2? is 0.001887079
time for n.primemr3? is 0.001818871

test value 18446744073709551629 is prime?: true
time for n.primemr?  is 0.104930787
time for n.primemr1? is 0.08522826
time for n.primemr2? is 0.068326143
time for n.primemr3? is 0.064138119

test value 340282366920938463463374607431768211296 is prime?: false
time for n.primemr?  is 0.035416507
time for n.primemr1? is 0.003739953
time for n.primemr2? is 0.001777073
time for n.primemr3? is 0.00171192

test value 340282366920938463463374607431768211297 is prime?: true
time for n.primemr?  is 0.21398621
time for n.primemr1? is 0.190769001
time for n.primemr2? is 0.171413123
time for n.primemr3? is 0.131613246

test value 340282366920938463463374607431768211455 is prime?: false
time for n.primemr?  is 0.034755878
time for n.primemr1? is 0.003716379
time for n.primemr2? is 0.001799555
time for n.primemr3? is 0.001675553

My system

➜  ~ neofetch

             ooooooooooooo               jzakiya@jz1 
         ooooooooooooooooooooo           ----------- 
      oooooooooooooooooooooooooo         OS: PCLinuxOS x86_64 
    oooooooo              oooooooo       Host: 83DH Legion Slim 5 16AHP9 
   oooooo                    oooooo      Kernel: 6.6.58-pclos1 
  oooooo                       ooooo     Uptime: 5 hours, 5 mins 
ooooo    pppppppp    cccccccc   ooooo    Packages: 2660 (rpm) 
 oooo    ppp  pppp  ccccccccc    oooo    Shell: zsh 5.8 
ooooo    ppp   ppp ccccc         ooooo   Resolution: 2560x1600 
ooooo    ppp  ppp  cccc          ooooo   DE: Plasma 5.27.11 
ooooo    ppppppp   ccccc         ooooo   WM: KWin 
 ooooo   ppp         cccccccc   ooooo    WM Theme: Breeze 
  ooooo  ppp          ccccccc   ooooo    Theme: [Plasma], Breeze [GTK3] 
   ooooo                      oooooo     Icons: [Plasma], breeze [GTK2/3] 
    ooooo                   ooooooo      Terminal: konsole 
     ooooooo              ooooooo        CPU: AMD Ryzen 7 8845HS w/ Radeon 780M Graphics (16) @ 3.800GHz 
       oooooooooooooooooooooooo          GPU: AMD ATI 05:00.0 Device 1900 
          oooooooooooooooooo             GPU: NVIDIA GeForce RTX 4070 Max-Q / Mobile 
               ooooooooo                 Memory: 2901MiB / 15306MiB 
 

[nirvdrum]

I'm seeing things are good deal faster running on TruffleRuby+GraalVM 24.1.1, but it is still slower than JRuby in some instances. It's worth looking into.

[jzakiya]

I also posted this to the JRuby about the performance anomaly it had.

It's problem seems to have been identified and potentially patched.
Maybe this can help TR.

jruby/jruby#8516

[eregon]

At first sight, it seems likely related to modular exponentiation (Integer#pow(n, m)), the performance of that varies greatly based on the range of the 3 arguments.
Related issues about that: https://github.com/oracle/truffleruby/issues?q=is%3Aissue+pow+is%3Aclosed

We should profile, if it's about Java BigInteger#modPow being slower than CRuby's GMP then I don't think we can do much about it.