Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

JRuby is super-slow to execute a big and trivial case-when statement #3672

Closed
mame opened this issue Feb 16, 2016 · 20 comments
Closed

JRuby is super-slow to execute a big and trivial case-when statement #3672

mame opened this issue Feb 16, 2016 · 20 comments

Comments

@mame
Copy link

mame commented Feb 16, 2016

Hello,

MRI adopts "jump table"-like optimization for case-when statement if all clauses have trivial immediate values such as Integer and Symbol. How about implementing this optimization in JRuby?

100000.times do
  case 1000
  when 0
  when 1
  when 2
  ...
  when 999
  end
end
$ time ruby -v t.rb
ruby 2.3.0p0 (2015-12-25 revision 53290) [x86_64-linux]

real    0m0.082s
user    0m0.068s
sys     0m0.012s

$ time ~/opt/jruby-9.0.5.0/bin/jruby --server -v t.rb
jruby 9.0.5.0 (2.2.3) 2016-01-26 7bee00d Java HotSpot(TM) 64-Bit Server VM 25.72-b15 on 1.8.0_72-b15 +jit [linux-amd64]

real    0m18.692s
user    0m25.232s
sys     0m0.244s

Thank you,

@chrisseaton
Copy link
Contributor

MRI adopts "jump table"-like optimization for case-when statement if all clauses have trivial immediate values such as Integer and Symbol

Is this documented somewhere? How does it interact with the existing semantics that cases are tried sequentially with =~? What if =~ has side effects? What if one case's =~ redefines =~ for a subsequent case?

If MRI does this then it's a language feature, not an optimisation, and it needs to be covered by the specs.

@enebo enebo added this to the Post-9000 milestone Feb 16, 2016
@enebo
Copy link
Member

enebo commented Feb 16, 2016

@mame we have some plans to reintroduce this at a later date. JRuby 1.7.x does a jump table for Fixnums and a couple of other simple types. We have not added them to 9k yet but we will at some point.

@mame
Copy link
Author

mame commented Feb 16, 2016

@chrisseaton

Is this documented somewhere?

Since this is an implementation detail of MRI, I don't think this behavior is documented anywhere.

How does it interact with the existing semantics that cases are tried sequentially with =~?

I think you meant ===. Whenever MRI evaluates trivial case statement, it checks if === of related classes is redefined or not, and cancels the optimization if any is redefined.

BTW, I have no intention to force you to do the same. This is just a suggestion.

@mame
Copy link
Author

mame commented Feb 16, 2016

@enebo Ah, do you mean this optimization has been already implemented but disabled for any reason? If so, sorry for noise. Thank you!

@enebo
Copy link
Member

enebo commented Feb 16, 2016

@mame it was not disabled, but we have a completely new runtime in JRuby 9000 so we could not just port the old optimization over as-is.

@mame
Copy link
Author

mame commented Feb 16, 2016

I understand very well. I'll try JRuby 1.7. Should I close this issue? May I leave it to you? Thank you very much!

@headius
Copy link
Member

headius commented Feb 16, 2016

We have an open issue for remaining optimizations in case/when, so we'll close this.

See #3513.

@headius
Copy link
Member

headius commented Mar 7, 2016

Reopening this as the better bug for ongoing optimization work.

@headius headius reopened this Mar 7, 2016
@headius headius removed this from the Invalid or Duplicate milestone Mar 7, 2016
@mame
Copy link
Author

mame commented Mar 31, 2016

FYI: I published my program and benchmark result.

@enebo
Copy link
Member

enebo commented Apr 1, 2016

@mame thanks for the link. We will be sure to reexamine the performance periodically and also once we re-add some jumptable optimizations.

@headius
Copy link
Member

headius commented Apr 8, 2016

@mame I have implemented constant-time Fixnum case/when but I'm getting a strange error running the --opt version of optcarrot:

[] ~/projects/optcarrot $ jruby -v -Xcompile.invokedynamic -Ilib bin/optcarrot --opt --benchmark examples/Lan_Master.nes
jruby 9.1.0.0-SNAPSHOT (2.3.0) 2016-04-05 2221210 Java HotSpot(TM) 64-Bit Server VM 25.60-b23 on 1.8.0_60-b27 +indy +jit [darwin-x86_64]
fps: 0
checksum: 27904
FiberError: can't yield from root fiber
      yield at org/jruby/ext/fiber/ThreadFiber.java:209
      yield at org/jruby/ext/fiber/ThreadFiber.java:200
        run at (generated PPU core):556
       sync at /Users/headius/projects/optcarrot/lib/optcarrot/ppu.rb:319
     update at /Users/headius/projects/optcarrot/lib/optcarrot/ppu.rb:254
  poke_2000 at /Users/headius/projects/optcarrot/lib/optcarrot/ppu.rb:344
       call at org/jruby/RubyMethod.java:127
        run at (generated CPU core):1478
       step at /Users/headius/projects/optcarrot/lib/optcarrot/nes.rb:42
        run at /Users/headius/projects/optcarrot/lib/optcarrot/nes.rb:77
      <top> at bin/optcarrot:6

Two questions:

  1. What are fibers being used for in the generated code? Fibers are generally much more expensive in JRuby than in MRI since we have to use native threads to simulate them. If they can be eliminated from the optimized code, we may do better.
  2. How can I look at the generated code?

@headius
Copy link
Member

headius commented Apr 8, 2016

Benchmark of 100 all-Fixnum cases (1000 does not JIT and remains interpreted):

[] ~/projects/optcarrot $ jruby -Xjit.threshold=0 bench_fixnum_case_when.rb 
  3.120000   0.040000   3.160000 (  1.925519)
  1.640000   0.010000   1.650000 (  1.485029)
  1.490000   0.000000   1.490000 (  1.491089)
  1.480000   0.000000   1.480000 (  1.480089)
  1.500000   0.010000   1.510000 (  1.503165)
  1.520000   0.000000   1.520000 (  1.533434)
  1.470000   0.000000   1.470000 (  1.458303)
  1.430000   0.000000   1.430000 (  1.440517)
  1.460000   0.000000   1.460000 (  1.454715)
  1.440000   0.000000   1.440000 (  1.443573)

[] ~/projects/optcarrot $ rvm jruby-9.0.5.0 do jruby -Xcompile.invokedynamic -Xjit.threshold=0 bench_fixnum_case_when.rb 
 79.910000   0.250000  80.160000 ( 78.924439)
 79.370000   0.200000  79.570000 ( 79.535567)
 79.720000   0.330000  80.050000 ( 80.274685)
 79.020000   0.200000  79.220000 ( 79.289017)
 78.380000   0.180000  78.560000 ( 78.604202)
 78.800000   0.190000  78.990000 ( 79.080842)
...

@mame @ko1 Can you point me toward the constant-time case/when optimization in MRI? I'd like to match it for JRuby 9.1.

@headius
Copy link
Member

headius commented Apr 8, 2016

@nobu You may know where this optimization is in MRI too...

@nobu
Copy link

nobu commented Apr 8, 2016

There are some points in compile.c and insns.def.
Try git grep -i cdhash.

@headius
Copy link
Member

headius commented Apr 8, 2016

@nobu: Great, thanks!

@mame
Copy link
Author

mame commented Apr 8, 2016

@headius

  1. What are fibers being used for in the generated code?

No fiber is used in the generated code. Maybe your jruby failed to generate a correct source code.

  1. How can I look at the generated code?

Try jruby bin/optcarrot --opt --dump-ppu. Compare the output with normal ruby's output.

@headius
Copy link
Member

headius commented Apr 20, 2016

Continuing work in post 9.1.

@headius headius removed this from the JRuby 9.1.1.0 milestone May 11, 2016
@headius headius modified the milestones: JRuby 9.1.2.0, JRuby 9.1.1.0 May 11, 2016
@enebo enebo modified the milestones: JRuby 9.1.2.0, JRuby 9.1.3.0 May 23, 2016
@headius
Copy link
Member

headius commented Aug 15, 2016

Fixnum case optimizations have been merged to master. Remaining work bumped to 9.1.4.0.

@headius headius modified the milestones: JRuby 9.1.4.0, JRuby 9.1.3.0 Aug 15, 2016
@enebo enebo modified the milestones: JRuby 9.2.0.0, JRuby 9.1.6.0 Nov 7, 2016
@headius headius removed this from the JRuby 9.2.0.0 milestone May 15, 2018
@headius
Copy link
Member

headius commented May 15, 2018

General problem with large case statements preventing JIT. I'm detargeting.

@headius
Copy link
Member

headius commented Jul 18, 2020

There's nothing specific to case here that isn't covered by other bugs about large methods failing to compile. We know about that issue and the work required to solve it.

JRuby will optimize homogeneous case/when to a jump table in at least the Fixnum case, so we'll call this one done as of 9.1.4.0.

@headius headius closed this as completed Jul 18, 2020
@headius headius added this to the JRuby 9.1.4.0 milestone Jul 18, 2020
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

5 participants