Hopscotch map
pybind11
Hopscotch map | pybind11 | |
---|---|---|
3 | 42 | |
704 | 14,835 | |
- | 1.4% | |
3.7 | 8.6 | |
7 months ago | 8 days ago | |
C++ | C++ | |
MIT License | GNU General Public License v3.0 or later |
Stars - the number of stars that a project has on GitHub. Growth - month over month growth in stars.
Activity is a relative number indicating how actively a project is being developed. Recent commits have higher weight than older ones.
For example, an activity of 9.0 indicates that a project is amongst the top 10% of the most actively developed projects that we are tracking.
Hopscotch map
-
boost::unordered map is a new king of data structures
Unordered hash map shootout CMAP = https://github.com/tylov/STC KMAP = https://github.com/attractivechaos/klib PMAP = https://github.com/greg7mdp/parallel-hashmap FMAP = https://github.com/skarupke/flat_hash_map RMAP = https://github.com/martinus/robin-hood-hashing HMAP = https://github.com/Tessil/hopscotch-map TMAP = https://github.com/Tessil/robin-map UMAP = std::unordered_map Usage: shootout [n-million=40 key-bits=25] Random keys are in range [0, 2^25). Seed = 1656617916: T1: Insert/update random keys: KMAP: time: 1.949, size: 15064129, buckets: 33554432, sum: 165525449561381 CMAP: time: 1.649, size: 15064129, buckets: 22145833, sum: 165525449561381 PMAP: time: 2.434, size: 15064129, buckets: 33554431, sum: 165525449561381 FMAP: time: 2.112, size: 15064129, buckets: 33554432, sum: 165525449561381 RMAP: time: 1.708, size: 15064129, buckets: 33554431, sum: 165525449561381 HMAP: time: 2.054, size: 15064129, buckets: 33554432, sum: 165525449561381 TMAP: time: 1.645, size: 15064129, buckets: 33554432, sum: 165525449561381 UMAP: time: 6.313, size: 15064129, buckets: 31160981, sum: 165525449561381 T2: Insert sequential keys, then remove them in same order: KMAP: time: 1.173, size: 0, buckets: 33554432, erased 20000000 CMAP: time: 1.651, size: 0, buckets: 33218751, erased 20000000 PMAP: time: 3.840, size: 0, buckets: 33554431, erased 20000000 FMAP: time: 1.722, size: 0, buckets: 33554432, erased 20000000 RMAP: time: 2.359, size: 0, buckets: 33554431, erased 20000000 HMAP: time: 0.849, size: 0, buckets: 33554432, erased 20000000 TMAP: time: 0.660, size: 0, buckets: 33554432, erased 20000000 UMAP: time: 2.138, size: 0, buckets: 31160981, erased 20000000 T3: Remove random keys: KMAP: time: 1.973, size: 0, buckets: 33554432, erased 23367671 CMAP: time: 2.020, size: 0, buckets: 33218751, erased 23367671 PMAP: time: 2.940, size: 0, buckets: 33554431, erased 23367671 FMAP: time: 1.147, size: 0, buckets: 33554432, erased 23367671 RMAP: time: 1.941, size: 0, buckets: 33554431, erased 23367671 HMAP: time: 1.135, size: 0, buckets: 33554432, erased 23367671 TMAP: time: 1.064, size: 0, buckets: 33554432, erased 23367671 UMAP: time: 5.632, size: 0, buckets: 31160981, erased 23367671 T4: Iterate random keys: KMAP: time: 0.748, size: 23367671, buckets: 33554432, repeats: 8, sum: 4465059465719680 CMAP: time: 0.627, size: 23367671, buckets: 33218751, repeats: 8, sum: 4465059465719680 PMAP: time: 0.680, size: 23367671, buckets: 33554431, repeats: 8, sum: 4465059465719680 FMAP: time: 0.735, size: 23367671, buckets: 33554432, repeats: 8, sum: 4465059465719680 RMAP: time: 0.464, size: 23367671, buckets: 33554431, repeats: 8, sum: 4465059465719680 HMAP: time: 0.719, size: 23367671, buckets: 33554432, repeats: 8, sum: 4465059465719680 TMAP: time: 0.662, size: 23367671, buckets: 33554432, repeats: 8, sum: 4465059465719680 UMAP: time: 6.168, size: 23367671, buckets: 31160981, repeats: 8, sum: 4465059465719680 T5: Lookup random keys: KMAP: time: 0.943, size: 23367671, buckets: 33554432, lookups: 34235332, found: 29040438 CMAP: time: 0.863, size: 23367671, buckets: 33218751, lookups: 34235332, found: 29040438 PMAP: time: 1.635, size: 23367671, buckets: 33554431, lookups: 34235332, found: 29040438 FMAP: time: 0.969, size: 23367671, buckets: 33554432, lookups: 34235332, found: 29040438 RMAP: time: 1.705, size: 23367671, buckets: 33554431, lookups: 34235332, found: 29040438 HMAP: time: 0.712, size: 23367671, buckets: 33554432, lookups: 34235332, found: 29040438 TMAP: time: 0.584, size: 23367671, buckets: 33554432, lookups: 34235332, found: 29040438 UMAP: time: 1.974, size: 23367671, buckets: 31160981, lookups: 34235332, found: 29040438
-
Yes, this is embarrassingly slow .so I solved your problem
the map member used for the lookups is a tsl::hopscotch_map (https://github.com/Tessil/hopscotch-map), which is a proper hash map. so it seems to be the latter, that the API is wrong, but from what I can tell it is only a wrongly named class. i don't see where the API makes guarantees about iteration order, which is where the implementation difference would be noticeable (beyond performance for lookup).
-
Any suggestions for resources to optimize for memory allocation/reallocation?
using an open-addressing hash table, such as abseil flat_hash_map or tessil/hopscotch-map
pybind11
-
Experience using crow as web server
I'm investigating using C++ to build a REST server, and would love to know of people's experiences with Crow-- or whether they would recommend something else as a "medium-level" abstraction C++ web server. As background, I started off experimenting with Python/FastAPI, which is great, but there is too much friction to translate from pybind11-exported C++ objects to the format that FastAPI expects, and, of course, there are inherent performance limitations using Python, which could impact scaling up if the project were to be successful.
- Swig – Connect C/C++ programs with high-level programming languages
-
returning numpy arrays via pybind11
I have a C++ function computing a large tensor which I would like to return to Python as a NumPy array via pybind11.
-
I created smooth_lines python module, great for drawing software
This is based on the Google Ink Stroke Modeler C++ library, and using pybind11 to make it available on python.
-
Facial Landmark Detection with C++
pybind11 makes it easy to call C++ from Python if you want to mix.
-
Python’s Multiprocessing Performance Problem
If you've never used Pybind before these pybind tests[1] and this repo[2] have good examples you can crib to get started (in addition to the docs). Once you handle passing/returning/creating the main data types (list, tuple, dict, set, numpy array) the first time, then it's mostly smooth sailing.
Pybind offers a lot of functionality, but core "good parts" I've found useful are (a) use a numpy array in Python and pass it to a C++ method to work on, (b) pass your python data structure to pybind and then do work on it in C++ (some copy overhead), and (c) Make a class/struct in C++ and expose it to Python (so no copying overhead and you can create nice cache-aware structs, etc.).
[1] https://github.com/pybind/pybind11/blob/master/tests/test_py...
- Making Python Web Application with C++ Backend
-
Using pybind11 with minGW to cross compile pyhton module for Windows
I have a python module for which the logic is written in C++ and I use pybind11 to expose the objects and functions to Python.
-
IPC communication between rust, c++, and python
Reading from Python requires a wrapper, using pybind11 this is fairly done.
-
[ADVICE] Python to C++
Also I can highly recommend starting using C++ to augment your Python code, i.e. find the parts that are slow or undoable in Python and write those in C++ then expose them as Python functions. You can use https://github.com/pybind/pybind11 to call C++ code from Python.
What are some alternatives?
C++ B-tree - Git mirror of the official (mercurial) repository of cpp-btree
PyO3 - Rust bindings for the Python interpreter
PEGTL - Parsing Expression Grammar Template Library
nanobind - nanobind: tiny and efficient C++/Python bindings
sparsehash-c11 - Experimental C++11 version of sparsehash
Optional Argument in C++ - Named Optional Arguments in C++17
sparsehash - C++ associative containers
setuptools-rust - Setuptools plugin for Rust support
sol2 - Sol3 (sol2 v3.0) - a C++ <-> Lua API wrapper with advanced features and top notch performance - is here, and it's great! Documentation:
Hashmaps - Various open addressing hashmap algorithms in C++