A memory-optimized wrapper for Python sets likely to be empty.
Project description
nanoset.py
A memory-optimized wrapper for Python sets likely to be empty.
⏱️ TL;DR
Save up to 85% of the memory used by empty set
instances in your code with
a single line of code:
from nanoset import PicoSet as set
🚩 Table of Contents
🗺️ Overview
🐏 About Python memory usage
Python is a great programming language (fight me), but sometimes you start
questioning why it does things in certain ways. Since Python 2.3, the standard
library provides the set
collection, which is a specialized container for membership testing. On the
contrary to the ubiquitous list
collection, set
is not ordered (or, more accurately, does not let you access
the order it stores the elements in). The other feature of set
is that just
like its mathematical counterpart, it does not allow duplicates, which is very
useful for some algorithms. However, sets are memory-expensive:
>>> import sys
>>> sys.getsizeof(list())
56
>>> sys.getsizeof(set())
216
An empty set takes more than three times the memory of an empty list! For some
data structures or objects with a lot of set
attributes, they can quickly
cause a very large part of the memory to be used for nothing. This is even more
sad when you are used to Rust, where most
collections allocate lazily.
This is where nanoset
comes to the rescue:
>>> import nanoset
>>> sys.getsizeof(nanoset.NanoSet())
48
>>> sys.getsizeof(nanoset.PicoSet())
32
Actually, that's a lie, but keep reading.
💡 Simple example usecase
Let's imagine we are building an ordered graph data structure, where we may want to store taxonomic data, or any other kind of hierarchy. We can simply define the graphs and its nodes with the two following classes:
class Graph:
root: Node
nodes: Dict[str, Node]
class Node:
neighbors: Set[node]
This makes adding an edge and querying for an edge existence between two nodes
an O(1)
operation, and iterating over all the nodes an O(n)
operation, which
is mot likely what we want here. We use set
and not list
because we want to
avoid storing an edge in duplicate, which is a sensible choice. But now let's
look at the statistics
of the NCBITaxon project, the
database for Organismal Classification developed by the US National Center for
Biotechnology Information:
Metrics
Number of classes*: 1595237
Number of individuals: 0
Number of properties: 0
Classes without definition: 1595237
Classes without label: 0
Average number of children: 12
Classes with a single child: 40319
Maximum number of children: 41761
Classes with more than 25 children: 0
Classes with more than 1 parent: 0
Maximum depth: 38
Number of leaves**: 1130671
According to these, we are going to have 1,130,671 leaves for a total of 1,595,237 nodes, which means 70.8% of empty sets. Now you may think:
Ok, I got this. But in this case, I just need a special case for leaves, where instead of storing an empty set of
neighbors
, I store a reference toNone
when that set would be empty. I can then replace that reference with an actual set only when I want to add new edges from that node. Problem solved!
Well, glad we are on the same level: this is what nanoset
does for you!
🔨 Implementation
Actually, it's not magic at all. Just imagine a class NanoSet
that works as
a proxy
to an actual Python set
it wraps, but which is only allocated when some data
actually needs to be stored:
class NanoSet(collections.abc.Set):
def __init__(self, iterable=None):
self.inner = None if iterable is None else set(iterable)
def add(self, element):
if self.inner is None:
self.inner = set()
self.inner.add(element)
# ... the rest of the `set` API ...
That's about it! However, doing it like so in Python would not be super
efficient, as the resulting object would be 48 bytes. Using
slots, this can be
reduced to 40 bytes, which is on par to what we get with NanoSet
.
Note that these values are only when the inner set is empty! When actually
allocating the set to store our values, we allocate an additional 232 bytes
of data. This means that using NanoSet
creates an overhead, since a
non-empty set will now weigh 264 bytes (248 bytes for PicoSet
).
Well, I was way better off with my approach of storing
Optional[Set]
everywhere then, I don't want to pay any additional cost for nonempty sets!
Sure. But that would mean changing your whole code. And actually, you may not
gain that much memory from doing that compared to using nanoset
, since the
only time the wrapper performs badly is when you have a load factor of more than
90%. Furthermore, just to give you some perspective, sys.getsizeof(1)
is
28 bytes.
By the way, you didn't mention
PicoSet
. How did you manage to get that down to 32 bytes, when a slotted Python object can't be less that 40 bytes?
Easy: PicoSet
is basically NanoSet
, but without an implementation of the
Garbage Collector protocol.
This saves us 8 bytes of object memory, but comes with a drawback: the
garbage collector cannot see the set allocated inside the PicoSet
. This
does not change anything for execution, but debugging with a memory profiler
will be harder. Here is an example where we allocate 1,000,000 singletons
first with NanoSet
, then with PicoSet
, using
guppy3
to check the heap:
>>> l = [nanoset.NanoSet({x}) for x in range(1000000)]
>>> guppy.hpy().heap()
Partition of a set of 3036763 objects. Total size = 304996526 bytes.
Index Count % Size % Cumulative % Kind (class / dict of class)
0 1000044 33 216105248 71 216105248 71 set
1 1000000 33 48000000 16 264105248 87 nanoset.NanoSet
...
3 113 0 8716880 3 300851404 99 list
...
>>> l = [nanoset.PicoSet({x}) for x in range(1000000)]
>>> guppy.hpy().heap()
Partition of a set of 1036905 objects. Total size = 44998965 bytes.
Index Count % Size % Cumulative % Kind (class / dict of class)
0 1000000 96 32000000 71 32000000 71 nanoset.PicoSet
1 96 0 8712752 24 32712752 89 list
...
On the second run, we have about the same order of allocated memory, saving
16 MB (16 bytes saved by switching from NanoSet
to PicoSet
times
1,000,000 instances). However, the garbage collector has no idea where
some of the memory is, because PicoSet
hides the sets it allocates (this is
fine: it will be deallocated along with the PicoSet
).
As such, I'd advise avoiding using PicoSet
when debugging, which can be done
easily with Python's __debug__
flag:
if __debug__:
from nanoset import NanoSet as set
else:
from nanoset import PicoSet as set
This will cause PicoSet
to be used instead of NanoSet
when running Python
with the -O
flag.
📈 Statistics
Okay, so let's do some maths. With S = 232
the size of an allocated set,
s
the size of the wrapper (48
for NanoSet
, 32
for PicoSet
), the
x
percentage of nonempty sets in our data structure, the relative size
of our sets is:
- if we're using
set
: S * x / (S * x) = 100% (we use that as a reference) - if we're using
nanoset
: ((S + s) * x + s * (100 - x)) / (S * x)
This gives us the following graph, which shows how much memory you can save depending of the ratio of empty sets you have at runtime:
If we get back to our NCBITaxon example, we have a total of 1,595,237 nodes
and 1,130,671 leaves, which means that by using sets we are allocating
1,595,237 * 232 = 328.6 MiB of memory simply for set
after the whole
taxonomy is loaded. If we use NanoSet
however, we
can reduce this to 168.7 MiB, or even to 144.4 MiB with PicoSet
!
We just saved about 45% memory just by using NanoSet
in place of set
.
🔧 Installing
This module is implemented in Rust, but native Python wheels are compiled for the following platforms:
- Windows x86-64: CPython 3.5, 3.6, 3.7, 3.8
- Linux x86-64: CPython 3.5, 3.6, 3.7, 3.8
- OSX x86-64: CPython 3.5, 3.6, 3.7, 3.8
If you platform is not among these, you will need a
working Rust nightly
toolchain
as well as the setuptools-rust
library installed to build the extension module.
Then, simply install with pip
:
$ pip install --user nanoset
📖 API Reference
Well, this is a comprehensive wrapper for set
, so you can just read the
standard library documentation.
Except for some very particular edge-cases, NanoSet
and PicoSet
both pass the
set
test suite
of CPython.
There are however things you can't do:
- Subclassing a
PicoSet
or aNanoSet
. - Weakrefing a
PicoSet
or aNanoSet
. - Checking for membership in a plain
set
orfrozenset
with implicit conversion tofrozenset
. - Creating a
dict
from aPicoSet
or aNanoSet
without rehashing keys.
📜 License
This library is provided under the open-source MIT license.
Project details
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distribution
Built Distributions
File details
Details for the file nanoset-0.2.1.tar.gz
.
File metadata
- Download URL: nanoset-0.2.1.tar.gz
- Upload date:
- Size: 44.4 kB
- Tags: Source
- Uploaded using Trusted Publishing? No
- Uploaded via: twine/3.2.0 pkginfo/1.5.0.1 requests/2.24.0 setuptools/40.8.0 requests-toolbelt/0.9.1 tqdm/4.47.0 CPython/3.7.1
File hashes
Algorithm | Hash digest | |
---|---|---|
SHA256 | 1bb91f585ffefe6c7d21ebb539b964ea40b308b0d9b490c8319948e298749f93 |
|
MD5 | 02298e1bc2f7455cc85028b747b5d4a6 |
|
BLAKE2b-256 | 0a42773b208c9c9eee249e6ccef5460b16874952c2838afdd9a7047e92cd042e |
Provenance
File details
Details for the file nanoset-0.2.1-cp38-cp38-win_amd64.whl
.
File metadata
- Download URL: nanoset-0.2.1-cp38-cp38-win_amd64.whl
- Upload date:
- Size: 186.4 kB
- Tags: CPython 3.8, Windows x86-64
- Uploaded using Trusted Publishing? No
- Uploaded via: twine/3.2.0 pkginfo/1.5.0.1 requests/2.24.0 setuptools/47.3.1 requests-toolbelt/0.9.1 tqdm/4.47.0 CPython/3.8.0
File hashes
Algorithm | Hash digest | |
---|---|---|
SHA256 | b556e271335fbab3a91d86ee6446b653c3e1e68c20794ea55af70d6757e4e852 |
|
MD5 | c500f204549c1e66ecf3f44668d3f0f2 |
|
BLAKE2b-256 | 326fac9c1928bbf5776288d07367d0c52aa0d976516823292c6183a2d77e5862 |
Provenance
File details
Details for the file nanoset-0.2.1-cp38-cp38-manylinux2010_x86_64.whl
.
File metadata
- Download URL: nanoset-0.2.1-cp38-cp38-manylinux2010_x86_64.whl
- Upload date:
- Size: 262.5 kB
- Tags: CPython 3.8, manylinux: glibc 2.12+ x86-64
- Uploaded using Trusted Publishing? No
- Uploaded via: twine/3.2.0 pkginfo/1.5.0.1 requests/2.24.0 setuptools/41.4.0 requests-toolbelt/0.9.1 tqdm/4.47.0 CPython/3.8.0
File hashes
Algorithm | Hash digest | |
---|---|---|
SHA256 | 8246395d235a5545bf151d7575dabaa74c8dfede3a0b4b7e753233e4167880d2 |
|
MD5 | 7a68cb7ee9f8f4cf3007a48cdbe9df84 |
|
BLAKE2b-256 | aa663e128d0547be0b668b0876d94ebc4833acc73c5309855d125cc79a3634e9 |
Provenance
File details
Details for the file nanoset-0.2.1-cp38-cp38-manylinux1_x86_64.whl
.
File metadata
- Download URL: nanoset-0.2.1-cp38-cp38-manylinux1_x86_64.whl
- Upload date:
- Size: 262.5 kB
- Tags: CPython 3.8
- Uploaded using Trusted Publishing? No
- Uploaded via: twine/3.2.0 pkginfo/1.5.0.1 requests/2.24.0 setuptools/41.4.0 requests-toolbelt/0.9.1 tqdm/4.47.0 CPython/3.8.0
File hashes
Algorithm | Hash digest | |
---|---|---|
SHA256 | 16430707b9f76ddfe0f07d4c51c3157c5048e282db2887ce6a578760b4196ec7 |
|
MD5 | 1cc2fa6e38bef204a7d612633467e22f |
|
BLAKE2b-256 | 420de4033b7874a7b837c69382631b7be1732dfd45c62636fa06da1ffdf29d3c |
Provenance
File details
Details for the file nanoset-0.2.1-cp37-cp37m-win_amd64.whl
.
File metadata
- Download URL: nanoset-0.2.1-cp37-cp37m-win_amd64.whl
- Upload date:
- Size: 186.7 kB
- Tags: CPython 3.7m, Windows x86-64
- Uploaded using Trusted Publishing? No
- Uploaded via: twine/3.2.0 pkginfo/1.5.0.1 requests/2.24.0 setuptools/47.3.1 requests-toolbelt/0.9.1 tqdm/4.47.0 CPython/3.7.5
File hashes
Algorithm | Hash digest | |
---|---|---|
SHA256 | 8dbb74b4f18bec303ed0e4f5de4398bc3426125bd2e4144e7b0192fb2fe29950 |
|
MD5 | 2f8c25d39127ee607eb383bb5f9b1149 |
|
BLAKE2b-256 | 4267fa4537bbbb8160861a792a7172be99afb7fd2ab35247bca984056b9e219c |
Provenance
File details
Details for the file nanoset-0.2.1-cp37-cp37m-manylinux2010_x86_64.whl
.
File metadata
- Download URL: nanoset-0.2.1-cp37-cp37m-manylinux2010_x86_64.whl
- Upload date:
- Size: 262.6 kB
- Tags: CPython 3.7m, manylinux: glibc 2.12+ x86-64
- Uploaded using Trusted Publishing? No
- Uploaded via: twine/3.2.0 pkginfo/1.5.0.1 requests/2.24.0 setuptools/40.8.0 requests-toolbelt/0.9.1 tqdm/4.47.0 CPython/3.7.1
File hashes
Algorithm | Hash digest | |
---|---|---|
SHA256 | a68bd74e6935c2b0a9a9de72ad46f1152bc1e3ea698a2bdbba4a4a6750d77145 |
|
MD5 | 3ceb78e531c4dc24590ba959242d51ae |
|
BLAKE2b-256 | 44d6de5c22a470313069e32a28a1d2d613fd42b38393cbd158edb856779d0747 |
Provenance
File details
Details for the file nanoset-0.2.1-cp37-cp37m-manylinux1_x86_64.whl
.
File metadata
- Download URL: nanoset-0.2.1-cp37-cp37m-manylinux1_x86_64.whl
- Upload date:
- Size: 262.6 kB
- Tags: CPython 3.7m
- Uploaded using Trusted Publishing? No
- Uploaded via: twine/3.2.0 pkginfo/1.5.0.1 requests/2.24.0 setuptools/40.8.0 requests-toolbelt/0.9.1 tqdm/4.47.0 CPython/3.7.1
File hashes
Algorithm | Hash digest | |
---|---|---|
SHA256 | bca09e4c238d6c3637ee5407da06d3f96fa100467a5a3888076e9ec74115b537 |
|
MD5 | f5671c53251c9adc9c21ac22eefe861d |
|
BLAKE2b-256 | 52e00aea8670c70120b81e9445c12e3b5fa3e1a301892596e74c77a058a1b2db |
Provenance
File details
Details for the file nanoset-0.2.1-cp36-cp36m-win_amd64.whl
.
File metadata
- Download URL: nanoset-0.2.1-cp36-cp36m-win_amd64.whl
- Upload date:
- Size: 186.8 kB
- Tags: CPython 3.6m, Windows x86-64
- Uploaded using Trusted Publishing? No
- Uploaded via: twine/3.2.0 pkginfo/1.5.0.1 requests/2.24.0 setuptools/47.3.1 requests-toolbelt/0.9.1 tqdm/4.47.0 CPython/3.6.8
File hashes
Algorithm | Hash digest | |
---|---|---|
SHA256 | 298382249f8eed40fc24c16d603cc5ce910b66d7ae772b48b16b545a7e1d1fad |
|
MD5 | a2ab732d1b11b55480b212bc42f8bd25 |
|
BLAKE2b-256 | c55e56c788e8d1b27f8718cd6b9f38a71ef96706f15b000e2ad06d55b9953887 |
Provenance
File details
Details for the file nanoset-0.2.1-cp36-cp36m-manylinux2010_x86_64.whl
.
File metadata
- Download URL: nanoset-0.2.1-cp36-cp36m-manylinux2010_x86_64.whl
- Upload date:
- Size: 262.9 kB
- Tags: CPython 3.6m, manylinux: glibc 2.12+ x86-64
- Uploaded using Trusted Publishing? No
- Uploaded via: twine/3.2.0 pkginfo/1.5.0.1 requests/2.24.0 setuptools/40.8.0 requests-toolbelt/0.9.1 tqdm/4.47.0 CPython/3.6.7
File hashes
Algorithm | Hash digest | |
---|---|---|
SHA256 | fbe5fcf711230f52cad052cc27bc931db644bbf64e9074984c2f817f59b48ab3 |
|
MD5 | c12441911c2dad0b10f9e1fc3254cf90 |
|
BLAKE2b-256 | d0f40d3da3937d7f488f32a069fd8cc37d8685c0de462244f988b68940a2d351 |
Provenance
File details
Details for the file nanoset-0.2.1-cp36-cp36m-manylinux1_x86_64.whl
.
File metadata
- Download URL: nanoset-0.2.1-cp36-cp36m-manylinux1_x86_64.whl
- Upload date:
- Size: 262.9 kB
- Tags: CPython 3.6m
- Uploaded using Trusted Publishing? No
- Uploaded via: twine/3.2.0 pkginfo/1.5.0.1 requests/2.24.0 setuptools/40.8.0 requests-toolbelt/0.9.1 tqdm/4.47.0 CPython/3.6.7
File hashes
Algorithm | Hash digest | |
---|---|---|
SHA256 | cb33fd7446a24b464c6d35bd3340dd027a420221029210c28813e75be06e506b |
|
MD5 | 6b634d3b1c966945b78c8736656dde61 |
|
BLAKE2b-256 | 67fd7a236585495c080261af46c5b2e996d7672d3a170fa48399ec1d8ae61c90 |
Provenance
File details
Details for the file nanoset-0.2.1-cp35-cp35m-win_amd64.whl
.
File metadata
- Download URL: nanoset-0.2.1-cp35-cp35m-win_amd64.whl
- Upload date:
- Size: 186.4 kB
- Tags: CPython 3.5m, Windows x86-64
- Uploaded using Trusted Publishing? No
- Uploaded via: twine/1.15.0 pkginfo/1.5.0.1 requests/2.24.0 setuptools/47.3.1 requests-toolbelt/0.9.1 tqdm/4.47.0 CPython/3.5.4
File hashes
Algorithm | Hash digest | |
---|---|---|
SHA256 | fbbdd8132c5a8d28e0bdc9469507ace5219f50a2d94158cf04fa6a862eab3ab2 |
|
MD5 | fde8c8ffc01f313950df1165d7ad4e1b |
|
BLAKE2b-256 | b3b57fdb11b6893073931a82e5ce234eb034642d507d7a1debb2c1d2ca052eaf |
Provenance
File details
Details for the file nanoset-0.2.1-cp35-cp35m-manylinux2010_x86_64.whl
.
File metadata
- Download URL: nanoset-0.2.1-cp35-cp35m-manylinux2010_x86_64.whl
- Upload date:
- Size: 262.2 kB
- Tags: CPython 3.5m, manylinux: glibc 2.12+ x86-64
- Uploaded using Trusted Publishing? No
- Uploaded via: twine/1.15.0 pkginfo/1.5.0.1 requests/2.24.0 setuptools/40.6.3 requests-toolbelt/0.9.1 tqdm/4.47.0 CPython/3.5.6
File hashes
Algorithm | Hash digest | |
---|---|---|
SHA256 | 892a3a76871342d3ca5361fed2db7c2c5f50fa5abe8262050566c017581578cd |
|
MD5 | 928cd6160f7dbe9e5b2650e69747aec2 |
|
BLAKE2b-256 | 7ec64f00e9f39942dca7fa764a20011e87e8c16165bc2765869b1733ad679346 |
Provenance
File details
Details for the file nanoset-0.2.1-cp35-cp35m-manylinux1_x86_64.whl
.
File metadata
- Download URL: nanoset-0.2.1-cp35-cp35m-manylinux1_x86_64.whl
- Upload date:
- Size: 262.2 kB
- Tags: CPython 3.5m
- Uploaded using Trusted Publishing? No
- Uploaded via: twine/1.15.0 pkginfo/1.5.0.1 requests/2.24.0 setuptools/40.6.3 requests-toolbelt/0.9.1 tqdm/4.47.0 CPython/3.5.6
File hashes
Algorithm | Hash digest | |
---|---|---|
SHA256 | 024371a7e4c3fae6c6b405b65f918fe2bedb5f0ad4e470f85b3eb525b64e215a |
|
MD5 | 26ee8cce54a26ea63c7abb5b47f1d622 |
|
BLAKE2b-256 | c9faf939b5b5149f8edb5a3ff46b6d2b660ea0fd76bc46e9ed4e576a58ff44c6 |