3 ms·
It is! Although my test case is probably an unrealistically bad scenario: It's the classic, why is processing sorted array faster than unsorted one def f(
by exyi 1y ago
It is! Although my test case is probably an unrealistically bad scenario:
It's the classic, why is processing sorted array faster than unsorted one
def f(arr):
r = True
for x in arr:
if x > 128: r = not r
return r
arr = [ random.randint(0, 255) for i in range(0, 1000_000) ]
arr_sorted = list(sorted(arr))
%timeit f(arr)
%timeit f(arr_sorted)
Results are (on my machine): 17.5 ms for unsorted, and 13.5 ms for sorted. For comparison, in a compiled language, the difference is 4x
- ammar2 1y agoEdit: Analyzed the wrong thing earlier. This depends on the Python version, but if it has the specializing interpreter changes, the `COMPARE_OP` comparing the integers there is probably hitting a specialized `_COMPARE_OP_INT` [1]. This specialization has a ternary that does `res = (sign_ish & oparg) ? PyStackRef_True : PyStackRef_False;`. This might be the branch that ends up getting predicted correctly? Older versions of Python go through a bunch of dynamic dispatch first and then end up with a similar sort of int comparison in `long_richcompare`. [2] [1] https://github.com/python/cpython/blob/561965fa5c8314dee5b86586ffa16c1f369d1fa2/Python/bytecodes.c#L2614-L2633 https://github.com/python/cpython/blob/561965fa5c8314dee5b86... [2] https://github.com/python/cpython/blob/561965fa5c8314dee5b86586ffa16c1f369d1fa2/Objects/longobject.c#L3590-L3592 https://github.com/python/cpython/blob/561965fa5c8314dee5b86...
- GBhpkmY 1y ago[dead]
- cma 1y agoPython speed up is probably from small integer caching, a sorted array will have runs of pointers to the same integers adjacent. The compiled language one is probably branch prediction right?
- exyi 1y agoI intentionally stayed in the small integer range to avoid benchmarking the cache. 256 distinct values should fit into L1 just fine in both cases. I'm now thinking that the difference might be even larger if we instead avoid small integers and let the CPU get stuck chasing pointers. The idea is that it gets stuck on a memory access, which forces it to speculate much further, which in turn makes it backtrack a longer path if a branch was mispredicted. I'm obviously no expert on this, feel free to correct me The results for 1B range instead of 255 are 17.6 ms for unsorted / 68.2 ms for sorted! We are back to what the original article observed and it's a way stronger effect than what branch prediction can offer. So don't sort your arrays, keep them in the order the boxed values were allocated ;)
- cma 1y agoHow big is the pointed to small integer? With alignment etc. I'm seeing some stuff saying 256 of them would fill an 8KB L1. Plus other stuff for the interpreter might overfill it. Sorted that would be less of an issue. Larger range one being slower unsorted yes makes sense because of allocation order no longer matching the iteration order.
- exyi 1y agoI don't know how large are those boxes, but normal CPU L1 cache has 32 or 48KB which should be plenty for this. Python opcodes for this program are going to be tiny, and the interpreter itself uses the instruction-L1 cache (which is another 32-48KB). I hope the sequential scan of the big array won't flush the L1 cache (there should be 12-way associativity with LRU, so I don't see how it could). Anyway, there is no need to have 256 integers, just 2 is enough. When I try that, the results are similar: 17.5 ms (unsorted) / 12.5 ms (sorted)
- 1y ago
- LPisGood 1y agoThis is a really good example. It is more like branch prediction than standard data/instruction caching. I wonder if you could do Spectre type vulnerabilities in python. You would need some way to leak micro-architectural state, so without being particularly clever maybe python code could only be used as a gadget or something.