lots of time is spent in allocation in puffin-dev resolve-many for the top PyPI packages

[BurntSushi]

One thing i'm seeing is that we are spending a lot of time in allocation, around 16% for malloc and 11.5% for free of total runtime for the top 1K pypi packages:

That jumps to about 18% for malloc and 13% for free in the top 4K.

My hypothesis for this is that we are allocating oodles of tiny little objects everywhere. For example, Version has two Vecs in it and WheelFilename adds many more allocs with more indirection. There are probably other places with lots of tiny little objects.

There are a variety of different approaches one can use to attack this problem (if we consider it a problem at all):

• Try container types that use inline storage for small elements and fallback to the heap for bigger elements. I'm thinking about things like smallvec. This is also known as a "small string optimization" (SSO). This might be a good first thing to try since I'm guessing it's quite relevant. I imagine many of the Vecs and Strings in WheelFilename and Version, for example, are quite small.
• We could try different allocators. It looks like ruff uses mimalloc. My system is using glibc's allocator which is generally pretty fast. So I wouldn't expect an enormous gain here.
• We could try different allocation styles. For example, a bump allocator like bumpalo. This will likely require some refactoring of the code.
• We could try representational changes to our data types to make fewer allocations. For example, a Version could probably be represented as a Vec<u8> internally. This makes its representation more complex and usually will incur some kind of perf penalty when you try to use a Vesion. But it could speed up objection creation enough to make it a worthwhile trade.
• We could use some kind of string interning to exploit cross-package redundancy. It is very likely for example that the total number of unique version strings is far smaller than the total number of version strings. Similarly for other things such as package names. (Since some packages have a lot of releases.)

Anyway, this is just what I have off the top of my head. I'm actually not even certain that we want to solve this problem at all. But it is worth pointing out that some of the above remedies are much easier to try than others (smallvec should be quite easy to slot into the existing code and could significantly reduce allocs).

[charliermarsh]

Personal opinion is that I'd love to improve this and these ideas strike me as being in the right direction.

[konstin]

I'd love to try smallvec for release. We can also use u32 instead of usize in there

[charliermarsh]

We could also use an enum for release that captures the overwhelmingly common cases of 1, 2, or 3 segments.

[charliermarsh]

That might be strictly more work. I recall smallvec introduces some overhead since you need to check if an element is on the stack or the heap, but I guess an enum would have the same problem :)

[konstin]

Perfwise we shouldn't see the difference, but smallvec would be more ergonomic with less effort

[BurntSushi]

#399 gets a ~10% perf win by switching the global allocator. I did attempt a smallvec optimization experiment (as mentioned above) but couldn't observe any measurable win. I'm not 100% convinced that smallvec has no role to play and I'm sure there is more that can still be done here.

[charliermarsh]

@BurntSushi - Should we close this when merging #789 or is there more that's worth tracking here?

[BurntSushi]

Ah yeah that's a good point. Yeah, I don't think this specific issue still exists once #789 gets merged. (Or even before it to be honest. I think gratuitous allocation has been removed from the happy path for the most part already.)