Note
Go to the end to download the full example code
Profiling of dictionary¶
Implementation Python dictionary is quite efficient.
It is possible to replace it with a C++ implementation?
The following code compares several implementation of
a dictionary { str, int: int }.
Implementation to compare¶
import matplotlib.pyplot as plt
import pandas
from cpyquickhelper.fastdata.fast_dict import (
FastDictStrInt64, FastDictInt64Int64, FastDictIntInt)
from cpyquickhelper.fastdata.fast_dict_c import (
UnorderedMapStrInt64_Create, UnorderedMapStrInt64_Insert,
UnorderedMapStrInt64_Get, UnorderedMapStrInt64_Get_Fast,
UnorderedMapStrInt64_Insert_Fast,
UnorderedMapRHStrInt64_Create, UnorderedMapRHStrInt64_Insert_Fast,
UnorderedMapRHStrInt64_Get_Fast)
from pyquickhelper.pycode.profiling import profile, profile2graph
data = [("*" * (i // 2), i, i) for i in range(0, 1000)]
fcts = []
class UnorderedMapRHStrInt64:
def __init__(self):
self.obj = UnorderedMapRHStrInt64_Create()
def insert_fast(self, name, key, value):
UnorderedMapRHStrInt64_Insert_Fast(self.obj, name, key, value)
def get_fast(self, name, key, default_value):
return UnorderedMapRHStrInt64_Get_Fast(self.obj, name, key, default_value)
Python implementation
def insert_py(d):
for n, k, v in data:
d[n, k] = v
def insert_py2(d):
for n, k, v in data:
if k in d:
d[k][n] = v
else:
d[k] = {n: v}
def fct_py():
d1 = {}
insert_py(d1)
get_py(d1)
fcts.append(fct_py)
Second Python implementation
def g_py(d, n, k, v):
return d.get((n, k), 0)
def get_py(d):
for n, k, v in data:
g_py(d, n, k, v)
def g_py2(d, n, k, v):
if k in d:
if n in d[k]:
return d[k][n]
return v
def get_py2(d):
for n, k, v in data:
g_py2(d, n, k, v)
def fct_py2():
d11 = {}
insert_py2(d11)
get_py2(d11)
fcts.append(fct_py2)
pybind11 + unordered_map
def insert_c11(d):
for n, k, v in data:
d.insert(n, k, v)
def get_c11(d):
for n, k, _ in data:
d.get(n, k, 0)
def fct_c11():
d2 = FastDictStrInt64()
insert_c11(d2)
get_c11(d2)
fcts.append(fct_c11)
C API + unordered_map + wrapper
class UnorderedMapStrInt64:
def __init__(self):
self.obj = UnorderedMapStrInt64_Create()
def insert(self, name, key, value):
UnorderedMapStrInt64_Insert(self.obj, name, key, value)
def insert_fast(self, name, key, value):
UnorderedMapStrInt64_Insert_Fast(self.obj, name, key, value)
def get(self, name, key, default_value):
return UnorderedMapStrInt64_Get(self.obj, name, key, default_value)
def get_fast(self, name, key, default_value):
return UnorderedMapStrInt64_Get_Fast(self.obj, name, key, default_value)
def insert_c(d):
for n, k, v in data:
d.insert(n, k, v)
def get_c(d):
for n, k, _ in data:
d.get(n, k, 0)
def fct_c():
d3 = UnorderedMapStrInt64()
insert_c(d3)
get_c(d3)
fcts.append(fct_c)
C API + unordered_map
def insert_c2(d):
for n, k, v in data:
UnorderedMapStrInt64_Insert(d, n, k, v)
def get_c2(d):
for n, k, _ in data:
UnorderedMapStrInt64_Get(d, n, k, 0)
def fct_c2():
d3c = UnorderedMapStrInt64_Create()
insert_c2(d3c)
get_c2(d3c)
fcts.append(fct_c2)
C API + unordered_map + FAST CALL
def insert_c_fast(d):
for n, k, v in data:
UnorderedMapStrInt64_Insert_Fast(d, n, k, v)
def get_c_fast(d):
for n, k, _ in data:
UnorderedMapStrInt64_Get_Fast(d, n, k, 0)
def fct_c_fast():
d3cf = UnorderedMapStrInt64_Create()
insert_c_fast(d3cf)
get_c_fast(d3cf)
fcts.append(fct_c_fast)
C API + unordered_map + FAST CALL + a different implementation, martinus/robin-hood-hashing
def insert_c_fast_rh(d):
for n, k, v in data:
UnorderedMapRHStrInt64_Insert_Fast(d, n, k, v)
def get_c_fast_rh(d):
for n, k, _ in data:
UnorderedMapRHStrInt64_Get_Fast(d, n, k, 0)
def fct_c_fast_rh():
d3cfrh = UnorderedMapRHStrInt64_Create()
insert_c_fast_rh(d3cfrh)
get_c_fast_rh(d3cfrh)
fcts.append(fct_c_fast_rh)
Profiling¶
def fctN(N=4000):
for _ in range(N):
for f in fcts:
f()
def clean_name(text):
text = text.replace("\\", "/")
return text.split("/examples/")[-1]
ps = profile(fctN)[0]
root, nodes = profile2graph(ps, clean_text=clean_name)
text = root.to_text()
print(text)
fctN -- 1 1 -- 5.57868 167.09483 -- plot_profiling_dict.py:244:fctN (fctN)
fct_py -- 4000 4000 -- 0.04002 14.57714 -- plot_profiling_dict.py:68:fct_py (fct_py)
insert_py -- 4000 4000 -- 2.06508 2.06508 -- plot_profiling_dict.py:55:insert_py (insert_py)
get_py -- 4000 4000 -- 4.14719 12.47204 -- plot_profiling_dict.py:84:get_py (get_py)
g_py -- 4000000 4000000 -- 5.44536 8.32485 -- plot_profiling_dict.py:80:g_py (g_py)
<method 'get' of 'dict' objects> -- 4000000 4000000 -- 2.87949 2.87949 -- ~:0:<method 'get' of 'dict' objects> (<method 'get' of 'dict' objects>)
fct_py2 -- 4000 4000 -- 0.02948 8.56800 -- plot_profiling_dict.py:101:fct_py2 (fct_py2)
insert_py2 -- 4000 4000 -- 2.45288 2.45288 -- plot_profiling_dict.py:60:insert_py2 (insert_py2)
get_py2 -- 4000 4000 -- 3.03467 6.08564 -- plot_profiling_dict.py:96:get_py2 (get_py2)
g_py2 -- 4000000 4000000 -- 3.05097 3.05097 -- plot_profiling_dict.py:89:g_py2 (g_py2)
fct_c11 -- 4000 4000 -- 0.14392 34.67301 -- plot_profiling_dict.py:123:fct_c11 (fct_c11)
insert_c11 -- 4000 4000 -- 18.06496 18.06496 -- plot_profiling_dict.py:113:insert_c11 (insert_c11)
get_c11 -- 4000 4000 -- 16.46413 16.46413 -- plot_profiling_dict.py:118:get_c11 (get_c11)
fct_c -- 4000 4000 -- 0.05022 45.80288 -- plot_profiling_dict.py:163:fct_c (fct_c)
__init__ -- 4000 4000 -- 0.02154 0.03150 -- plot_profiling_dict.py:137:__init__ (__init__)
<built-in method cpyqui...redMapStrInt64_Create> -- 4000 4000 -- 0.00996 0.00996 -- ~:0:<built-in method cpyquickhelper.fastdata.fast_dict_c.UnorderedMapStrInt64_Create> (<built-in method cpyquickhelper.fastdata.fast_dict_c.UnorderedMapStrInt64_Create>) +++
insert_c -- 4000 4000 -- 6.03909 22.70496 -- plot_profiling_dict.py:153:insert_c (insert_c)
insert -- 4000000 4000000 -- 4.83787 16.66587 -- plot_profiling_dict.py:140:insert (insert)
<built-in method cpyq...dMapStrInt64_Insert> -- 4000000 4000000 -- 11.82800 11.82800 -- ~:0:<built-in method cpyquickhelper.fastdata.fast_dict_c.UnorderedMapStrInt64_Insert> (<built-in method cpyquickhelper.fastdata.fast_dict_c.UnorderedMapStrInt64_Insert>) +++
get_c -- 4000 4000 -- 6.50076 23.01620 -- plot_profiling_dict.py:158:get_c (get_c)
get -- 4000000 4000000 -- 4.79434 16.51544 -- plot_profiling_dict.py:146:get (get)
<built-in method cpyq...eredMapStrInt64_Get> -- 4000000 4000000 -- 11.72110 11.72110 -- ~:0:<built-in method cpyquickhelper.fastdata.fast_dict_c.UnorderedMapStrInt64_Get> (<built-in method cpyquickhelper.fastdata.fast_dict_c.UnorderedMapStrInt64_Get>) +++
fct_c2 -- 4000 4000 -- 0.03729 24.16863 -- plot_profiling_dict.py:185:fct_c2 (fct_c2)
insert_c2 -- 4000 4000 -- 2.63120 11.30506 -- plot_profiling_dict.py:175:insert_c2 (insert_c2)
<built-in method cpyqui...redMapStrInt64_Insert> -- 4000000 4000000 -- 8.67386 8.67386 -- ~:0:<built-in method cpyquickhelper.fastdata.fast_dict_c.UnorderedMapStrInt64_Insert> (<built-in method cpyquickhelper.fastdata.fast_dict_c.UnorderedMapStrInt64_Insert>) +++
get_c2 -- 4000 4000 -- 3.31370 12.81909 -- plot_profiling_dict.py:180:get_c2 (get_c2)
<built-in method cpyqui...rderedMapStrInt64_Get> -- 4000000 4000000 -- 9.50540 9.50540 -- ~:0:<built-in method cpyquickhelper.fastdata.fast_dict_c.UnorderedMapStrInt64_Get> (<built-in method cpyquickhelper.fastdata.fast_dict_c.UnorderedMapStrInt64_Get>) +++
<built-in method cpyquick...deredMapStrInt64_Create> -- 4000 4000 -- 0.00718 0.00718 -- ~:0:<built-in method cpyquickhelper.fastdata.fast_dict_c.UnorderedMapStrInt64_Create> (<built-in method cpyquickhelper.fastdata.fast_dict_c.UnorderedMapStrInt64_Create>) +++
fct_c_fast -- 4000 4000 -- 0.04222 17.07807 -- plot_profiling_dict.py:207:fct_c_fast (fct_c_fast)
insert_c_fast -- 4000 4000 -- 2.43304 8.65435 -- plot_profiling_dict.py:197:insert_c_fast (insert_c_fast)
<built-in method cpyqui...pStrInt64_Insert_Fast> -- 4000000 4000000 -- 6.22131 6.22131 -- ~:0:<built-in method cpyquickhelper.fastdata.fast_dict_c.UnorderedMapStrInt64_Insert_Fast> (<built-in method cpyquickhelper.fastdata.fast_dict_c.UnorderedMapStrInt64_Insert_Fast>)
get_c_fast -- 4000 4000 -- 2.68198 8.37368 -- plot_profiling_dict.py:202:get_c_fast (get_c_fast)
<built-in method cpyqui...dMapStrInt64_Get_Fast> -- 4000000 4000000 -- 5.69170 5.69170 -- ~:0:<built-in method cpyquickhelper.fastdata.fast_dict_c.UnorderedMapStrInt64_Get_Fast> (<built-in method cpyquickhelper.fastdata.fast_dict_c.UnorderedMapStrInt64_Get_Fast>)
<built-in method cpyquick...deredMapStrInt64_Create> -- 4000 4000 -- 0.00781 0.00781 -- ~:0:<built-in method cpyquickhelper.fastdata.fast_dict_c.UnorderedMapStrInt64_Create> (<built-in method cpyquickhelper.fastdata.fast_dict_c.UnorderedMapStrInt64_Create>) +++
fct_c_fast_rh -- 4000 4000 -- 0.04408 16.64842 -- plot_profiling_dict.py:231:fct_c_fast_rh (fct_c_fast_rh)
insert_c_fast_rh -- 4000 4000 -- 2.42561 8.96549 -- plot_profiling_dict.py:221:insert_c_fast_rh (insert_c_fast_rh)
<built-in method cpyqui...HStrInt64_Insert_Fast> -- 4000000 4000000 -- 6.53989 6.53989 -- ~:0:<built-in method cpyquickhelper.fastdata.fast_dict_c.UnorderedMapRHStrInt64_Insert_Fast> (<built-in method cpyquickhelper.fastdata.fast_dict_c.UnorderedMapRHStrInt64_Insert_Fast>)
get_c_fast_rh -- 4000 4000 -- 2.63531 7.63062 -- plot_profiling_dict.py:226:get_c_fast_rh (get_c_fast_rh)
<built-in method cpyqui...apRHStrInt64_Get_Fast> -- 4000000 4000000 -- 4.99531 4.99531 -- ~:0:<built-in method cpyquickhelper.fastdata.fast_dict_c.UnorderedMapRHStrInt64_Get_Fast> (<built-in method cpyquickhelper.fastdata.fast_dict_c.UnorderedMapRHStrInt64_Get_Fast>)
<built-in method cpyquick...redMapRHStrInt64_Create> -- 4000 4000 -- 0.00822 0.00822 -- ~:0:<built-in method cpyquickhelper.fastdata.fast_dict_c.UnorderedMapRHStrInt64_Create> (<built-in method cpyquickhelper.fastdata.fast_dict_c.UnorderedMapRHStrInt64_Create>)
<built-in method cpyquickhelp...UnorderedMapStrInt64_Create> -- 12000 12000 -- 0.02495 0.02495 -- ~:0:<built-in method cpyquickhelper.fastdata.fast_dict_c.UnorderedMapStrInt64_Create> (<built-in method cpyquickhelper.fastdata.fast_dict_c.UnorderedMapStrInt64_Create>)
<built-in method cpyquickhelp..._c.UnorderedMapStrInt64_Get> -- 8000000 8000000 -- 21.22650 21.22650 -- ~:0:<built-in method cpyquickhelper.fastdata.fast_dict_c.UnorderedMapStrInt64_Get> (<built-in method cpyquickhelper.fastdata.fast_dict_c.UnorderedMapStrInt64_Get>)
<built-in method cpyquickhelp...UnorderedMapStrInt64_Insert> -- 8000000 8000000 -- 20.50185 20.50185 -- ~:0:<built-in method cpyquickhelper.fastdata.fast_dict_c.UnorderedMapStrInt64_Insert> (<built-in method cpyquickhelper.fastdata.fast_dict_c.UnorderedMapStrInt64_Insert>)
Visually.
data = []
for node in root:
data.append(dict(name=node.func_name, time=node.tall))
df = pandas.DataFrame(data).set_index('name').sort_values('time')
fig, ax = plt.subplots(1, 1, figsize=(20, 4))
df.plot.barh(title="Profiling", ax=ax)
fig.tight_layout()
# plt.show()
Total running time of the script: ( 2 minutes 48.770 seconds)
