en en en pt es en en en en cv az en en en en en en en en en en en en en en en en it en es en en en en en en en ca es en es ne en en en en en en fr en en en en en tr en en en en en fr en en en en en en en fr en en en en en es en en en en en en en en en en en en en en en en en en en en en en en en zh nl en en en en en en en en en en en en en en it en en en en en en en pt en en en en en en en en en en en en en en en en
benchmark, benchmarking, compiler, higgs, javascript, jit, loop, optimization, performance, ropes, strings
The Fastest For-In Loops in the Whole Wide Web
This Monday, I met with Marc Feeley, my PhD advisor. I showed him graphs comparing the performance of Higgs to that of the TraceMonkey compiler. Reviewers at conferences we’ve previously submitted papers to have been very skeptical, and pressed us multiple times to produce some kind of comparison of basic block versioning against tracing. We believe that faring well against TraceMonkey could increase our odds of getting our work published.
So far, we’re beating TraceMonkey on about half of our benchmark set. There are, however, cases where we’re not doing well at all. The above graph compares speedups produced by Higgs relative to V8 baseline and TraceMonkey. The scale is logarithmic and higher bars are better. If you look at the last bars at the far right, you’ll notice that they’re actually negative. That’s because our performance on that benchmark is about 100 times slower than that of TraceMonkey (ouch). The scale of this graph could be fixed so that the bars no longer show up as negative, but Marc rightly pointed out that reviewers may latch on instances like this. Does this benchmark exhibit some pathological case that basic block versioning can’t handle?
The poorly-performing benchmark is string-fasta, from the SunSpider suite. A little bit of digging revealed what was going wrong. The benchmark uses the JavaScript for-in loop to iterate through object keys. The for-in loop uses reflection to iterate through the property names of an object and all of its parents. The semantics of this simple-looking construct are annoyingly complex. It deals with arrays and strings in addition to objects. If a property is deleted during iteration and hasn’t been listed yet, it must never be listed. Properties of child objects must “shadow” parent properties with the same name so that duplicate property names won’t show up twice.
The reason my for-in loop was slow is that I never bothered to optimize it. With such complex semantics, it seemed easier to take the “comfortable” approach. I implemented the loop with a closure that gets generated when iteration begins. This closure is a generator that returns a different property name on each call. It hides all of the iteration state and complex logic from the outside. What also added to the slowness is that this closure made multiple calls to the D part of my runtime to traverse object shapes. I wrote a microbenchmark to measure the speed of the for-in loop itself and sure enough, it was over 100 times slower than that of V8 and TraceMonkey.
My advisor convinced me that I should address this performance problem, and to do that, I had to make for-in loops faster. It was obvious that I should probably get rid of the closure created on each traversal and eliminate the D runtime calls. I had to remove the slow things, but what would I replace them with? For the closure, it was fairly obvious: initialize the variables I need before the loop, and thread them through manually as appropriate. The bigger issue was how I would go about enumerating all the properties in an object without calling into my D runtime code, and without traversing the shape tree structure at all, if possible.
I knew that V8 and TraceMonkey had fast for-in loops, so surely, they must have found a way to make them fast. They must have some kind of trick that I hadn’t thought of. My eureka moment came when I realized that for a given object shape (aka hidden class), the properties enumerated are always the same. Aha! There’s an easy solution then. A list of the properties to be enumerated over can be generated per-shape. To avoid D runtime calls, this list can take the form of a JS array that can be directly accessed by my JS runtime. Furthermore, it can be lazily generated the first time a for-in loop touches a given shape, and cached for future reuse. Clever, and not too difficult to implement.
After a few iterations of tweaking, I was quite pleased with the performance results I got (see above). Higgs went from having a horribly slow for-in loop to having the fastest of all. Quite possibly, the precached table trick I came up with is something other engines don’t have in their implementation.
The faster for-in loop satisfied my original goal. The fasta benchmark now runs several times faster on Higgs. The performance we get is no longer abhorrent. However, we still aren’t beating the other engines on that benchmark, we’re about 3 times slower now. There’s another detail that hinders performance in this specific benchmark. In the body of the for-in loops, properties are being accessed with dynamic keys that are only known at execution time. Higgs currently deals with that by doing a D runtime call. Clearly, again, the other engines have some better way of handling this particular case than I do.
I’ve been working hard in the last two weeks to try and fix every obvious performance issue I could find. Among other things, I implemented ropes to make string concatenation faster. Now, I made for-in loops faster. In the end though, each optimization I make is just a drop in the bucket. To compete effectively on every benchmark, there are many individual things to optimize. Everything must be made fast. The people at Google and Mozilla have had years to optimize their engines specifically so that they would perform well on the well-known sets of benchmarks. They’ve gone as far as implementing memoization of sine values based on the knowledge that this one benchmark calls the sine functions with the same angle values repeatedly.
What I wish conference reviewers would understand is just how high they’re raising the bar by asking little me to compare the performance of Higgs to that of commercial implementations. More than two years of work went into my JIT compiler, and I’m just barely starting to have performance numbers I can be proud of. You’ll notice though that I’m not comparing the performance of Higgs on benchmarks to that of IonMonkey, Crankshaft or TurboFan. I simply don’t think I can match the tens of man-years of (over)engineering and that went into it. It would take me several years to get anywhere close, and by then, V8 would be even faster than it is now. I’ve got the fastest for-in loop for the moment, but it takes a lot more than that to have a competitive JavaScript implementation.
From → Compilers, Higgs, JavaScript, Programming Languages
You mention that you’re beating Tracemonkey on about 50% of your benchmark suite, but in the chart, your speedup vs. Tracemonkey is >0% for all but one test. What gives? Is your benchmark suite different to what’s shown in the chart?
Bare above 100% are a win. Below that is a slowdown.
Vyacheslav Egorov (@mraleph) permalink
Crankshaft doesn’t support global iteration variable in the for() loops. I admit it’s my fault at taking a short-cut when implementing for-in.
If you rewrite innermost loop your microbenchmark from
for (k in o) { }
for (var k0 in o) { k = k0; }
then Crankshaft will kick-in and deliver ~2x improvement.
I am not sure why you decided to go with a global variable in your microbenchmark as fasta in SunSpider for example does not use global variable. Arguably global variables as loop iteration variables are bad smell anyways.
Why does crankshaft handle the global case? How does it make the iteration faster when it kicks in?
Vyacheslav Egorov (@mraleph) permalink
I guess the first question misses “not” – “why doesn’t Crankshaft”. I just did not implement that as it did not seem important. I implemented simple local variable case because I was mostly interested in optimizing pattern like for (var k in o) { o[k]; }. There is no technical reason why it can’t – in fact it should be fairly simple to cover if anybody was interested in this. I don’t think anybody should care much about for( in ) this days though, especially given ES6 for ( of ).
It makes iteration faster because it inlines fast paths (e.g. getting enumeration cache from the hidden class is inlined).
Code produced by Crankshaft is in general faster than code produced by baseline compiler, so even for (var i = 0; ...; i++) becomes faster itself.
Thanks for your insight. I’m curious as to how do you optimize the for (var k in o) { o[k]; } ?
I was thinking that I could generate the IR for the for loop, and then look at what depends on k inside the loop body, so that I can then replace my normal getProp (only optimized for constant string keys) by a version that takes the property slot index as argument, a specialized getPropEnum(obj, key, idx).
Vyacheslav Egorov (@mraleph) permalink
That’s precisely the optimization V8 does: o[k] is rewritten to become access by known offset.
(Somehow I can’t reply to your comment directly – WordPress limits the depth of comments?)
Reblogged this on Rodrigo Argumedo's Blog.
Reblogged this on Java Prorgram Examples and commented:
One of the nice programming article for your weekend.
The Fastest For-In Loops in the Whole Wide Web | Roweb Design
Leave a Reply Cancel reply
Enter your comment here...
Fill in your details below or click an icon to log in:
Email (required) (Address never made public)
You are commenting using your WordPress.com account. ( Log Out /  Change )
You are commenting using your Twitter account. ( Log Out /  Change )
You are commenting using your Facebook account. ( Log Out /  Change )
Notify me of new comments via email.
Notify me of new posts via email.
« Visit to Northeastern University
Pushing Higgs to the Limit »
Typed vs Untyped Virtual Machines
Minimalism in Programming Language Design
Democracy, Dictatorships and Access to Information
Code that Doesn’t Rot
The Internet Changed My Life
What’s Could You Use Tesla Bot For?
NoiseCraft: a Browser-Based Visual Programming Language for Sound & Music
Art Artificial Intelligence Artificial Life Assembly Biology Compilers Creativity D Language Electronics Future Game Development Genetic Algorithms Grad studies Graphics Higgs JavaScript Microcontrollers Microprocessors Music Programming Programming Languages Psychology Rant Robotics Tachyon Technology Uncategorized work x86 Zeta
Archives Select Month June 2022  (1) May 2022  (1) March 2022  (1) February 2022  (2) January 2022  (2) December 2021  (1) June 2021  (1) February 2021  (2) December 2020  (1) September 2020  (1) January 2020  (1) November 2019  (2) October 2019  (2) June 2019  (1) January 2019  (1) December 2018  (1) May 2018  (2) February 2018  (1) January 2018  (1) December 2017  (1) October 2017  (1) June 2017  (1) April 2017  (1) January 2017  (1) December 2016  (1) November 2016  (2) September 2016  (2) May 2016  (1) March 2016  (1) February 2016  (2) January 2016  (1) November 2015  (4) October 2015  (1) September 2015  (3) August 2015  (2) July 2015  (3) June 2015  (1) May 2015  (3) April 2015  (2) March 2015  (1) February 2015  (1) December 2014  (1) November 2014  (2) October 2014  (2) September 2014  (3) July 2014  (3) May 2014  (1) April 2014  (1) March 2014  (1) February 2014  (1) January 2014  (3) December 2013  (3) October 2013  (2) September 2013  (1) August 2013  (2) July 2013  (3) June 2013  (2) May 2013  (3) March 2013  (2) February 2013  (1) January 2013  (3) December 2012  (4) November 2012  (1) October 2012  (1) September 2012  (3) July 2012  (4) June 2012  (2) May 2012  (2) April 2012  (4) March 2012  (2) February 2012  (3) January 2012  (6) December 2011  (2) November 2011  (3) October 2011  (8) September 2011  (4) August 2011  (3)