That is the issue I have with it: ‘an afternoon’ is already way too vague. Make it ‘5 minutes’ (left pad etc) then I think it works out.
var cache = [
'',
' ',
' ',
' ',
' ',
' ',
' ',
' ',
' ',
' '
];
function leftPad (str, len, ch) {
// convert `str` to a `string`
str = str + '';
// `len` is the `pad`'s length now
len = len - str.length;
// doesn't need to pad
if (len <= 0) return str;
// `ch` defaults to `' '`
if (!ch && ch !== 0) ch = ' ';
// convert `ch` to a `string` cuz it could be a number
ch = ch + '';
// cache common use cases
if (ch === ' ' && len < 10) return cache[len] + str;
// `pad` starts with an empty string
var pad = '';
// loop
while (true) {
// add `ch` to `pad` if `len` is odd
if (len & 1) pad += ch;
// divide `len` by 2, ditch the remainder
len >>= 1;
// "double" the `ch` so this operation count grows logarithmically on `len`
// each time `ch` is "doubled", the `len` would need to be "doubled" too
// similar to finding a value in binary search tree, hence O(log(n))
if (len) ch += ch;
// `len` is 0, exit the loop
else break;
}
// pad `str`!
return pad + str;
}I started with the problem of "I need a function that pads a string with a character out to some length". Coding it up took under 1 minute, easily under 5 minutes.
function leftPad (str, len, ch) {
const neededPadding = len - str.length;
if (neededPadding <= 0) {
return str;
}
return ch.repeat(neededPadding) + str;
}
The fact that the left-pad code has optimizations (which don't matter for the place I'm using it) and type-checks (which don't matter; my higher level unit tests would catch that mistake) is beside the point.
All of those properties make the code easier to reason about and test.
Being easier to reason about, and being a more exact abstraction for my needs, are both incredibly valuable properties.
I don’t have to care about how the underlying libraries work. I can treat them as a black box.
When I wrote haskell, the majority of the libraries did just work, and I didn't have to dig into their code to find bugs often.
When I wrote javascript, hundreds of the libraries I used did not just work. I usually had to care very much about their details because they were poorly implemented, full of bugs and incorrect abstractions, and often abandoned soon after.
I agree that there's benefits in reusing some well-socialized and well-implemented generic frameworks and abstractions. It's not worth using generic abstractions that are not well understood, buggy, and don't match your needs closely. In that case, write your own.
More generic is not always better. Above, I'm arguing that it's important for code to be easier to reason about. If a generic abstraction helps with that, cool, but it's not always going to be the case.
Any other scripting I do with Python. Any more complicated development it’s using a language with an ecosystem with adults - C# or Go.
Rob pike espoused "A little copying is better than a little dependency", and go refuses to add suitable abstractions to build generic reusable pieces.
Go has a strong culture of doing exactly the sort of thing I was talking about, and you were arguing against.
Almost everything I work with has bugs, so chances are I'm going to run into one. It's a lot easier for me to fix bugs when there are fewer layers and more of them are written by me. Of course, I can't write all the layers, but if they run on my service, I have to be prepared to fix them, or suffer from them being broken until a benevolent force fixes them for me. (Sometimes that happens, but usually not for the harder problems)
But I can maintain code that uses Entity Framework (or Dapper) much easier than I can maintain code based on a custom ORM that the “architect“ wrote.
I can count on one hand[0] the number of JS dependencies I've used in enterprise/large projects for extended periods of time where I've never needed to manually debug the library or read the source code. For enterprise software, sometimes the easiest solution is to directly hotpatch a vendored version of the dependency.
This is especially true with dependencies where bugs are fixed in major versions, but where upgrading and dealing with breaking changes would require significant code refactoring.
To drive the point home, I've been bitten by bugs in NPM itself.[1] Fixing that required reading through the source and manually swapping out one NPM's internal dependencies to a newer version.
And it doesn't matter if someone somewhere has had the same problem and posted it on the Internet unless I can find their answer online faster than I can fix the problem myself in my own library. Often this is not the case, filtering through issue trackers and trying to find the one blog post or comment that tells me how to solve the problem can be a big time sink.
[0]: Okay, maybe 2. But the point stands, it's not a rare or exceptional occurance.
Probably the worst was with a decently popular library someone had brought in, that tried to do a refactor from callbacks to async/await, without understanding at all how async/await worked. They'd leaked an async operation in the library code, so 'await'ing a specific function call in their API that returned a promise, didn't actually await everything the call was doing, ending up in a debugging nightmare. Of course their perfectly manicured suite of 8000 tests with 110% test coverage didn't catch it either, because the number of people who can write good quality tests is shockingly low, and library-writers aren't somehow magically ahead of the pack in that regard.
JS really feels like PHP did back when I was a newbie learning that shit. In other ecosystems, the 95th percentile devs seem to write all the libraries, so everyone comes here and posts repeatedly about how great dependencies are. In JS, it's the average dev writing all the libraries, and the average dev's code is enough to make my brain bleed.
I'm a big proponent of different advice for different ecosystems. If you're doing front-end JS, the pendulum has swung so far to one side that 'NIH syndrome' is treated like it's going to lead to the fourth reich, which makes 'chill out a bit on dependencies' pretty good advice if you're looking to get a leg up in the industry. But I'm sure there's other ecosystems where the same advice will just leave you with a tangled mess while your competitors leapfrog you in productivity with a good 3rd party dependency.
I'd say take any advice in threads like these with a grain of salt unless it's given in a bit of a narrower context. Taking some one liner about software engineering in general and applying it to your specific project is probably just a coin flip as to whether it's going to improve your code or not.
I've not profiled it, but I'm going to guess that now-a-days this will be faster than the current implementation on npm.
function leftPad (str, len, ch) {
str += '';
len = len - str.length;
if (len <= 0) return str;
if (!ch && ch !== 0) ch = ' ';
ch += '';
return ch.repeat(len) + str;
}
Static typing would actually fix this kind of coding error.
> Static typing would actually fix this kind of coding error.
That's not a coding error, that's addressing an oddity of JS coercion rules that a less experienced developer could easily have missed.
> if (!ch && ch !== 0) ch = ' '
That code says that if `ch` is falsey and not equal to 0, then set it to a space. The only arguable falsey value that should be excluded here is a literal `false`, but that's not a single character and is fairly ambiguous either way. I'd certainly fall on the side that a literal false should not be converted to `'false'` here.
> ch += '';
The next line converts to to a string by adding it to the empty string.
> return ch.repeat(len) + str;
So by the time it gets to this line we know ch is a string.
Static typing is great, but the bug you claim is there is not actually there.
It may specialize or inline, but that's a separate matter.
P.S. I think there's a bug here.
Step 1, inline repeat.
Step 2, remove the intermediate array allocation
Step 3, allocated a string array sized for the pad + str
Step 4, Use one of the many CPU instructions to repeatably copy the padding character and then the `str` into the same array of characters.
Nowadays there's a native padStart function and the left-pad package is deprecated as a result.
JITs only optimize hot code which means any benchmark without a warmup is going to measure cold + hot code time.
Further, JITs will optimize away unused results. They aren't using the leftpad results in any meaningful way.
What they are likely measuring is how long it takes for the JIT to optimize the benchmarking framework.
watch: https://vimeo.com/78900556 for how to microbenchmark a JITed language.
Luckily, they didn't, and instead pulled in the the `benchmark` library as a development dependency[1]. The author of said library works on V8, and already considered all those problems and much, much, more[2].
[1]: https://github.com/left-pad/left-pad/blob/master/perf/perf.j...
Sure, It's popular. It's also wrong.
Also I seem to remember that someone benchmarked the cached version and found it to be slower than the naive approach anyway. I could be mistaken there.
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)`
It's not overengineered if thousands of downstream projects are relying on it, some of which might see significant benefits from those performance optimizations.
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).
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].
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.
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.
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.
This is the "benchmark lib" that was mentioned in the very first sentece of the comment you replied to.
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.
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.
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;`
let padding = '';
for (let i = 0; i < len; ++i)
padding += ch;
return padding + str;
You’re a webdev aren’t you?
https://stackoverflow.com/questions/13865420/why-is-haskells...
And yeah, I would and do write leftpad myself it it's not in the stdlib. But if there is a large library full of similar (string) functions that I might need, I would include that library. Not a singular dependency for this type of function.
Numbers or ASCII-only-printing? OK that's a reasonable. Is there a desired overflow behavior?
Past that it becomes more an issue of where and why. The suddenly not-trivial example includes questions about fonts, layout, and multi-byte characters. Emoji, etc.
Incidentally, in pseudoscope:
Create a valid full-space pad string (termination / etc), then decrement back from the end of the source string and over-write the pad characters from the end to the start of the string, exiting either on no more pad characters or no more input.
A second algorithm might combine those two steps as one pass, fill the output buffer from back to front. Only for C style strings would this be an issue given the dynamic end point for the data structure.