the TL;DR is that .NET objects actually have a fair bit of metadata on the heap, which takes up space if the object's fields are small. if the object is mostly just a wrapper around two other object references, then you end up with 72 bytes allocated just for runtime metadata. in my case, by the time I counted other fields, it's 148 bytes per object. by changing how that object is represented (in this case storing all the elements of a range rather than the range description itself) it's smaller
checking whether an element is in a list of ranges took a long time because you needed to execute a lambda for all entries until you found a matching one, so worst case O(n), and the lambda itself required a few calls (and pointer dereferences internally).
the expanded variant allowed the items in the range to packed into unsigned integers, which could be placed into a HashSet instead, which has O(1) complexity for lookups, making it ~7x faster.
@gsuberland I believe Python takes 24 bytes per element in a list (AFAIK they're always references).
Probably overall well motivated from an ergonomics perspective but it kills cache locality. Often worth using numpy arrays even for things that have nothing to do with math.
Add comment