investigating npm 3 perf

[samccone]

npm3 perf 🔍

TL;DR: We've got a network 📉 utilization regression that's at the root of the npm3 install performance. Here's the bird's 🐦 eye view:

How'd we get here? Read on…

---

After using npm3 for a while now, it is clear that there has been a slowdown in the time to install packages. Although a level of slowdown was to be expected given the new complexity around the flat tree and deduping dependencies, a 2 - 3x (and sometimes worse) slowdown across installs has become somewhat painful across the node community.

Instead of just yelling at the world, I decided to hop in and do some profiling work to better understand what is happening under the hood and observe (via profiling) the cause and perhaps just maybe some ideas to make it fast again. (yay OSS ✨)

Profiling NPM's JS Activity

To start this journey into answering the question of why something is slow, the first thing that I wanted to do was gather some numbers and some metrics. As anyone who has ever done or attempted to try to profile in node.js, you know that upon a basic google search you are immediately thrown into a dystopian world of outdated stackoverflow answers, gists that redirect to stackoverflow questions, that end in WIP, assorted comments buried deep within the threads on github, and enterprise debugging tools :( ….

However if you are persistent you eventually will stumble upon the two magical and useful things. First, the ability to get v8 logs out of node by passing the --prof flag which gives us a dandy v8 trace you can load in chrome://tracing… In our case this is not so useful.

The second thing that you will find is this repo node-inspector/v8-profiler which gives us exactly what we want… a CPU profile of our node process. A small patch then hooks in the instrumentation: npm 3 patch: (samccone@64cc5ca) npm 2 patch (kdzwinel@3978acc)

Profiling NPM's Network Activity

There was one major piece of the perf story that I was missing and that I knew was really important to get, on top of just the cpu profile, and that was the network activity. I had the hypothesis that one of the reasons why the new version of npm got slower was not due to a CPU bound issue #8826 (comment) but rather a change in how the requests to the npm registry were being made. To get a HAR dump of the process I got in touch with @kdzwinel who has been working on just this thing https://github.com/kdzwinel/betwixt . He was able to send over raw HAR dumps from both npm 2 and npm 3 🎉

For my test case I chose to use the package yo https://github.com/yeoman/yo as the example. For both npm2 and npm3 I made sure to install the package with no local npm cache, and also in forced http mode (due to a limitation around the current HAR dumping)

After gathering both of the results I was left with CPU profiles and the HAR dumps for each version of npm installing the same project under the same kind of constraints. It was now time to take a look at the numbers inside of chrome devtools profiler and a handy HAR viewer to try and prove my initial hypothesis about network perf vs cpu bound perf.

First let’s take a look at the CPU profile to see where time is being spent, and see if we can visually see a difference between what is going on in npm2 and npm3.

Results: NPM2 JS Activity

Results: NPM3 JS Activity

Well that is interesting, npm3 seems to be a much more sparse flame chart when installing the exact same package (yo), with large gaps in between brief periods of javascript execution. When we zoom in closer to get a look at exactly what is happening between the blank spots we get our first lead

It looks like each of the spikes in-between the blank space on the flame chart is when npm is handling the result from the registry. This is repeated over and over again until all of the packages have been resolved….

Now this pattern of downloading things, and moving on seems totally 100% reasonable, but still at this point I am not sure why there is a big difference between npm2 and npm3, why are there gaps in the timeline of npm3 and not npm2 what exactly is different?

At this point, I am pretty sure the answer to these questions is all within the HAR dump, so let's take a look.

Results: NPM2 Network Activity

Results: NPM3 Network Activity

Right off the bat you notice the difference in how the network requests are being made, instead of groups of parallel requests as in npm2, npm3 seems to be doing its requests in a serial fashion (thus taking around 4x as long), where it waits for previous requests to complete before continuing the chain of requests. I further confirmed this by zooming into the waterfall of requests in npm3 where you can pretty clearly see this exact stair stepping of dependant requests

On the initial request for yo everything lines up, we see a batch of requests for all of the root level dependency meta but after this point npm3 and npm2 diverge significantly

Further down in the chain of requests we start to see this pattern, where we make a request of a package's metadata and then make a request for the package, and then repeat the process for all of the packages dependencies. This approach of walking through the dependencies really starts to add up because it looks like every batch of requests is dependent of the previous finishing, thus if a single request takes some time (like rx in this case) it pushes the entire request start time of many other packages.

The end result here, is that we end up with a very sparse dependent network requests that for packages with many dependencies such as yo, is very slow for the end user.

---

Closing thoughts and ideas.. 💭

npm3 under the hood is operating in a totally new way, and there is a cost for all of the awesome new features such as a deduped tree and a flat tree structure, however there is a pretty significant cost 💰 when it comes to install time. Topically it seems like investigating ways to prebundle on the server and or batch requests to the registry would boost perf significantly, there is a fixed cost per network request that npm is making and just the volume of said requests adds up quickly. Figuring out a way to cut this number would boost performance significantly 🚤 .

The other big takeaway here was how hard it was to get these kind of perf metrics out of node, one day this will be fixed when nodejs/node#2546 lands…

Hopefully this was somewhat helpful and can help others who know the code way better than I look into the causes of these perf hits 🐎 📈 .

---

special thanks to @paulirish and @kdzwinel 💖

[addyosmani]

cc @othiym23. Thanks for digging into the performance regressions in such detail, @samccone. Super appreciated.

[paulirish]

While the above network details are from forced HTTP, I was able to get one chart of insight from npm3 on HTTPS (the default).

npm@3 install -g gulp with Microsoft Visual Round Trip Analyzer

Basically indicates we have ~122KB/sec average throughput over a 22s install time. And the lulls in network utilization match the above network traces.

Great writeup, @samccone !

[glenjamin]

This is some excellent analysis! It looks very similar to profiling results i've seen from a previous project. I'd built a crawler in Node which had to crawl a deeply nested tree structure somewhat similarly to npm, the code itself is unfortunately proprietary, but perhaps some of the approaches I took would be relevant here.

From the looks of the npm3 graph, there's a starvation in work while waiting for network responses, I'll have to poke around into the code to confirm, but to me this implies that npm is doing a depth-first traversal rather than a breadth-first

I think it should be possible to model the downloading/tree-walking process as a work queue with a certain amount of concurrency - I used https://github.com/glenjamin/async-pool-cue to achieve this previously.

The rough sketch looks something like this:

1. Create a queue for outgoing requests with a limited concurrency (say, 10 reqs at once)
2. Add each top-level dependency to this queue with priority 100
3. When a response is received for each of these, add to queue with priority 99
4. Repeat ad nauseum, new items receive priority of max - depth

The reason I believe this to be effective is that it prioritizes requests which are more likely to produce more requests, therefore keeping the queue topped up and avoiding work droughts.

It might also be beneficial to use https://www.npmjs.com/package/agentkeepalive on the "connection pool", and maintain a separate pool with a distinct concurrency limit for the tarball downloads.

[kdzwinel]

You can explore HAR files that Sam refers to here (give it a sec to load the timeline):

• npm 2.14.10
• npm 3.3.3

[othiym23]

Thank you for the thorough and detailed investigation, @samccone (and for the HTTPS followup, @paulirish – I'm glad to have so much of Google's help here). I agree that this information is still frustratingly hard to pull together, and I'm impressed by the determination that it took to get this far.

Background & context

One of the major goals @iarna and I (and @isaacs, who was the original impetus for the installer rewrite) had for npm@3 was to rework the installer to do a couple things:

1. break the install process into a set of discrete phases
2. have a way of capturing the "real" dependency tree, the "ideal" dependency tree, and the set of operations necessary to convert the one into the other

This is because it was very hard to follow the operation of the installer before, even if you were intimately familiar with the code (there are maybe a handful of people who can claim that familiarity, and I'm not sure I can count myself among them). Because much (if not most) of the functionality of the installer accreted organically over time, features like bundledDependencies, Git and local dependencies, npm dedupe, and npm shrinkwrap interacted in surprising (even confounding) ways, the process was often non-deterministic, and race conditions and edge cases were everywhere. So, the first purpose of npm@3 was to get ourselves to a place where the installer was behaving in a way we could understand, and to do so repeatably and reliably.

You'll note that "deduping by default" and "flattening the tree" aren't in the list above – @iarna noticed while she was doing exploratory work (a year ago – software is hard) that these would be easy features to add, and would greatly improve the usefulness of npm for both Windows and front-end developers. More significantly, they don't have a really major impact on performance – the bulk of the work is in resolving dependencies, and building up the two trees in a form such that they can be used to produce the final order of execution for the install. So the changes to performance characteristics seen here are not due to those changes, but the deeper redesign of the install process.

Everyone involved in this project knew that there was a certain amount of slowdown inherent in this work. There are two primary things that are inherently slower in npm@3 vs npm@2, they're related, and @samccone has pointed straight at one of them.

1. When checking the status of already-installed packages in node_modules, npm@2 and earlier only looked at the top level of dependencies in the tree. Because the new install algorithm is realizing the real tree, it ends up looking at much more of the dependency tree. Unless you were a really avid user of npm dedupe, this is probably going to result in a significant (and more or less unavoidable, without complex workarounds) performance hit.
2. Many of the operations that were previously done in a catch-as-catch-can order, where operations were triggered as soon as they were needed, are now serialized. This is a natural consequence of the multi-stage installer, and makes it much easier to understand what npm is doing. However, because there are a lot of possible ways for things to either get into the dependency tree (which can have significant knock-on effects), this serialization ends up slowing things down. The team cares very deeply about maintaining backwards compatibility whenever possible, and we're probably going to be chasing down and fixing unintended behavior regressions well into next year. Frequently, this causes us to have to do more network requests in even more of a staggered order.

One last consideration to keep in mind is that we're starting to see significant problems with installs failing due to network issues. This is something that happens regardless of the npm version, with only loose correlation to the underlying Node version. It's particularly bad for users on Windows, users with less robust broadband connections or cheap DSL routers, and users of containerization software, and while we haven't isolated the cause with total certainty, right now the finger seems to point at Node and npm's propensity to open many, many network connections at once and hammer out tremendous numbers of requests in short order.

One of the consequences of the small module philosophy is that the amount of work being requested at the network level has grown tremendously over the last couple of years, and it makes the caching process much more brittle. Also, it magnifies the effects of whatever latency may exist between the installing process and whatever registries or git hosts npm may be talking to.

Where we are now

So, with the above in mind, and looking at @samccone's results, I'm left in a bit of a quandary, mostly because I don't see obvious or simple fixes. We do have a number of ideas we're mulling over, and none of them are the sort of thing that we can do as a quick patch (both the existence of and the patch to the deepClone issue were anomalous in this respect). That said, I think it would be helpful to lay them all out here, so that everyone has a better idea of what we have in mind, so y'all can provide feedback or alternative suggestions:

Minimize round trip latency to the registry

According to @seldo, average request latency for simple metadata fetches to the registry average ~500ms at present. This means that even if npm's cache is just doing a freshness check (i.e. it will end up being logged as a 304 and the cached metadata & tarball will be used for an install), there's a 500ms wait for each package involved in the install. @soldair (with some help from @chrisdickinson) is looking into this, and @seldo seems confident that we can cut this number in half. I think that will have a pretty significant impact.

Cache more metadata

One of the trickiest pieces of the install process is that packages need to be unpacked and their package.json manifests checked for bundledDependencies, so the installer can figure out if the bundled versions of the dependencies are up to date (so they can be added to the list of packages to have their metadata fetched). There is alllll kinds of weird stuff inside published packages, and npm ignores this reality at the peril of producing strange, invalid installed trees. We can't handle this at present without fetching the package tarball and examining its contents. I hope it's clear how this imposes a certain amount of serialization on the process of realizing the dependency tree.

Another thing it needs to do is scan the package tarballs for npm-shrinkwrap.json files, because those, if present, will override any dependencies for that package. I could probably write a whole other response as long as this one about the complications presented by shrinkwrap files and how the community uses them, but for the purposes of this discussion, all I need to say is that this has to be pulled out of the tarball in sequence now, which is part of what serializes the process of metadata fetching.

Were we to add a serialized dump of what the bundledDependencies are, as well as the versions present in the cached tarball; and cache any extracted npm-shrinkwrap.json files, it would reduce the number of network requests we'd need to make for tarballs in the metadata fetching phase, as well as the number of tarballs we'd need to unpack. This would only affect users with warm npm caches, though, and so it wouldn't necessarily affect initial installs.

Push more of the tree-building work onto the registry

This one could have a very significant impact, but it's trickier than it looks (for reasons very similar to the complications mentioned above). We've long had hopes that SPDY or HTTP2 could, along with some reworking of the npm cache APIs, greatly reduce the number of round trips necessary to produce a finished install. That said, this implies a much more sophisticated API between the CLI and the registry than currently exists, and as such is going to take a while so that both the CLI and registry teams have the time and resources available to build this out.

Be smarter about how git is used

This is an important piece, and probably too large for this issue, but it's worth keeping in mind that the way that git-hosted dependencies are downloaded and cached is very different from packages hosted on a registry, and is largely done by the Git toolchain itself, over which npm has very little control.

Replace npm's download code

Although it may not look like it, a fair amount of attention has already been given to how npm downloads packages. The networking code is some of the most delicate and important in the CLI, because it has to work in an astonishing array of pretty adverse circumstances. It needs to work under Node all the way back to 0.8, it has to support a wide variety of proxies (and is still barely adequate in many Windows environments, given the lack of built-in NTLM or Kerberos support) and custom SSL configuration for same, deal with lots of fairly dicey corners of the internet (or, as @sebmck has recently noted, with the horrors of hotel or conference wifi). It needs to take advantage of HTTP Keep-Alive whenever possible. It needs to deal with connection resets and timeouts and other failures with some degree of resiliency.

Not to put too fine a point on it, Node's built-in HTTP client code is not nearly as high quality as its server implementation. request has come a long way, and npm has piggybacked on that to its great benefit, but it's still got rough spots. Also, Node-style concurrency when it comes to network access kind of breaks down under the level of traffic something like npm can generate, and simply limiting the number of requests you can originate at once (which @iarna has been experimenting with) isn't sufficient to handle all of these issues.

I think npm has reached a point where it needs its own download manager that is optimized for its peculiar and somewhat extreme needs. I have a really rough cut at a spec for what that thing might look like, but it's early days for that still, and I don't want to understate the difficulty or complexity of that work. This work needs to serve two masters: reducing the frequency with which installs fail due to excessive network traffic, and also ensuring that downloads do happen as quickly as possible once they've started.

What's next?

• @soldair is going to work on reducing the latency of normal requests to the primary registry network
• I'm going to keep working on refining the requirements and defining the API for the replacement for the networking layer (and then, probably, @zkat will be responsible for getting that integrated into the CLI, and / or building that package itself)
• @iarna is going to document the install algorithm in all its complicated glory. I feel that this is an essential tool to have when talking about the performance of the CLI, because it's really easy to suggest what looks like straightforward optimizations that come with disastrously unfortunate complications, due to the details of the install algorithm.
• The team will experiment with things like metadata caching and reordering when and where various steps in the algorithm things happen, so we can maybe reduce the size and frequency of the CPU stalls shown in the above.
• The CLI team is probably going to spend the rest of this year getting the npm test suite into better shape, largely for the purposes of getting Travis green and npm tested under Windows CI, but also with an eye towards adding unit tests, increasing meaningful test coverage, and making it easier to use as a diagnostic for performance testing.

How you can help

• More in-depth performance analysis like this. Visualizations and specific metrics (along with discussions of the use cases and workloads used to generate them) are extremely helpful in guiding the prioritization of performance work.
• It's likely that @iarna and I have overlooked opportunities to save work within the installer and in the interface between the installer and fetchPackageMetadata (which is where most, if not all, of the network requests in the installer go through). Also, it would be extremely useful to have more expertise in the operation of the installer. This isn't a simple request, because the installer is the most complex piece of npm, but if you wanted to spend some time getting to know it, your ability to make substantive improvements to the performance would increase dramatically.
• If somebody really wanted to help us out, baking an image of some with testing tools and scripts installed and configured would be amazing. Especially if that were done in such a way that it could be deployed to Windows as well as Linux and OS X, or into a virtualized or containerized setup. It feels like every time we touch the networking code and make the networking code better for one class of users, we degrade it for another. Having a way to meaningfully benchmark and QA changes to the network code would be hugely helpful.

Thanks again, everybody! I apologize for the length of this, but I want to tweet this around and get more eyes on it, and I've had a lot of these thoughts in my head for a while, but not written down in one place. I hope you find the detail more useful than distracting.

[lxe]

I've made a flamegraph of running an uncached, un-shrinkwrapped npm install on hapi from a cpuprofile collected using node-inspector.

I notice a lot of idle (waiting on network/io?), and a huge chunk of time taken by fs. I am unsure what that means.

it makes sense that the network reqs will not be parallelized ideally in an unshrinkwrapped project, but I'm curious to see how much other things like tarball unzipping, url.parse, gc, and other things affect the install.

SVG and cpuprofile source here:
https://gist.github.com/lxe/7b1d178f8df941e5f597

[devongovett]

I imagine this would require a significant amount of work, but one idea that would significantly improve performance, and reduce the number of requests npm needs to do when installing things, would be to do a lot more work on the server side instead of on the client. For example, when requesting a module, the server could bundle the module, and its entire dependency tree into a single tarball. This way, the npm client would only need to request the modules at the root level, and would get the rest of the tree for free. Going a step further, when requesting multiple modules, the requests could be batched so that only a single tarball of the entire dependency tree (pre-deduped by the server) could be downloaded.

Doing this on the server side instead of on the client has several benefits. It would be faster (since the data is local to the server), and require fewer HTTP requests for one. But for another, it would be much easier to add future optimizations on top of. For example, the npm server could pre-render common install trees for popular modules into static tarballs that could be hosted on a CDN, requiring no work to bundle each time they are installed.

[pthrasher]

@devongovett The issue with this approach is that modules allow for version ranges. Multiple modules may ask for the same dependency. One might ask for "4.3.1" exactly, and another might ask for ">= 4.0.0" -- In this case, npm.com can't know which to provide. The only other way would be to ask npm.com to fulfill the entire dependency tree for a whole project. Further complicating this, npm tries to do the right thing in the case that you already have some but not all of the required packages installed locally.

[devongovett]

The client would receive tarballs, each containing a root dependency and all sub-dependencies. Then it would merge the trees. It could receive multiple copies of the same module (different versions, or the same version), due to shared dependencies, but it could dedup them on the client side while merging the trees. While this might seem like a waste, my guess is that it would be faster to download a few extra bytes (most modules aren't that large) than make a million http requests from the client in series, especially if some of the popular modules were pre-rendered and cached on a CDN. For ranges, the server would bundle the latest version matching that range in the tarball (the same as if you ran npm install module in an empty directory, and then tar node_modules).

If batching were supported, the deduping could happen on the server side (npm install all the modules, then tar node_modules). It could be smart and send a list of already installed modules to the server in the request or something too...

This is just an idea at this point. Would require further experimentation to determine actual viability.

[rektide]

The network usage graphs point to a case where a number of TCP connections are fighting among one another. Rather than fundamentally rework the sending strategy/revise downloading, the new HTTP spec has a number of new techniques to allow for efficient parallel transfers to occur on a single TCP connections. Simply switching to HTTP2 is a clear, very low coupling (no need to restructure how npm works) way to improve things in radical way that ought get a lot of progress, and adding some basic prioritization to that is a simple refinement that should be investigated well before any restructuring work is attempted, to get a baseline of what http2 is capable of doing on a widely-parallel problem.

[othiym23]

"Simply switching to HTTP 2" is not something that can be done right now:

1. HTTP 2 is not supported by Node's core APIs.
2. I'm not aware of a pure JS HTTP 2 client that is known to work with versions of Node < 0.12.
3. npm's registry and content-delivery network will need significant work to support HTTP 2.

HTTP 2 offers a lot of possibilities to improve network performance and download reliability, but it's not a simple, drop-in change, nor does it address the architectural serialization issues I discussed in my response. It does bring with it a whole host of interoperability challenges and opportunities for new sources of fragility and regressions. It's the future, but it's going to take some sustained effort to get there.