dict: Change to a sticky Copy-On-Write based table.

[alanjds]

google#259 opened on Feb 19, 2017 by @nairb774

This improves the speed of the previous dict implementation through a reduction in the number of atomic loads in the read path (max 1 when the dict is read-only - think globals) as well as the number of allocations needed in the write path.

Overall the performance is improved by about 30%.

Some of the major changes are as follows:

• The internal table layout was changed from []*dictEntry to []dictEntry reducing a memory indirection as well as hopefully improving the speed of slot probing in insertAbsentEntry as well as lookupEntry.

• Many iteration operations which might have needed to grab a relatively expensive lock previously can now do so without locking if the dict is in the read-only mode.

• The sizeof(Dict) increased some as a few variables (used and fill) were moved from the dictTable to Dict itself. The addition of a write and misses values to the Dict makes the overall memory usage of Dict generally larger. This is offset by the type change of dictTable and the reduction of additional pointers there. An empty dict weighs in at 304 bytes compared to 176 previously. At 4 elements, both the old and new implementation use 304 bytes of memory. From that point on, the new implementation actually uses less memory.

Benchmark data (unchanged/statistically insignificant results removed):

name                       old time/op    new time/op    delta
DictIterItems/0-elements      515ns ± 0%     503ns ± 0%    -2.45%  (p=0.008 n=5+5)
DictIterItems/1-elements      579ns ± 0%     574ns ± 1%    -0.86%  (p=0.016 n=5+5)
DictIterItems/2-elements      644ns ± 1%     633ns ± 1%    -1.71%  (p=0.008 n=5+5)
DictIterItems/4-elements      782ns ± 2%     839ns ±15%    +7.21%  (p=0.032 n=5+5)
DictIterItems/5-elements      856ns ± 0%     865ns ± 0%    +0.98%  (p=0.008 n=5+5)
DictIterItems/6-elements     1.12µs ± 0%    1.06µs ± 0%    -5.27%  (p=0.008 n=5+5)
DictIterItems/7-elements     1.19µs ± 0%    1.13µs ± 1%    -4.93%  (p=0.008 n=5+5)
DictIterItems/8-elements     1.25µs ± 1%    1.19µs ± 2%    -4.16%  (p=0.008 n=5+5)
DictIterKeys/0-elements       521ns ± 1%     505ns ± 0%    -3.00%  (p=0.008 n=5+5)
DictIterKeys/1-elements       531ns ± 0%     517ns ± 0%    -2.67%  (p=0.008 n=5+5)
DictIterKeys/2-elements       541ns ± 0%     529ns ± 1%    -2.22%  (p=0.008 n=5+5)
DictIterKeys/3-elements       556ns ± 0%     543ns ± 0%    -2.27%  (p=0.008 n=5+5)
DictIterKeys/4-elements       566ns ± 0%     554ns ± 0%    -2.19%  (p=0.008 n=5+5)
DictIterKeys/5-elements       584ns ± 2%     572ns ± 1%    -2.06%  (p=0.016 n=5+5)
DictIterKeys/6-elements       848ns ± 5%     765ns ± 2%    -9.83%  (p=0.008 n=5+5)
DictIterKeys/7-elements       851ns ± 0%     764ns ± 1%   -10.23%  (p=0.008 n=5+5)
DictIterKeys/8-elements       862ns ± 0%     774ns ± 0%   -10.28%  (p=0.008 n=5+5)
DictIterValues/0-elements     518ns ± 1%     506ns ± 2%    -2.35%  (p=0.008 n=5+5)
DictIterValues/1-elements     535ns ± 2%     514ns ± 0%    -3.97%  (p=0.016 n=5+4)
DictIterValues/2-elements     545ns ± 0%     527ns ± 0%    -3.16%  (p=0.008 n=5+5)
DictIterValues/3-elements     559ns ± 1%     543ns ± 1%    -2.79%  (p=0.008 n=5+5)
DictIterValues/4-elements     582ns ± 8%     552ns ± 0%    -5.09%  (p=0.016 n=5+4)
DictIterValues/5-elements     581ns ± 2%     564ns ± 0%    -2.96%  (p=0.008 n=5+5)
DictIterValues/6-elements     843ns ± 2%     752ns ± 1%   -10.77%  (p=0.008 n=5+5)
DictIterValues/7-elements     850ns ± 1%     764ns ± 1%   -10.07%  (p=0.008 n=5+5)
DictIterValues/8-elements     869ns ± 3%     789ns ± 1%    -9.21%  (p=0.008 n=5+5)
CallSimple                    277ms ± 2%     204ms ± 4%   -26.36%  (p=0.008 n=5+5)
CallKeywords                  310ns ± 5%     328ns ± 1%    +5.67%  (p=0.008 n=5+5)
DictCompCreate                457µs ± 3%     423µs ± 9%    -7.45%  (p=0.032 n=5+5)
Fib                          6.00µs ±11%    5.16µs ± 3%   -14.08%  (p=0.008 n=5+5)
FibParallel10                5.81µs ± 1%    5.22µs ± 4%   -10.22%  (p=0.008 n=5+5)
FibParallel11                6.03µs ±12%    5.27µs ± 4%   -12.61%  (p=0.008 n=5+5)
FibParallel2                 5.44µs ± 1%    4.86µs ± 1%   -10.59%  (p=0.016 n=4+5)
FibParallel3                 5.76µs ±15%    4.88µs ± 2%   -15.34%  (p=0.008 n=5+5)
FibParallel4                 5.76µs ± 9%    5.05µs ± 4%   -12.45%  (p=0.008 n=5+5)
FibParallel5                 5.76µs ± 3%    4.99µs ± 3%   -13.32%  (p=0.008 n=5+5)
FibParallel6                 5.62µs ± 5%    5.07µs ± 1%    -9.65%  (p=0.016 n=5+4)
FibParallel8                 5.68µs ± 3%    5.15µs ± 3%    -9.36%  (p=0.016 n=5+4)
FibParallel9                 5.92µs ± 9%    5.18µs ± 7%   -12.53%  (p=0.008 n=5+5)
DictCreate                    953ns ± 4%     838ns ± 4%   -12.07%  (p=0.008 n=5+5)
DictCreateFunc               1.67µs ± 4%    1.19µs ± 3%   -28.67%  (p=0.008 n=5+5)
DictSetItem                   252ns ± 7%     169ns ± 3%   -32.88%  (p=0.008 n=5+5)
DictStringOnlyGetItem         129ns ± 3%     108ns ± 2%   -15.84%  (p=0.008 n=5+5)
DictStringOnlySetItem         245ns ± 4%     172ns ± 5%   -30.02%  (p=0.008 n=5+5)
ListContains3                 432ns ± 2%     456ns ± 3%    +5.51%  (p=0.008 n=5+5)
WhileXRange                   399ns ± 4%     377ns ± 1%    -5.32%  (p=0.008 n=5+5)

name                       old alloc/op   new alloc/op   delta
DictIterItems/0-elements       320B ± 0%      464B ± 0%   +45.00%  (p=0.008 n=5+5)
DictIterItems/1-elements       384B ± 0%      528B ± 0%   +37.50%  (p=0.008 n=5+5)
DictIterItems/2-elements       448B ± 0%      592B ± 0%   +32.14%  (p=0.008 n=5+5)
DictIterItems/3-elements       512B ± 0%      656B ± 0%   +28.12%  (p=0.008 n=5+5)
DictIterItems/4-elements       576B ± 0%      720B ± 0%   +25.00%  (p=0.008 n=5+5)
DictIterItems/5-elements       640B ± 0%      784B ± 0%   +22.50%  (p=0.008 n=5+5)
DictIterItems/6-elements       704B ± 0%      848B ± 0%   +20.45%  (p=0.008 n=5+5)
DictIterItems/7-elements       768B ± 0%      912B ± 0%   +18.75%  (p=0.008 n=5+5)
DictIterItems/8-elements       832B ± 0%      976B ± 0%   +17.31%  (p=0.008 n=5+5)
DictIterKeys/0-elements        320B ± 0%      464B ± 0%   +45.00%  (p=0.008 n=5+5)
DictIterKeys/1-elements        320B ± 0%      464B ± 0%   +45.00%  (p=0.008 n=5+5)
DictIterKeys/2-elements        320B ± 0%      464B ± 0%   +45.00%  (p=0.008 n=5+5)
DictIterKeys/3-elements        320B ± 0%      464B ± 0%   +45.00%  (p=0.008 n=5+5)
DictIterKeys/4-elements        320B ± 0%      464B ± 0%   +45.00%  (p=0.008 n=5+5)
DictIterKeys/5-elements        320B ± 0%      464B ± 0%   +45.00%  (p=0.008 n=5+5)
DictIterKeys/6-elements        320B ± 0%      464B ± 0%   +45.00%  (p=0.008 n=5+5)
DictIterKeys/7-elements        320B ± 0%      464B ± 0%   +45.00%  (p=0.008 n=5+5)
DictIterKeys/8-elements        320B ± 0%      464B ± 0%   +45.00%  (p=0.008 n=5+5)
DictIterValues/0-elements      320B ± 0%      464B ± 0%   +45.00%  (p=0.008 n=5+5)
DictIterValues/1-elements      320B ± 0%      464B ± 0%   +45.00%  (p=0.008 n=5+5)
DictIterValues/2-elements      320B ± 0%      464B ± 0%   +45.00%  (p=0.008 n=5+5)
DictIterValues/3-elements      320B ± 0%      464B ± 0%   +45.00%  (p=0.008 n=5+5)
DictIterValues/4-elements      320B ± 0%      464B ± 0%   +45.00%  (p=0.008 n=5+5)
DictIterValues/5-elements      320B ± 0%      464B ± 0%   +45.00%  (p=0.008 n=5+5)
DictIterValues/6-elements      320B ± 0%      464B ± 0%   +45.00%  (p=0.008 n=5+5)
DictIterValues/7-elements      320B ± 0%      464B ± 0%   +45.00%  (p=0.008 n=5+5)
DictIterValues/8-elements      320B ± 0%      464B ± 0%   +45.00%  (p=0.008 n=5+5)
ListContains/false-3           336B ± 0%      464B ± 0%   +38.10%  (p=0.008 n=5+5)
ListContains/false-10          336B ± 0%      464B ± 0%   +38.10%  (p=0.008 n=5+5)
TupleContains/false-3          400B ± 0%      528B ± 0%   +32.00%  (p=0.008 n=5+5)
TupleContains/false-10         400B ± 0%      528B ± 0%   +32.00%  (p=0.008 n=5+5)
CallMethod                    244MB ± 0%     244MB ± 0%    -0.07%  (p=0.016 n=4+5)
CallKwargs                     383B ± 0%      415B ± 0%    +8.36%  (p=0.008 n=5+5)
DictCompCreate                142kB ± 0%     154kB ± 0%    +8.21%  (p=0.016 n=5+4)
GeneratorExpCreate             735B ± 0%      863B ± 0%   +17.41%  (p=0.008 n=5+5)
ListCompCreate               40.4kB ± 0%    41.0kB ± 0%    +1.27%  (p=0.008 n=5+5)
DictCreate                     303B ± 0%      335B ± 0%   +10.56%  (p=0.008 n=5+5)
DictCreateFunc                 559B ± 0%      415B ± 0%   -25.76%  (p=0.008 n=5+5)
DictSetItem                   63.0B ± 0%     31.0B ± 0%   -50.79%  (p=0.008 n=5+5)
DictStringOnlySetItem         63.0B ± 0%     31.0B ± 0%   -50.79%  (p=0.008 n=5+5)

name                       old allocs/op  new allocs/op  delta
DictIterItems/0-elements       6.00 ± 0%      5.00 ± 0%   -16.67%  (p=0.008 n=5+5)
DictIterItems/1-elements       7.00 ± 0%      6.00 ± 0%   -14.29%  (p=0.008 n=5+5)
DictIterItems/2-elements       8.00 ± 0%      7.00 ± 0%   -12.50%  (p=0.008 n=5+5)
DictIterItems/3-elements       9.00 ± 0%      8.00 ± 0%   -11.11%  (p=0.008 n=5+5)
DictIterItems/4-elements       10.0 ± 0%       9.0 ± 0%   -10.00%  (p=0.008 n=5+5)
DictIterItems/5-elements       11.0 ± 0%      10.0 ± 0%    -9.09%  (p=0.008 n=5+5)
DictIterItems/6-elements       12.0 ± 0%      11.0 ± 0%    -8.33%  (p=0.008 n=5+5)
DictIterItems/7-elements       13.0 ± 0%      12.0 ± 0%    -7.69%  (p=0.008 n=5+5)
DictIterItems/8-elements       14.0 ± 0%      13.0 ± 0%    -7.14%  (p=0.008 n=5+5)
DictIterKeys/0-elements        6.00 ± 0%      5.00 ± 0%   -16.67%  (p=0.008 n=5+5)
DictIterKeys/1-elements        6.00 ± 0%      5.00 ± 0%   -16.67%  (p=0.008 n=5+5)
DictIterKeys/2-elements        6.00 ± 0%      5.00 ± 0%   -16.67%  (p=0.008 n=5+5)
DictIterKeys/3-elements        6.00 ± 0%      5.00 ± 0%   -16.67%  (p=0.008 n=5+5)
DictIterKeys/4-elements        6.00 ± 0%      5.00 ± 0%   -16.67%  (p=0.008 n=5+5)
DictIterKeys/5-elements        6.00 ± 0%      5.00 ± 0%   -16.67%  (p=0.008 n=5+5)
DictIterKeys/6-elements        6.00 ± 0%      5.00 ± 0%   -16.67%  (p=0.008 n=5+5)
DictIterKeys/7-elements        6.00 ± 0%      5.00 ± 0%   -16.67%  (p=0.008 n=5+5)
DictIterKeys/8-elements        6.00 ± 0%      5.00 ± 0%   -16.67%  (p=0.008 n=5+5)
DictIterValues/0-elements      6.00 ± 0%      5.00 ± 0%   -16.67%  (p=0.008 n=5+5)
DictIterValues/1-elements      6.00 ± 0%      5.00 ± 0%   -16.67%  (p=0.008 n=5+5)
DictIterValues/2-elements      6.00 ± 0%      5.00 ± 0%   -16.67%  (p=0.008 n=5+5)
DictIterValues/3-elements      6.00 ± 0%      5.00 ± 0%   -16.67%  (p=0.008 n=5+5)
DictIterValues/4-elements      6.00 ± 0%      5.00 ± 0%   -16.67%  (p=0.008 n=5+5)
DictIterValues/5-elements      6.00 ± 0%      5.00 ± 0%   -16.67%  (p=0.008 n=5+5)
DictIterValues/6-elements      6.00 ± 0%      5.00 ± 0%   -16.67%  (p=0.008 n=5+5)
DictIterValues/7-elements      6.00 ± 0%      5.00 ± 0%   -16.67%  (p=0.008 n=5+5)
DictIterValues/8-elements      6.00 ± 0%      5.00 ± 0%   -16.67%  (p=0.008 n=5+5)
ListContains/false-3           7.00 ± 0%      6.00 ± 0%   -14.29%  (p=0.008 n=5+5)
ListContains/false-10          7.00 ± 0%      6.00 ± 0%   -14.29%  (p=0.008 n=5+5)
TupleContains/false-3          8.00 ± 0%      7.00 ± 0%   -12.50%  (p=0.008 n=5+5)
TupleContains/false-10         8.00 ± 0%      7.00 ± 0%   -12.50%  (p=0.008 n=5+5)
CallMethod                    6.74M ± 0%     6.74M ± 0%    -0.01%  (p=0.016 n=4+5)
CallSimple                     6.00 ± 0%      3.80 ±47%   -36.67%  (p=0.008 n=5+5)
CallKwargs                     7.00 ± 0%      3.00 ± 0%   -57.14%  (p=0.008 n=5+5)
DictCompCreate                2.75k ± 0%     1.73k ± 0%   -36.83%  (p=0.008 n=5+5)
GeneratorExpCreate             14.0 ± 0%      13.0 ± 0%    -7.14%  (p=0.008 n=5+5)
ListCompCreate                  745 ± 0%       741 ± 0%    -0.54%  (p=0.008 n=5+5)
DictCreate                     6.00 ± 0%      2.00 ± 0%   -66.67%  (p=0.008 n=5+5)
DictCreateFunc                 10.0 ± 0%       3.0 ± 0%   -70.00%  (p=0.008 n=5+5)
DictSetItem                    1.00 ± 0%      0.00       -100.00%  (p=0.008 n=5+5)
DictStringOnlySetItem          1.00 ± 0%      0.00       -100.00%  (p=0.008 n=5+5)

[alanjds]

Comment by trotterdylan
Monday Feb 20, 2017 at 18:40 GMT

---

This is really cool. Thanks for preparing this PR. It's a bit involved so I may take a few days to get through it.

At a high level, I wanted to point out that the immutability of dictEntry objects is an important invariant of the current design. I can't remember all the details off hand but I think it ultimately comes down to not being able to update both the key and value atomically. Can you comment on why this is no longer important in this design?

[alanjds]

Comment by nairb774
Tuesday Feb 21, 2017 at 01:36 GMT

---

Sorry about the size. It wouldn't surprise me to take some time - the nice part is that this is a performance change, not new functionality so time is on our side.

As an overview, the implementation is a blending of the table layout of the Python dict implementation, and a concurrency implementation borrowed from golang/sync@54b13b0. In that light, writes to the table are serialized by a mutex, while reads are performed from a immutable table (assuming the map has transitioned to fast reads). This means that for heavy read-only dicts (think globals) most reads only have the cost of a single atomic read. For heavy read/write dicts, the cost mostly the overhead of locking the recursiveMutex.

If anything I write here would make better sense in the code or commit comment, let me know. I'd also be happy to add/modify existing benchmarks if you think that would be good to make sure this is as good an improvement as I think it is. The main goal for me has been to try to get the CallSimple benchmark closer to the speed that CPython is able to execute it (12ms).

[alanjds]

@nairb774 I pulled your PR, but had to make some changes to fit the updated overwrite option that you added later on another PR. I am not sure that it is still correct now. Can you please take a look on #103 ?

Thanks.