c++ unordered_map 10x slower than python dict?

[ecolss]

Hi folks, I exposed a c++ unordered_map<string, int> to python, and it turned out this map is 10x slower than python's dict.

See code below.

// map.cpp file
#include <pybind11/pybind11.h>
#include <pybind11/stl.h>
#include <pybind11/stl_bind.h>
#include <string>
#include <unordered_map>

namespace py = pybind11;

PYBIND11_MAKE_OPAQUE(std::unordered_map<std::string, int>);

PYBIND11_MODULE(map, m) {
    // map
    py::bind_map<std::unordered_map<std::string, int>>(m, "MapStr2Int");
}

On MacOS, compile it with this cmd:

c++ -O3 -std=c++14 -shared -fPIC -Wl,-undefined,dynamic_lookup $(python3 -m pybind11 --includes) map.cpp -o map$(python3-config --extension-suffix)

Finally, compare with python dict in ipython:

In [20]: import map

In [21]: c_dict = map.MapStr2Int()

In [22]: for i in range(100000):
    ...:     c_dict[str(i)] = i
    ...:

In [23]: py_dict = {w:i for w,i in c_dict.items()}

In [24]: arr = [str(i) for i in np.random.randint(0,100000, 100)]

In [25]: %timeit [c_dict[w] for w in arr]
59 µs ± 2 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)

In [26]: %timeit [py_dict[w] for w in arr]
6.58 µs ± 87.1 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

As seen, c_dict is much much slower than python version.
Why and how to improve?

[Leopold80]

I think you used dict comprehensions {w:i for w,i in c_dict.items()} in python dict, it maybe alloc the memory for one time, but your c dict used for loop for i in range(100000): c_dict[str(i)] = i so that it maybe alloc the memory for many times. Try to use for loop to fill your py_dict .

[jiwaszki]

@2milesaway There is overhead in the module as dictionary is currently performing easy task of just assigning stuff over and over again. You want to compete with simple type that is already efficient inside Python. Remember that Python->pybind->Python conversion in this case would always come at some cost -- that means transferring strings and integers (which in Python are more complicated than cpp's int32_t or int64_t) is not exactly the place you would perform such optimisation. "Don't fix what is already working" would be a great quote here even when optimisation is mentioned.

However, now we know what is a bootle neck here. Is there a way to overcome this issue? In fact there is a way if we know the routine. Let's define such function in our bindings. You need to know that dicts are simply classes under the magic bind_map function. Let's extend it with new code:

auto my_map = py::bind_map<std::unordered_map<std::string, int>>(module, "MapStr2Int");

my_map.def("super_function", [](std::unordered_map<std::string, int> &self, py::list &arr)
            {
                std::vector<int> res;
                for (auto it = arr.begin(); it != arr.end(); it++)
                {
                    res.push_back(self[it->cast<std::string>()]);
                }
                return res;
            });

Now it is testing time:

In [2]: %timeit [c_dict[w] for w in arr]
31.6 µs ± 358 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)

In [3]: %timeit [py_dict[w] for w in arr]
3.56 µs ± 18.3 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)

In [4]: %timeit c_dict.super_function(arr)
4.73 µs ± 18.4 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)

It is clear that moving work to pure cpp is getting us somewhere. It depends on you if you want to build on top of it. But this is just a simple example how-to start.

Additionally @Leopold80 it does not matter how dict is filled in this case. It is outside of scope for time measurements. Other than that this is simple type of int which is getting copied.

EDIT: just changed map to unordered_map, however whole idea is basically the same:)