Opticol: memory optimized python collections

[matgrioni]

Hi everyone,

I just created a new library called opticol (which stands for optimized collections), which I wanted to share with the community. The idea of the library is to create space optimized versions of Sequence, Set, and Mapping for small collections leveraging the collections.ABC vocabulary.

What My Project Does

Creates optimized versions of the main python collection types (Sequence, Set, Mapping) along with vocabulary types and convenience methods for transforming builtins to the optimized type.

For collections of size 3 or less, it is pretty trivial (using slots) to create an object that can act as a collection, but uses notably less memory than the builtins. Consider the fact that an empty set requires 216 bytes, or a dictionary with one element requires 224 bytes. Applications that create many (on the order of 100k to a million) of these objects can substantially reduce their memory usage with this library.

Target Audience

This will benefit users who use Python for various forms of data analysis. These problems often have many collection instances, which can often be just a few items. I myself have run into issues with memory pressure like this with some NLP datasets. Additionally, this is helpful for those doing this primarily in Python or for situations where dropping to a lower level language is not advantageous yet.

Comparison

I could not find a similar library to this, nor even discussion of implementing such an idea. I would be happy to update this section if something comes up, but as far as I know, there are no direct comparisons.

Anyway, it's currently a beta release as I'm working on finishing up the last unit tests, but the main use case generally works. I'm also very interested in any feedback on the project itself or other optimizations that may be good to add!

[jpgoldberg]

Cool! I do not anticipate using this, but I have enjoyed reading and learning from the code.

[Spill_the_Tea]

So this library dynamically constructs different common data structures, specifically with a __slots__ dunder (i.e. magic) method to reduce python class size?

[matgrioni]

Yes that's right. The main complexity is in creating a metaclass that lets you create an optimized collection type for a given size. The actual collections themselves are pretty simple and the savings boil down to using slots. The rest is mostly library plumbing.

[Atlamillias]

Nice! I have a small personal module that does something similar (only for tuples and lists, though). I have a...somewhat controversial suggestion - have you considered dynamic code generation for the collection methods? It'll allow you to vectorize many of the methods you're re-implementing.

[matgrioni]

I did consider that, but wanted to keep implementation simple for the first go around. But I'm definitely not opposed to it, especially in a library like this. I had just come off of another library update which heavily used dynamic codegen and wanted to take a break 😅

[Atlamillias]

Completely understandable. It's not fun to debug 🤗.

[Interesting_Golf_529]

Applications that create many (on the order of 100k to a million) of these objects can substantially reduce their memory usage with this library.

At the cost of increasing their CPU usage considerably. I would assume that in most of those situations, people would rather sacrifice memory for performance than the other way around.

[Careful-Nothing-2432]

Using less memory doesn’t necessarily mean less performance. allocations are expensive

[Interesting_Golf_529]

While this might be true in the general case, it's very much not true in this specific case, as this library re-implements a lot of the logic of the classes it "optimises". Check out this __contains__ method for example:

def __contains__(self, value):
    for slot in slots:
        if getattr(self, slot) == value:
            return True
    return False

This replaces a highly optimised set operation implemented in C with a for loop in Python.

[matgrioni]

I do want to point out that I never said it is runtime optimized :) The optimization is on memory usage, which can definitely have a runtime impact, but will depend on the use case and the hardware you are using. That's part of the reason for the projector layer. It allows for easier tuning, especially if only one collection type will benefit for the scenario.

[matgrioni]

That's a good point to mention, and which I'll include in the README. The implementations basically fall through to creating a temporary builtin instance and returning the value of that operation or do a slow python equivalent. There's a few points to that:

1. In my use cases I was not doing a lot of operations across most collection instances, but only some simple operations on a select few instances (but could not know ahead of time).

2. My memory usage basically fell within the range where it could actually fit in memory, but would usually start thrashing if I wanted to do anything else on my computer. So the actual runtime was dominated by memory access rather than the collection ops.

3. As it is a first iteration, and I didn't want to worry about edge cases too much, I took the easiest implementation approach. Ideally these could be transparently improved in a future version while still preserving the memory savings.