Repository navigation
mp_obj_list_append - allocation policy not sensitive to RAM usage #4087
Description
Activity
On PC, with gigabytes of RAM this is fine
Unless your application wants to allocate gigabytes of RAM :)
We should change it to something other than doubling.
Not sure if it's that simple. If anything, it should be configurable. But this should then probably be made confgurable at compile time, or we end up with non-standard Python code for modifying list allocation policy since the standard has no notion of that (e.g. having a
reserve()method sounds nice but makes the code not work in any other Python version)But even if it can be changed, the question then is, to what? This is non-trivial to solve. There is no allocation policy which is a good fit for all considering both performance, fragmentation and memory usage. In extreme cases there's not even 1 allocation policy which is a good fit for an entire application: the best allocation policy for a particular piece of code is the one which takes that piece of code in consideration so there's an infinite number of optimal allocation policies..
tldr; given that the out of memory problem can be normally be solved using preallocation+indexing instead of append anyway it's probably easier to stick with some widely-used default..
There is no method to preallocate a list.
There is :
data = [None]*sizegives you a list, filled with None, of length size. This list is allocated once (list_binary_op in /py/objlist.c).You are correct but that still doesn’t solve the problem that when you append one additional item to a list that is full, the list size doubles.
Because division by ten is expensive operation. But it's definitely should be made *1.5 ASAP. It has to be multiplication (i.e. exponential growth) to ensure
"asymptotically O(1)" behavior for such a common operation as constructing list item by item.We're dealing with severely memory constrained situations where asymptotic complexity cannot be the only, or even primary, consideration.
No matter how small the multiplication factor, you're still going to run into issues that confuse the user:
I have 1000 bytes left but I cannot append to the
listAt the very least, the size should saturate instead of overflow and fail.
That way, the user doesn't see1000 bytes leftThe Stack Overflow solution seems to be to preallocate the list using
[None] * sizehttps://stackoverflow.com/questions/311775/python-create-a-list-with-initial-capacity
This is probably the only truly portable solution, and it will give you a list of exactly the size you want. You could create your own wrapper class for managing your array which then expands things however you see fit.MicroPython could also have some micropython specific list behaviour which allows a user to specify a multiplier (i.e. use 1.3 instead of 2) or an addition (i.e. increase list by 10 elements) and the user can tune things how they like but not have portable code. Or perhaps, this could be specified as a compile time option.
The Stack Overflow solution seems to be to preallocate the list using [None] * size
The still doesn't solve the
append()problem.This is probably the only truly portable solution,
The usage of the list in
.pycode has nothing to do with how its underlying size is managed:list.append()only cares about whether there's additional memory or not.Does CPython specify the asymptotic performance of the allocation policy?
If not, this has nothing to do with portability of
.pycode.The actual problem is not that
listtakes “too much space“ but that the user sees that there is abundantly free space but cannot append one more item.Of course it’s not the users business to know how much memory the underlying python data structure uses. I realize that the problem is more of a perception problem: “I have 1000 bytes left yet I cannot append one more integer to this list”.
There is a simple fix to this perception problem: if reallocation, using whatever policy, fails when growing the list then simply reallocate an amount which ends up saturating the memory.
In addition to the perception problem, there still is the problem that for memory constrained systems doubling is too big.
If it has to be a multiply > 1 AND efficient to implement, the divisor should be a power of 2:
X, N integers
Factor = X / 2^N
For any N, X can be
2^(N+1) < X < 2^ NWe might even consider having the factor be a function of the size of the array: a smaller array should increase faster than a bigger one.
And of course we need to make that initial array size * initial factor will be > initial array size.
No matter how small the multiplication factor, you're still going to run into issues that confuse the user: https://forum.micropython.org/viewtopic.php?f=3&t=5074&start=10#p29755
Confusion is such a thing, that it likes to go in layers and circles. For example, "script" by the link above doesn't use list.append(), so if you'd do something to list.append, that probably wouldn't help and user would stay confused.
Otherwise, you're absolutely right that:
-
Allocation policy should be overridable. It was clear from the beginning that
"one size" won't fit all. That's why there're "// TODO: use alloc policy" comments are sprinkled in the code. It's just nobody came up with both manageable and general way to do that yet. -
Default allocation policy/ies should be optimized. Like, ASAP. What you say on how to do that also makes sense, just needs to be adjusted for realistic/efficient implementabillity.
-
For bytearrays, I currently use this trick:
b = bytearray(preallocate) b[:] = bytes()I was puzzled by this so I tried it. As far as I can see it works.
$ upython MicroPython v1.9.4-479-g828f771 on 2018-09-01; linux version Use Ctrl-D to exit, Ctrl-E for paste mode >>> a = bytearray(10) >>> a bytearray(b'\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00') >>> id(a) 139849550460928 >>> a[:] = b'\x01\x02' >>> a bytearray(b'\x01\x02') >>> id(a) 139849550460928 >>> a[:] = b'\x06\x07\x08' >>> a bytearray(b'\x06\x07\x08') >>> id(a) 139849550460928 >>>
40 remaining items
- added a commit that references this issue
on Jun 12, 2026 - added 6 commits that reference this issue
on Jul 8, 2026
micropython/py/objlist.c
Lines 234 to 244 in 828f771
When the user appends ONE additional item to the list, the underlying size is always doubled.
On PC, with gigabytes of RAM this is fine but not in our
microenvironment where an attempt to increase the length of the list leads to out of memory even when attempting to add just ONE more element.We should change it to something other than doubling.