Repository navigation
qstr uniqueness handling is overkill! #8
Description
Activity
Btw, did you consider design where some strings are interned and some not? I can say from my experiments (with other language) that non-interning design definitely spends more memory (there are lot of short strings which are used again). On the other hand, common sense says that wasting time to hash random strings destined just for printing makes no sense...
The implementation of qstr (unique strings) and it's use needs thought.
Using qstr's to store the string of an actual Python string object is a quick hack, really. We can change it so that Python string objects are not interned (turned into a qstr).
I wanted to have it so that the initial qstr's can be put in read-only memory. That is, have part of the qstr table fixed at compile time. This basically implements enums but with a string representation.
I'm brave enough to write a custom preprocessor if needed!
Using qstr's to store the string of an actual Python string object is a quick hack, really.
Well, string interning is a common design pattern since early LISP interpreters and to present day, as http://en.wikipedia.org/wiki/String_interning shows a lot of modern languages keep using it. What's more important for the case that unbloated languages like Lua or Squirrel also use it. So, interning in MicroPython is definitely not a quick hack, but adherence to the best practices ;-).
I did some testing on Squirrel (I spent hacking on it entire summer, and that's after ~2 years of consideration of whether I should bend me into Helsinki syndrome for Lua, try to continue with TinyPy or PyMite, or something else - yeah, I wish MicroPython came up a bit earlier ;-) ), and found that non-interning of strings leads to higher memory usage just for start up (i.e. just for initing method tables of objects and stuff) - something I didn't expect to be so noticeable even for interpreter startup. So, common sense says that interning is not always useful, but getting rid of it completely is unlikely a good idea.
I wanted to have it so that the initial qstr's can be put in read-only memory.
Great, then you understand my worry about both supporting hashability of strings and supporting it for static strings either. I wish there were a language which could sanely represent strings, arrays, dictionaries (well, dictionaries' static support is definitely needed, because that's how object methods/fields are supposed to be stored - though I didn't review that part of uPy code yet).
I did always plan to have qstr's hashed, but left that excercise for "some time down the road". Maybe that time is now :)
I would want to have the global qstr table part static (for known keywords/names like "len" and "range") and part dynamic (for method names, etc that the user has in their script).
Therefore, we need a way to have static hashing. Probably that means a custom preprocessor, or maybe just 1 file that is auto-generated and has all the static qstr's in it.
Finally, I think it's a good idea to have 2 different kinds of Python string objects: one that is represented as a qstr, and one that is represented as a normal dynamically allocated array of char's. Of course, the end user does not see any difference between the 2, as they both have the same methods and type signature. The qstr objects are ones that are made directly in the script (eg x = 'abc'), the array of char ones are made dynamically in the script, eg x= 'abc'+'def', and y = '{} {}'.format(1,2)
Maybe that time is now :)
Well, I didn't want to imply that everything should be dropped and this issue fixed ASAP ;-), just wanted to record issues I see as I go thru the code. It all should be ordered by priority, for example #14 is definitely more important.
I'm glad that we agree on the approach, and thanks for sharing other points like when to use interned vs raw strings - indeed, seems to be viable!
I'd suggest to take a chance and store length with string.
Actually, on a second thought (d'oh!) we must store length together with a string, because Python strings can contain '\0', so current implementation using strcmp() and friends isn't really compliant.
I didn't realise Python strings can contain '\0'... bytearray yes, but strings not. In the language reference it says strings can only contain "source characters", ie unicode characters in UTF-8 encoding. I didn't think '\0' was a unicode character.
But, a simple test in Python ('\000') shows indeed that you can have '\0' in a string.
If we want interned strings to live along side non-interned strings (in Python, in eg a dict), then, eg, interned
"abc"must hash to the same value as non-interned"abc". Thus we can't use the qstr ptr or qstr index of the interned string as the hash value. We must compute the hash of the actual data. And so, for efficiency, we need to store the hash of an interned string.Proposal: the first 4 bytes of the qstr are the hash. For compact memory storage it can be done the following way: first store the variably-encoded length, then optional hash bytes (the number of hash bytes depend on length of string), then the data. More explicitly (L=len byte, h=hash byte, d=data byte):
0 0 0 0 // empty string 1 h h d // 1 byte data 2 h d d // 2 bytes data 3 d d d // 3 bytes data L h d d d d ... // 4-7 bytes data L h h d d d ... // 8-127 bytes data L L h h d d d ... // when length needs 2 bytes to store it (eg 128 <= len <= 16383) L L L h d d d ... // when length needs 3 bytes to store itSuch data could be 4-byte aligned, or not.
Well, since the beginning of the discussion I had different layout in head, sorry if I doesn't come out clear - I indeed mixed up few things. Let me try to summarize what I had in mind with requirements behind it.
Requirements:
- All identifiers (keywords, buildtin object, function, method names) in uPy core are interned - it means that comparison by ptr gives 100% probability of match/mismatch.
- It should be possible to intern/check internship of any string - quickly. This means that we should do match by hash and to strcmp() only if hashes match.
- Minimal practical size of hash is one byte. That would theoretically give 256x speed up on string comparisons, but let's go conservative and (arbitrarily) say we'll get only 100x speedup due to imperfection of hash function. Still good enough for _Micro_Python IMHO. (If you're concerned that 8 bits of hash are too few, see below).
- We should support non-interned strings. Then, if they're used as keys for a dictionary, we can't rely on ptr, so would need to use hash value. That means that storage layout of interned and non-interned string should include hash => it (storage layout can be the same).
- Hash function is expected to be quick, which means that if you loop over string for some reason, you can in parallel compute hash. But there's still important usecase when: a) we get a string from outside (I/O) as is, i.e. won't necessarily iterate over it; b) a string can be long (consider read(64K) or read(1M)), c) hash is needed only for few operations (dictionary lookup is the only 100% case). That calls for condition that hashing of non-interned can be lazy, and we need to signify "hash is not computed" case.
This leads to following layout
hash (1 byte) - as hash has fixed size (1 byte), it can go first (also, hash is the most discriminating string param, and *p is more efficient than *(p+N) for some CPUs) flags and len lsbyte (1byte): bit 7: hash_valid, bit 6: more_length, bits 5-0: length lsbits (potentially, store few more flags here) more length: if bit 6 of previous byte set, another len byte is here, if its bit 7 is set, another len byte follows, etc. data: len bytes C-compatible \0 term: 1 byte - we would need to go a bit out of way to get rid of it, could NOT do that.That means that minimal-length non-empty string would be 4 bytes, which matches 32bit CPU alignment.
Extra features:
- Concern: 8 bits of hash too few, for example, consider hash table with > 256s slots. Well, we can use following length byte as additional discriminator to get 16 bits of "hash". For _micro_python, that's definitely enough.
- Actually, when doing string search, as optimization, we can match on 32-bit values at the beginning of the string. Beginnings of string ideally should be 32-bit aligned, but note that's the strict requirement only for Coretx-M0 & (classical) MIPS (dunno about Sparc, would assume too), but Cortex-M3 and higher and x86 can handle non-aligned access transparently.
Nice argumentation, I like it :-) Only point, since we have already the
string lenght, I would not store C-style null-terminated strings, but
instead I would use Pascal-style (lenght prefixed) strings that would solve
the problem of storing null characters in the middle of an string and also
improve security requiring us to use length-requiring functions (strncmp
instead of strcmp, for example).http://en.wikipedia.org/wiki/String_%28computer_science%29#Representations
http://stackoverflow.com/questions/7648947/declaring-pascal-style-strings-in-c2014/1/10 Paul Sokolovsky [email protected]
Well, since the beginning of the discussion I had different layout in
head, sorry if I doesn't come out clear - I indeed mixed up few things. Let
me try to summarize what I had in mind with requirements behind it.Requirements:
- All identifiers (keywords, buildtin object, function, method names)
in uPy core are interned - it means that comparison by ptr gives 100%
probability of match/mismatch. - It should be possible to intern/check internship of any string -
quickly. This means that we should do match by hash and to strcmp() only if
hashes match. - Minimal practical size of hash is one byte. That would
theoretically give 256x speed up on string comparisons, but let's go
conservative and (arbitrarily) say we'll get only 100x speedup due to
imperfection of hash function. Still good enough for _Micro_Python
IMHO. (If you're concerned that 8 bits of hash are too few, see below). - We should support non-interned strings. Then, if they're used as
keys for a dictionary, we can't rely on ptr, so would need to use hash
value. That means that storage layout of interned and non-interned string
should include hash => it (storage layout can be the same). - Hash function is expected to be quick, which means that if you loop
over string for some reason, you can in parallel compute hash. But there's
still important usecase when: a) we get a string from outside (I/O) as is,
i.e. won't necessarily iterate over it; b) a string can be long (consider
read(64K) or read(1M)), c) hash is needed only for few operations
(dictionary lookup is the only 100% case). That calls for condition that
hashing of non-interned can be lazy, and we need to signify "hash is not
computed" case.
This leads to following layout
hash (1 byte) - as hash has fixed size (1 byte), it can go first (also, hash is the most discriminating string param, and *p is more efficient than *(p+N) for some CPUs)
flags and len lsbyte (1byte): bit 7: hash_valid, bit 6: more_length, bits 5-0: length lsbits (potentially, store few more flags here)
more length: if bit 6 of previous byte set, another len byte is here, if its bit 7 is set, another len byte follows, etc.
data: len bytes
C-compatible \0 term: 1 byte - we would need to go a bit out of way to get rid of it, could NOT do that.That means that minimal-length non-empty string would be 4 bytes, which
matches 32bit CPU alignment.Extra features:
- Concern: 8 bits of hash too few, for example, consider hash table with
256s slots. Well, we can use following length byte as additional
discriminator to get 16 bits of "hash". For _micro_python, that's
definitely enough.
2. Actually, when doing string search, as optimization, we can match on
32-bit values at the beginning of the string. Beginnings of string ideally
should be 32-bit aligned, but note that's the strict requirement only for
Coretx-M0 & (classical) MIPS (dunno about Sparc, would assume too), but
Cortex-M3 and higher and x86 can handle non-aligned access transparently.—
Reply to this email directly or view it on GitHubhttps://github.com//issues/8#issuecomment-32069605
."Si quieres viajar alrededor del mundo y ser invitado a hablar en un monton
de sitios diferentes, simplemente escribe un sistema operativo Unix."
– Linus Tordvals, creador del sistema operativo Linux- All identifiers (keywords, buildtin object, function, method names)
Only point, since we have already the string lenght, I would not store C-style null-terminated strings
Well, want I meant is that C compiler will store \0 for any literal string anyway. The only way to get around that is to use array init syntax:
char foo[4] = "\x03foo"will get you "Pascal-style" string of exactly 4 bytes length. Butsome_func("\x03foo")andchar *s = "\x03foo"will actually store in flash 5-byte string. For the purpose of our discussion, that trailing \0 is just a padding byte, driven into picture just to argument the acceptance of the fact that minimal size of string would be 4 bytes, which in turn enables potential optimization of comparing string headers as int32_t values.We of course not going to store \0 for dynamic strings (not coming from string literals). For example, dynamic string of 6 bytes will take strictly 8 bytes (6 bytes content + 1 byte hash + 1 byte (small) len).
I see. So, you are saying that it shouldn't give any problems beside adding
the end null character, isn't it?Send from my Samsung Galaxy Note II
El 10/01/2014 23:31, "Paul Sokolovsky" [email protected] escribió:Only point, since we have already the string lenght, I would not store
C-style null-terminated stringsWell, want I meant is that C compiler will store \0 for any literal string
anyway. The only way to get around that is to use array init syntax: char
foo[4] = "\x03foo" will get you "Pascal-style" string of exactly 4 bytes
length. But some_func("\x03foo") and char s = ""\x03foo"" will actually
store in flash 5-byte string. For the purpose of our discussion, that
trailing \0 is just a padding byte, driven into picture just to argument
the acceptance of the fact that minimal size of string would be 4 bytes,
which in turn enables *potential optimization of comparing string
headers as int32_t values.We of course not going to store \0 for dynamic strings (not coming from
string literals). For example, dynamic string of 6 bytes will take strictly
8 bytes (6 bytes content + 1 byte hash + 1 byte (small) len).—
Reply to this email directly or view it on GitHubhttps://github.com//issues/8#issuecomment-32073160
.One use of storing the null byte at the end is so you can parse strings without having to always check that you are within the string data boundaries. Eg, so long as I'm not looking for the null character, I can do a look-ahead check for some character, knowing that if I get a match then that match is before the end of the string (else I would hit the null character and not get a match).
Anyway, adding the null byte is a small issue.
In the end, I think @pfalcon and I argee with most things, it's just the way we are saying it.
- I think we should use 2 hash bytes, and use the length as the second byte (ie
H L ...). - We need hash for 2 things: to quickly lookup a string in the intern pool, to check if it's there or not; and as a hash value so it can be inserted into a dictionary.
- The ability to have interned and non-interned strings in the same dictionary makes it a bit ugly/inefficient. If it was all interned, you could just check pointers for equality (and even use pointers as the hash value). But with a mix of interned/non-interned, you now need to check the actual values for equality (ie the string bytes). Using a hash value speeds this up, but if the hashes match you still need to check the bytes (eg using strcmp). In the current implementation of
mp_map_tit actually has a flag to tell when the map has all interned strings, or not. So this is not really an issue, but something to be aware of. - Is it really worth doing lazy hash evaluation for non-interned strings? Just compute the hash when you create the string and that's it. If hash is quick, O(N), this won't be too bad (since O(N) already for creation).
- I think we should use 2 hash bytes, and use the length as the second byte (ie
We need hash for 2 things: to quickly lookup a string in the intern pool, to check if it's there or not; and as a hash value so it can be inserted into a dictionary.
Yeah, I can't immediately come up with other uses for hash (for example, comparing 2 non-interned strings, we don't need to compute hash - we can use it if it's there, but otherwise, computing hash will take ~ same amount of time as comparing chars directly). But those 2 uses are rather important to warrant having hash in qstr.
The ability to have interned and non-interned strings in the same dictionary makes it a bit ugly/inefficient.
Well, we're not JavaScript here - python dicts can contain arbitrary type of keys, so we won't get around using object hash for that. And with all-interned optimization that you have, we're golden IMHO.
Is it really worth doing lazy hash evaluation for non-interned strings? Just compute the hash when you create the string and that's it. If hash is quick, O(N), this won't be too bad (since O(N) already for creation).
Well, I gave example where hash calc is superfluous and expensive - file.read() a big string, then write it somewhere. On our side it's O < O(N) (only allocation time, which is O(1) with ideal allocator). Then OS will read in string for us. It won't compute hash in parallel with reading, so we'll need to do that afterwards, spending O(N) time, which will be waste if we won't use that string as a key in dict. But I agree this case is an optimization, not giving (too) much for MCU case, so we can leave it for later.
Another adv of adding byte length as part of string - then strcmp can cmpare this first and fail if not same.
Question - this is just for Qstr right so never get unicode in here. My question is related to possibility of swelling struct by one more byte for type of string. so (H L T ...)38 remaining items
- added a commit that references this issue
on Apr 25, 2024 - added a commit that references this issue
on Sep 21, 2024 - added a commit that references this issue
on Nov 21, 2025 - added a commit that references this issue
on Dec 29, 2025 - added 2 commits that reference this issue
on May 23, 2026 - added a commit that references this issue
on Sep 21, 2026
Well, checking each string using strcmp() against inter pool obviously has quadratic complexity - on creation on each string, which is often in a dynamic language. That's not a good design choice, not even for small systems, not even as initial implementation, to be optimized later. Please don't follow Espruino way where dead simple algorithms lead to speed of program depend on number of spaces in source.
So, there definitely should be hashing. Here's my suggestion:
Now, I may imagine one of the reason hashing, etc. wasn't added right away. It's definitely nice to be able to do qstr_from_str_static("foo"), and know this doesn't waste any single byte more than absolutely needed. But now hash and length would need to be part of string, or otherwise they should be computed at runtime, and stored in RAM (oh no!).
With C++11, it might be possible to deal with that in compile-time automagically using constexpr's. But C macros are obviously won't help here. So, general way to solve that would be to have custom preprocessor which replace "macros" like HSTR(hash, len, "foo") with HSTR("\xff", "\x03", "foo").
Are you brave enough to go for something like that? ;-)
(Extra note: As you also use C99, I tried to look for a way to (ab)use compound literals, but there doesn't seem to be a way to create static compound literal).