4 ms·

How timely. I just ran into one today using the duktape† javascript engine and the hogan‡ mustache template expansion code. If you make a ~4MB output using deep

by jws 12y ago

How timely. I just ran into one today using the duktape† javascript engine and the hogan‡ mustache template expansion code. If you make a ~4MB output using deep in your library bowels… output += tiny_string; … a million or so times in Javascript, and that means you create a new string and reallocate and copy every time, then you end up with the impression that you have somehow made an infinite loop, but it should be a quadratic function. Switching the hogan buffer appending code to… chunks.push(tiny_string); … and ending with a … output = chunks.join(''); … gets back down into the milliseconds range instead of the "so long I have no idea if it would ever complete, left running while I developed a work around and it didn't finish" range. ␄ † http://duktape.org/index.html http://duktape.org/index.html ‡ http://twitter.github.io/hogan.js/ http://twitter.github.io/hogan.js/

smilekzs 12y ago
No. http://stackoverflow.com/questions/7299010/why-is-string-concatenation-faster-than-array-join http://stackoverflow.com/questions/7299010/why-is-string-con...
- peterfirefly 12y ago
  Not all Javascript implementations use ropes internally.
- jws 12y ago
  Yes. I'm not using the V8 engine. Tiny embedded engine, no super powers other than EC5 correct, small size, and reasonable performance. Of course V8 and its multimillion dollar development cost rivals probably only have this superpower because programers kept writing quadratic code.
  - pcwalton 12y ago
    > Of course V8 and its multimillion dollar development cost rivals probably only have this superpower because programers kept writing quadratic code. …and because SunSpider does it. https://github.com/WebKit/webkit/blob/master/PerformanceTests/SunSpider/tests/sunspider-1.0.2/string-base64.js https://github.com/WebKit/webkit/blob/master/PerformanceTest...
  - smilekzs 12y ago
    ... which is __the__ problem I was referring to, because these two implementations have essentially become black boxes with different performance on differnt runtimes. Should all library writers detect runtime and choose the optimal one? I don't think so. They're far more likely to simply write `a+=b`, which is NOT quadratic without any knowledge of the underlying impl.
mjcohen 12y ago
I ran into this a few years back. In a gawk program, I had to build a 300,000,000 character string by concatenating about 10,000,000 32-character strings. My naive code of doing 10,000,000 "a = a+str" took forever. I finally did sqrt(n) iterations of sqrt(n) concatenations and it took about 10 seconds.

by jws 12y ago

smilekzs 12y ago

No. http://stackoverflow.com/questions/7299010/why-is-string-concatenation-faster-than-array-join http://stackoverflow.com/questions/7299010/why-is-string-con...

peterfirefly 12y ago
Not all Javascript implementations use ropes internally.
jws 12y ago
Yes. I'm not using the V8 engine. Tiny embedded engine, no super powers other than EC5 correct, small size, and reasonable performance. Of course V8 and its multimillion dollar development cost rivals probably only have this superpower because programers kept writing quadratic code.
- pcwalton 12y ago
  > Of course V8 and its multimillion dollar development cost rivals probably only have this superpower because programers kept writing quadratic code. …and because SunSpider does it. https://github.com/WebKit/webkit/blob/master/PerformanceTests/SunSpider/tests/sunspider-1.0.2/string-base64.js https://github.com/WebKit/webkit/blob/master/PerformanceTest...
- smilekzs 12y ago
  ... which is __the__ problem I was referring to, because these two implementations have essentially become black boxes with different performance on differnt runtimes. Should all library writers detect runtime and choose the optimal one? I don't think so. They're far more likely to simply write `a+=b`, which is NOT quadratic without any knowledge of the underlying impl.

mjcohen 12y ago

I ran into this a few years back. In a gawk program, I had to build a 300,000,000 character string by concatenating about 10,000,000 32-character strings. My naive code of doing 10,000,000 "a = a+str" took forever. I finally did sqrt(n) iterations of sqrt(n) concatenations and it took about 10 seconds.