13 ms·
It's a little surprising that this works at all, since the partitioning step in the radix sort is itself the same kind of sharding operation. But I guess that's
by zahlman 2y ago
It's a little surprising that this works at all, since the partitioning step in the radix sort is itself the same kind of sharding operation. But I guess that's because it allows for working on smaller pieces at a time that fit in whatever cache they need to.
> Python can't really reserve space for lists, but pretend `reserve` did that anyway.
FWIW, you can pre-fill a list with e.g. `None` values, and then replacing those values won't cause resizes or relocations (of the list's memory - the elements are still indirected). But of course you'd then need to keep track of the count of "real" elements yourself.
But of course, tricks like this are going to be counterproductive in Python anyway, because of all the indirection inherent in the system. They'll also get worse if you actually do have objects (unless perhaps they're statically, constantly sized, and in a language that can avoid indirection in that case) with a "group ID" attribute, rather than integers to which you can apply some hash function. Some test results, trying to approximate the Rust code in Python but with such objects:
https://gist.github.com/zahlman/c1d2e98eac57cbb853ce2af515fecc23 https://gist.github.com/zahlman/c1d2e98eac57cbb853ce2af515fe...
And as I expected, the results on my (admittedly underpowered) machine are terrible (output is time in seconds):
$ ./shard.py
Naive: 1.1765959519980242
Presized: 2.254509582002356
Library sort / groupby: 6.990680840001005
Simple radixing first: 3.571575194997422
It's important to understand the domain. For Pythonistas, simple really is better than complex. And identifying the bottlenecks and moving them to a faster language is also important (Numpy isn't successful by accident). The naive result here is still, if I'm understanding the graphs right, dozens of times worse than what any of the Rust code achieves.
(Edit: merely "several" times worse. I forgot that I told `timeit` to run 10 iterations over the same input, so each test processes ~10M elements.)
- purplesyringa 2y ago> It's a little surprising that this works at all, since the partitioning step in the radix sort is itself the same kind of sharding operation. The key property here is the number of groups. When sharding data to n groups, only n locations have to be stored in cache -- the tails of the groups. In my radix sort implementation, this is just 256 locations, which works well with cache.