qstr uniqueness handling is overkill! #8

pfalcon · 2013-12-29T22:28:50Z

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:

Wasting much memory on hash is not good either. Single byte is enough to make a great difference. Yes, that will limit efficiency of very large hash tables, but well, the talk is about handling real-word case and scaling down, for real-world and scaling up there's CPython after all. But see below anyway.
I'd suggest to take a chance and store length with string. That's obviously useful for len(), for comparison, and for hash tables too, effectively adding more bits (maybe not as uniformly spread as hash). It's harder to figure out how to store it. It's definitely not good to store 4 bytes of it (using 32-bit speak). Arbitrary limits on string length are not good either. Variable-length encoding is the only good choice then - that's still will be much faster then strlen().

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

pfalcon · 2013-12-29T22:46:23Z

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

dpgeorge · 2013-12-29T23:20:35Z

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!

pfalcon · 2013-12-30T03:08:58Z

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

dpgeorge · 2013-12-30T17:25:13Z

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)

pfalcon · 2013-12-31T16:52:05Z

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!

pfalcon · 2013-12-31T16:54:58Z

I'd suggest to take a chanc 8000 e 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.

dpgeorge · 2014-01-02T18:04:28Z

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.

dpgeorge · 2014-01-10T12:59:00Z

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 it

Such data could be 4-byte aligned, or not.

pfalcon · 2014-01-10T21:47:50Z

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.

piranna · 2014-01-10T22:12:08Z

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

2014/1/10 Paul Sokolovsky notifications@github.com

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

pfalcon · 2014-01-10T22:30:23Z

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

piranna · 2014-01-10T23:28:56Z

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" notifications@github.com escribió:

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

dpgeorge · 2014-01-10T23:44:50Z

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_t it 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).

pfalcon · 2014-01-11T00:14:27Z

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.

Neon22 · 2014-01-11T01:39:28Z

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

pfalcon · 2014-01-11T01:54:18Z

this is just for Qstr right so never get unicode in here

Per previous discussion, qstr is generic container type for any immutable strings. It can be bytes, utf-8, utf-16, utf-32, etc.

My question is related to possibility of swelling struct by one more byte for type of string

We definitely don't want to swell it by whole byte, but above I already proposed to add few more bits to first varlen byte (to still keep 2 bytes of overhead for short strings).

So, it would be: bit 7 - "hash not valid", bits 6-5: content type (00 - bytes, 01 - utf-8, 10, 11 - reserved for custom implementations), bit 4 - "more length bytes", bits 3-0 - length lsbits.

dpgeorge · 2014-01-11T10:56:11Z

Yes, we can add bits to indicate the type, if needed.

I think I just want to get the framework for this up and running first (ie a custom "preprocessor" that works out the static const hashes, etc), and then we can work out exactly what bits of information we need to store.

pfalcon · 2014-01-11T11:14:17Z

custom "preprocessor"

I had an idea how to implement that much more automagical than I first thought. For reference, I thought we'd need something like:

Q("\x12", "\x03", "foo")

each time in source we need a static hash-len qstr, and preprocessor would go thru each source file and update it in place to make sure hash and length values are actual.

Well, no need for that Q("foo") in source and a generate header will be enough for 99% cases.

pfalcon · 2014-01-11T11:17:53Z

But first let's consider how we can get automagical interned static strings. As I said, having all keywords/identifiers used in source to be interned string should be one of the top goals of refactor, and here's how to get it for free (i.e. compile-time, not runtime).

The keyword is string pooling, which is on by default in gcc (and apparently not even turnable off any longer). Demo of the idea:

#include <stdio.h>

void foo(const char *s)
{
    printf("%p ", s);
    if (s == "foo")
        printf("matched!");
    printf("\n");
}

struct entry {
    char *key;
    char *val;
};

const char arr[] = "foo";
const char *ptr = "foo";
const struct entry table[2] = {
    {"foo", "sth"},
    {NULL}
};

int main()
{
    printf("#1 literal\n");
    foo("foo");
    printf("#2 pointer\n");
    foo(ptr);
    printf("#3 pointer in struct\n");
    foo(table[0].key);
    printf("#4 array\n");
    foo(arr);
}

So, as you see, only array syntax produces non-pooled string value, other string syntaxes are automagically "interned" in C app string table.

pfalcon · 2014-01-11T11:18:40Z

And now impl of hash-len strings:

#include <stdio.h>

#define Q(str) QH_##str QL_##str #str

#define QH_foo "\x55"
#define QL_foo "\x03"

#define QH_1 "\xaa"
#define QL_1 "\x01"

void foo(const char *s)
{
    printf("%p ", s);
    if (s == Q(foo))
        printf("matched!");
    printf("\n");
}

const char *ptr = Q(foo);

int main()
{
    printf("#1 literal\n");
 
8000
   foo(Q(foo));
    printf("#2 pointer\n");
    foo(ptr);
    Q(1);
}

pfalcon · 2014-01-11T11:21:09Z

So, preprocessor would need to just go thru source and generate separate header with

#define QH_foo "\x55"
#define QL_foo "\x03"

defines. This will work for any string which contains identifier-clean chars (may even start with digits). Again, my guess that covers 99%f our needs. If we ever need to hash-len "+" or something, we can precompute hash by hand, and just put "\xNN" "\x01" "+" in source for such exceptional case ;-)

dpgeorge · 2014-01-11T13:09:03Z

Nice.

Problem: we are relying heavily on the way gcc optimises strings. What if a particular C compiler for another architecture behaves differently? Then some qstrs match, and some don't.

What about:

#include <stdio.h>

#define Q_DEF(s) const char qstr_##s[] = "\x12\x34" #s;

#define Q(s) qstr_##s

Q_DEF(foo)
Q_DEF(1)

void foo(const char *s) {
    printf("%p ", s);
    if (s == Q(foo))
        printf("matched!");
    printf("\n");
}

const char *ptr = Q(foo);

int main(void) {
    printf("#1 literal\n");
    foo(Q(foo));
    printf("#2 pointer\n");
    foo(ptr);
    Q(1);
}

The idea would be to generate the Q_DEF.

dr2chase · 2014-01-11T15:05:36Z

Perhaps late to the party:

Would you consider
byte 1 = hash (and if hash is not valid, is zero, but some valid hashes can have zero here)
byte 2, bit 7 = more_length (short strings always have hash computed, they are short)
byte 2, bit 6 = is UTF8
byte 2, bits 5-0 = len lsbits

For longer strings, record hash_is_set in bit 6 of byte 3
byte 3, bit 7 = more_length
byte 3, bit 6 = hash_is_valid

A minor detail, but yes, Sparc likes 32-bit aligned 32-bit words.

One difficulty is the possibility that a non-Unicode string and a Unicode string might encode the same
letters; if there are 8-bit characters, those require multiple bytes in Unicode, but only one byte in ASCII.
Do we care about this when interning?

Does the len describe the length in characters or the data length in bytes?
Not necessarily the same for Unicode.

No matter what:
Use a mathematically good hash function, I'll see if I can find a cheap fast one in the public domain.
"Universal" hash functions based on GF(2^8) are better than a poke in the eye with a sharp stick.
Seems perfectly fine to define that the zero-length string has a hash function of zero, therefore it can
be represented in as few as 2 bytes (if not doing the zero termination thing) or 3 (if zero terminating).
It might be worthwhile to consider aligning strings only to a 16-bit boundary, depending on how we
feel about "micro".

On 2014-01-10, at 4:47 PM, Paul Sokolovsky notifications@github.com wrote:

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 MicroPython 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 micropython, 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.

—
Reply to this email directly or view it on GitHub.

dhylands · 2014-01-11T18:50:13Z

They way gcc optimizes strings also changes from time to time (as newer ways of doing things are discovered). So you might find that micropython starts to behave differently on a newer version of the toolchain.

pfalcon · 2014-01-11T20:46:01Z

#define Q_DEF(s) const char qstr_##s[] = "\x12\x34" #s;

Yes, natural progression of the idea. And by using arrays, we'll even be able to get rid of trailing \0 if needed.

pfalcon · 2014-01-11T20:59:59Z

For longer strings, record hash_is_set in bit 6 of byte 3

Probably not in default source, but you can make your fork, profile it, and share results of how much speed up you get while using such highly conditional encoding ;-).

One difficulty is the possibility that a non-Unicode string and a Unicode string; if there are 8-bit characters,

Python3 doesn't have non-unicode strings and 8-bit characters. Sadly. When hashing unicode strings (in any encoding), we'd rather hash chars (aka codepoints), not bytes. Note that currently uPy doesn't support unicode at all, so any suggestions are wishful thinking so far.

Does the len describe the length in characters or the data length in bytes?
Supposedly all the time in bytes, so we know what to pass to m_free() when garbage-collecting.

Use a mathematically good hash function

You're welcome to criticize one which will be used at the beginning (I vote for xor :-D ) and submit patches for alternatives (profiling data is plus) ;-).

It might be worthwhile to consider aligning strings only to a 16-bit boundary, depending on how we feel about "micro".

Per the above discussion, "performance-optimized" build would align on 32-bit boundary. But ideally we'd support 8-bit. Also note that GC implementation used has own alignment requirements.

piranna · 2014-01-11T21:11:39Z

Use a mathematically good hash function

You're welcome to criticize one which will be used at the beginning (I
vote for xor :-D ) and submit patches for alternatives (profiling data is
plus) ;-).

I was thinking about CRC-8...

dr2chase · 2014-01-12T02:11:27Z

On 2014-01-11, at 4:00 PM, Paul Sokolovsky notifications@github.com wrote:

Use a mathematically good hash function

You're welcome to criticize one which will be used at the beginning (I vote for xor :-D ) and submit patches for alternatives (profiling data is plus) ;-).

I don't have scads of time, or I would.
I have my own hacking and benchmarking to do for work.
What would be nice is to avoid standardizing on a poor hash
function, which is common practice. XOR is not so awesome.

I agree with Jesus that CRC-8 is a fine candidate.
It can be implemented with a 256-byte lookup table.
See http://www.miscel.dk/MiscEl/CRCcalculations.html#CRC8bi
for examples.

There are also good "bit shufflers" that I know less
about, a friend of mine knows more an I can ask him
for pointers.

Given that this is microPython, what are processors
that should be targeted for good performance?
Some of these processors (e.g., Intel Haswell)
have instructions that can be used to provide a nice
acceleration for CRC calculations on large strings.
But that might be silly.

pfalcon · 2014-01-12T02:47:50Z

XOR is not so awesome.

XOR is horrible. Only ADD is worse. But XOR+ROL would give good baseline to compare more "advanced" algos against.

It can be implemented with a 256-byte lookup table.

That's huge surely?

Given that this is microPython, what are processors that should be targeted for good performance?

For me it's simple: target not processors, but algorithms (large-scale, not just few features out of hundreds). Performance should be better than Lua and better than Node.js, or we won't take over the world ;-).

Some of these processors (e.g., Intel Haswell) have instructions

Who cares? ;-) Nobody will waste their tiny free time left from their work and real life to support somebody's magic instructions from press releases ;-).

Note: everything is just IMHO ;-).

dpgeorge · 2014-01-22T11:44:19Z

I kinda thought that we switch to qstr-in-mp_obj_t altogether, and thought that we could handle internship implicitly.

Okay, now I understand fully what you meant! You wanted a string object to always be a raw pointer stuffed into an mp_obj_t, with bit 1 set to indicate this. The only difference between static/interned and dynamic is just where it pointed: ROM or RAM. The representation is the same. And that's why you were concerned about specifiying the encoding (UTF-8, UTF-16, ASCII) in the qstr data.

I now see that wouldn't work for dynamically created interned strings, so what you say is good plan.

Okay, now I don't understand this statement. Why won't your original idea work? (One thing I can say is that it doesn't play nice with the GC, since the pointer to a dynamic string is not a proper pointer that the GC will recognise.)

Note that with my way of doing it, the only performance hit is that a dynamic string needs only an extra word (or 2) in RAM, and that you need to distinguish between qstrs and dynamic strings. The storage for the dynamic string would like mp_obj_tulpe_t: a uPy header then the actual data (plus any extra info you wanted, like len and alloc). So there's no additional ptr dereference to get the data from the uPy object.

But with that in mind, that's only partial implementation of what we discussed above. My idea was to make any static string used in uPy (except those used just for output, like printf) to have size/hash embedded. Then for all such string we'd get implicit compile-time internship, which would simplify builtin methods handling, etc.

This would only work with help from the compiler (and its constant pooling optimisation), something I don't want to rely on. But actually even this is not enough: to dynamically intern a string I need a list of all static interned strings so I can see if the string already exists in the intern pool. If we have implicit interning in, eg, method definitions, there's no way we can tell which strings have been statically interned (without looking into the .rodata section at runtime, which is going to be very compiler dependent...).

The only (?) solution to this (to stick with your idea) is to no longer require that qstrs are unique. A qstr is just a pointer to some data with a hash, len, and bytes. To check for equality, the hash and the data must match, ie we need to do a full strcmp for (at least) each successful lookup.

For efficient equality comparison of qstrs (eg method & attr lookup) we need to guarantee that qstrs are unique, so that 2 qstrs are equal if and only if their pointers (or indexes, as is done now) match.

At the moment we can actually have method names as qstrs: just add the string to the qstrdefs.h file and use the constant MP_QSTR_xxx where xxx is your string value. I think this is a neat solution.

pfalcon · 2014-01-22T16:07:19Z

Okay, now I understand fully what you meant! You wanted a string object to always be a raw pointer stuffed into an mp_obj_t, with bit 1 set to indicate this.

Not exactly, per #22, I wanted to come up with a grand unified scheme of storing string-like data. Then when you introduced qstr-in-mp_obj_t, I thus automagically thought about switching to qstr-in-mp_obj_t, which was logical mistake on my side.

The only difference between static/interned and dynamic is just where it pointed: ROM or RAM. Okay, now I don't understand this statement. Why won't your original idea work?

Well, we also have dynamic interned strings. My idea was that we intern any dictionary-key like string, and so if we for example take a string from dictionary key, we know it's interned. But here's where it breaks: if we pass such string to another function, it no longer know if it's interned or not (in general case; it may happen that we'd pass interned string to functions where non-interned can never be passed, but that's too many if's for now).

Note that with my way of doing it, the only performance hit is that a dynamic string needs only an extra word (or 2) in RAM

Well, pointer to type + pointer to data is minimal overhead we can achieve, and if it goes beyond that (for example, to store length in object structure), then my original IMHO was that it's inefficient use of mem (that's why I wanted to use same encoding (which includes var-len len encoding) for all string objects).

The storage for the dynamic string would like mp_obj_tulpe_t: a uPy header then the actual data (plus any extra info you wanted, like len and alloc).

And this is not ok per my previous thought: any non-interned string can become interned whenever it is used as a key in dictionary. If the operation of turning non-interned string into interned requires memory allocation (to build hash+len header), then it's not efficient. That's why I wanted to have same underlying encoding for all strings.

My mistake is that I called such encoding [new] qstr, because I thought we can replace old qstr with this new encoding in one go. It's better to keep "qstr" for what it is now (and index into interning table), and use for example "hstr" for string with hash+varlen header.

This would only work with help from the compiler (and its constant pooling optimisation), something I don't want to rely on.

Above we found a way how to do our own constant string pooling without relying on compiler ;-).

But actually even this is not enough: to dynamically intern a string I need a list of all static interned strings so I can see if the string already exists in the intern pool.

Sure, but now that we have custom preprocessor, we can do any magic, like building any structures we want automatically!

The only (?) solution to this (to stick with your idea) is to no longer require that qstrs are unique. A qstr is just a pointer to some data with a hash, len, and bytes.

Yes, that's the idea I had stuck in my head ;-). Except that all static (i.e. compile-time) strings are automagically interned using a constant pool (maintained by custom preprocessor to avoid relying on compiler behavior).

To check for equality, the hash and the data must match, ie we need to do a full strcmp for (at least) each successful lookup.

Yes, that's the operation we'd do to intern a dynamic string.

At the moment we can actually have method names as qstrs: just add the string to the qstrdefs.h file and use the constant MP_QSTR_xxx where xxx is your string value. I think this is a neat solution.

Yes, but my whole idea was to make that all automatic. You just write Q(write) straight in the source code and you get static interned string object which is always ==-equal to any other Q(write) object written in the source code elsewhere. All MP_QSTR_xxx, etc. magic is handled by preprocessor behind the scenes. (Note: Q() above has nothing to do with Q() as used in current source, sorry again for confusion. Maybe it should be H() ;-) )

All in all: what we have now (especially with today's patch) is good enough, and we can pause and start leveraging binary-safe strings (and do other things). I'll follow up with my ideas, and try to implement them, paying attention to details, and if everything actually fall into place, will submit patches for review.

dpgeorge · 2014-01-22T18:44:05Z

Note that we cannot intern a non-interned string just to do a dictionary lookup. Dict lookups (a pure lookup, fail if not found) must not allocate memory (else it becomes another banned operation in interrupts, etc). If you do a dict lookup of a non-interned string and you try to intern it, then, even if it is stored with hash/len/etc, you might still need to allocate a new qstr pool to point to this new interned string.

*: Heading to 2015-09-08

475 pindefs added to ugfx ginput

dpgeorge · 2017-06-07T03:11:05Z

This can be closed: qstrs now have a hash and a length stored with them, this data is generated automatically, and strings don't need to be interned (and are usually not interned if their length is above a threshold).

curlyz · 2018-08-15T17:18:36Z

@dpgeorge May I ask what is the threshold ?

#ifndef MICROPY_ALLOC_PARSE_INTERN_STRING_LEN
#define MICROPY_ALLOC_PARSE_INTERN_STRING_LEN (10)
#endif

I thought that string with len > 10 will not be interned , but apprently not .
Also , every random variables name (that is not defined) when typed in REPL will also be interned.
Although the variable is not created , the interned string is there already .

Should we implement some special character to imply that the string should not be interned .
I expect that it is not Pythonic , but considering the limited RAM of embedded device , should we ?

dpgeorge · 2018-08-17T04:18:46Z

I thought that string with len > 10 will not be interned , but apprently not .

That's right, strings with len>10 are not interned.

Also , every random variables name (that is not defined) when typed in REPL will also be interned.
Although the variable is not created , the interned string is there already .

Yes, all variable names are interned. But that's not the same as strings.

Eg:

$ micropython
MicroPython v1.9.4-474-g2e3e5707b-dirty on 2018-08-17; linux version
Use Ctrl-D to exit, Ctrl-E for paste mode
>>> import micropython
>>> micropython.qstr_info(1)
qstr pool: n_pool=1, n_qstr=1, n_str_data_bytes=24, n_total_bytes=216
Q(/usr/lib/micropython)
>>> short_var = 1
>>> long_variable_name = 2
>>> 'short str'
'short str'
>>> 'longer string'
'longer string'
>>> micropython.qstr_info(1)
qstr pool: n_pool=1, n_qstr=4, n_str_data_bytes=72, n_total_bytes=264
Q(/usr/lib/micropython)
Q(short_var)
Q(long_variable_name)
Q(short str)

You can see that 'longer string' is not interned.

update from adafruit

… to include PR micropython#8 Signed-off-by: Christopher Arndt <chris@chrisarndt.de>

machine.pin.c: Some modifications to the Pin module

Merge latest changes

Add strings for morph

asan considers that memcmp(p, q, N) is permitted to access N bytes at each of p and q, even for values of p and q that have a difference earlier. Accessing additional values is frequently done in practice, reading 4 or more bytes from each input at a time for efficiency, so when completing "non_exist<TAB>" in the repl, this causes a diagnostic: ==16938==ERROR: AddressSanitizer: global-buffer-overflow on address 0x555555cd8dc8 at pc 0x7ffff726457b bp 0x7fffffffda20 sp 0x7fff READ of size 9 at 0x555555cd8dc8 thread T0 #0 0x7ffff726457a (/usr/lib/x86_64-linux-gnu/libasan.so.5+0xb857a) #1 0x555555b0e82a in mp_repl_autocomplete ../../py/repl.c:301 #2 0x555555c89585 in readline_process_char ../../lib/mp-readline/re #3 0x555555c8ac6e in readline ../../lib/mp-readline/readline.c:513 #4 0x555555b8dcbd in do_repl /home/jepler/src/micropython/ports/uni #5 0x555555b90859 in main_ /home/jepler/src/micropython/ports/unix/ #6 0x555555b90a3a in main /home/jepler/src/micropython/ports/unix/m #7 0x7ffff619a09a in __libc_start_main ../csu/libc-start.c:308 #8 0x55555595fd69 in _start (/home/jepler/src/micropython/ports/uni 0x555555cd8dc8 is located 0 bytes to the right of global variable 'import_str' defined in '../../py/repl.c:285:23' (0x555555cd8dc0) of size 8 'import_str' is ascii string 'import ' Signed-off-by: Jeff Epler <jepler@gmail.com>

asan considers that memcmp(p, q, N) is permitted to access N bytes at each of p and q, even for values of p and q that have a difference earlier. Accessing additional values is frequently done in practice, reading 4 or more bytes from each input at a time for efficiency, so when completing "non_exist<TAB>" in the repl, this causes a diagnostic: ==16938==ERROR: AddressSanitizer: global-buffer-overflow on address 0x555555cd8dc8 at pc 0x7ffff726457b bp 0x7fffffffda20 sp 0x7fff READ of size 9 at 0x555555cd8dc8 thread T0 #0 0x7ffff726457a (/usr/lib/x86_64-linux-gnu/libasan.so.5+0xb857a) micropython#1 0x555555b0e82a in mp_repl_autocomplete ../../py/repl.c:301 micropython#2 0x555555c89585 in readline_process_char ../../lib/mp-readline/re micropython#3 0x555555c8ac6e in readline ../../lib/mp-readline/readline.c:513 micropython#4 0x555555b8dcbd in do_repl /home/jepler/src/micropython/ports/uni micropython#5 0x555555b90859 in main_ /home/jepler/src/micropython/ports/unix/ micropython#6 0x555555b90a3a in main /home/jepler/src/micropython/ports/unix/m micropython#7 0x7ffff619a09a in __libc_start_main ../csu/libc-start.c:308 micropython#8 0x55555595fd69 in _start (/home/jepler/src/micropython/ports/uni 0x555555cd8dc8 is located 0 bytes to the right of global variable 'import_str' defined in '../../py/repl.c:285:23' (0x555555cd8dc0) of size 8 'import_str' is ascii string 'import ' Signed-off-by: Jeff Epler <jepler@gmail.com>

Although the original motivation given for the workaround[1] is correct, nlr.o and nlrthumb.o are linked with a small enough distance that the problem does not occur, and the workaround isn't necessary. The distance between the b instruction and its target (nlr_push_tail) is just 64 bytes[2], well within the ±2046 byte range addressable by an unconditional branch instruction in Thumb mode. The workaround induces a relocation in the text section (textrel), which isn't supported everywhere, notably not on musl-libc, where it causes a crash on start-up. With the workaround removed, micropython works on an ARMv5T Linux built with musl-libc. [1]: commit dd376a2 Author: Damien George <damien.p.george@gmail.com> Date: Fri Sep 1 15:25:29 2017 +1000 py/nlrthumb: Get working again on standard Thumb arch (ie not Thumb2). "b" on Thumb might not be long enough for the jump to nlr_push_tail so it must be done indirectly. [2]: Excerpt from objdump -d micropython: 000095c4 <nlr_push_tail>: 95c4: b510 push {r4, lr} 95c6: 0004 movs r4, r0 95c8: f02d fd42 bl 37050 <mp_thread_get_state> 95cc: 6943 ldr r3, [r0, micropython#20] 95ce: 6023 str r3, [r4, #0] 95d0: 6144 str r4, [r0, micropython#20] 95d2: 2000 movs r0, #0 95d4: bd10 pop {r4, pc} 000095d6 <nlr_pop>: 95d6: b510 push {r4, lr} 95d8: f02d fd3a bl 37050 <mp_thread_get_state> 95dc: 6943 ldr r3, [r0, micropython#20] 95de: 681b ldr r3, [r3, #0] 95e0: 6143 str r3, [r0, micropython#20] 95e2: bd10 pop {r4, pc} 000095e4 <nlr_push>: 95e4: 60c4 str r4, [r0, micropython#12] 95e6: 6105 str r5, [r0, micropython#16] 95e8: 6146 str r6, [r0, micropython#20] 95ea: 6187 str r7, [r0, micropython#24] 95ec: 4641 mov r1, r8 95ee: 61c1 str r1, [r0, micropython#28] 95f0: 4649 mov r1, r9 95f2: 6201 str r1, [r0, micropython#32] 95f4: 4651 mov r1, sl 95f6: 6241 str r1, [r0, micropython#36] @ 0x24 95f8: 4659 mov r1, fp 95fa: 6281 str r1, [r0, micropython#40] @ 0x28 95fc: 4669 mov r1, sp 95fe: 62c1 str r1, [r0, micropython#44] @ 0x2c 9600: 4671 mov r1, lr 9602: 6081 str r1, [r0, micropython#8] 9604: e7de b.n 95c4 <nlr_push_tail> Signed-off-by: Jonathan Neuschäfer <j.neuschaefer@gmx.net>

Although the original motivation given for the workaround[1] is correct, nlr.o and nlrthumb.o are linked with a small enough distance that the problem does not occur, and the workaround isn't necessary. The distance between the b instruction and its target (nlr_push_tail) is just 64 bytes[2], well within the ±2046 byte range addressable by an unconditional branch instruction in Thumb mode. The workaround induces a relocation in the text section (textrel), which isn't supported everywhere, notably not on musl-libc, where it causes a crash on start-up. With the workaround removed, micropython works on an ARMv5T Linux system built with musl-libc. [1]: commit dd376a2 Author: Damien George <damien.p.george@gmail.com> Date: Fri Sep 1 15:25:29 2017 +1000 py/nlrthumb: Get working again on standard Thumb arch (ie not Thumb2). "b" on Thumb might not be long enough for the jump to nlr_push_tail so it must be done indirectly. [2]: Excerpt from objdump -d micropython: 000095c4 <nlr_push_tail>: 95c4: b510 push {r4, lr} 95c6: 0004 movs r4, r0 95c8: f02d fd42 bl 37050 <mp_thread_get_state> 95cc: 6943 ldr r3, [r0, micropython#20] 95ce: 6023 str r3, [r4, #0] 95d0: 6144 str r4, [r0, micropython#20] 95d2: 2000 movs r0, #0 95d4: bd10 pop {r4, pc} 000095d6 <nlr_pop>: 95d6: b510 push {r4, lr} 95d8: f02d fd3a bl 37050 <mp_thread_get_state> 95dc: 6943 ldr r3, [r0, micropython#20] 95de: 681b ldr r3, [r3, #0] 95e0: 6143 str r3, [r0, micropython#20] 95e2: bd10 pop {r4, pc} 000095e4 <nlr_push>: 95e4: 60c4 str r4, [r0, micropython#12] 95e6: 6105 str r5, [r0, micropython#16] 95e8: 6146 str r6, [r0, micropython#20] 95ea: 6187 str r7, [r0, micropython#24] 95ec: 4641 mov r1, r8 95ee: 61c1 str r1, [r0, micropython#28] 95f0: 4649 mov r1, r9 95f2: 6201 str r1, [r0, micropython#32] 95f4: 4651 mov r1, sl 95f6: 6241 str r1, [r0, micropython#36] @ 0x24 95f8: 4659 mov r1, fp 95fa: 6281 str r1, [r0, micropython#40] @ 0x28 95fc: 4669 mov r1, sp 95fe: 62c1 str r1, [r0, micropython#44] @ 0x2c 9600: 4671 mov r1, lr 9602: 6081 str r1, [r0, micropython#8] 9604: e7de b.n 95c4 <nlr_push_tail> Signed-off-by: Jonathan Neuschäfer <j.neuschaefer@gmx.net>

Although the original motivation given for the workaround[1] is correct, nlr.o and nlrthumb.o are linked with a small enough distance that the problem does not occur, and the workaround isn't necessary. The distance between the b instruction and its target (nlr_push_tail) is just 64 bytes[2], well within the ±2046 byte range addressable by an unconditional branch instruction in Thumb mode. The workaround induces a relocation in the text section (textrel), which isn't supported everywhere, notably not on musl-libc[3], where it causes a crash on start-up. With the workaround removed, micropython works on an ARMv5T Linux system built with musl-libc. [1]: commit dd376a2 Author: Damien George <damien.p.george@gmail.com> Date: Fri Sep 1 15:25:29 2017 +1000 py/nlrthumb: Get working again on standard Thumb arch (ie not Thumb2). "b" on Thumb might not be long enough for the jump to nlr_push_tail so it must be done indirectly. [2]: Excerpt from objdump -d micropython: 000095c4 <nlr_push_tail>: 95c4: b510 push {r4, lr} 95c6: 0004 movs r4, r0 95c8: f02d fd42 bl 37050 <mp_thread_get_state> 95cc: 6943 ldr r3, [r0, micropython#20] 95ce: 6023 str r3, [r4, #0] 95d0: 6144 str r4, [r0, micropython#20] 95d2: 2000 movs r0, #0 95d4: bd10 pop {r4, pc} 000095d6 <nlr_pop>: 95d6: b510 push {r4, lr} 95d8: f02d fd3a bl 37050 <mp_thread_get_state> 95dc: 6943 ldr r3, [r0, micropython#20] 95de: 681b ldr r3, [r3, #0] 95e0: 6143 str r3, [r0, micropython#20] 95e2: bd10 pop {r4, pc} 000095e4 <nlr_push>: 95e4: 60c4 str F987 r4, [r0, micropython#12] 95e6: 6105 str r5, [r0, micropython#16] 95e8: 6146 str r6, [r0, micropython#20] 95ea: 6187 str r7, [r0, micropython#24] 95ec: 4641 mov r1, r8 95ee: 61c1 str r1, [r0, micropython#28] 95f0: 4649 mov r1, r9 95f2: 6201 str r1, [r0, micropython#32] 95f4: 4651 mov r1, sl 95f6: 6241 str r1, [r0, micropython#36] @ 0x24 95f8: 4659 mov r1, fp 95fa: 6281 str r1, [r0, micropython#40] @ 0x28 95fc: 4669 mov r1, sp 95fe: 62c1 str r1, [r0, micropython#44] @ 0x2c 9600: 4671 mov r1, lr 9602: 6081 str r1, [r0, micropython#8] 9604: e7de b.n 95c4 <nlr_push_tail> [3]: https://www.openwall.com/lists/musl/2020/09/25/4 Signed-off-by: Jonathan Neuschäfer <j.neuschaefer@gmx.net>

Although the original motivation given for the workaround[1] is correct, nlr.o and nlrthumb.o are linked with a small enough distance that the problem does not occur, and the workaround isn't necessary. The distance between the b instruction and its target (nlr_push_tail) is just 64 bytes[2], well within the ±2046 byte range addressable by an unconditional branch instruction in Thumb mode. The workaround induces a relocation in the text section (textrel), which isn't supported everywhere, notably not on musl-libc[3], where it causes a crash on start-up. With the workaround removed, micropython works on an ARMv5T Linux system built with musl-libc. This commit changes nlrthumb.c to use a direct jump by default, but leaves the long jump workaround as an option for those cases where it's actually needed. [1]: commit dd376a2 Author: Damien George <damien.p.george@gmail.com> Date: Fri Sep 1 15:25:29 2017 +1000 py/nlrthumb: Get working again on standard Thumb arch (ie not Thumb2). "b" on Thumb might not be long enough for the jump to nlr_push_tail so it must be done indirectly. [2]: Excerpt from objdump -d micropython: 000095c4 <nlr_push_tail>: 95c4: b510 push {r4, lr} 95c6: 0004 movs r4, r0 95c8: f02d fd42 bl 37050 <mp_thread_get_state> 95cc: 6943 ldr r3, [r0, micropython#20] 95ce: 6023 str r3, [r4, #0] 95d0: 6144 str r4, [r0, micropython#20] 95d2: 2000 movs r0, #0 95d4: bd10 pop {r4, pc} 000095d6 <nlr_pop>: 95d6: b510 push {r4, lr} 95d8: f02d fd3a bl 37050 <mp_thread_get_state> 95dc: 6943 ldr r3, [r0, micropython#20] 95de: 681b ldr r3, [r3, #0] 95e0: 6143 str r3, [r0, micropython#20] 95e2: bd10 pop {r4, pc} 000095e4 <nlr_push>: 95e4: 60c4 str r4, [r0, micropython#12] 95e6: 6105 str r5, [r0, micropython#16] 95e8: 6146 str r6, [r0, micropython#20] 95ea: 6187 str r7, [r0, micropython#24] 95ec: 4641 mov r1, r8 95ee: 61c1 str r1, [r0, micropython#28] 95f0: 4649 mov r1, r9 95f2: 6201 str r1, [r0, micropython#32] 95f4: 4651 mov r1, sl 95f6: 6241 str r1, [r0, micropython#36] @ 0x24 95f8: 4659 mov r1, fp 95fa: 6281 str r1, [r0, micropython#40] @ 0x28 95fc: 4669 mov r1, sp 95fe: 62c1 str r1, [r0, micropython#44] @ 0x2c 9600: 4671 mov r1, lr 9602: 6081 str r1, [r0, micropython#8] 9604: e7de b.n 95c4 <nlr_push_tail> [3]: https://www.openwall.com/lists/musl/2020/09/25/4 Signed-off-by: Jonathan Neuschäfer <j.neuschaefer@gmx.net>

Although the original motivation given for the workaround[1] is correct, nlr.o and nlrthumb.o are linked with a small enough distance that the problem does not occur, and the workaround isn't necessary. The distance between the b instruction and its target (nlr_push_tail) is just 64 bytes[2], well within the ±2046 byte range addressable by an unconditional branch instruction in Thumb mode. The workaround induces a relocation in the text section (textrel), which isn't supported everywhere, notably not on musl-libc[3], where it causes a crash on start-up. With the workaround removed, micropython works on an ARMv5T Linux system built with musl-libc. This commit changes nlrthumb.c to use a direct jump by default, but leaves the long jump workaround as an option for those cases where it's actually needed. [1]: commit dd376a2 Author: Damien George <damien.p.george@gmail.com> Date: Fri Sep 1 15:25:29 2017 +1000 py/nlrthumb: Get working again on standard Thumb arch (ie not Thumb2). "b" on Thumb might not be long enough for the jump to nlr_push_tail so it must be done indirectly. [2]: Excerpt from objdump -d micropython: 000095c4 <nlr_push_tail>: 95c4: b510 push {r4, lr} 95c6: 0004 movs r4, r0 95c8: f02d fd42 bl 37050 <mp_thread_get_state> 95cc: 6943 ldr r3, [r0, micropython#20] 95ce: 6023 str r3, [r4, #0] 95d0: 6144 str r4, [r0, micropython#20] 95d2: 2000 movs r0, #0 95d4: bd10 pop {r4, pc} 000095d6 <nlr_pop>: 95d6: b510 push {r4, lr} 95d8: f02d fd3a bl 37050 <mp_thread_get_state> 95dc: 6943 ldr r3, [r0, micropython#20] 95de: 681b ldr r3, [r3, #0] 95e0: 6143 str r3, [r0, micropython#20] 95e2: bd10 pop {r4, pc} 000095e4 <nlr_push>: 95e4: 60c4 str r4, [r0, micropython#12] 95e6: 6105 str r5, [r0, micropython#16] 95e8: 6146 str r6, [r0, micropython#20] 95ea: 6187 str r7, [r0, micropython#24] 95ec: 4641 mov r1, r8 95ee: 61c1 str r1, [r0, micropython#28] 95f0: 4649 mov r1, r9 95f2: 6201 str r1, [r0, micropython#32] 95f4: 4651 mov r1, sl 95f6: 6241 str r1, [r0, micropython#36] @ 0x24 95f8: 4659 mov r1, fp 95fa: 6281 str r1, [r0, micropython#40] @ 0x28 95fc: 4669 mov r1, sp 95fe: 62c1 str r1, [r0, micropython#44] @ 0x2c 9600: 4671 mov r1, lr 9602: 6081 str r1, [r0, micropython#8] 9604: e7de b.n 95c4 <nlr_push_tail> [3]: https://www.openwall.com/lists/musl/2020/09/25/4 Signed-off-by: J. Neuschäfer <j.ne@posteo.net>

Although the original motivation given for the workaround[1] is correct, nlr.o and nlrthumb.o are linked with a small enough distance that the problem does not occur, and the workaround isn't necessary. The distance between the b instruction and its target (nlr_push_tail) is just 64 bytes[2], well within the ±2046 byte range addressable by an unconditional branch instruction in Thumb mode. The workaround induces a relocation in the text section (textrel), which isn't supported everywhere, notably not on musl-libc[3], where it causes a crash on start-up. With the workaround removed, micropython works on an ARMv5T Linux system built with musl-libc. This commit changes nlrthumb.c to use a direct jump by default, but leaves the long jump workaround as an option for those cases where it's actually needed. [1]: commit dd376a2 Author: Damien George <damien.p.george@gmail.com> Date: Fri Sep 1 15:25:29 2017 +1000 py/nlrthumb: Get working again on standard Thumb arch (ie not Thumb2). "b" on Thumb might not be long enough for the jump to nlr_push_tail so it must be done indirectly. [2]: Excerpt from objdump -d micropython: 000095c4 <nlr_push_tail>: 95c4: b510 push {r4, lr} 95c6: 0004 movs r4, r0 95c8: f02d fd42 bl 37050 <mp_thread_get_state> 95cc: 6943 ldr r3, [r0, micropython#20] 95ce: 6023 str r3, [r4, #0] 95d0: 6144 str r4, [r0, micropython#20] 95d2: 2000 movs r0, #0 95d4: bd10 pop {r4, pc} 000095d6 <nlr_pop>: 95d6: b510 push {r4, lr} 95d8: f02d fd3a bl 37050 <mp_thread_get_state> 95dc: 6943 ldr r3, [r0, micropython#20] 95de: 681b ldr r3, [r3, #0] 95e0: 6143 str r3, [r0, micropython#20] 95e2: bd10 pop {r4, pc} 000095e4 <nlr_push>: 95e4: 60c4 str r4, [r0, micropython#12] 95e6: 6105 str r5, [r0, micropython#16] 95e8: 6 1241 146 str r6, [r0, micropython#20] 95ea: 6187 str r7, [r0, micropython#24] 95ec: 4641 mov r1, r8 95ee: 61c1 str r1, [r0, micropython#28] 95f0: 4649 mov r1, r9 95f2: 6201 str r1, [r0, micropython#32] 95f4: 4651 mov r1, sl 95f6: 6241 str r1, [r0, micropython#36] @ 0x24 95f8: 4659 mov r1, fp 95fa: 6281 str r1, [r0, micropython#40] @ 0x28 95fc: 4669 mov r1, sp 95fe: 62c1 str r1, [r0, micropython#44] @ 0x2c 9600: 4671 mov r1, lr 9602: 6081 str r1, [r0, micropython#8] 9604: e7de b.n 95c4 <nlr_push_tail> [3]: https://www.openwall.com/lists/musl/2020/09/25/4 Signed-off-by: J. Neuschäfer <j.ne@posteo.net>

Although the original motivation given for the workaround[1] is correct, nlr.o and nlrthumb.o are linked with a small enough distance that the problem does not occur, and the workaround isn't necessary. The distance between the b instruction and its target (nlr_push_tail) is just 64 bytes[2], well within the ±2046 byte range addressable by an unconditional branch instruction in Thumb mode. The workaround induces a relocation in the text section (textrel), which isn't supported everywhere, notably not on musl-libc[3], where it causes a crash on start-up. With the workaround removed, micropython works on an ARMv5T Linux system built with musl-libc. This commit changes nlrthumb.c to use a direct jump by default, but leaves the long jump workaround as an option for those cases where it's actually needed. [1]: commit dd376a2 Author: Damien George <damien.p.george@gmail.com> Date: Fri Sep 1 15:25:29 2017 +1000 py/nlrthumb: Get working again on standard Thumb arch (ie not Thumb2). "b" on Thumb might not be long enough for the jump to nlr_push_tail so it must be done indirectly. [2]: Excerpt from objdump -d micropython: 000095c4 <nlr_push_tail>: 95c4: b510 push {r4, lr} 95c6: 0004 movs r4, r0 95c8: f02d fd42 bl 37050 <mp_thread_get_state> 95cc: 6943 ldr r3, [r0, micropython#20] 95ce: 6023 str r3, [r4, #0] 95d0: 6144 str r4, [r0, micropython#20] 95d2: 2000 movs r0, #0 95d4: bd10 pop {r4, pc} 000095d6 <nlr_pop>: 95d6: b510 push {r4, lr} 95d8: f02d fd3a bl 37050 <mp_thread_get_state> 95dc: 6943 ldr r3, [r0, micropython#20] 95de: 681b ldr r3, [r3, #0] 95e0: 6143 str r3, [r0, micropython#20] 95e2: bd10 pop {r4, pc} 000095e4 <nlr_push>: 95e4: 60c4 str r4, [r0, micropython#12] 95e6: 6105 str r5, [r0, micropython#16] 95e8: 6146 str r6, [r0, micropython#20] 95ea: 6187 str r7, [r0, micropython#24] 95ec: 4641 mov r1, r8 95ee: 61c1 str r1, [r0, micropython#28] 95f0: 4649 mov r1, r9 95f2: 6201 str r1, [r0, micropython#32] 95f4: 4651 mov r1, sl 95f6: 6241 str r1, [r0, micropython#36] @ 0x24 95f8: 4659 mov r1, fp 95fa: 6281 str r1, [r0, micropython#40] @ 0x28 95fc: 4669 mov r1, sp 95fe: 62c1 str r1, [r0, micropython#44] @ 0x2c 9600: 4671 mov r1, lr 9602: 6081 str r1, [r0, micropython#8] 9604: e7de b.n 95c4 <nlr_push_tail> [3]: https://www.openwall.com/lists/musl/2020/09/25/4 Signed-off-by: J. Neuschäfer <j.ne@posteo.net>

Chananyah mentioned this issue Jan 2, 2014

The unix version crashes #38

Closed

robert-hh mentioned this issue Dec 16, 2015

Control-C isn't handled in all cases #1722

Closed

EcmaXp added a commit to OpenPythons/micropython-opencom-legacy that referenced this issue Aug 28, 2016

Merge pull request micropython#8 from micropython/master

a5491fc

*: Heading to 2015-09-08

drrk pushed a commit to drrk/micropython that referenced this issue Jan 22, 2017

Merge pull request micropython#8 from emfcamp/gtoggle_multiboard

6bcf3dc

475 pindefs added to ugfx ginput

dpgeorge closed this as completed Jun 7, 2017

elfman2 mentioned this issue Jul 1, 2017

Enable btree duplicate key functionality #3187

Closed

kamtom480 pushed a commit to kamtom480/micropython that referenced this issue Jun 24, 2020

Merge pull request micropython#8 from adafruit/main

6fd2472

update from adafruit

SpotlightKid added a commit to SpotlightKid/micropython that referenced this issue Jun 24, 2020

Update submodule for BLACK_F407ZG board definition from upstream repo…

fbb912b

… to include PR micropython#8 Signed-off-by: Christopher Arndt <chris@chrisarndt.de>

retryfail pushed a commit to retryfail/micropython that referenced this issue Aug 20, 2020

Merge pull request micropython#8 from robert-hh1/w600_pin

dc7a80d

machine.pin.c: Some modifications to the Pin module

tannewt referenced this issue in tannewt/circuitpython Feb 13, 2021

Merge pull request #8 from adafruit/main

984f1a1

Merge latest changes

WeActStudio pushed a commit to WeActStudio/micropython that referenced this issue Feb 14, 2021

Merge pull request micropython#8 from kwagyeman/openmv

f6783f1

Add strings for morph

neuschaefer mentioned this issue Apr 27, 2023

py/nlrthumb: Make non-Thumb2 workaround opt-in. #11353

Merged

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

qstr uniqueness handling is overkill! #8

qstr uniqueness handling is overkill! #8

qstr uniqueness handling is overkill! #8

qstr uniqueness handling is overkill! #8

Comments