PyPy: серьезное снижение производительности при использовании None в списке с целыми числами


Поскольку алгоритм, который я хочу реализовать, использует индексы 1..n и поскольку он очень подвержен ошибкам, чтобы сдвинуть каждый индекс на единицу, я решил проявить смекалку и вставил фиктивный элемент в начало каждого списка, чтобы я мог использовать оригинальные формулы из статьи.

Для краткости рассмотрим такой игрушечный пример:

def calc(N):
    nums=[0]+range(1,N+1)
    return sum(nums[1:]) #skip first element
Тем не менее, я забеспокоился, что мои результаты ложны, потому что я мог получить доступ к 0-му элементу случайно где-то и не осознавать этого. Так Что Я стал еще умнее и использовал None вместо 0 в качестве первого элемента-каждая арифметическая операция с ним приводила бы к ошибке времени выполнения:
def calc_safe(N):
    nums=[None]+range(1,N+1) #here we use "None"
    return sum(nums[1:]) 
Удивительно, но это небольшое изменение привело к огромному снижению производительности для pypy (даже с текущей версией 5.8) - код стал примерно в 10 раз медленнее! Вот время на моей машине:
                    pypy-5.8    cpython
calc(10**8)         0.5 sec     5.5 sec
calc_safe(10**8)    7.5 sec     5.5 sec

Как побочный узел: Cpython не заботится, используется ли Noneили нет.

Итак, мой вопрос двояко:

  1. очевидно, что использование None не является хорошей идеей, но почему?
  2. Можно ли получить безопасность None-подхода и сохранить производительность?

Edit: Как объяснил Армин, не все списки равны, и мы можем видеть, какая стратегия используется через:

import __pypy__ 
print __pypy__.strategy(nums)

В первом случае это IntegerListStrategy, а во втором ObjectListStrategy. То же самое произойдет, если мы используем большое целое значение (например, 2**100) вместо None.

1 7

1 ответ:

У PyPy есть специальный случай для списков, содержащих только целые числа-он хранит их как array.array. Если в нем нет ни одного, то эта оптимизация больше не работает.

Это, вероятно, можно было бы зафиксировать внутри PyPy, чтобы не допустить ни одного в качестве частного случая...