Repository navigation
Unexpected performance on CPU heavy workload (string slices, concatenations and dict lookups) #16316
Description
Activity
Slowness comes from performing many lookups on a dictionary of size 58,110. When I rewrite the algorithm to store words of different lengths in different dictionaries (only keeping 2 at any time, largest of which has size 9396), micropython completes in less than 5 seconds! Could
hash_allocation_sizes[]be responsible for this performance cliff?(rewrite)
with open("corncob_lowercase.txt", "rt") as lines: words = [line.rstrip() for line in lines] words.sort(key=len) curr = {} prev = {} old = len(words[0]) maxlen = 1 for word in words: new = len(word) if new > old: old = new maxlen = max(maxlen, *curr.values()) prev = curr curr = {} curr[word] = max( prev.get(word[:i] + word[i+1:], 0) for i in range(new) ) + 1 print(max(maxlen, *prev.values(), *curr.values()))
Thanks for the report and detailed reproduction. I can reproduce the issue using the unix port.
For starters,
dict.fromkeys(words, 0)is slow, but still only a few seconds, so not the cause of the extreme slowness.The actual issue is the string operation in the inner loop. It's doing two slices and a string concatenation for each word times by the length of that word. If the average length of a word is 7 then it's doing roughly 58,000 * 7 of these string operations, and that's the issue.
Replacing
f"{word[:i]}{word[i+1:]}"with justwordthe program completes in under 1 minute.MicroPython does not have the best performance for string operations, and that would be the place to look to optimise this issue.
For the time being I suggest using a different algorithm that's not string heavy.
Slowness comes from performing many lookups on a dictionary of size 58,110
You are right, this is the main issue.
Doing just the string operations:
for word in words: list(f"{word[:i]}{word[i+1:]}" for i in range(len(word)))
it's very fast (less than 10 seconds).
Knowing very little about micropython's hash implementation, I naively tried extending
hash_allocation_sizes[]thusly and rebuilding:static const size_t hash_allocation_sizes[] = { 0, 2, 4, 6, 8, 10, 12, // +2 17, 23, 29, 37, 47, 59, 73, // *1.25 97, 127, 167, 223, 293, 389, 521, 691, 919, 1223, 1627, 2161, // *1.33 3229, 4831, 7243, 10861, 16273, 24407, 36607, 54907, 82351, 123517, // *1.5 };
(see last 2 entries and
uint16_t=>size_t). That doesn't seem to help.Replacing
f"{word[:i]}{word[i+1:]}"with justwordthe program completes in under 1 minute.The reason it runs much faster using just
wordis because the dict lookup ofwordalways succeeds, it's always in the dict. But the shortened word created by the f-string is usually not in the dict, and that is a lot slower because (1) the dict is 100% full, and (2) the search for something not in the full dict must go through the entire table. So the algorithm above is O(N^2), where N is the number of words.(MicroPython uses linear probing for the dict and allows the dict's table to get 100% because RAM is usually scarce.)
dict.fromkeys(words, 0)is slowThis is the other clue, and actually the root cause:
fromkeysasks for the size ofwordsand creates an empty dict with exactly that many slots in it. That means (1) it's very slow inserting the final elements because the table is close to 100% full, and (2) the dict that it returns will be very slow when looking up keys that do not exist.The fix for this issue is to make
fromkeysallocate a slightly larger initial table when the length of the input argument is known.A workaround for the time being for this issue is to insert a few extra elements into the result of
fromkeysand then remove them, to force a larger table and a rehash, eg:d = dict.fromkeys(words, 0) d['---0'] = None d['---1'] = None del d['---0'] del d['---1']
Here's a minimal reproduction of the issue:
numbers = list(range(50000)) d = dict.fromkeys(numbers, None) for _ in range(len(numbers)): d.get(-1) # lookup a value that doesn't exist in the dict
That takes around 30 seconds to run on the unix port. With the issue fixed (
fromkeysallocating a larger table) it takes a few milliseconds.Would a more robust fix involve a maxfill heuristic less than 100%?
Yes, in the implementation of
fromkeysit should allocate more than the length of the input argument.Doing some tests on how much more it should allocate (eg *3/2 or *9/8 or +100) the results vary a lot, it's all very sensitive to the size of the dict and what you put in it (how the hashing ends up placing items in the table). So I'm not sure what the best solution is.
- changed the title
[-]Unexpected performance on CPU heavy workload (string slices, concatenationss and dict lookups)[/-][+]Unexpected performance on CPU heavy workload (string slices, concatenations and dict lookups)[/+]on Aug 14, 2025
Port, board and/or hardware
pyscript, unix
MicroPython version
MicroPython 78d017f on 2024-11-27; linux [GCC 12.2.0] version
Reproduction
Visit https://pyscript.com/@janburgy/weird-performance/latest for pyscript version.
Otherwise download corncob_lowercase.txt then execute the following script with
-X heapsize=1024MExpected behaviour
The same script under cpython (3.11.2) on my aging chromebook completes in less than 500ms. Micropython was still running after several minutes (took more than 31 minutes to complete).
Observed behaviour
Micropython is significantly slower than cpython on this specific workload. I am unsure how to isolate the root cause.
Additional Information
No, I've provided everything above.
Code of Conduct
Yes, I agree