Why is a loop on list slice faster than range()?

user_243099 0
Viewed 189

See the following code:

from timeit import timeit
import random 


for size in (10 ** 3, 10 ** 4, 10 ** 5, 10 ** 6):
    print('---')
    nums = [random.randint(1, 10000000) for i in range(size)]
    l = len(nums)    
    sp = l // 2

    def with_slice(): 
        for n in nums[sp:]:
            pass

    def pure_loop(): 
        for i in range(sp, l):
            pass        
        
    def no_slice(): 
        for i in range(sp, l):
            n = nums[i]
            
        
    for method in (with_slice, pure_loop, no_slice):
        print(f'Size={size:<10} method={method.__name__:<20} time={timeit(method, number=300)} ms')

The test results:

---
Size=1000       method=with_slice           time=0.003086836077272892 ms
Size=1000       method=pure_loop            time=0.00524100661277771 ms
Size=1000       method=no_slice             time=0.01368624996393919 ms
---
Size=10000      method=with_slice           time=0.031104332767426968 ms
Size=10000      method=pure_loop            time=0.05062220152467489 ms
Size=10000      method=no_slice             time=0.12812853325158358 ms
---
Size=100000     method=with_slice           time=0.35493253357708454 ms
Size=100000     method=pure_loop            time=0.5190340830013156 ms
Size=100000     method=no_slice             time=1.2699861200526357 ms
---
Size=1000000    method=with_slice           time=5.068190313875675 ms
Size=1000000    method=pure_loop            time=5.029146575368941 ms
Size=1000000    method=no_slice             time=12.877492633648217 ms

As far I as know, the slice operation will create a new list with the copy of the reference of the each item in the slice. In my imagination, it should be expensive than the no_slice way which doesn't have any copy operation. But from the test result, the slice way even is faster than the pure loop on a range(). Why does this happen?

python-3.x performance
1 Answers

As far I as know, the slice operation will create a new list with the copy of the reference of the each item in the slice

Indeed, the standard implementation which is the CPython interpreter does make a copy.

In my imagination, it should be expensive than the no_slice way which doesn't have any copy operation. But from the test result, the slice way even is faster than the pure loop on a range(). Why does this happen?

The point is copying a list is much faster than iterating over it because the loops of the interpreter are pretty slow compared to the slicing operation optimized in C (using the same interpreter).

On my machine, with nums containing 5000 random items, slicing nums takes about 8 µs while iterating over nums takes about 33 µs. Iterating over a sliced nums takes 41 µs. Iterating over a range object (with the same number of items) takes 68 µs.

The fact that iterating over a range object is significantly slower than other methods is quite surprising at first glance. You may expect it to be faster than iterating over nums or at least as fast. It is more expensive because the loop iterate over a generator (more specifically a range_iterator). Iterating over such a generator object is pretty slow on CPython. This is mainly due to the increment of pure-Python integers and their comparisons for each loop iteration. Pure-Python integers are quite expensive because they can be bigger than native integers (CPython needs to consider the case where the range can be very large although it never happens in practice). Managing pure-Python objects also introduce an additional overhead too (allocation, deallocation, reference counting, indirections, etc.). There is no need to use such integers when CPython internally iterates over lists because the size of the list should always fit in a native integer (typically about 2**64 on a 64-bit machine).

To conclude, with_slice measures the time of slicing nums and then iterating over a list object. pure_loop measures the time taken to iterate over a range object. no_slice measures the time of iterating over a range object and for each item accessing nums to put the value in a local variable. This last operation is much more expensive than the two others because the nums access is interpreted for each iteration while the interpreter can iterate over the list faster in the first function. It also include the cost of the second function which is already pretty big. What is missing is a comparison between an iteration of nums[:] versus nums.

Note that the cost of with_slice is closer to pure_loop when size is big because the list is too big to fit in the fast L1 cache and need to be copied from the LLC cache or typically from the slow main RAM.

user_129395570
Related