How Fast is Python's Sort? Performance Testing 

I try to include a more general lesson in my videos beyond the answer to the title!

you could say it is a merge of merge and insertion, or just inmergion, which happens to sound like immersion which is a similar concept.

Thanks for mentioning, that's named after Tim Peters by the way!

@@_trbr I have memoized this answer.

thanks for the kind words!

Thanks for the kind words!

Great to hear!

Cool sched_yield trick! Hmm... I read somewhere that process_time_ns should not be used for performance testing because it is less accurate than perf_counter, despite having the same resolution, I'll have to look into it. It certainly wouldn't be a good idea if your code ever intentionally sleeps, but I suppose it just depends on what you are trying to measure.

@@mCoding Yeah, guess it does depend on what you're trying to measure. If you're trying to get a sense for how long a running process is going to take (e.g. updating a progress bar), you'd want to use perf_counter, since there, you _want_ the figures to account for and scheduling congestion. Something like process_time, on the other hand, isn't even _trying_ to be an accurate representation of how much wall time a program using that algorithm might take - the only purpose is getting a low-noise relative estimate of a process's "cumulative cpu utilization" (which is really the main thing thing we care about when doing algorithm A/B testing).

enjoy!

The biggest part of learning is not how to learn something new but how to think about something you already know.

Do you mean the function and function2 difference? It's likely because of having a cold system cache. Look up "cache warming" to read more on this.

Indeed, from listobject.c in CPython: /* Avoid malloc for small temp arrays. */ #define MERGESTATE_TEMP_SIZE 256 This is the cause.

TL;DR: It's probably because exponential search, which is used to merge already sorted parts of the array, uses powers of 2. Not quite sure what's going on with random strings (it may have to do with the fact that they are compared symbol by symbol), but here's the deal with almost sorted ints. The algorithm used in Python is Timsort (en.wikipedia.org/wiki/Timsort). This algorithm tries to take advantage of runs (consecutive elements that are **already sorted**) that are present in real-world data. It keeps track of three runs and merges two of them whenever necessary. While merging, if it encounters the situation where it thinks a large chunk of a final merged run will be taken from one run, it tries jumping further in the run to see if it can find the position where it can skip to to start using another run, using exponential search/galloping (en.wikipedia.org/wiki/Exponential_search), which uses powers of 2, example below. And hey, this situation of a bunch of runs in the data is exactly what we see with almost ordered data like these ints. Exponential search example: We have a run that begins like [1,2,3,4,5,6,7,....] and another one, which begins like [396,397,398,...]. We've already checked 7 elements of the first run, and we still haven't used anything from the second one. Then, let's try jumping to the 15th element in the first run (let's call that [15]). Let's say we see 15 there. Then we can try jumping to [31]. Let's say we see 31 there. Ok, then we jump to [63]. We see 401 there. 401 > 396. Now we search where we need to start using the second run to make our final merged run using binary search (en.wikipedia.org/wiki/Binary_search) (the position is between [31] and [63] in this case). In these tests we make exactly 10 swaps. It means that as list sizes get larger we get less randomness in the list (since more numbers end up in runs). At some points randomness becomes small enough for the algorithm to utilize exponential search better and better. Try increasing the number of swaps - those dips will only start popping up much later, with larger sizes. I tried using 1 swap, and the first dip appeared at size 64 already, but with 100 swaps there were no dips up to 1000 (I didn't bother checking for larger sizes), which is not surprising since our average run size becomes ~10, which is kinda small, so the algorithm rightfully decides to avoid galloping when merging runs. Now, I'm not exactly sure *why* these dips happen at powers of 2, but I'm assuming it's because the algorithm decides minimum run size using powers of 2 and the list length to increase efficiency (see wiki), plus average run sizes become just large enough at these sizes for the algorithm to efficiently use galloping, since more numbers end up in order. For example at size 127 with 8 swaps the average run size is =16, so the algorithm decides it should use it. At sizes like 16 with 8 swaps the average run size is

Glad you liked it!

We can guess the answer from the source code, from listobject.c: /* Avoid malloc for small temp arrays. */ #define MERGESTATE_TEMP_SIZE 256

@@mCoding Thanks!

@@mCoding Shouldn't that produce upward jumps not downwards ones?

@@jbaidley I wonder. It's implying that malloc is somehow faster than putting the variables on the stack. Maybe that is due to freeing and reallocating (test order again) in which case malloc can actually get significantly faster (stackoverflow.com/questions/41869662/is-malloc-faster-when-i-freed-memory-before). Not sure if at that point it would be faster than the stack but who knows? To allocate the array on the stack you need to shift the stack pointer whereas when you just get the pointer from `malloc` there is no shifting.

@@jbaidley I suspect that is where TimSort changes strategies from a strategy better suited for small lists (such as insertion sort) to a strategy that has extra overhead but is faster for larger lists.

Much faster. It's optimized and I heard the sorting algorithm python uses "timsort" is a little faster than a regular quicksort on sorted data.

Indeed, builtins are much faster than writing it yourself, and timsort is closer in spirit to a stable mergesort.

Numpy probably wins over built ins if you use numpy arrays thanks to vectorization in the implementation

This is just matplotlib. Search for the "Legend Picking" example, which shows you how to make it so you can click on lines in the legend to toggle the plots on/off. I also threw in an ax.relim and ax.autoscale_view to make the axes auto adjust on toggle. See the github code for details!

@@mCoding thanks!! Will do :)

Yep!

Thank you! I'm finding it is a small world lately! But lots to learn no matter what!

Python is a dynamic language and will always be, but type hints that can be checked _before_ running the code is a huge win. Remember that code is read typically many more times than it is written. Type hints are a great way to communicate to the reader what your intentions are. And if you actually check your type hints with a static analyzer, then you can catch bugs _before_ you run the code. No more "you forgot to pass an argument" or "wrong order of arguments" or "passed a str but expected bytes" errors.

@@mCoding Plus, editors can benefit from the type hints to provide autocomplete!

The Pycharm builtin theme "Darcula"

@@mCoding Thank you very much

Thanks!

Unfortunately there is no way to do this accurately. The best we can do is use the high precision clock time.perf_counter or time.perf_counter_ns, but an alpha particle can hit your CPU at any time and slow a single execution down at any time, so you really need to run things multiple times. Also your operating system decides when Python gets CPU cycles, so it can just randomly decide to make Python wait. You can see this in some of the graphs where there is a huge spike relative to nearby points.

@@mCoding i meant time.process_time(), it gets the time passed in the processed, and it doesn't matter if the os made python wait

I appreciate it!

Glad you think so!

Thank you!

I was more interested in accurate measurements than saving space in this video. If you want to use exponential spacing (which would be necessary if you wanted to test a higher upper limit) feel free to run it yourself and just change the sizes list!

At the same time keep in mind "how much performance do I need?". Readable code is better than fastly executable code if the refactoring time is high. Doing things through classes may have some pitfalls but if the code is easier to read (provided a new hire has a good comprehension of OOP concepts) then it may be worth the slight performance impact, especially if the size of input is small. We should also be cognizant of code needing updates over time as we learn edge cases or work with new hardware/software. So just as its important to measure worst case, we also should look at best case and the average case to determine when to refactor/update our code.

@@MagnumCarta yes only in performance critical code should such tricks be considered

Since we measure things in a binary fashion (each bit of data is either 0 or 1, two possible values), it is easy for outside radiation to potentially cause a bit to flip. This is how electromagnetic fields can cause data corruption. Think of measuring a bit as either 0 or 1 as a case of saying "is the voltage level above {{ THRESHOLD_AMOUNT }} ?". Where "THRESHOLD_AMOUNT" is something like 0.5 Volts (the actual figure can vary so don't rely on just that particular value, it is a case example commonly seen in textbooks talking about voltage levels of circuits). And the "{{ }}" is a Python style way of implementing the value of a variable (where THRESHOLD_AMOUNT=0.5). So if we were to read the value and it is above that amount (e.g. 0.5) we just arbitrarily say it is a 1 else it is a 0. Even a slight uptick in the amount at some point in time from an outside radio wave could cause the voltage level to increase to the point of the threshold we're measuring for.

Knowing Python's sort is n log n doesn't really answer the question. As I mention in the video, it depends on many many other factors that are not captured from the time complexity. E.g. 1000000 n log n and 3 n log n are both O(n log n), but one is much worse than the other. And even if you knew it was 3 n log n, this still doesn't take into account cache performance and many other things that can vary the speed of an algorithm by factors of 10000.

@@mCoding python’s sorting algorithm is O(n) but yeah there are lots of other factors

Which are machine specific of course

@@rban123 > sorting > O(n) It’s time for your evening medication and electroshock therapy, sir.

Zing! This is why you gotta test yourself!