{"action":"created","issue":{"url":"https://api.github.com/repos/ruby/ruby/issues/1943","repository_url":"https://api.github.com/repos/ruby/ruby","labels_url":"https://api.github.com/repos/ruby/ruby/issues/1943/labels{/name}","comments_url":"https://api.github.com/repos/ruby/ruby/issues/1943/comments","events_url":"https://api.github.com/repos/ruby/ruby/issues/1943/events","html_url":"https://github.com/ruby/ruby/pull/1943","id":355503197,"node_id":"MDExOlB1bGxSZXF1ZXN0MjEyMDE1MDA4","number":1943,"title":"Omit executing methods/blocks that are side-effect free","user":{"login":"shyouhei","id":15377,"node_id":"MDQ6VXNlcjE1Mzc3","avatar_url":"https://avatars0.githubusercontent.com/u/15377?v=4","gravatar_id":"","url":"https://api.github.com/users/shyouhei","html_url":"https://github.com/shyouhei","followers_url":"https://api.github.com/users/shyouhei/followers","following_url":"https://api.github.com/users/shyouhei/following{/other_user}","gists_url":"https://api.github.com/users/shyouhei/gists{/gist_id}","starred_url":"https://api.github.com/users/shyouhei/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/shyouhei/subscriptions","organizations_url":"https://api.github.com/users/shyouhei/orgs","repos_url":"https://api.github.com/users/shyouhei/repos","events_url":"https://api.github.com/users/shyouhei/events{/privacy}","received_events_url":"https://api.github.com/users/shyouhei/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":2,"created_at":"2018-08-30T09:34:28Z","updated_at":"2018-09-04T17:02:06Z","closed_at":null,"author_association":"MEMBER","pull_request":{"url":"https://api.github.com/repos/ruby/ruby/pulls/1943","html_url":"https://github.com/ruby/ruby/pull/1943","diff_url":"https://github.com/ruby/ruby/pull/1943.diff","patch_url":"https://github.com/ruby/ruby/pull/1943.patch"},"body":"### Abstract\r\n\r\nWe propose a kind of optimisation so that known safe methods can be skipped.  In order to do so, we introduce a new instruction attribute called purity.  By checking the purity of every instruction inside of an instruction sequence, we can say if the sequence has any side effects or not.  This brings a room for optimisation, by skipping execution of such pure sequence.\r\n\r\nThe effect of this optimisation is somewhat limited (compared to #1419), but because we don't modify the form of instruction sequences at all, this pull request is safer to merge.  Passes test-all.\r\n\r\n![untitled](https://user-images.githubusercontent.com/15377/44839026-ac34e200-ac78-11e8-9a59-51e3c32f2603.png)\r\n\r\n### Related\r\n\r\n- This changeset is another single-cut of #1419\r\n- This changeset includes #1804 \r\n\r\n### Purity of instructions and merging them into one\r\n\r\nEach instruction is now categorised into the following 4 purity kinds namely \"pure\", \"notpure\", \"unpredictable\" and \"dependsblock\". Pure and not pure are intuitive.  Unpredictable means the instruction is unpredictable _at that moment_, maybe because that instruction has never been executed.  Thus when you evaluate that part later, the purity of the instruction might vary from time to time.  Depends block makes sense for method calls.  When a method itself had no side effects, there still are chances of breakage when the method yields and calling block that does something nasty.  But the purity of such block can be checked beforehand.  This value represents such situations.\r\n\r\nGiven this, a series of instructions are said to be pure or not by merging them altogether. An instruction sequence as a whole is not pure if it contains any instructions that are not pure.  It is unpredictable if it contains any unpredictable instructions (but no notpure ones).  Otherwise, the sequence is almost clean.  The purity then depends if it contains any dependsblock instruction or not.  In other words, an instruction sequence is said to be pure if and only if its containing instructions are all pure.\r\n\r\nSo far so simple.  The problem is, a call to a method (send instruction and such) can both be pure and not pure at the same time.  What is called at a specific call site cannot be determined until the very moment when we actually call it.  Of course, a method cannot be pure, until every and all of the methods it calls are pure.  So in short, we have to update a purity of a method on-the-fly.  This is done prior to we check the purity for skipping its execution.\r\n\r\n### Purity caching and invalidating\r\n\r\nRecursively reconstructing purity of each instruction sequences every time we call them is definitely a waste of time that we want to avoid.  Also, a method call is not always an execution of an instruction sequence; there are C methods.  So we are going to cache the calculated purity.\r\n\r\nThis is done in two places; first, the current effective purity is stored inside of `struct rb_iseq_constant_body`.  Then, at each call site, the purity is copied inside of `struct rb_call_cache`. The call cache also handles situations of non-Ruby methods.\r\n\r\nThese cached purites can become invalid on occasions.  For instance, a formerly pure instruction sequence can become not pure because of redefinitions.  In order to detect such things, we introduce per-VM global timestamp.  See #1804 for the details.  We consider cached purities invalid when its timestamp differs from the global one.\r\n\r\n### Optimisation using the purity\r\n\r\nIn this pull request, we modify `CALL_METHOD` macro.  This is where a method is called.  We change it so that if a method is called, then the return value is immediately discarded, and the method is pure, this is subject to optimise.  We don't call it at all; just clean up the stack.\r\n\r\n### Limitation of the proposed optimisation\r\n\r\nThe technique described above is in fact weak, compared to what we proposed in #1419.\r\n\r\nSuppose we have a ruby snippet `foo.bar.baz` and the three methods are in fact all pure. #1419 could eliminate them all by gradually replacing the method calls into nops.  What is proposed here, however, is not possible to optimise `foo` and `bar`.  It can optimise `baz` call, but not until it actually tries to call `baz`.  In order to do so, `foo` and `bar` cannot be optimised out.  The same discussion goes with method arguments e.g. `foo(bar(baz()))`.\r\n\r\n### Benchmarks\r\n\r\nThat being said, we believe the proposed method is not meaningless. We exercised ruby's standard benchmark set using benchmark-driver/benchmark-driver and got this result:\r\n\r\n```\r\n                              trunk        ours\r\n           vm1_attr_ivar    43.410M     45.331M i/s -     30.000M times in 0.691083s 0.661802s\r\n       vm1_attr_ivar_set    37.409M     29.019M i/s -     30.000M times in 0.801943s 1.033810s\r\n               vm1_block    25.388M     56.543M i/s -     30.000M times in 1.181643s 0.530568s\r\n          vm1_blockparam    26.034M     79.532M i/s -     30.000M times in 1.152326s 0.377207s\r\n     vm1_blockparam_call    14.282M     13.995M i/s -     30.000M times in 2.100567s 2.143563s\r\n     vm1_blockparam_pass    12.578M     12.652M i/s -     30.000M times in 2.385203s 2.371244s\r\n    vm1_blockparam_yield    16.627M     58.780M i/s -     30.000M times in 1.804334s 0.510376s\r\n               vm1_const   138.488M    138.751M i/s -     30.000M times in 0.216626s 0.216214s\r\n              vm1_ensure      2.129       2.136 i/s -       1.000 times in 0.469715s 0.468274s\r\n        vm1_float_simple    14.116M     14.545M i/s -     30.000M times in 2.125194s 2.062547s\r\n                vm1_ivar   129.643M    138.232M i/s -     30.000M times in 0.231404s 0.217027s\r\n            vm1_ivar_set    85.501M     91.704M i/s -     30.000M times in 0.350871s 0.327139s\r\n              vm1_length    86.600M     87.724M i/s -     30.000M times in 0.346422s 0.341983s\r\n           vm1_lvar_init      0.776       1.214 i/s -       1.000 times in 1.288198s 0.823900s\r\n            vm1_lvar_set    14.897M     14.851M i/s -     30.000M times in 2.013887s 2.020001s\r\n                 vm1_neq    69.289M     73.268M i/s -     30.000M times in 0.432969s 0.409453s\r\n                 vm1_not   225.745M    259.525M i/s -     30.000M times in 0.132893s 0.115596s\r\n              vm1_rescue   375.547M    241.017M i/s -     30.000M times in 0.079883s 0.124472s\r\n        vm1_simplereturn    70.230M    104.059M i/s -     30.000M times in 0.427169s 0.288299s\r\n                vm1_swap   126.279M    128.451M i/s -     30.000M times in 0.237569s 0.233552s\r\n               vm1_yield      0.992       1.423 i/s -       1.000 times in 1.008184s 0.702558s\r\n               vm2_array     5.358M      7.739M i/s -      6.000M times in 1.119869s 0.775304s\r\n            vm2_bigarray   811.932k    853.831k i/s -      6.000M times in 7.389783s 7.027156s\r\n             vm2_bighash    92.879k    112.642k i/s -     60.000k times in 0.646004s 0.532660s\r\n                vm2_case    73.899M     62.589M i/s -      6.000M times in 0.081192s 0.095864s\r\n            vm2_case_lit      1.389       1.320 i/s -       1.000 times in 0.720132s 0.757372s\r\n      vm2_defined_method     2.156M     11.467M i/s -      6.000M times in 2.782473s 0.523226s\r\n                vm2_dstr     5.175M      5.417M i/s -      6.000M times in 1.159329s 1.107629s\r\n        vm2_fiber_switch   600.175k    572.593k i/s -      6.000M times in 9.997092s 10.478648s\r\n              vm2_method     7.655M     11.707M i/s -      6.000M times in 0.783848s 0.512531s\r\n      vm2_method_missing     2.734M      2.401M i/s -      6.000M times in 2.194879s 2.498677s\r\n   vm2_method_with_block     6.299M      9.117M i/s -      6.000M times in 0.952600s 0.658145s\r\nvm2_module_ann_const_set   663.286k    961.725k i/s -      6.000M times in 9.045878s 6.238790s\r\n    vm2_module_const_set   804.539k      1.045M i/s -      6.000M times in 7.457687s 5.740310s\r\n               vm2_mutex    10.657M     10.524M i/s -      6.000M times in 0.563004s 0.570145s\r\n           vm2_newlambda     4.829M      7.083M i/s -      6.000M times in 1.242599s 0.847065s\r\n         vm2_poly_method      0.484       0.376 i/s -       1.000 times in 2.066164s 2.661122s\r\n      vm2_poly_method_ov      5.129       4.119 i/s -       1.000 times in 0.194978s 0.242782s\r\n      vm2_poly_singleton      0.988       1.230 i/s -       1.000 times in 1.012463s 0.812685s\r\n                vm2_proc    28.184M     27.420M i/s -      6.000M times in 0.212888s 0.218815s\r\n              vm2_raise1     1.118M      1.430M i/s -      6.000M times in 5.367653s 4.195418s\r\n              vm2_raise2   806.302k    931.697k i/s -      6.000M times in 7.441383s 6.439860s\r\n              vm2_regexp     5.622M      5.567M i/s -      6.000M times in 1.067146s 1.077827s\r\n                vm2_send    20.295M     17.299M i/s -      6.000M times in 0.295641s 0.346846s\r\n      vm2_string_literal    38.817M     38.084M i/s -      6.000M times in 0.154573s 0.157546s\r\n               vm2_super    16.609M     16.216M i/s -      6.000M times in 0.361260s 0.370014s\r\n               vm2_unif1    57.266M     75.720M i/s -      6.000M times in 0.104774s 0.079239s\r\n              vm2_zsuper    15.855M     15.090M i/s -      6.000M times in 0.378434s 0.397627s\r\n           vm3_backtrace      7.237       8.713 i/s -       1.000 times in 0.138172s 0.114765s\r\n    vm3_clearmethodcache      2.183       3.402 i/s -       1.000 times in 0.458154s 0.293988s\r\n```\r\n\r\nTrunk is `ruby 2.6.0dev (2018-08-28 trunk 64582) [x86_64-darwin15]`. Ours is a patch on top of it.  Both compiled using the same compiler (clang), same option.\r\n\r\nHere, the result shows that for most test cases, the patch does nothing.  On some benchmarks where pure methods act a significant role, our approach outperforms the trunk.\r\n\r\n### Conclusion\r\n\r\nWe propose a new kind of instruction attribute called purity.  By checking them, we can find a room for optimisation by skipping execution of such pure things.  It can boost benchmark performance for some instances, yet has no significant overhead."},"comment":{"url":"https://api.github.com/repos/ruby/ruby/issues/comments/418443701","html_url":"https://github.com/ruby/ruby/pull/1943#issuecomment-418443701","issue_url":"https://api.github.com/repos/ruby/ruby/issues/1943","id":418443701,"node_id":"MDEyOklzc3VlQ29tbWVudDQxODQ0MzcwMQ==","user":{"login":"k0kubun","id":3138447,"node_id":"MDQ6VXNlcjMxMzg0NDc=","avatar_url":"https://avatars1.githubusercontent.com/u/3138447?v=4","gravatar_id":"","url":"https://api.github.com/users/k0kubun","html_url":"https://github.com/k0kubun","followers_url":"https://api.github.com/users/k0kubun/followers","following_url":"https://api.github.com/users/k0kubun/following{/other_user}","gists_url":"https://api.github.com/users/k0kubun/gists{/gist_id}","starred_url":"https://api.github.com/users/k0kubun/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/k0kubun/subscriptions","organizations_url":"https://api.github.com/users/k0kubun/orgs","repos_url":"https://api.github.com/users/k0kubun/repos","events_url":"https://api.github.com/users/k0kubun/events{/privacy}","received_events_url":"https://api.github.com/users/k0kubun/received_events","type":"User","site_admin":false},"created_at":"2018-09-04T17:02:06Z","updated_at":"2018-09-04T17:02:06Z","author_association":"MEMBER","body":"> purity: describes if the instruction has a side effect or not.\r\n\r\nCould you elaborate the definition of \"side effect\" more? At first I imagined all instructions that alter *any* state are not pure, but it seems that you consider state changes *inside the method* as pure, like `setlocal` for a local variable in the method and almost all instructions that modify stack pointer.\r\n\r\nSo, to be more precise, does \"purity\" mean that the instruction does not alter states outside the method which has the instruction?\r\n\r\n<hr>\r\n\r\nDuring an insn is pure, can we think arbitrary method call does not happen? If so, we may be able to skip program counter motion for pure insns on MJIT.\r\n\r\n<hr>\r\n\r\nAlso, how did you detect / implement the purity flags? Reading all related code? After merging this, every time we modify any C function, how can we know all instructions that may call the modified function are pure?\r\n\r\nIf there were assertions enabled by `VM_CHECK_MODE` that ensure side effect is not happening inside pure insns, it would be very helpful to maintain the flags."}}
{"actor":{"display_login":"k0kubun"}}