mp_obj_list_append - allocation policy not sensitive to RAM usage

Lines 234 to 244 in 828f771

    
           mp_obj_t mp_obj_list_append(mp_obj_t self_in, mp_obj_t arg) { 
        
               mp_check_self(MP_OBJ_IS_TYPE(self_in, &mp_type_list)); 
        
               mp_obj_list_t *self = MP_OBJ_TO_PTR(self_in); 
        
               if (self->len >= self->alloc) { 
        
                   self->items = m_renew(mp_obj_t, self->items, self->alloc, self->alloc * 2); 
        
                   self->alloc *= 2; 
        
                   mp_seq_clear(self->items, self->len + 1, self->alloc, sizeof(*self->items)); 
        
               } 
        
               self->items[self->len++] = arg; 
        
               return mp_const_none; // return None, as per CPython 
        
           }

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 micro environment 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.

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]*size gives 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.

@stinos

@stinos why does it have to be double? Why can't it be a 10% increase? Or why not triple?

There's nothing special about doubling other than it's a bad idea for micropython.

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 list

At the very least, the size should saturate instead of overflow and fail.
That way, the user doesn't see 1000 bytes left

The Stack Overflow solution seems to be to preallocate the list using [None] * size https://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 .py code 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 .py code.

@dhylands

@dhylands @stinos @pfalcon

The actual problem is not that list takes “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.

@pfalcon

@pfalcon

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^ N

We 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()

@jpochyla

@jpochyla what is that supposed to do?

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
>>>

py/objlist: Make list append allocation more gentle.

Navigation Menu

mp_obj_list_append - allocation policy not sensitive to RAM usage #4087

40 remaining items

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

	mp_obj_t mp_obj_list_append(mp_obj_t self_in, mp_obj_t arg) {
	mp_check_self(MP_OBJ_IS_TYPE(self_in, &mp_type_list));
	mp_obj_list_t *self = MP_OBJ_TO_PTR(self_in);
	if (self->len >= self->alloc) {
	self->items = m_renew(mp_obj_t, self->items, self->alloc, self->alloc * 2);
	self->alloc *= 2;
	mp_seq_clear(self->items, self->len + 1, self->alloc, sizeof(*self->items));
	}
	self->items[self->len++] = arg;
	return mp_const_none; // return None, as per CPython
	}

mp_obj_list_append - allocation policy not sensitive to RAM usage #4087

Description

Activity

stinos commented on Aug 31, 2018

adritium commented on Aug 31, 2018

Anton-2 commented on Aug 31, 2018

adritium commented on Aug 31, 2018

adritium commented on Aug 31, 2018

pfalcon commented on Aug 31, 2018

adritium commented on Aug 31, 2018

dhylands commented on Aug 31, 2018

adritium commented on Aug 31, 2018

adritium commented on Sep 2, 2018

adritium commented on Sep 2, 2018

pfalcon commented on Sep 2, 2018

jpochyla commented on Sep 3, 2018

adritium commented on Sep 3, 2018

peterhinch commented on Sep 5, 2018

40 remaining items

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions