#left-pad

If you’re a programmer, there’s a good chance you noticed the node.js left-pad fiasco of a few weeks back that temporarily broke most of the npm ecosystem.

This blog doesn’t have an opinion on any of that. However, in the ensuing kerfluffle, several people observed that left-pad appears to be quadratic, and that is definitely this blog’s concern.

If we look at the code, we see that the main loop looks like so:

while (++i < len) { str = ch + str; }

In most languages’ string implementations, this would be definitely quadratic — + copies the entire string (of size O(len)) on each iteration, and this loop runs O(len) times.

However, I happen to know that modern JS implementations have a whole pile of complex String optimizations, including rope-like data structures. And this is an evidence-driven blog, so I decided to take a deeper look. And what I found is fascinating and bizarre and I honestly can’t explain it yet.

The benchmarks

But let’s start with something easy. I ran a benchmark in rhino, which I judged to be the javascript implementation that I had easy access to least likely to have super-advanced string optimizations. We can clearly see the telltale quadratic curve:

But now let’s try something a bit more sophisticated, which also happens to be my primary browser: Chrome. Running a left-pad benchmark in Chrome yields the following result:

There’s bit of anomalous behavior, especially at small sizes, but it makes a compelling case for being linear out through the 1MB limit I ran the test over!

(I’m running Chrome Version 50.0.2661.57 beta (64-bit); your results may well vary with Chrome version!)

And in fact, the Chrome developer tools will let us see the rope structure that Chrome has used to make these concatenations efficient! If we leftpad('hi', 100000, 'x') in a Chrome console and then take a heap snapshot, we can see that the string is a “concatenated string” made up of a huge number of chunks linked together:

(The downside of this optimization, as you can also see from that screenshot, is that our 100kb string now consumes 4MB of RAM…)

Moving on, we can also try Safari, another modern browser with an incredibly-sophisticated Javascript engine. In Safari, we see this odd behavior:

It’s a bit hard to be sure, but the data appears to fit two linear fits, with a cutover somewhere around 350k. This pattern was reproducible across multiple experiments, but I don’t have an explanation.

I also decided to try node, since that is the actual runtime that NPM primarily targets, after all. node runs the same v8 engine as Chrome, so we’d expect similar behavior, but version skew, configuration, or who knows what could cause divergence. And in fact, we see:

Oddly, it also seems to exhibit two separate linear regimes!

At this point, I’m out of energy for what was meant to be a short post, but if anyone can follow-up and explain what’s happening, I’d be terribly curious.

In Conclusion

NPM should be doing this!

Here’s another tool

Extremism doesn't make the world a better place, and this has been proven every day. Similar *political* situation arose few days ago, when the fight of ego between a corporate software company and an opensource developer ended up to lifting all the npm hosted packages the developer had maintained.

Kik's side of story https://medium.com/@mproberts/a-discussion-about-the-breaking-of-the-internet-3d4d2a83aa4d#.d7llbp1nw

Azer's blog on his take to Liberate the modules *he was maintaining* https://medium.com/@azerbike/i-ve-just-liberated-my-modules-9045c06be67c#.euctwjsy3

NPM Blog on the Kik, Azer and left-pad issues http://blog.npmjs.org/post/141577284765/kik-left-pad-and-npm

Upon following the conversations revolving around the chaos, feels like had either of the parties taken a step back, the whole community wouldn't have to suffer the disgrace and downtime (2.5 hours as reported by the NPM blog).

Few cents: 1. You can't drag every corporate to being a Dick over a trademark claim that someone made which though seems to be a valid claim. If being corporate is so dick-y, the world wouldn't have this massive corporate boom. After all a startup is an SME, eventually heading towards being a corporate. 2. Why should an opensource developer act so childish and take down the modules he was maintaining, without thinking twice on the possible aftermath. 3. You put so much onto a product and being corporate isn't any lesser than being a developer maintaining a reputed opensource package/module. Each one has its own sorts of responsibility, liability and sufferings. 4. These days products get more momentum with their support towards opensource community. A corporate shouldn't always make trademark claims where it isn't mandatory and the risk of theft isn't very high.

All we can wish that this chaos puts forward a big lesson to both the believers and won't create any situation that makes the community suffer.

What do I feel: 1. Developer should neither have made the claims and nor the way he had reacted on each of the replies he had made. 2. Corporate could have easily appended other suffixes/prefixes to their official repo, and could have linked properly on their official developer page. Eventually, someone ends up searching a package only if he/she gets convinced from the developer page the product explains.

Some opinions that I followed and liked. Nadia - There is no "my" in opensource. https://medium.com/@nayafia/there-is-no-my-in-open-source-c3e5555390fa#.lfcmykc3z

some corporation invests in a brand

they found out that there is already someone using that brand which is obviously not good because the brand's worth is then shared between multiple parties

so they decide to take the name away, keeping the whole value to themselves, but obviously they ask first nicely hoping to get lucky, most of the times people give up their values if they are asked nicely and it's not very important for them personally

obviously in this case, Azer felt that he deserves as much right to the name as anyone else and i think we all agree that in situations like these there should be careful consideration who deserves what from the shared property (specifically the name on npm), so he responded clearly stating that he builds something for the common good, something open on that name and he doesn't care what the company does anywhere else, but on npm, there is something built on it and it should deserve the same respect as anyone else's work imho.

and this is where they fucking threatened him, which is not surprising, given they are more powerful and they have the law on their side, even if we all know it's a bad law. when they saw that Azer is unphased from their threats and gives (probably because of anger) a value of the name that's way more than what they would've wanted to pay.

so they just continue their original strategy of threatening people, but this time npm. npm given that it shares its core values with kik, instantly gives them what they want, and writes a bullshit PR email to Azer, and it's all legal, and all fine, and in a world where money talks it's not even offensive or anything.

Azer realizes that he misplaced his trust in npm and can not deal with this in any other way than cutting all ties between him an npm. he does have enough conscience to both explain what happened and make it clear, that he doesn't want to stop anyone from putting back up even his own code, it's just has to be someone else not him because he can not bare any more connection to npm.

tl;dr damage control! npm, not our fault and “This is not a legal dispute.” 

Talking about being in total denial. @IZS and NPM INC, please read Mike Roberts’, (Head of Messenger at Kik’s) post. It includes the email trail.

Here’s a teaser from Kik, “We don’t mean to be a dick about it, but it’s a registered Trademark in most countries around the world and if you actually release an open source project called kik, our trademark lawyers are going to be banging on your door and taking down your accounts and stuff like that — and we’d have no choice but to do all that because you have to enforce trademarks or you lose them.”

Earlier this week, many npm users suffered a disruption when a package that many projects depend on — directly or indirectly — was unpublished by its author, as part of a dispute over a package name. The event generated a lot of attention and raised many concerns, because of the scale of disruption, the circumstances that led to this dispute, and the actions npm, Inc. took in response.

Here’s an explanation of what happened.

I wonder how many lawyers had to proof and approve all of the words between what's above and that below. 

To Recap (tl;dr)

We dropped the ball in not protecting you from a disruption caused by unrestricted unpublishing. We’re addressing this with technical and policy changes.

npm’s well-established and documented dispute resolution policy was followed to the letter. This is not a legal dispute.

We’ll continue to do everything we can to reduce friction in the lives of JavaScript developers.

My thoughts (for better or worse): I get that the guy didn't know who or what 'kik' was/is. But also, I don't understand how he's so pissed about it. If someone said "Hey, we're <InsertMajorBrandNameHere>. It doesn't matter that you haven't heard of us; you're using our trademark and you can't do that" then everyone would be like: yeah dude you can't do that. Just because Kik is smaller, doesn't mean you can infringe because you want to. It's kind of oddly discriminating against smaller companies that are struggling for brand recognition. Is it a little mean to force an OSS guy to change the name of his package? Maybe. However, I'd say it's totally understandable and reasonable for a business to do so. Especially when they offered some compensation for his trouble.

Unpublishing everything because you're upset is petulant, childish behavior. There are innocent people consuming your package (and you know they are) that have suffered for it (regardless of their mistakes in process to be so dependent on you+npm hosting).