Message353976
Currently list uses the following formula for allocating an array for items (if size != 0):
allocated = size + (size >> 3) + (3 if size < 9 else 6)
If add items by 1 the growth pattern is: 0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ...
I think this strategy can be improved.
1. There is no much sense in allocating the space for 25 items. The standard Python allocator returns addresses aligned to 16 bytes on 64-bit platform. It will allocate a space for 26 items. It is more efficient if the starting address is a multiple of some power of two, and perhaps larger than the pointer size.
So it may be better to allocate a multiple of two or four items. Few first sizes are multiple of four, so this is good multiplier. I suggest to use the following expression:
allocated = (size + (size >> 3) + 6) & ~3
It adds bits AND, but removes conditional value.
2. It is common enough case if the list is created from a sequence of a known size and do not adds items anymore. Or if it is created by concatenating of few sequences. In such cases the list can overallocate a space which will never be used. For example:
>>> import sys
>>> sys.getsizeof([1, 2, 3])
80
>>> sys.getsizeof([*(1, 2, 3)])
104
List display allocates a space for exactly 3 items. But a list created from a tuple allocates a space for 6 items.
Other example. Let extend a list by 10 items at a time.
size allocated
10 17
20 28
30 39
40 51
50 51
60 73
70 73
80 96
90 96
100 118
We need to reallocate an array after first four steps. 17 is too small for 20, 28 is too small for 30, 39 is too small for 40. So overallocating does not help, it just spends a space.
My idea, that if we adds several items at a time and need to reallocate an array, we check if the overallocated size is enough for adding the same amount of items next time. If it is not enough, we do not overallocate.
The final algorithm is:
allocated = (size + (size >> 3) + 6) & ~3
if size - old_size > allocated - size:
allocated = (size + 3) & ~3
It will save a space if extend a list by many items few times. |
|
Date |
User |
Action |
Args |
2019-10-04 22:43:43 | serhiy.storchaka | set | recipients:
+ serhiy.storchaka, tim.peters, rhettinger |
2019-10-04 22:43:43 | serhiy.storchaka | set | messageid: <1570229023.08.0.986734049649.issue38373@roundup.psfhosted.org> |
2019-10-04 22:43:43 | serhiy.storchaka | link | issue38373 messages |
2019-10-04 22:43:42 | serhiy.storchaka | create | |
|