Hacker News Reader

Comment by ghj | Hacker News Reader

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.

View on HN

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