frozendict: an experiment
Marco Sulla
Marco.Sulla.Python at gmail.com
Tue Jul 14 03:03:01 EDT 2020
On Mon, 13 Jul 2020 at 19:28, Barry Scott <barry at barrys-emacs.org> wrote:
> > On 13 Jul 2020, at 03:20, Marco Sulla <elbarbun at gmail.com> wrote:
> > So why did I try to implement it? IMO, apart the considerations in PEP
> > 416, a frozendict can be useful:
> >
> > - as a faster base for types.MutableMappingProxy
> > - as a substitute of namedtuple
> > - as set values
> > - as a faster dict. Indeed a frozendict does not need views. Keys,
> > values and items can be cached and could be a subclass of frozendict
> > that implements also the set API (values apart).
>
>
> Why is it faster? Have you benchmarked that claim?
It's not faster now, but it can. And yes, I've done a bench. I explain
it better in the mail.
> Why do you think I do not need views to use the frozendict?
> I thought that is what make d.key(), d.items() etc work?
Views for dict exist because dict is mutable. See this example:
>>> d = {1: 2}
>>> keys = d.keys()
>>> d[2] = 3
>>> keys
dict_keys([1, 2])
As you see, even if you modified the dict __after__ you created the
keys view, the view returns also the new key, 2.
This is desirable for a mutable object, but it's not needed for an
immutable one. frozendict could create lazily an object that contains
all its keys and cache it.
It *seems* that this is already done, because PyDictObject struct has
ma_keys and ma_values. But this is not always true. If you read the
documentation in the comments of Object/dictobject.c, it's stated
that, if the keys are not strings, there's actually not two separate
objects for keys and values. On the contrary, key and value are stored
together in ma_keys.
This seems to be done because it's easier to preserve order when you
modify the dict. But since frozendict cannot be modified, it could be
a split dict every time.
> > A possible problem is that frozendict requires more memory, since the
> > hash is cached.
>
> The hash is tiny 64 bits?
Well, it's the sum that makes the total. If, and only if, frozendict
is really faster than dict, using always a split dict and cached
"views", it could be used for a bunch of cases. kwargs for example.
About bench, yes, as I wrote I've done a simple bench:
################################################################################
////////////////////////////////////////////////////////////////////////////////
Dictionary size: 8; Type: dict; Statement: `d.get(key)`;
total time: 0.389; iterations: 13000000; time: 2.990e-08
Dictionary size: 8; Type: frozendict; Statement: `d.get(key)`;
total time: 0.416; iterations: 13000000; time: 3.202e-08
Dictionary size: 8; Type: Map; Statement: `d.get(key)`;
total time: 0.559; iterations: 13000000; time: 4.302e-08
////////////////////////////////////////////////////////////////////////////////
Dictionary size: 8; Type: dict; Statement: `d[key]`;
total time: 0.375; iterations: 10000000; time: 3.753e-08
Dictionary size: 8; Type: frozendict; Statement: `d[key]`;
total time: 0.338; iterations: 10000000; time: 3.384e-08
Dictionary size: 8; Type: Map; Statement: `d[key]`;
total time: 0.502; iterations: 10000000; time: 5.021e-08
////////////////////////////////////////////////////////////////////////////////
Dictionary size: 8; Type: dict; Statement: `key in d`;
total time: 0.600; iterations: 20000000; time: 3.000e-08
Dictionary size: 8; Type: frozendict; Statement: `key in d`;
total time: 0.541; iterations: 20000000; time: 2.703e-08
Dictionary size: 8; Type: Map; Statement: `key in d`;
total time: 0.545; iterations: 20000000; time: 2.723e-08
////////////////////////////////////////////////////////////////////////////////
Dictionary size: 8; Type: dict; Statement: `key not in d`;
total time: 0.607; iterations: 20000000; time: 3.033e-08
Dictionary size: 8; Type: frozendict; Statement: `key not in d`;
total time: 0.548; iterations: 20000000; time: 2.738e-08
Dictionary size: 8; Type: Map; Statement: `key not in d`;
total time: 0.548; iterations: 20000000; time: 2.738e-08
////////////////////////////////////////////////////////////////////////////////
Dictionary size: 8; Type: dict; Statement: `pickle.dumps(d)`;
total time: 0.554; iterations: 625000; time: 8.869e-07
Dictionary size: 8; Type: frozendict; Statement: `pickle.dumps(d)`;
total time: 0.545; iterations: 625000; time: 8.720e-07
Dictionary size: 8; Type: Map; Statement: `pickle.dumps(d)`;
total time: 1.562; iterations: 625000; time: 2.499e-06
////////////////////////////////////////////////////////////////////////////////
Dictionary size: 8; Type: dict; Statement:
`pickle.loads(dump)`; total time: 0.685; iterations: 500000;
time: 1.371e-06
Dictionary size: 8; Type: frozendict; Statement:
`pickle.loads(dump)`; total time: 0.816; iterations: 500000;
time: 1.633e-06
Dictionary size: 8; Type: Map; Statement:
`pickle.loads(dump)`; total time: 1.388; iterations: 500000;
time: 2.775e-06
////////////////////////////////////////////////////////////////////////////////
Dictionary size: 8; Type: frozendict; Statement: `hash(d)`;
total time: 0.548; iterations: 10000000; time: 5.484e-08
Dictionary size: 8; Type: Map; Statement: `hash(d)`;
total time: 0.539; iterations: 10000000; time: 5.391e-08
////////////////////////////////////////////////////////////////////////////////
Dictionary size: 8; Type: dict; Statement: `len(d)`;
total time: 0.872; iterations: 20000000; time: 4.358e-08
Dictionary size: 8; Type: frozendict; Statement: `len(d)`;
total time: 0.872; iterations: 20000000; time: 4.362e-08
Dictionary size: 8; Type: Map; Statement: `len(d)`;
total time: 0.869; iterations: 20000000; time: 4.347e-08
////////////////////////////////////////////////////////////////////////////////
Dictionary size: 8; Type: dict; Statement: `d.keys()`;
total time: 1.453; iterations: 12500000; time: 1.163e-07
Dictionary size: 8; Type: frozendict; Statement: `d.keys()`;
total time: 1.457; iterations: 12500000; time: 1.165e-07
Dictionary size: 8; Type: Map; Statement: `d.keys()`;
total time: 1.896; iterations: 12500000; time: 1.517e-07
////////////////////////////////////////////////////////////////////////////////
Dictionary size: 8; Type: dict; Statement: `d.values()`;
total time: 1.505; iterations: 12500000; time: 1.204e-07
Dictionary size: 8; Type: frozendict; Statement: `d.values()`;
total time: 1.494; iterations: 12500000; time: 1.195e-07
Dictionary size: 8; Type: Map; Statement: `d.values()`;
total time: 1.890; iterations: 12500000; time: 1.512e-07
////////////////////////////////////////////////////////////////////////////////
Dictionary size: 8; Type: dict; Statement: `d.items()`;
total time: 1.213; iterations: 6250000; time: 1.941e-07
Dictionary size: 8; Type: frozendict; Statement: `d.items()`;
total time: 1.214; iterations: 6250000; time: 1.942e-07
Dictionary size: 8; Type: Map; Statement: `d.items()`;
total time: 1.759; iterations: 6250000; time: 2.815e-07
////////////////////////////////////////////////////////////////////////////////
Dictionary size: 8; Type: dict; Statement: `iter(d)`;
total time: 1.594; iterations: 12500000; time: 1.275e-07
Dictionary size: 8; Type: frozendict; Statement: `iter(d)`;
total time: 1.622; iterations: 12500000; time: 1.298e-07
Dictionary size: 8; Type: Map; Statement: `iter(d)`;
total time: 1.990; iterations: 12500000; time: 1.592e-07
////////////////////////////////////////////////////////////////////////////////
Dictionary size: 8; Type: dict; Statement:
`constructor(dict)`; total time: 0.301; iterations: 1250000;
time: 2.405e-07
Dictionary size: 8; Type: frozendict; Statement:
`constructor(dict)`; total time: 0.308; iterations: 1250000;
time: 2.466e-07
Dictionary size: 8; Type: Map; Statement:
`constructor(dict)`; total time: 0.815; iterations: 1250000;
time: 6.523e-07
////////////////////////////////////////////////////////////////////////////////
Dictionary size: 8; Type: dict; Statement:
`constructor(d.items())`; total time: 0.363; iterations: 1250000;
time: 2.902e-07
Dictionary size: 8; Type: frozendict; Statement:
`constructor(d.items())`; total time: 0.374; iterations: 1250000;
time: 2.994e-07
Dictionary size: 8; Type: Map; Statement:
`constructor(d.items())`; total time: 0.764; iterations: 1250000;
time: 6.109e-07
////////////////////////////////////////////////////////////////////////////////
Dictionary size: 8; Type: dict; Statement:
`constructor(**d)`; total time: 0.150; iterations: 625000;
time: 2.393e-07
Dictionary size: 8; Type: frozendict; Statement:
`constructor(**d)`; total time: 0.152; iterations: 625000;
time: 2.428e-07
Dictionary size: 8; Type: Map; Statement:
`constructor(**d)`; total time: 0.408; iterations: 625000;
time: 6.536e-07
////////////////////////////////////////////////////////////////////////////////
Dictionary size: 8; Type: dict; Statement:
`constructor(self)`; total time: 1.499; iterations: 6250000;
time: 2.399e-07
Dictionary size: 8; Type: frozendict; Statement:
`constructor(self)`; total time: 0.279; iterations: 6250000;
time: 4.466e-08
Dictionary size: 8; Type: Map; Statement:
`constructor(self)`; total time: 0.395; iterations: 6250000;
time: 6.327e-08
////////////////////////////////////////////////////////////////////////////////
Dictionary size: 8; Type: dict; Statement: `d.copy()`;
total time: 1.320; iterations: 12500000; time: 1.056e-07
Dictionary size: 8; Type: frozendict; Statement: `d.copy()`;
total time: 0.439; iterations: 12500000; time: 3.511e-08
////////////////////////////////////////////////////////////////////////////////
Dictionary size: 8; Type: dict; Statement: `d1 == d2`;
total time: 1.295; iterations: 12500000; time: 1.036e-07
Dictionary size: 8; Type: frozendict; Statement: `d1 == d2`;
total time: 1.305; iterations: 12500000; time: 1.044e-07
Dictionary size: 8; Type: Map; Statement: `d1 == d2`;
total time: 0.501; iterations: 12500000; time: 4.004e-08
////////////////////////////////////////////////////////////////////////////////
Dictionary size: 8; Type: dict; Statement: `self == self`;
total time: 1.286; iterations: 12500000; time: 1.029e-07
Dictionary size: 8; Type: frozendict; Statement: `self == self`;
total time: 1.296; iterations: 12500000; time: 1.037e-07
Dictionary size: 8; Type: Map; Statement: `self == self`;
total time: 0.403; iterations: 12500000; time: 3.223e-08
////////////////////////////////////////////////////////////////////////////////
Dictionary size: 8; Type: dict; Statement: `repr(d)`;
total time: 0.991; iterations: 375000; time: 2.643e-06
Dictionary size: 8; Type: frozendict; Statement: `repr(d)`;
total time: 1.145; iterations: 375000; time: 3.052e-06
Dictionary size: 8; Type: Map; Statement: `repr(d)`;
total time: 1.426; iterations: 375000; time: 3.802e-06
////////////////////////////////////////////////////////////////////////////////
Dictionary size: 8; Type: dict; Statement: `str(d)`;
total time: 1.003; iterations: 375000; time: 2.676e-06
Dictionary size: 8; Type: frozendict; Statement: `str(d)`;
total time: 1.156; iterations: 375000; time: 3.084e-06
Dictionary size: 8; Type: Map; Statement: `str(d)`;
total time: 1.453; iterations: 375000; time: 3.876e-06
////////////////////////////////////////////////////////////////////////////////
Dictionary size: 8; Type: dict; Statement:
`class.fromkeys()`; total time: 1.075; iterations: 3125000;
time: 3.441e-07
Dictionary size: 8; Type: frozendict; Statement:
`class.fromkeys()`; total time: 1.083; iterations: 3125000;
time: 3.464e-07
################################################################################
////////////////////////////////////////////////////////////////////////////////
Dictionary size: 1000; Type: dict; Statement: `d.get(key)`;
total time: 0.387; iterations: 13000000; time: 2.975e-08
Dictionary size: 1000; Type: frozendict; Statement: `d.get(key)`;
total time: 0.386; iterations: 13000000; time: 2.971e-08
Dictionary size: 1000; Type: Map; Statement: `d.get(key)`;
total time: 0.611; iterations: 13000000; time: 4.703e-08
////////////////////////////////////////////////////////////////////////////////
Dictionary size: 1000; Type: dict; Statement: `d[key]`;
total time: 0.332; iterations: 10000000; time: 3.317e-08
Dictionary size: 1000; Type: frozendict; Statement: `d[key]`;
total time: 0.333; iterations: 10000000; time: 3.328e-08
Dictionary size: 1000; Type: Map; Statement: `d[key]`;
total time: 0.448; iterations: 10000000; time: 4.480e-08
////////////////////////////////////////////////////////////////////////////////
Dictionary size: 1000; Type: dict; Statement: `key in d`;
total time: 0.552; iterations: 20000000; time: 2.760e-08
Dictionary size: 1000; Type: frozendict; Statement: `key in d`;
total time: 0.582; iterations: 20000000; time: 2.911e-08
Dictionary size: 1000; Type: Map; Statement: `key in d`;
total time: 0.599; iterations: 20000000; time: 2.996e-08
////////////////////////////////////////////////////////////////////////////////
Dictionary size: 1000; Type: dict; Statement: `key not in d`;
total time: 0.561; iterations: 20000000; time: 2.807e-08
Dictionary size: 1000; Type: frozendict; Statement: `key not in d`;
total time: 0.557; iterations: 20000000; time: 2.784e-08
Dictionary size: 1000; Type: Map; Statement: `key not in d`;
total time: 0.645; iterations: 20000000; time: 3.224e-08
////////////////////////////////////////////////////////////////////////////////
Dictionary size: 1000; Type: dict; Statement: `pickle.dumps(d)`;
total time: 0.677; iterations: 5000; time: 1.353e-04
Dictionary size: 1000; Type: frozendict; Statement: `pickle.dumps(d)`;
total time: 0.672; iterations: 5000; time: 1.345e-04
Dictionary size: 1000; Type: Map; Statement: `pickle.dumps(d)`;
total time: 1.049; iterations: 5000; time: 2.098e-04
////////////////////////////////////////////////////////////////////////////////
Dictionary size: 1000; Type: dict; Statement:
`pickle.loads(dump)`; total time: 0.557; iterations: 4000;
time: 1.392e-04
Dictionary size: 1000; Type: frozendict; Statement:
`pickle.loads(dump)`; total time: 0.622; iterations: 4000;
time: 1.554e-04
Dictionary size: 1000; Type: Map; Statement:
`pickle.loads(dump)`; total time: 1.312; iterations: 4000;
time: 3.279e-04
////////////////////////////////////////////////////////////////////////////////
Dictionary size: 1000; Type: frozendict; Statement: `hash(d)`;
total time: 0.545; iterations: 10000000; time: 5.447e-08
Dictionary size: 1000; Type: Map; Statement: `hash(d)`;
total time: 0.539; iterations: 10000000; time: 5.394e-08
////////////////////////////////////////////////////////////////////////////////
Dictionary size: 1000; Type: dict; Statement: `len(d)`;
total time: 1.032; iterations: 20000000; time: 5.161e-08
Dictionary size: 1000; Type: frozendict; Statement: `len(d)`;
total time: 1.035; iterations: 20000000; time: 5.177e-08
Dictionary size: 1000; Type: Map; Statement: `len(d)`;
total time: 1.032; iterations: 20000000; time: 5.162e-08
////////////////////////////////////////////////////////////////////////////////
Dictionary size: 1000; Type: dict; Statement: `d.keys()`;
total time: 0.907; iterations: 100000; time: 9.066e-06
Dictionary size: 1000; Type: frozendict; Statement: `d.keys()`;
total time: 0.906; iterations: 100000; time: 9.055e-06
Dictionary size: 1000; Type: Map; Statement: `d.keys()`;
total time: 1.699; iterations: 100000; time: 1.699e-05
////////////////////////////////////////////////////////////////////////////////
Dictionary size: 1000; Type: dict; Statement: `d.values()`;
total time: 0.964; iterations: 100000; time: 9.644e-06
Dictionary size: 1000; Type: frozendict; Statement: `d.values()`;
total time: 0.962; iterations: 100000; time: 9.622e-06
Dictionary size: 1000; Type: Map; Statement: `d.values()`;
total time: 1.701; iterations: 100000; time: 1.701e-05
////////////////////////////////////////////////////////////////////////////////
Dictionary size: 1000; Type: dict; Statement: `d.items()`;
total time: 0.842; iterations: 50000; time: 1.684e-05
Dictionary size: 1000; Type: frozendict; Statement: `d.items()`;
total time: 0.833; iterations: 50000; time: 1.666e-05
Dictionary size: 1000; Type: Map; Statement: `d.items()`;
total time: 1.669; iterations: 50000; time: 3.338e-05
////////////////////////////////////////////////////////////////////////////////
Dictionary size: 1000; Type: dict; Statement: `iter(d)`;
total time: 0.918; iterations: 100000; time: 9.183e-06
Dictionary size: 1000; Type: frozendict; Statement: `iter(d)`;
total time: 0.906; iterations: 100000; time: 9.065e-06
Dictionary size: 1000; Type: Map; Statement: `iter(d)`;
total time: 1.703; iterations: 100000; time: 1.703e-05
////////////////////////////////////////////////////////////////////////////////
Dictionary size: 1000; Type: dict; Statement:
`constructor(dict)`; total time: 0.214; iterations: 10000;
time: 2.140e-05
Dictionary size: 1000; Type: frozendict; Statement:
`constructor(dict)`; total time: 0.214; iterations: 10000;
time: 2.139e-05
Dictionary size: 1000; Type: Map; Statement:
`constructor(dict)`; total time: 1.718; iterations: 10000;
time: 1.718e-04
////////////////////////////////////////////////////////////////////////////////
Dictionary size: 1000; Type: dict; Statement:
`constructor(d.items())`; total time: 0.326; iterations: 10000;
time: 3.260e-05
Dictionary size: 1000; Type: frozendict; Statement:
`constructor(d.items())`; total time: 0.329; iterations: 10000;
time: 3.294e-05
Dictionary size: 1000; Type: Map; Statement:
`constructor(d.items())`; total time: 1.617; iterations: 10000;
time: 1.617e-04
////////////////////////////////////////////////////////////////////////////////
Dictionary size: 1000; Type: dict; Statement:
`constructor(**d)`; total time: 0.108; iterations: 5000;
time: 2.168e-05
Dictionary size: 1000; Type: frozendict; Statement:
`constructor(**d)`; total time: 0.108; iterations: 5000;
time: 2.165e-05
Dictionary size: 1000; Type: Map; Statement:
`constructor(**d)`; total time: 0.854; iterations: 5000;
time: 1.707e-04
////////////////////////////////////////////////////////////////////////////////
Dictionary size: 1000; Type: dict; Statement:
`constructor(self)`; total time: 1.066; iterations: 50000;
time: 2.132e-05
Dictionary size: 1000; Type: frozendict; Statement:
`constructor(self)`; total time: 0.002; iterations: 50000;
time: 4.366e-08
Dictionary size: 1000; Type: Map; Statement:
`constructor(self)`; total time: 0.003; iterations: 50000;
time: 6.227e-08
////////////////////////////////////////////////////////////////////////////////
Dictionary size: 1000; Type: dict; Statement: `d.copy()`;
total time: 0.635; iterations: 100000; time: 6.348e-06
Dictionary size: 1000; Type: frozendict; Statement: `d.copy()`;
total time: 0.003; iterations: 100000; time: 3.495e-08
////////////////////////////////////////////////////////////////////////////////
Dictionary size: 1000; Type: dict; Statement: `d1 == d2`;
total time: 1.270; iterations: 100000; time: 1.270e-05
Dictionary size: 1000; Type: frozendict; Statement: `d1 == d2`;
total time: 1.280; iterations: 100000; time: 1.280e-05
Dictionary size: 1000; Type: Map; Statement: `d1 == d2`;
total time: 0.004; iterations: 100000; time: 3.928e-08
////////////////////////////////////////////////////////////////////////////////
Dictionary size: 1000; Type: dict; Statement: `self == self`;
total time: 1.262; iterations: 100000; time: 1.262e-05
Dictionary size: 1000; Type: frozendict; Statement: `self == self`;
total time: 1.278; iterations: 100000; time: 1.278e-05
Dictionary size: 1000; Type: Map; Statement: `self == self`;
total time: 0.003; iterations: 100000; time: 3.210e-08
////////////////////////////////////////////////////////////////////////////////
Dictionary size: 1000; Type: dict; Statement: `repr(d)`;
total time: 0.716; iterations: 3000; time: 2.386e-04
Dictionary size: 1000; Type: frozendict; Statement: `repr(d)`;
total time: 0.804; iterations: 3000; time: 2.680e-04
Dictionary size: 1000; Type: Map; Statement: `repr(d)`;
total time: 1.180; iterations: 3000; time: 3.934e-04
////////////////////////////////////////////////////////////////////////////////
Dictionary size: 1000; Type: dict; Statement: `str(d)`;
total time: 0.712; iterations: 3000; time: 2.374e-04
Dictionary size: 1000; Type: frozendict; Statement: `str(d)`;
total time: 0.798; iterations: 3000; time: 2.660e-04
Dictionary size: 1000; Type: Map; Statement: `str(d)`;
total time: 1.179; iterations: 3000; time: 3.931e-04
////////////////////////////////////////////////////////////////////////////////
Dictionary size: 1000; Type: dict; Statement:
`class.fromkeys()`; total time: 0.900; iterations: 25000;
time: 3.600e-05
Dictionary size: 1000; Type: frozendict; Statement:
`class.fromkeys()`; total time: 0.511; iterations: 25000;
time: 2.045e-05
Some considerations:
1. copy() and frozendict(a_frozendict) are faster. This is expected,
since they simply returns the same frozendict, as frozenset and tuple
2. pickle.loads is slower. This is expected too, since my pickle
implementation for frozendict is very quick and dirty...
3. immutables.Map seems to be faster in equal comparison, but only
because it does not implement it.
4. the other operations have the same performance. Again, this is
expected since no optimization was done.
More information about the Python-list
mailing list