[issue40088] list.reverse(): slow sublist reverse

[Yury Norov]

New submission from Yury Norov <yury.norov at gmail.com>:

Hi all,

In Python, I need a tool to reverse part of a list (tail) quickly.
I expected that

        nums[start:end].reverse()

would do it inplace with the performance similar to nums.reverse().
However, it doesn't work at all. The fastest way to reverse a part of
the list that I found is like this:

nums[start:end] = nums[end:start-1:-1]

But it is 30 times slower than pure reverse(). The patch below adds
a region support for the reverse(). It works as fast as I expect.

The test results and script are like this:

            exec(open('test.py').read())
            nums.reverse() 0.006764888763427734
            nums = nums[::-1] 0.10066413879394531
            nums.reverse(-L/2) 0.003548145294189453
            nums.reverse(L/2, L) 0.003538370132446289
            nums = nums[:L/2] + nums[L:L/2-1:-1] 0.19934582710266113
            nums[L/2:L] = nums[L:L/2-1:-1] 0.11419057846069336

import time

nums = list(range(10000000))
L = len(nums)
LL = int(L/2)

t = time.time()
nums.reverse()
print('nums.reverse()\t\t\t\t', str(time.time() - t))

t = time.time()
nums = nums[::-1]
print('nums = nums[::-1]\t\t\t', str(time.time() - t))

t = time.time()
nums.reverse(-LL)
print('nums.reverse(-L/2)\t\t\t', time.time() - t)

t = time.time()
nums.reverse(LL, L)
print('nums.reverse(L/2, L)\t\t\t', time.time() - t)

t = time.time()
nums = nums[:LL] + nums[L : LL - 1 : -1]
print('nums = nums[:L/2] + nums[L:L/2-1:-1]\t', time.time() - t)

t = time.time()
nums[LL:L] = nums[L:LL-1:-1]
print('nums[L/2:L] = nums[L:L/2-1:-1]\t\t', time.time() - t)

If there is better way to reverse lists, can someone point me at the right direction? If not, I'll be happy to fix all existing issues and upstream
this approach.

PR: https://github.com/python/cpython/pull/19181

Thanks,
Yury

----------
components: C API, Interpreter Core
messages: 365147
nosy: Yury
priority: normal
pull_requests: 18548
severity: normal
status: open
title: list.reverse(): slow sublist reverse
versions: Python 3.9

_______________________________________
Python tracker <report at bugs.python.org>
<https://bugs.python.org/issue40088>
_______________________________________