diff options
Diffstat (limited to 'ASimpleReply')
| -rw-r--r-- | ASimpleReply/ASimpleReply2.md | 123 | ||||
| -rw-r--r-- | ASimpleReply/ASimpleReply3.md | 127 | ||||
| -rw-r--r-- | ASimpleReply/ASimpleReplyChain.md | 16 | ||||
| -rw-r--r-- | ASimpleReply/DadalReply2.md | 58 | ||||
| -rw-r--r-- | ASimpleReply/DadalReply3.md | 25 |
5 files changed, 338 insertions, 11 deletions
diff --git a/ASimpleReply/ASimpleReply2.md b/ASimpleReply/ASimpleReply2.md index 62f1a5ba..45017b61 100644 --- a/ASimpleReply/ASimpleReply2.md +++ b/ASimpleReply/ASimpleReply2.md @@ -7,23 +7,128 @@ The whole reply chain: https://github.com/SeaOfNodes/Simple/blob/main/ASimpleReply/ASimpleReplyChain.md I find long, involved, multi-part discussions difficult to follow because -basically we're really having 8 unrelated technical discussions. I broke up my +basically we're really having 6 unrelated technical discussions. I broke up my replies so each part is easier to consider on its own. -# Reply - Using t effect chains based on equivalence classes +## Reply - "Guard tests for correctness" -# Reply - "Guard tests for correctness" +Score one for static typing! -# Reply - "Graphs are nice for intuition but they don't scale well." +Here perhaps there is another win, but not really SoN related as least not +directly. Every "guardable" aspect in Java - except range checks - falls +neatly into a type *lattice*. This includes all kinds of subtype checks +(including instanceof, checkcast, user-written, arraystore, etc), null checks, +and constant bounds. A type *lattice* allows Sparse Conditional Constant +Propagation on all these types, which makes for a linear time, super cheap +analysis which wipes out that 90% of checks. -# Reply - "Use a worklist!" + +## Reply - "Graphs are nice for intuition but they don't scale well." + +Could be that graph viz tech has improved enough - although I tried hard with +GraphViz on Simple, and other than some pretty demos its not cut out for +serious debugging work. Meanwhile, ASCII dumps in C2 run into the 100 +thousands of lines, are instantly quick, land in my editor buffer where they +are ready to be searched, grep'ed, folded, stapled and mutalilated. Of course +they appear as a full CFG, with loop structure, typed, backlinks to source code, +etc. So maybe the answer is: "if you work on your debugging tools long enough, +they work for you". + + +## Reply - "Use a worklist!" I think we agree, at least in theory, here. -# Reply - Late arriving control flow from expanding small "diamonds" -# Reply - "Data? Perf discussions with facts? Apples to apples comparisons? No?" +## Reply - "Data? Perf discussions with facts? Apples to apples comparisons? No?" + +Yeah, apples & oranges. The obvious observation to make about any comparison +is that many benchmarkers have a desired outcome in mind... and will pick their +comparison according. Turboshaft was compared with the V8 variant SoN. +I'll betcha when doing comparable work C2 is *very* competitive with +Turboshaft, *especially* on a cache miss basis. This was *the number one +timing thing* I tracked in during C2's development. "Back in the day" nearly +all small to medium methods (plus inlines) fit in those processors *L1* cache. + + +## Reply - Late arriving control flow from expanding small "diamonds" +## Reply - Hard to introduce new control flow + +Full optimization of "diamond like things", without being a diamond and +remaining "pure" (no CFG at least), is done generally via the type lattice on +higher level common ops. They get lowered after there's no hope of other +optimization (provable no-progress by the lattice) - which is generally during +instruction scheduling for C2. + +If that's not enough and if you want to introduce control flow - its the same +problem in a CFG as in SoN (which *has* a CFG embedded). So whatever solution +you have for your CFG approach... SoN can use directly. + + +## Reply - It's easy in Simple + +Yeah, yeah, more opcodes and complexier semantics. C2 also has a zillion +opcodes, and deopts and re-opts, handles large graphs, multi IR levels, and +sings and dances.... and Simple has all the right compiler pieces to slot into +a runtime as complex as a JVM. I don't buy the "its easy because its Simple", +its easy because... its *simple*. Simplicity is a virtue in its own right, and +many hard looking things become, well, *simple* when you start from the right +base. + + +## Reply - Using multiple effect chains based on equivalence classes + +Well, this is the biggest failure I see in the V8 SoN effort and deserves the +most inspection... and has the most room for valid design tradeoffs. So I'm +saying a little more here, to match your larger writings, but also because +there's just more stuff to chew on. + + +"It requires typing the whole graph throughout the whole pipeline" - yes. This +is basically free in Simple/SoN, or at least costs some modest count of cpu +cycles (and generally no cache misses). Then it sits as a pointer in an IR +node. There's no bulk copy/bulk read going on, so... it costs nothing to sit +there. But then, when you need some type info - lo! There it is! C2 +maintains type info end-to-end, because its free to do so and because its +useful. + +"Equivalence classes are much weaker for arrays" - sure. And basically make no +differece to 99% of all Java programs. 1-d arrays vectorize just fine; stencil +calculations also fine. Register blocking and tiling? First Java needs to +change how multi-D arrays are laid out then we can worry about loop carried +aliasing. Basically, Java was never intended to replace Fortran, although in +the 1-D space it can hold its own. + +"Every call to user-defined functions, as well as most builtin calls have +arbitrary side effects" - sure same as Java. Doesn't really matter in the +grand scheme of things. If you can inline, the problem goes away. If not, +well *There's Yer Problem*. The lack of call aliasing info means you didn't +optimize some things around the call - all dwarfed by the call overhead itself. + +"Memory optimizations also cannot typically float past deoptimization state" - +plenty of those in Java too. C2 also does not sink stores *below* a deopt +state. At least for Java, we can float loads *up* past a deopt state (and do +so plenty). + +Also, call inline points *completely* disappear in C2. There is no +optimization barrier after inlining, even for memory effects. This is +different from *deoptimization* in this regard. + +# "Because of polymorphism.... but rather union types". + +Here I honestly don't know. I can fit some kinds of union types in a type +*lattice*, and then we're back to "basically free types". On the other hand, +the usefulness of the equivalence class model is based on "since you *cannot* +alias, the other aliases are not even representable". + +This gets into a weak argument from me about how after specialization guards, +we're back to equivalence classes... but I honestly dunno. Not tried it in JS +at least (C2 certainly does this, but its not so common as JS). +Very curious though... + +Curious enough for Google to fund a reprise with me lending a hand? + +:-) -# Reply - Hard to introduce new control flow +Cliff -# Reply - It's easy in Simple diff --git a/ASimpleReply/ASimpleReply3.md b/ASimpleReply/ASimpleReply3.md new file mode 100644 index 00000000..395f4b77 --- /dev/null +++ b/ASimpleReply/ASimpleReply3.md @@ -0,0 +1,127 @@ +# A Simple Reply (3) + +The whole reply chain: + +https://github.com/SeaOfNodes/Simple/blob/main/ASimpleReply/ASimpleReplyChain.md + + +## Unzipping + +Starting from Dadal's code, which has inlined some specialization checks: + +``` +foo (o) { + let x; + if (o.map == Map1) { + x = RawLoad(o, offset=8); + } else if (o.map == Map2) { + x = RawLoad(o, offset=16); + } else if (o.map == Map3) { + x = RawLoad(o, offset=12); + } else throw deopt; // Cliff added + .... // Cliff adds: call this code "S1" + let y; + if (o.map == Map1) { + y = RawLoad(o, offset=0); + } else if (o.map == Map2) { + y = RawLoad(o, offset=20); + } else if (o.map == Map3) { + y = RawLoad(o, offset=4); + } else throw depopt; // Cliff added +} +``` + +I added the "throw deopt", which I assume Dadal implies when `x` and `y` are +none of `Map1, Map2, Map3`. + +Dadal then adds: + +> "Here, it's not like any of the type-checks when loading `y` could be +> removed. Well, in some cases, we do things like double-diamond elimination to +> remove some checks, but often it's not possible." + +C2 sees this kind of pattern fairly often as well; generally replacing `o.map +== Map1` with `o instanceof Map1`; not that it matters. C2 uses a "unzipping" +xform for repeated checks; I've talked about it publically numerous times. +Here C2 will look at the `S1` code above, and based on a heuristic (mostly +size) it will clone `S1` to remove the excess checks: + +``` +foo (o) { + let x,y; + if (o.map == Map1) { + x = RawLoad(o, offset=8); + S1; + y = RawLoad(o, offset=0); + + } else if (o.map == Map2) { + x = RawLoad(o, offset=16); + S1; + y = RawLoad(o, offset=20); + + } else if (o.map == Map3) { + x = RawLoad(o, offset=12); + S1; + y = RawLoad(o, offset=4); + + } else throw deopt; // Cliff added +} +``` + +Now you get 3 chunks of specialized code where in each case you know the type +of `o.map` throughout. This process can be repeated at all kinds of levels, +and assuming the strong knowledge of `o.map` allows more optimizations, can pay +for itself despite cloning some amount of `S1`. Its certainly common for C2 to +clone long runs of repeated checks such that in the end there's a fast-path +where all checks pass "the good way", and bail-out points all long that go to a +correct but slow path. + + +## Common Case vs Deopt + +``` +foo (o) { + let x = o.x; + bar(); // Might change the "shape" of `o` + let y = o.y; +} +``` + +Dadal: + +> "If `bar` isn't inlined, then we have to assume that `bar` could change +> the shape of `o`, and thus a type-check is needed before loading `y`." + +In a similar situation C2 will do the same. Of course, for sufficiently hot +`foo` and modest `bar`, inlining is the answer. This makes me wonder if C2's +inlininhg budget is substantially higher than V8's. + +Dadal: +> "Oh, and `bar` could be changing the shape of `o` only some times" + +In any of these "sometimes Bad Things Happens" situations, C2's go-to answer is +to register a dependency and deopt if the Bad Thing happens. The set of Bad +Things that happen between JS and the JVM are different, but it seems to me the +general theory still holds. Similar (not exact) situation: + +```java +foo( Object o ) { + var x = ((Cat)o).x; // Dependency that Cat has no subclasses + x.bar(); // Always a `Cat` so call Cat.bar +} +``` + +If later `Cat` is extended with `Siamese` which implements an alternative +`bar`, this code is deopt'd. The existing calls to `foo` can finish - they are +correct because they got called with a `Cat` and cannot change that - but no +new calls are allowed; they will use an alternative more conservative execution +until a fresh JITd code for `foo` can be made. + + +## Summary + +Yeah, the problems between JS and the JVM are different... but not hugely so. +And the problems shown here are *utterly* unrelated to the Sea-of-Nodes. +I'd do this stuff in a normal CFG framework just the same. + +Cliff diff --git a/ASimpleReply/ASimpleReplyChain.md b/ASimpleReply/ASimpleReplyChain.md index 2d53a8ee..eb0bc80e 100644 --- a/ASimpleReply/ASimpleReplyChain.md +++ b/ASimpleReply/ASimpleReplyChain.md @@ -17,10 +17,22 @@ https://gist.github.com/DadaIsCrazy/8ce07d409f8f74bad7b36e74b77a3129 ### Cliff's Reply(2): -(first, this reply-chain to gather all the parts) - https://github.com/SeaOfNodes/Simple/blob/main/ASimpleReply/ASimpleReply2.md +### Dadal's Reply(2): + +https://studio.youtube.com/channel/UCbutMk6cKrH8q4sJyQHGPVQ/comments/inbox?filter=%5B%5D +https://github.com/SeaOfNodes/Simple/blob/main/ASimpleReply/DadalReply2.md + + +### Cliff's Reply(3) + +https://github.com/SeaOfNodes/Simple/blob/main/ASimpleReply/ASimpleReply3.md + +### Dadal's Reply(3) + +https://github.com/SeaOfNodes/Simple/blob/main/ASimpleReply/DadalReply3.md + [room for more conversations] diff --git a/ASimpleReply/DadalReply2.md b/ASimpleReply/DadalReply2.md new file mode 100644 index 00000000..bb30e155 --- /dev/null +++ b/ASimpleReply/DadalReply2.md @@ -0,0 +1,58 @@ + +This is Dadal's reply from U-tube, recreated here (permission pending) so its +both easier to find and not lost if U-tube changes their mind. + +The original link I copied from: + +https://studio.youtube.com/channel/UCbutMk6cKrH8q4sJyQHGPVQ/comments/inbox?filter=%5B%5D + +The whole replace chain: + +https://github.com/SeaOfNodes/Simple/blob/main/ASimpleReply/ASimpleReplyChain.md + + + +Type checks: to give an example: + +``` +foo(o) { + let x = o.x; + .... + let y = o.y; +} +``` + +Assuming polymorphic feedback (which is very frequent in JS), this will become something like (using JS-like syntax, but this happening inside the compiler of course) +``` +foo (o) { + let x; + if (o.map == Map1) { + x = RawLoad(o, offset=8); + } else if (o.map == Map2) { + x = RawLoad(o, offset=16); + } else if (o.map == Map3) { + x = RawLoad(o, offset=12); + } + .... + let y; + if (o.map == Map1) { + y = RawLoad(o, offset=0); + } else if (o.map == Map2) { + y = RawLoad(o, offset=20); + } else if (o.map == Map3) { + y = RawLoad(o, offset=4); + } +} +``` + +Here, it's not like any of the type-checks when loading `y` could be removed. Well, in some cases, we do things like double-diamond elimination to remove some checks, but often it's not possible. + +For monomorphic cases, subsequent checks will be removed when possible, but objects can change shapes in JavaScript. This means that if you have something like +``` +foo (o) { + let x = o.x; + bar(); + let y = o.y; +} +``` +If `bar` isn't inlined, then we have to assume that `bar` could change the shape of `o`, and thus a type-check is needed before loading `y`. Oh, and `bar` could be changing the shape of `o` only some times, so `o.x` could have monomorphic feedback while `o.y` could have polymorphic feedback. Or the other way around :) diff --git a/ASimpleReply/DadalReply3.md b/ASimpleReply/DadalReply3.md new file mode 100644 index 00000000..e5e89aa4 --- /dev/null +++ b/ASimpleReply/DadalReply3.md @@ -0,0 +1,25 @@ + +This is Dadal's reply from U-tube, recreated here (permission pending) so its +both easier to find and not lost if U-tube changes their mind. + +The original link I copied from: + +https://www.youtube.com/watch?v=iNWAgSAEPAg&lc=Ugwn_YpruALAauwRLqt4AaABAg.AGbLSQ5tlmFAGcQm0uZyZO + +The whole replace chain: + +https://github.com/SeaOfNodes/Simple/blob/main/ASimpleReply/ASimpleReplyChain.md + + + +On medium sized functions, everything tends to be inlined in V8, but on larger +functions it tends to be more complicated. We've tried before to increase the +inclining budget, but this means reducing compile time, which means delaying +the time until the optimized code starts being executed, which in turns +regresses whatever benchmarks we're using to measure how fast V8 is. One +difference with Java here might be 1- how slow unoptimized JS code is (after +all, V8 bytecodes are ultra-generic, assuming any types for inputs, and having +to check a ton of various cases) and 2- how fast-running JS applications are +compared to Java (not in the sense that "JS is faster" but in the sense that +"JS applications probably stop running at least one order of magnitude earlier +than Java ones") |