5 ms·

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

• 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?
    • imtringued 6y ago
      Well, Haskell did it... https://stackoverflow.com/questions/13865420/why-is-haskells-default-string-implementation-a-linked-list-of-chars https://stackoverflow.com/questions/13865420/why-is-haskells...
    • Domenic_S 6y ago
      Haskell's default String implementation is a linked list; no need for the snark