Hacker News Reader

Comment by ghj | Hacker News Reader

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)`

View on HN

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.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.

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

It's about microprofiling the JVM, but the principles are the same for other JIT based languages (such as javascript).

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

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.... )

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.

> 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.

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.

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.

> 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].

This is the "benchmark lib" that was mentioned in the very first sentece of the comment you replied to.

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).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.

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.

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://jandemooij.nl/blog/2017/12/06/some-spidermonkey-opti...

But it's very unlikely that the jit can optimize `str = ch + str;`

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.

String implemented as a linked list.

You’re a webdev aren’t you?

Well, Haskell did it...

https://stackoverflow.com/questions/13865420/why-is-haskells...

Haskell's default String implementation is a linked list; no need for the snark

Reply on news.ycombinator.com