Repository navigation
Why qstr is passed by handle (instead of pointer)? #4
Description
Activity
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.
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?
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.
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?
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.
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 ;-) ).
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.
I don't mind leaving this open, since it reminds me to think deeply about the problem :)
- added a commit that references this issue
on Aug 28, 2016 - added a commit that references this issue
on Dec 12, 2016 - added a commit that references this issue
on Jan 22, 2017 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).
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.
7 remaining items
- added a commit that references this issue
on Jun 1, 2020 - added a commit that references this issue
on Nov 19, 2020 - added a commit that references this issue
on Feb 22, 2021 - added a commit that references this issue
on May 30, 2021 - added a commit that references this issue
on Jul 16, 2021 - added a commit that references this issue
on Aug 25, 2021 - added a commit that references this issue
on Apr 16, 2023 - added a commit that references this issue
on Feb 11, 2026 - added a commit that references this issue
on May 23, 2026
Is there any special design decisions why qstr's are referenced by index in a table, instead of direct pointers? Having extra indirection of course affects performance, especially for cached archs.
My first thought was about limiting value domain, but "qstr" type is still defined as uint, so generally takes same size as a pointer. Though I found that qstr's are stored in parse nodes as MP_PARSE_NODE_LEAF_ARG(pn), which takes 4 bits for kind. But for pointer that would mean that qstr should be 16-byte aligned. Probably too harsh for strings in constrained environment indeed. But on the other hand, if this is only required for parsing source code...
So, I wonder is there're more tricks/optimizations which assume that qstr's have limited value domain, of that's the only one?