Extensions to standard Python's heapq for performance applications
Fast CPython extensions to Python standard library with focus on performance.
This library provides CPython native extensions to mimic some of the well known built-in types. The implementation relies on enforced protocol - all the objects and abstract data types are implemented in C/C++ to provide highly effective manipulation.
Extended dict - fext.ExtDict
The implementation of fext.ExtDict was introduce to provide a data structure capable of limiting number of items stored in a dictionary (a hash table).
fext.ExtDict is implemented as a standard Python dict and supports most dict methods. To restrict number of items stored in the dictionary, fext.edict.ExtDict uses a min-heap queue that stores key-value pairs (key to the dictionary with it’s value). When an item is inserted into the dictionary, fext.ExtDict checks its size and possibly performs pushpop-like operation on the heap to limit number of items stored.
The comparision is done solely on the actual value. Keys are stored in min-heap queue together with values as pairs to guarantee O(1) time when removing an item from the fext.edictExtDict and O(log(N)) when removing the item from the underlying min-heap queue.
Extended heapq - fext.ExtHeapQueue
The extended heap queue acts as a min-heap queue from the standard Python library. It uses a hash table for storing information about indexes (where values sit in the min-heap queue) to optimize removals from the heap to O(log(N)).
Using fext in a C++ project
The design of this library allows you to use sources in your C++ project as well. The eheapq.hpp file defines the extended heap queue and edict.hpp the extended dictionary. Python files then act as a bindings to their respective Python interfaces. Mind the API design for the templated classes - it was meant to be used with pointers to objects (so avoid possible copy constructors).
Building the extensions
To build extensions, install the following packages (Fedora):
dnf install -y python3-devel g++ gcc
Now you can build extensions:
python3 setup.py build
If you would like to produce binaries with debug information:
CFLAGS='-Wall -O0 -ggdb' python3 setup.py build
Check sections below for more info on testing the C/C++ parts of extensions.
Reference count and memory leak checks
You can find Makefile in the Git repo. This repo defines targets to perform leak checks and reference count checks. Note they use different Python interpreters (with/without debug information) so make sure you do not mix virtual environments when running the tests.
Developing the extension
First, prepare your environment:
dnf install -y make make deps
To develop or adjust sources, simply change sources and verify your change is accepted by the test suite:
The check target will run the actual test suite (see also make test). Besides it, the test suite will be executed two more times to check test suite and its behaviour with respect to Python object reference counting (python3-debug dependency will be automatically installed with the provided make deps). This part of the test suite can be executed using make check-refcount. The last part of the test suite runs valgrind against the test suite - you can explicitly trigger this part by calling make check-leaks.
Mind make check-refcount and make check-leaks will take some time given the checks and processing that is done on the background. To verify your changes more iterativelly, make test should do the trick (don’t forget to do make check after that though).
To clean up your environment, perform:
Building and releasing
The release can be done from a containerized environment:
podman run --rm --workdir /io --entrypoint bash -it --volume `pwd`:/io:Z quay.io/pypa/manylinux2014_x86_64 -c "install -y make && make all"
To check what’s happening, let’s run a containerized environment - this can be helpful when you are testing or developing the extension:
podman run --rm --workdir /io --entrypoint bash -it --volume `pwd`:/io:Z quay.io/pypa/manylinux2014_x86_64
The following commands (run in the container stated above) will install all the necessary tools:
yum install -y make make deps
Once tests pass, clean the environment:
Now we should be ready to produce bdist_wheel and sdist distribution for PyPI:
python3 setup.py bdist_wheel python3 setup.py sdist
Finally, upload artifacts to PyPI:
auditwheel repair fext/*.whl twine upload wheelhouse/*.whl
Alternativelly you can let make all happen.
The project is hosted on PyPI. You can install it via pip or Pipenv:
pipenv install fext # pip3 install fext
If there is no release conforming your system, a build process is triggered during the installation - requires python3-devel and gcc/g++.
These data structures were designed for Thoth’s adviser - for data kept in resolver’s internal state as well as in the reinforcement learning part.
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
|Filename, size||File type||Python version||Upload date||Hashes|
|Filename, size fext-0.1.3-cp36-cp36m-manylinux2014_x86_64.whl (317.0 kB)||File type Wheel||Python version cp36||Upload date||Hashes View|
|Filename, size fext-0.1.3.tar.gz (13.5 kB)||File type Source||Python version None||Upload date||Hashes View|
Hashes for fext-0.1.3-cp36-cp36m-manylinux2014_x86_64.whl