4 ms·

Show HN: Manually tracking a subscript isn't any faster than pop() in Python

2 points by logicallee 4y ago

Someone 4y ago
My educated guess would be that creating the list and, in particular, doing the shuffle using ‘random’ take most of the time. It’s 100 times 10,000,000 items, so going through a billion items. Iterating over that shouldn’t take more than a few seconds on modern hardware. Shuffling probably adds a billion calls to a random number generator. See also https://stackoverflow.com/questions/53378699/random-shuffle-very-slow-in-python-3-with-list https://stackoverflow.com/questions/53378699/random-shuffle-...
- logicallee 4y ago
  Ah, good point! I wonder what happens if I remove the shuffle...? :D
- logicallee 4y ago
  I tried removing the shuffle and got these results: Finished 100 runs of popping from 10000000 elements in 208.10663533210754 seconds. Finished 100 runs of manually 'popping' via headat tracking from 10000000 elements in 243.4968180656433 seconds. Which means that the shuffling code took about 80% of the runtime since including the shuffle took about 1000 seconds and now it's about 200 seconds. But if you look at the updated times I just quoted you see that pop()ing is still faster than manually incrementing a subscript! Tracking the pointer without any copying takes about 16% longer which is really hard for me to understand. How can all those memmoves still be faster than simply incrementing a subscript without changing or moving anything at all?
  - yorwba 4y ago
    You're only popping the last element, so no memmoves are required.
    - Someone 4y ago
      Indeed. https://docs.python.org/3/tutorial/datastructures.html https://docs.python.org/3/tutorial/datastructures.html: > If no index is specified, a.pop() removes and returns the last item in the list The speed up then (again an educated guess) is because the pop code dives into compiled C faster. I expect the other code to do more type checks. headat += 1, for example, has to check that headat is something to which you can add 1, and find the function to do that. ThePython compiler isn’t very smart and likely does that at runtime, and each time through the loop. Even if it doesn’t, Python‘s integers are arbitrary length, mak8ng the actual +1 code slower than C’s. (Also, for the education of the OP: if you want to benchmark, move all initialization out of the loop. There’s no need to include mylist = list(range(numtoshuffle)) in the timing, for example (and no need to create a new list every time through the loop))
      - logicallee 4y ago
        Thanks for all that. Finally I got the headat approach faster by removing shuffling, removing the range operation (just filling a list with ten million zeroes using mylist = [0] * 10000000), and hardcoding the constant for the size of the test as a literal 10000000 rather than a variable (ie headat < 10000000 rather than headat < numtopop). I couldn't remove the initialization code entirely since I'm approximating reading through a list, so in the pop() version, having the list is necessary for being able to do that (otherwise if the initialization is outside the run loop then how do you do the second loop loop after you've already pop()'ed every element). If I reused the same list for each run in the headat version it would be kind of like cheating, since the fundamental reason for this whole exercise is to speed up a monte carlo simulation that depends on shuffling and reading all the elements of a list, which is why I originally included that in the benchmarking code. Anyway even after I removed all that, the headat version is now just 3.2% faster and with everything hard-coded, without any shuffling, the whole thing stops being an approximation of anything actually useful for any real code. So the bottom line is that Python lists are plenty fast and there is no reason to try to do hamfisted optimization with runtime variables, as it doesn't get us any useful speedup.

2 points by logicallee 4y ago

My educated guess would be that creating the list and, in particular, doing the shuffle using ‘random’ take most of the time. It’s 100 times 10,000,000 items, so going through a billion items. Iterating over that shouldn’t take more than a few seconds on modern hardware. Shuffling probably adds a billion calls to a random number generator. See also https://stackoverflow.com/questions/53378699/random-shuffle-very-slow-in-python-3-with-list https://stackoverflow.com/questions/53378699/random-shuffle-...

logicallee 4y ago
Ah, good point! I wonder what happens if I remove the shuffle...? :D
logicallee 4y ago
I tried removing the shuffle and got these results: Finished 100 runs of popping from 10000000 elements in 208.10663533210754 seconds. Finished 100 runs of manually 'popping' via headat tracking from 10000000 elements in 243.4968180656433 seconds. Which means that the shuffling code took about 80% of the runtime since including the shuffle took about 1000 seconds and now it's about 200 seconds. But if you look at the updated times I just quoted you see that pop()ing is still faster than manually incrementing a subscript! Tracking the pointer without any copying takes about 16% longer which is really hard for me to understand. How can all those memmoves still be faster than simply incrementing a subscript without changing or moving anything at all?
- yorwba 4y ago
  You're only popping the last element, so no memmoves are required.
  - Someone 4y ago
    Indeed. https://docs.python.org/3/tutorial/datastructures.html https://docs.python.org/3/tutorial/datastructures.html: > If no index is specified, a.pop() removes and returns the last item in the list The speed up then (again an educated guess) is because the pop code dives into compiled C faster. I expect the other code to do more type checks. headat += 1, for example, has to check that headat is something to which you can add 1, and find the function to do that. ThePython compiler isn’t very smart and likely does that at runtime, and each time through the loop. Even if it doesn’t, Python‘s integers are arbitrary length, mak8ng the actual +1 code slower than C’s. (Also, for the education of the OP: if you want to benchmark, move all initialization out of the loop. There’s no need to include mylist = list(range(numtoshuffle)) in the timing, for example (and no need to create a new list every time through the loop))
    - logicallee 4y ago
      Thanks for all that. Finally I got the headat approach faster by removing shuffling, removing the range operation (just filling a list with ten million zeroes using mylist = [0] * 10000000), and hardcoding the constant for the size of the test as a literal 10000000 rather than a variable (ie headat < 10000000 rather than headat < numtopop). I couldn't remove the initialization code entirely since I'm approximating reading through a list, so in the pop() version, having the list is necessary for being able to do that (otherwise if the initialization is outside the run loop then how do you do the second loop loop after you've already pop()'ed every element). If I reused the same list for each run in the headat version it would be kind of like cheating, since the fundamental reason for this whole exercise is to speed up a monte carlo simulation that depends on shuffling and reading all the elements of a list, which is why I originally included that in the benchmarking code. Anyway even after I removed all that, the headat version is now just 3.2% faster and with everything hard-coded, without any shuffling, the whole thing stops being an approximation of anything actually useful for any real code. So the bottom line is that Python lists are plenty fast and there is no reason to try to do hamfisted optimization with runtime variables, as it doesn't get us any useful speedup.