https://accidentallyquadratic.tumblr.com/post/142387131042/nodejs-left-pad * [ ] * Archive * Submit an Accidentally Quadratic [sphere_ope] Accidentally Quadratic node.js left-pad If you're a programmer, there's a good chance you noticed the node.js left-pad fiasco of a few weeks back that temporarily broke most of the npm ecosystem. This blog doesn't have an opinion on any of that. However, in the ensuing kerfluffle, several peopleobserved that left-pad appears to be quadratic, and that is definitely this blog's concern. If we look at the code, we see that the main loop looks like so: while (++i < len) { str = ch + str; } In most languages' string implementations, this would be definitely quadratic -- + copies the entire string (of size O(len)) on each iteration, and this loop runs O(len) times. However, I happen to know that modern JS implementations have a whole pile of complex String optimizations, including rope-like data structures. And this is an evidence-driven blog, so I decided to take a deeper look. And what I found is fascinating and bizarre and I honestly can't explain it yet. The benchmarks But let's start with something easy. I ran a benchmark in rhino, which I judged to be the javascript implementation that I had easy access to least likely to have super-advanced string optimizations. We can clearly see the telltale quadratic curve: [tumblr_inl] But now let's try something a bit more sophisticated, which also happens to be my primary browser: Chrome. Running a left-pad benchmark in Chrome yields the following result: [tumblr_inl] There's bit of anomalous behavior, especially at small sizes, but it makes a compelling case for being linear out through the 1MB limit I ran the test over! (I'm running Chrome Version 50.0.2661.57 beta (64-bit); your results may well vary with Chrome version!) And in fact, the Chrome developer tools will let us see the rope structure that Chrome has used to make these concatenations efficient! If we leftpad('hi', 100000, 'x') in a Chrome console and then take a heap snapshot, we can see that the string is a "concatenated string" made up of a huge number of chunks linked together: [tumblr_inl] (The downside of this optimization, as you can also see from that screenshot, is that our 100kb string now consumes 4MB of RAM...) Moving on, we can also try Safari, another modern browser with an incredibly-sophisticated Javascript engine. In Safari, we see this odd behavior: [tumblr_inl] It's a bit hard to be sure, but the data appears to fit two linear fits, with a cutover somewhere around 350k. This pattern was reproducible across multiple experiments, but I don't have an explanation. I also decided to try node, since that is the actual runtime that NPM primarily targets, after all. node runs the same v8 engine as Chrome, so we'd expect similar behavior, but version skew, configuration, or who knows what could cause divergence. And in fact, we see: [tumblr_inl] Oddly, it also seems to exhibit two separate linear regimes! At this point, I'm out of energy for what was meant to be a short post, but if anyone can follow-up and explain what's happening, I'd be terribly curious. In Conclusion This adventure turned out to be another excellent demonstration of a principle I've expounded on frequently in this blog: Quadratic behavior (or, in this case, the lack there of!) often results in complex interactions between pieces of code operating at different layers of abstraction. In this case, the action-at-a-distance saved us: Modern Javascript VMs, in their sophistication, were able to optimize what looked like extremely quadratic code into a linear linked list! But the principle remains, that it was actually completely impossible for us to analyze left-pad's performance without a deep understanding of the specific underlying Javascript VM we cared about (or, in my case, resorting to brute experiment!). accidentally quadratic left-pad node javascript js 56 notes Apr 6th, 2016 * Open in app * Facebook * Tweet * Mail * Permalink 1. [avatar_6bb]iamcreasy liked this 2. [avatar_459]olupiksel liked this 3. [avatar_a02]injygo liked this 4. [avatar_86d]stumpyjoepete liked this 5. [avatar_635]minimirai liked this 6. [e13d0ced92]skiingcows reblogged this from accidentallyquadratic 7. [e13d0ced92]skiingcows liked this 8. [avatar_603]gothdotblack liked this 9. [avatar_8d0]proceduralpolymatheia reblogged this from accidentallyquadratic 10. [cube_open_]neo-queen-gay reblogged this from rootkit 11. [avatar_404]starrynightcinema liked this 12. [c36d47e11d]gravityjunior liked this 13. [avatar_e86]guavaorb liked this 14. [e1f25bb1c1]rootkit reblogged this from accidentallyquadratic 15. [avatar_2d0]naillig liked this 16. [avatar_2b9]superdrivel reblogged this from accidentallyquadratic and added: this is a good blog 17. [avatar_2b9]superdrivel liked this 18. [avatar_d21]tangerinebonfire liked this 19. [avatar_afe]tubaterry reblogged this from accidentallyquadratic 20. [avatar_36e]counterfaith liked this 21. [avatar_afe]tubaterry liked this 22. [avatar_127]amyquispe liked this 23. [cone_open_]thejessyouveallbeenhearingabout liked this 24. [avatar_db6]k-abdelsalam liked this 25. [avatar_855]thedefaultlocation liked this 26. [avatar_23a]guldumnet liked this 27. [avatar_ae5]hydrakecat reblogged this from accidentallyquadratic 28. [avatar_ae5]hydrakecat liked this 29. [avatar_79c]poly-trans-gal-pal reblogged this from accidentallyquadratic 30. [avatar_79c]poly-trans-gal-pal liked this 31. [default_av]a-chinaman liked this 32. [avatar_d99]boldlywaywardtaco liked this 33. [avatar_332]valzq liked this 34. [avatar_38f]marcospinello liked this 35. [avatar_464]spacejewfromhell-blog liked this 36. [sphere_ope]accidentallyquadratic posted this 37. Show more notesLoading... [impixu][impixu]