[issue38373] List overallocation strategy

Change by Serhiy Storchaka : -- resolution: -> fixed stage: patch review -> resolved status: open -> closed ___ Python tracker ___

[issue38373] List overallocation strategy

Serhiy Storchaka added the comment: New changeset 2fe815edd6778fb9deef8f8044848647659c2eb8 by Serhiy Storchaka in branch 'master': bpo-38373: Change list overallocating strategy. (GH-18952) https://github.com/python/cpython/commit/2fe815edd6778fb9deef8f8044848647659c2eb8 --

[issue38373] List overallocation strategy

Change by Serhiy Storchaka : -- keywords: +patch pull_requests: +18303 stage: -> patch review pull_request: https://github.com/python/cpython/pull/18952 ___ Python tracker

[issue38373] List overallocation strategy

Change by Inada Naoki : -- nosy: +inada.naoki ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubscribe:

[issue38373] List overallocation strategy

Tim Peters added the comment: Don't know. Define "the problem" ;-) As soon as the allocation is over 512 bytes (64 pointers), it's punted to the system malloc family. Before then, do a relative handful of relatively small memcpy's really matter? pymalloc is faster than system mallocs,

[issue38373] List overallocation strategy

Raymond Hettinger added the comment: > WRT pymalloc, it will always copy on growing resize in this context That sounds like an excellent reason NOT to use pymalloc ;-) -- ___ Python tracker

[issue38373] List overallocation strategy

Tim Peters added the comment: WRT pymalloc, it will always copy on growing resize in this context. A pymalloc pool is dedicated to blocks of the same size class, so if the size class increases (they're 16 bytes apart now), the data must be copied to a different pool (dedicated to blocks of

[issue38373] List overallocation strategy

Serhiy Storchaka added the comment: Here is some data. step is the number of items added at a time, the first row is the size, the second row is the currently allocated size, the third row is the proposed allocated size. for step in (1, 2, 3, 4, 5, 6, 7, 8, 9, 10): sizes0 = range(step,

[issue38373] List overallocation strategy

Raymond Hettinger added the comment: We should definitely revisit the over-allocation strategy. I last worked on the existing strategy back in 2004. Since then, the weighting of the speed/space trade-off considerations have changed. We need to keep the amortized O(1) append() behavior,

[issue38373] List overallocation strategy

Change by Brandt Bucher : -- nosy: +brandtbucher ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubscribe:

[issue38373] List overallocation strategy

New submission from Serhiy Storchaka : 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