[Python-Dev] cpython (2.7): Fix comment blocks. Adjust blocksize to a power-of-two for better divmod

[Victor Stinner]

2013/6/24 Raymond Hettinger <raymond.hettinger at gmail.com>:
> Changing the BLOCKLEN from 62 to 64 is debatable.
> It measureably improved deque_index without an
> observable negative effect on the other operations.

Out of curiosity, do you know (remember) how was the number 62 chosen?
Is it a compromise between memory usage and performances? 62 is
surprising because it is not a power of two :-)

Is it to just have 64 (2+62) pointers in the structure? (64 is a power
of 2) Does it help the memory allocator (reduce memory fragmentation)
to have a structure of 256 bytes (32-bit pointer) or 512 bytes (64-bit
pointer), which are power of 2, instead of 264 or 528 bytes?

It would be interesting to test pymalloc memory allocator on deque: I
plan to test Python globally with PyMem_Malloc using pymalloc.
pymalloc has a threshold of 512 bytes (and  528 bytes is greater than
512!). I suppose that the memory allocator is (much) more expensive
than integer divisions.

Would it be possible to change dynamically BLOCKLEN depending on the
total size of the deque? Python dict does something like that, but for
other reasons (reduce the number of hash collisions). According to
your comment, "Larger numbers  reduce the number of calls to the
memory allocator, give faster  indexing and rotation, and reduce the
link::data overhead ratio."

With dynamic BLOCKLEN, it would also be possible to reduce the memory
usage for small deque (less than 62 items).

Victor