Skip to main content

A memory-optimized wrapper for Python sets likely to be empty.

Project description

nanoset.py starme

A memory-optimized wrapper for Python sets likely to be empty.

TravisCI AppVeyor License Source PyPI Crates Wheel Python Versions Python Implementations Changelog GitHub issues

⏱️ 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 to None 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:

sizegraph

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 a NanoSet.
  • Weakrefing a PicoSet or a NanoSet.
  • Checking for membership in a plain set or frozenset with implicit conversion to frozenset.
  • Creating a dict from a PicoSet or a NanoSet 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

nanoset-0.2.1.tar.gz (44.4 kB view details)

Uploaded Source

Built Distributions

nanoset-0.2.1-cp38-cp38-win_amd64.whl (186.4 kB view details)

Uploaded CPython 3.8 Windows x86-64

nanoset-0.2.1-cp38-cp38-manylinux2010_x86_64.whl (262.5 kB view details)

Uploaded CPython 3.8 manylinux: glibc 2.12+ x86-64

nanoset-0.2.1-cp38-cp38-manylinux1_x86_64.whl (262.5 kB view details)

Uploaded CPython 3.8

nanoset-0.2.1-cp37-cp37m-win_amd64.whl (186.7 kB view details)

Uploaded CPython 3.7m Windows x86-64

nanoset-0.2.1-cp37-cp37m-manylinux2010_x86_64.whl (262.6 kB view details)

Uploaded CPython 3.7m manylinux: glibc 2.12+ x86-64

nanoset-0.2.1-cp37-cp37m-manylinux1_x86_64.whl (262.6 kB view details)

Uploaded CPython 3.7m

nanoset-0.2.1-cp36-cp36m-win_amd64.whl (186.8 kB view details)

Uploaded CPython 3.6m Windows x86-64

nanoset-0.2.1-cp36-cp36m-manylinux2010_x86_64.whl (262.9 kB view details)

Uploaded CPython 3.6m manylinux: glibc 2.12+ x86-64

nanoset-0.2.1-cp36-cp36m-manylinux1_x86_64.whl (262.9 kB view details)

Uploaded CPython 3.6m

nanoset-0.2.1-cp35-cp35m-win_amd64.whl (186.4 kB view details)

Uploaded CPython 3.5m Windows x86-64

nanoset-0.2.1-cp35-cp35m-manylinux2010_x86_64.whl (262.2 kB view details)

Uploaded CPython 3.5m manylinux: glibc 2.12+ x86-64

nanoset-0.2.1-cp35-cp35m-manylinux1_x86_64.whl (262.2 kB view details)

Uploaded CPython 3.5m

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

Hashes for nanoset-0.2.1.tar.gz
Algorithm Hash digest
SHA256 1bb91f585ffefe6c7d21ebb539b964ea40b308b0d9b490c8319948e298749f93
MD5 02298e1bc2f7455cc85028b747b5d4a6
BLAKE2b-256 0a42773b208c9c9eee249e6ccef5460b16874952c2838afdd9a7047e92cd042e

See more details on using hashes here.

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

Hashes for nanoset-0.2.1-cp38-cp38-win_amd64.whl
Algorithm Hash digest
SHA256 b556e271335fbab3a91d86ee6446b653c3e1e68c20794ea55af70d6757e4e852
MD5 c500f204549c1e66ecf3f44668d3f0f2
BLAKE2b-256 326fac9c1928bbf5776288d07367d0c52aa0d976516823292c6183a2d77e5862

See more details on using hashes here.

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

Hashes for nanoset-0.2.1-cp38-cp38-manylinux2010_x86_64.whl
Algorithm Hash digest
SHA256 8246395d235a5545bf151d7575dabaa74c8dfede3a0b4b7e753233e4167880d2
MD5 7a68cb7ee9f8f4cf3007a48cdbe9df84
BLAKE2b-256 aa663e128d0547be0b668b0876d94ebc4833acc73c5309855d125cc79a3634e9

See more details on using hashes here.

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

Hashes for nanoset-0.2.1-cp38-cp38-manylinux1_x86_64.whl
Algorithm Hash digest
SHA256 16430707b9f76ddfe0f07d4c51c3157c5048e282db2887ce6a578760b4196ec7
MD5 1cc2fa6e38bef204a7d612633467e22f
BLAKE2b-256 420de4033b7874a7b837c69382631b7be1732dfd45c62636fa06da1ffdf29d3c

See more details on using hashes here.

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

Hashes for nanoset-0.2.1-cp37-cp37m-win_amd64.whl
Algorithm Hash digest
SHA256 8dbb74b4f18bec303ed0e4f5de4398bc3426125bd2e4144e7b0192fb2fe29950
MD5 2f8c25d39127ee607eb383bb5f9b1149
BLAKE2b-256 4267fa4537bbbb8160861a792a7172be99afb7fd2ab35247bca984056b9e219c

See more details on using hashes here.

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

Hashes for nanoset-0.2.1-cp37-cp37m-manylinux2010_x86_64.whl
Algorithm Hash digest
SHA256 a68bd74e6935c2b0a9a9de72ad46f1152bc1e3ea698a2bdbba4a4a6750d77145
MD5 3ceb78e531c4dc24590ba959242d51ae
BLAKE2b-256 44d6de5c22a470313069e32a28a1d2d613fd42b38393cbd158edb856779d0747

See more details on using hashes here.

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

Hashes for nanoset-0.2.1-cp37-cp37m-manylinux1_x86_64.whl
Algorithm Hash digest
SHA256 bca09e4c238d6c3637ee5407da06d3f96fa100467a5a3888076e9ec74115b537
MD5 f5671c53251c9adc9c21ac22eefe861d
BLAKE2b-256 52e00aea8670c70120b81e9445c12e3b5fa3e1a301892596e74c77a058a1b2db

See more details on using hashes here.

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

Hashes for nanoset-0.2.1-cp36-cp36m-win_amd64.whl
Algorithm Hash digest
SHA256 298382249f8eed40fc24c16d603cc5ce910b66d7ae772b48b16b545a7e1d1fad
MD5 a2ab732d1b11b55480b212bc42f8bd25
BLAKE2b-256 c55e56c788e8d1b27f8718cd6b9f38a71ef96706f15b000e2ad06d55b9953887

See more details on using hashes here.

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

Hashes for nanoset-0.2.1-cp36-cp36m-manylinux2010_x86_64.whl
Algorithm Hash digest
SHA256 fbe5fcf711230f52cad052cc27bc931db644bbf64e9074984c2f817f59b48ab3
MD5 c12441911c2dad0b10f9e1fc3254cf90
BLAKE2b-256 d0f40d3da3937d7f488f32a069fd8cc37d8685c0de462244f988b68940a2d351

See more details on using hashes here.

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

Hashes for nanoset-0.2.1-cp36-cp36m-manylinux1_x86_64.whl
Algorithm Hash digest
SHA256 cb33fd7446a24b464c6d35bd3340dd027a420221029210c28813e75be06e506b
MD5 6b634d3b1c966945b78c8736656dde61
BLAKE2b-256 67fd7a236585495c080261af46c5b2e996d7672d3a170fa48399ec1d8ae61c90

See more details on using hashes here.

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

Hashes for nanoset-0.2.1-cp35-cp35m-win_amd64.whl
Algorithm Hash digest
SHA256 fbbdd8132c5a8d28e0bdc9469507ace5219f50a2d94158cf04fa6a862eab3ab2
MD5 fde8c8ffc01f313950df1165d7ad4e1b
BLAKE2b-256 b3b57fdb11b6893073931a82e5ce234eb034642d507d7a1debb2c1d2ca052eaf

See more details on using hashes here.

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

Hashes for nanoset-0.2.1-cp35-cp35m-manylinux2010_x86_64.whl
Algorithm Hash digest
SHA256 892a3a76871342d3ca5361fed2db7c2c5f50fa5abe8262050566c017581578cd
MD5 928cd6160f7dbe9e5b2650e69747aec2
BLAKE2b-256 7ec64f00e9f39942dca7fa764a20011e87e8c16165bc2765869b1733ad679346

See more details on using hashes here.

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

Hashes for nanoset-0.2.1-cp35-cp35m-manylinux1_x86_64.whl
Algorithm Hash digest
SHA256 024371a7e4c3fae6c6b405b65f918fe2bedb5f0ad4e470f85b3eb525b64e215a
MD5 26ee8cce54a26ea63c7abb5b47f1d622
BLAKE2b-256 c9faf939b5b5149f8edb5a3ff46b6d2b660ea0fd76bc46e9ed4e576a58ff44c6

See more details on using hashes here.

Provenance

Supported by

AWS AWS Cloud computing and Security Sponsor Datadog Datadog Monitoring Fastly Fastly CDN Google Google Download Analytics Microsoft Microsoft PSF Sponsor Pingdom Pingdom Monitoring Sentry Sentry Error logging StatusPage StatusPage Status page