4 ms·

This is so hilariously overengineered: not failing when passed the wrong types, arbitrarily caching padding of len < 10, etc The most egregious is the bad big

by ghj 6y ago

This is so hilariously overengineered: not failing when passed the wrong types, arbitrarily caching padding of len < 10, etc The most egregious is the bad big O analysis for a pointless binary search. The loop does indeed run O(log(n)) times but `ch += ch` still takes O(ch.length) which is growing exponentially. It ends up being a complicated way of still taking O(n) time while creating a lot of intermediate strings. It isn't any faster than just creating the padding with a loop or `new Array(len).fill(ch).join('')` or `ch.repeat(len)`

Ajedi32 6y ago
Did you run benchmarks to validate those assumptions? The developers of left-pad did: https://github.com/left-pad/left-pad/blob/master/perf/perf.js https://github.com/left-pad/left-pad/blob/master/perf/perf.j... It's not overengineered if thousands of downstream projects are relying on it, some of which might see significant benefits from those performance optimizations.
- cogman10 6y ago
  Too bad that's a flawed benchmarking methodolgy. JITs are notoriously hard to correctly profile and the benchmark lib isn't even sort of doing the right thing. For example, it's missing warmup. The results aren't being consumed in a way that wouldn't optimize them away. The framework itself imposes a pretty large amount of overhead (moreso than I'd expect from leftpad). It is somewhat likely that what they are measuring isn't leftpad performance, but rather how fast the JIT ends up optimizing the benchmark code. I'd suggest watching this video https://vimeo.com/78900556 https://vimeo.com/78900556 It's about microprofiling the JVM, but the principles are the same for other JIT based languages (such as javascript).
  - Ajedi32 6y ago
    Yeah benchmarks can be much more difficult to get right than it might seem at first glance. Good thing they didn't try to write their own benchmarking code, otherwise they might have fallen into those traps you just mentioned. Luckily, they didn't, and instead pulled in the the `benchmark` library as a development dependency. The author of said library works on V8, and already considered all those problems and much, much, more[1]. [1]: https://mathiasbynens.be/notes/javascript-benchmarking https://mathiasbynens.be/notes/javascript-benchmarking
    - cogman10 6y ago
      You are making the assumption that the library doesn't have the flaws I mentioned. It does (You can go read the source yourself https://raw.githubusercontent.com/bestiejs/benchmark.js/2.1.2/benchmark.js https://raw.githubusercontent.com/bestiejs/benchmark.js/2.1.... ) There's no portion of the code that does warmups. There's no portion of code that "blackholes" the results to keep the JIT from optimizing away the code under benchmark. There is a lot of code though... so that's... good? You make the assumption that just because a lib is popular or widely used it is "correct" or "the best". When it comes to microbenchmarks, that's usually flawed. Very VERY few people actually get them right, benchmark.js is no exception. That, of course, doesn't mean that benchmark.js can't be useful. For macrobenchmarks it will be roughly right. However, for something as small as leftpad, it's almost certainly not the right way to measure performance.
      - Ajedi32 6y ago
        Okay, you win. I'm not going to read the entire source of that package just to make a point. Though I do find it strange that the author of that library would write an entire blog post on the topic and then not take his own advice in the implementation of the library he wrote.
        cogman10 6y ago
        Tell me, where in that blog post does he mention doing warm up cycles or avoiding having the JIT optimize away the method? (Hint, he doesn't mention that... so, no, he didn't actually miss his own advice.) The article is completely consumed with getting the timing of benchmarking right. Which, to be fair, is a place where microbenchmarks often go wrong. It, however, isn't the ONLY place they go wrong.
      - phpnode 6y ago
        > There's no portion of the code that does warmups. This isn't true - Benchmark.js will repeatedly rerun benchmarks until it gathers statistically meaningful results. > There's no portion of code that "blackholes" the results to keep the JIT from optimizing away the code under benchmark. True, and there's actually nothing benchmark.js can do to ensure that doesn't happen in the general case but when this does happen the results are usually pretty obvious - we'd see billions of ops/sec. Incidentally the left-pad benchmarks do not suffer from this issue.
- ghj 6y ago
  They failed at writing a correct O(n) left pad in their benchmark: https://github.com/left-pad/left-pad/blob/master/perf/O(n).js#L13 https://github.com/left-pad/left-pad/blob/master/perf/O(n).j... They are repeatedly appending a single character to the front of a string. This is actually O(n^2) so of course they are winning against it.
  - Ajedi32 6y ago
    That would depend on the underlying implementation of the string object, no? (If the string is implemented as a linked list it's O(n)) Anyway, it makes no practical difference in this case, since the one they labeled "O(n)" is the naive implementation that most people would write if they implemented left-pad themselves.
    - ghj 6y ago
      I highly doubt js engines would compile a string down to a linked list. But you're right they might compile it to a circular buffer or deque which can have O(1) prepends. Quick googling shows that this optimization might exist but only for firefox and only if you use "unshift": https://lannonbr.com/blog/2020-01-27-shift-optimizations https://lannonbr.com/blog/2020-01-27-shift-optimizations https://jandemooij.nl/blog/2017/12/06/some-spidermonkey-optimizations-in-firefox-quantum/ https://jandemooij.nl/blog/2017/12/06/some-spidermonkey-opti... But it's very unlikely that the jit can optimize `str = ch + str;`
      - cogman10 6y ago
        Depends on the form that `str = ch + str` takes inside the loop. But yeah, the way they wrote the code makes it less likely to work well. let padding = ''; for (let i = 0; i < len; ++i) padding += ch; return padding + str; The above would probably get caught by the JIT and would essentially be optimized to what `ch.repeat(len) + str;` would do.
    - layoutIfNeeded 6y ago
      String implemented as a linked list. You’re a webdev aren’t you?

by ghj 6y ago

Ajedi32 6y ago

Did you run benchmarks to validate those assumptions? The developers of left-pad did: https://github.com/left-pad/left-pad/blob/master/perf/perf.js https://github.com/left-pad/left-pad/blob/master/perf/perf.j... It's not overengineered if thousands of downstream projects are relying on it, some of which might see significant benefits from those performance optimizations.

cogman10 6y ago
Too bad that's a flawed benchmarking methodolgy. JITs are notoriously hard to correctly profile and the benchmark lib isn't even sort of doing the right thing. For example, it's missing warmup. The results aren't being consumed in a way that wouldn't optimize them away. The framework itself imposes a pretty large amount of overhead (moreso than I'd expect from leftpad). It is somewhat likely that what they are measuring isn't leftpad performance, but rather how fast the JIT ends up optimizing the benchmark code. I'd suggest watching this video https://vimeo.com/78900556 https://vimeo.com/78900556 It's about microprofiling the JVM, but the principles are the same for other JIT based languages (such as javascript).
- Ajedi32 6y ago
  Yeah benchmarks can be much more difficult to get right than it might seem at first glance. Good thing they didn't try to write their own benchmarking code, otherwise they might have fallen into those traps you just mentioned. Luckily, they didn't, and instead pulled in the the `benchmark` library as a development dependency. The author of said library works on V8, and already considered all those problems and much, much, more[1]. [1]: https://mathiasbynens.be/notes/javascript-benchmarking https://mathiasbynens.be/notes/javascript-benchmarking
  - cogman10 6y ago
    You are making the assumption that the library doesn't have the flaws I mentioned. It does (You can go read the source yourself https://raw.githubusercontent.com/bestiejs/benchmark.js/2.1.2/benchmark.js https://raw.githubusercontent.com/bestiejs/benchmark.js/2.1.... ) There's no portion of the code that does warmups. There's no portion of code that "blackholes" the results to keep the JIT from optimizing away the code under benchmark. There is a lot of code though... so that's... good? You make the assumption that just because a lib is popular or widely used it is "correct" or "the best". When it comes to microbenchmarks, that's usually flawed. Very VERY few people actually get them right, benchmark.js is no exception. That, of course, doesn't mean that benchmark.js can't be useful. For macrobenchmarks it will be roughly right. However, for something as small as leftpad, it's almost certainly not the right way to measure performance.
    - Ajedi32 6y ago
      Okay, you win. I'm not going to read the entire source of that package just to make a point. Though I do find it strange that the author of that library would write an entire blog post on the topic and then not take his own advice in the implementation of the library he wrote.
      - cogman10 6y ago
        Tell me, where in that blog post does he mention doing warm up cycles or avoiding having the JIT optimize away the method? (Hint, he doesn't mention that... so, no, he didn't actually miss his own advice.) The article is completely consumed with getting the timing of benchmarking right. Which, to be fair, is a place where microbenchmarks often go wrong. It, however, isn't the ONLY place they go wrong.
    - phpnode 6y ago
      > There's no portion of the code that does warmups. This isn't true - Benchmark.js will repeatedly rerun benchmarks until it gathers statistically meaningful results. > There's no portion of code that "blackholes" the results to keep the JIT from optimizing away the code under benchmark. True, and there's actually nothing benchmark.js can do to ensure that doesn't happen in the general case but when this does happen the results are usually pretty obvious - we'd see billions of ops/sec. Incidentally the left-pad benchmarks do not suffer from this issue.
ghj 6y ago
They failed at writing a correct O(n) left pad in their benchmark: https://github.com/left-pad/left-pad/blob/master/perf/O(n).js#L13 https://github.com/left-pad/left-pad/blob/master/perf/O(n).j... They are repeatedly appending a single character to the front of a string. This is actually O(n^2) so of course they are winning against it.
- Ajedi32 6y ago
  That would depend on the underlying implementation of the string object, no? (If the string is implemented as a linked list it's O(n)) Anyway, it makes no practical difference in this case, since the one they labeled "O(n)" is the naive implementation that most people would write if they implemented left-pad themselves.
  - ghj 6y ago
    I highly doubt js engines would compile a string down to a linked list. But you're right they might compile it to a circular buffer or deque which can have O(1) prepends. Quick googling shows that this optimization might exist but only for firefox and only if you use "unshift": https://lannonbr.com/blog/2020-01-27-shift-optimizations https://lannonbr.com/blog/2020-01-27-shift-optimizations https://jandemooij.nl/blog/2017/12/06/some-spidermonkey-optimizations-in-firefox-quantum/ https://jandemooij.nl/blog/2017/12/06/some-spidermonkey-opti... But it's very unlikely that the jit can optimize `str = ch + str;`
    - cogman10 6y ago
      Depends on the form that `str = ch + str` takes inside the loop. But yeah, the way they wrote the code makes it less likely to work well. let padding = ''; for (let i = 0; i < len; ++i) padding += ch; return padding + str; The above would probably get caught by the JIT and would essentially be optimized to what `ch.repeat(len) + str;` would do.
  - layoutIfNeeded 6y ago
    String implemented as a linked list. You’re a webdev aren’t you?