Repository navigation
Unexpected performance on CPU heavy workload (string slices, concatenations and dict lookups) #16316
Description
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=1024M
with open("corncob_lowercase.txt", "rt") as lines:
words = [line.rstrip() for line in lines]
words.sort(key=len)
maxlen = dict.fromkeys(words, 0)
for word in words:
maxlen[word] = max(
maxlen.get(f"{word[:i]}{word[i+1:]}", 0) for i in range(len(word))
) + 1
print(max(maxlen.values()))Expected 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
Activity
jburgy commentedon Nov 27, 2024
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)
dpgeorge commentedon Nov 28, 2024
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.
dpgeorge commentedon Nov 28, 2024
You are right, this is the main issue.
Doing just the string operations:
it's very fast (less than 10 seconds).
jburgy commentedon Nov 28, 2024
Knowing very little about micropython's hash implementation, I naively tried extending
hash_allocation_sizes[]thusly and rebuilding:(see last 2 entries and
uint16_t=>size_t). That doesn't seem to help.dpgeorge commentedon Nov 29, 2024
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.)
This 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:dpgeorge commentedon Nov 29, 2024
Here's a minimal reproduction of the issue:
That takes around 30 seconds to run on the unix port. With the issue fixed (
fromkeysallocating a larger table) it takes a few milliseconds.jburgy commentedon Nov 29, 2024
Thanks for getting to the bottom of this, @dpgeorge ! I, for one, am rather impressed by your kludge-around. Would a more robust fix involve a maxfill heuristic less than 100%?
dpgeorge commentedon Nov 30, 2024
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.
[-]Unexpected performance on CPU heavy workload (string slices, concatenationss and dict lookups)[/-][+]Unexpected performance on CPU heavy workload (string slices, concatenations and dict lookups)[/+]