[issue10408] Denser dicts and linear probing

[Antoine Pitrou]

Antoine Pitrou <pitrou at free.fr> added the comment:

Here is a benchmark adapted from another bug entry (I merely adapted the dict sizes in order to better exhibit the performance degradation when the CPU cache becomes too small to hold the whole dict).

Results without the patch:

   10000 words (    9092 keys), 2928369 inserts/s, 13911456 lookups/s, 86 bytes/key (0.8MB)
   20000 words (   17699 keys), 3290037 inserts/s, 12746707 lookups/s, 44 bytes/key (0.8MB)
   40000 words (   34490 keys), 2620007 inserts/s, 7723605 lookups/s, 91 bytes/key (3.0MB)
   80000 words (   67148 keys), 2698863 inserts/s, 6573500 lookups/s, 46 bytes/key (3.0MB)
  160000 words (  130897 keys), 2401067 inserts/s, 4886971 lookups/s, 48 bytes/key (6.0MB)
  320000 words (  254233 keys), 2077558 inserts/s, 5061763 lookups/s, 49 bytes/key (12.0MB)
  640000 words (  493191 keys), 1923967 inserts/s, 4490697 lookups/s, 51 bytes/key (24.0MB)
 1280000 words (  956820 keys), 1792729 inserts/s, 4353711 lookups/s, 52 bytes/key (48.0MB)

Results with the patch:

   10000 words (    9092 keys), 3324590 inserts/s, 13911456 lookups/s, 43 bytes/key (0.4MB)
   20000 words (   17699 keys), 3243603 inserts/s, 13202090 lookups/s, 44 bytes/key (0.8MB)
   40000 words (   34490 keys), 2858372 inserts/s, 10686124 lookups/s, 45 bytes/key (1.5MB)
   80000 words (   67148 keys), 2585146 inserts/s, 6917441 lookups/s, 46 bytes/key (3.0MB)
  160000 words (  130897 keys), 2395923 inserts/s, 6455817 lookups/s, 48 bytes/key (6.0MB)
  320000 words (  254233 keys), 2247141 inserts/s, 5529826 lookups/s, 49 bytes/key (12.0MB)
  640000 words (  493191 keys), 2064675 inserts/s, 5073732 lookups/s, 51 bytes/key (24.0MB)
 1280000 words (  956820 keys), 1997615 inserts/s, 4760878 lookups/s, 52 bytes/key (48.0MB)


Lookups become 10% faster when the dict is bigger than the cache, and even inserts seem to benefit a bit.
(not to mention that small dicts take almost half the memory)

----------
Added file: http://bugs.python.org/file19596/dcbench-py3k.py

_______________________________________
Python tracker <report at bugs.python.org>
<http://bugs.python.org/issue10408>
_______________________________________