Why qstr is passed by handle (instead of pointer)? about micropython HOT 11 CLOSED

In an early version, qstr's were exactly their pointer. The main reason to make them an index into a table was to make them smaller. In the byte code, constants (like qstr's) are encoded with a variable width encoding (like UTF-8). Thus, smaller numbers lead to smaller byte code. Pointers are not small, they have high-bits set.

from micropython.

Another place where I see that pointers won't fit is parse.h/mp_parse_node_t, which uses 4 tag bits.

But well, what we can do about this is to use pointers when possible, and when not, use handles. For example, with qstr pools, handle lookup is no longer O(1). Yeah, with exponential pool size growth it's O(log N), but exponential growth is greedy on memory, and why look up at all, if we can use pointer right away?

from micropython.

But well, what we can do about this is to use pointers when possible, and when not, use handles.

I was just pondering this exact point. I think it would be better to have qstrs as direct pointers to their data (their hash, len and bytes). But how to compress them in the byte code? CPython uses a table of strings, and byte codes index that table.

from micropython.

Well, first of all, static qstr table should be much bigger than it is now - include builtin functions/objects/their methods, etc. For other strings, compiler will intern them unconditionally so far, so you'll get qstr index, and can store it varlen in bytecode. On interpreting bytecode, just applies qstr_str() immediately and store ptr in all structures. Do I miss some additional issues?

from micropython.

On interpreting bytecode, just applies qstr_str() immediately and store ptr in all structures.

That's going to have a big performance penalty. Eg LOAD_ATTR, you would need to convert qstr_idx to qstr_ptr, requiring a very complex operation to search the qstr pools. Then you do a dictionary lookup to find the attribute you wanted (insignificant compared with qstr_str call). This would happen each time the byte code was executed.

from micropython.

requiring a very complex operation to search the qstr pools
Then you do a dictionary lookup to find the attribute you wanted (insignificant compared with qstr_str call)

How is it very complex? And how dictionary lookup is insignificant? Exponential pool look up will have worst-case complexity O(log N) (N - total number of items). For dictionary, worst case is O(N). Realistically, 5-10 backtracks thru pools will be enough (well, it should improve once we make not all string intern), once pool is found, it's O(1). Dictionary of some class can easily have 20 attributes ;-), and due to algorithm used, even on average you'll need to loop thru 1/2 of items.

But all in all, if it's clear that some operation requires speed, we should use ptr (even in bytecode I mean). (And as it can't be that clearly really, having configurable even better ;-) ).

from micropython.

Ok, I still fill slight intuitive dissatisfaction with this extra indirection design, but it's pretty deep into interpreter now, and any resolution should take #222 needs into account (and that either means sticking with handles, or have different format for persistable and loaded bytecode, which is bloat).

So, closing for now.

from micropython.

I don't mind leaving this open, since it reminds me to think deeply about the problem :)

from micropython.

Ok, let's keep open, but #386 would be still more important to resolve sooner.

from micropython.

I don't see a reason to keep this open anymore. Having small bytecode size (and hence compressed/indexed qstrs) is much more important than optimising for speed. And there are places now in the code which assume only 16-bit of storage for qstrs (especially when persistent bytecode is enabled).

from micropython.

Ack. I try to to old ticket cleanup myself from time to time, and wanted to close these my "green naive" tickets too, but wanted to re-read them first to see what direction we went since then, but that doesn't happen for months, so just closing them sounds good.

from micropython.