6 ms·

Algorithmic Complexity of Left-Pad (2016)

68 points by pcr910303 5y ago

venzlombardo 5y ago
This post is off-topic as this is Covid News, not Hacker News. covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid
keville 5y ago
(Circa 2016)
- jwlake 5y ago
  where to i submit the issue to have it reposted to substack?
kccqzy 5y ago
The fact that the Safari result appears to have two linear fits doesn't surprise me at all. Apple has a history of implementing multiple concrete classes for different sizes for the same abstract class. It has been known that NSArray and CFArray will switch the underlying data structure once it grows past a certain size: https://ridiculousfish.com/blog/posts/array.html https://ridiculousfish.com/blog/posts/array.html Now I'm not saying this NSArray trick was what happened here: it clearly is not because otherwise we'd see a quadratic curve followed by a linear curve. I'm just saying the data structure seems to have changed at a certain size cutoff.
jonathrg 5y ago
It had been optimized (and deprecated) since then. See https://github.com/left-pad/left-pad/blob/master/index.js https://github.com/left-pad/left-pad/blob/master/index.js
- deleted 5y ago
  [deleted]
- ghj 5y ago
  I've commented about this before, but their supposedly optimized implementation is still garbage: https://news.ycombinator.com/item?id=24125312 https://news.ycombinator.com/item?id=24125312 There's no reason to build the repeats up by doubling since the string concatenation of two same string is still linear time.
throwanem 5y ago
An optimized implementation (as "padStart") is in the standard library now: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/String/padStart https://developer.mozilla.org/en-US/docs/Web/JavaScript/Refe...
- pwdisswordfish8 5y ago
  The C-influenced nomenclature is not needed here. By the nature of what you're referring to, it is not a library. "In the standard" will do.
  - bqa65 5y ago
    Er, C did not invent libraries by any measure whatsoever, and is completely appropriate to call a function available to code without imports “in the standard library”. It is a library function. You did not write it. Simple as that. This is one of the more unnecessary pedantries I’ve ever seen, and that’s saying something on HN.
    - skrtskrt 5y ago
      I always assumed just from how people used the terms that available without imports = “core language” and available via import without installing external packages = “standard library”
      - throwanem 5y ago
        That may indeed be a more useful distinction to draw here. In it, Node could be said to provide a "standard library" (although not actually standardized, and I'm not sure how much it overlaps with eg Deno), while padStart and such would be core language features inasmuch as a compliant JS implementation is guaranteed to include them. edit: It is not, however, an accurate distinction. https://news.ycombinator.com/item?id=28021135 https://news.ycombinator.com/item?id=28021135
        5y ago
brundolf 5y ago
> But the principle remains, that it was actually completely impossible for us to analyze left-pad’s performance without a deep understanding of the specific underlying Javascript VM we cared about (or, in my case, resorting to brute experiment!). And this is why we benchmark before optimizing
iamcreasy 5y ago
I am wondering if the graph that shows Safari performance is actually quadratic. I am referring to the the 2nd linear segment. On that graph, 400,000 length required 2500 in time. If it's quadratic, 800,000 would require 10,000 in time. If you imagine the plot goes all the way to 800,000 - it's not hard to see that the line/curve hitting at 10,000. Thoughts?
- lilyball 5y ago
  You're cherry-picking your data. If you pick any two points on a line, you can build a quadratic curve that meets those points, but doesn't match the rest of the line. Not to mention that in this case while the line is somewhat close to 2.5k, 400,000 actually has a plotted point at about 3k.
  - iamcreasy 5y ago
    Lets try a different one then. 400,000 needs 2800 unit of time. If it's quadratic 600,000 would need 2800 * 1.5^2 = 6300. On the plot 600,000 takes about ~6300 unit of time. I think the line is drawn incorrectly. You can always fit a straight line into a curve if you zoom in enough which is what I think is happening here. I have not tried it myself but I strongly suspect that if you try to fit a linear and quadratic regression line in that part of dataset - the quadratic line would have better fit(coefficient of determination) compared to linear regression line.
    - Delk 5y ago
      Would that quadratic formula generally work if you picked any two random points from the graph instead? Anyway, the graph doesn't even try to suggest the performance behaviour shows a single linear relationship. The post (and the graph) explicitly says there seem two be two different linear segments. It's true that a single linear relationship would be a wrong model, but does that mean quadratic is right either? I might be completely off but I wonder if the relationship could be generally linear but with different coefficients before and after the cutover point due to the data becoming larger than fits in the cache at once, or something.
deleted 5y ago
[deleted]
8bitsrule 5y ago
After pre-creating a pad-string constant of sufficient length, no loop is needed. For each target$, calculate how long the needed pad is, grab that many characters, and prepend.

68 points by pcr910303 5y ago

This post is off-topic as this is Covid News, not Hacker News. covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid covid

keville 5y ago

(Circa 2016)

jwlake 5y ago
where to i submit the issue to have it reposted to substack?

kccqzy 5y ago

The fact that the Safari result appears to have two linear fits doesn't surprise me at all. Apple has a history of implementing multiple concrete classes for different sizes for the same abstract class. It has been known that NSArray and CFArray will switch the underlying data structure once it grows past a certain size: https://ridiculousfish.com/blog/posts/array.html https://ridiculousfish.com/blog/posts/array.html Now I'm not saying this NSArray trick was what happened here: it clearly is not because otherwise we'd see a quadratic curve followed by a linear curve. I'm just saying the data structure seems to have changed at a certain size cutoff.

jonathrg 5y ago

It had been optimized (and deprecated) since then. See https://github.com/left-pad/left-pad/blob/master/index.js https://github.com/left-pad/left-pad/blob/master/index.js

deleted 5y ago
[deleted]
ghj 5y ago
I've commented about this before, but their supposedly optimized implementation is still garbage: https://news.ycombinator.com/item?id=24125312 https://news.ycombinator.com/item?id=24125312 There's no reason to build the repeats up by doubling since the string concatenation of two same string is still linear time.

throwanem 5y ago

An optimized implementation (as "padStart") is in the standard library now: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/String/padStart https://developer.mozilla.org/en-US/docs/Web/JavaScript/Refe...

pwdisswordfish8 5y ago
The C-influenced nomenclature is not needed here. By the nature of what you're referring to, it is not a library. "In the standard" will do.
- bqa65 5y ago
  Er, C did not invent libraries by any measure whatsoever, and is completely appropriate to call a function available to code without imports “in the standard library”. It is a library function. You did not write it. Simple as that. This is one of the more unnecessary pedantries I’ve ever seen, and that’s saying something on HN.
  - skrtskrt 5y ago
    I always assumed just from how people used the terms that available without imports = “core language” and available via import without installing external packages = “standard library”
    - throwanem 5y ago
      That may indeed be a more useful distinction to draw here. In it, Node could be said to provide a "standard library" (although not actually standardized, and I'm not sure how much it overlaps with eg Deno), while padStart and such would be core language features inasmuch as a compliant JS implementation is guaranteed to include them. edit: It is not, however, an accurate distinction. https://news.ycombinator.com/item?id=28021135 https://news.ycombinator.com/item?id=28021135
      - 5y ago

brundolf 5y ago

> But the principle remains, that it was actually completely impossible for us to analyze left-pad’s performance without a deep understanding of the specific underlying Javascript VM we cared about (or, in my case, resorting to brute experiment!). And this is why we benchmark before optimizing

iamcreasy 5y ago

I am wondering if the graph that shows Safari performance is actually quadratic. I am referring to the the 2nd linear segment. On that graph, 400,000 length required 2500 in time. If it's quadratic, 800,000 would require 10,000 in time. If you imagine the plot goes all the way to 800,000 - it's not hard to see that the line/curve hitting at 10,000. Thoughts?

lilyball 5y ago
You're cherry-picking your data. If you pick any two points on a line, you can build a quadratic curve that meets those points, but doesn't match the rest of the line. Not to mention that in this case while the line is somewhat close to 2.5k, 400,000 actually has a plotted point at about 3k.
- iamcreasy 5y ago
  Lets try a different one then. 400,000 needs 2800 unit of time. If it's quadratic 600,000 would need 2800 * 1.5^2 = 6300. On the plot 600,000 takes about ~6300 unit of time. I think the line is drawn incorrectly. You can always fit a straight line into a curve if you zoom in enough which is what I think is happening here. I have not tried it myself but I strongly suspect that if you try to fit a linear and quadratic regression line in that part of dataset - the quadratic line would have better fit(coefficient of determination) compared to linear regression line.
  - Delk 5y ago
    Would that quadratic formula generally work if you picked any two random points from the graph instead? Anyway, the graph doesn't even try to suggest the performance behaviour shows a single linear relationship. The post (and the graph) explicitly says there seem two be two different linear segments. It's true that a single linear relationship would be a wrong model, but does that mean quadratic is right either? I might be completely off but I wonder if the relationship could be generally linear but with different coefficients before and after the cutover point due to the data becoming larger than fits in the cache at once, or something.

deleted 5y ago

[deleted]

8bitsrule 5y ago

After pre-creating a pad-string constant of sufficient length, no loop is needed. For each target$, calculate how long the needed pad is, grab that many characters, and prepend.