Почему это улучшенное сито медленнее с pypy?

def sieve(n): nums = [0] * n for i in range(2, int(n**0.5)+1): if nums[i] == 0: for j in range(i*i, n, i): nums[j] = 1 return [i for i in range(2, n) if nums[i] == 0] def sieve_var(n): nums = [0] * n for i in range(3, int(n**0.5)+1, 2): if nums[i] == 0: for j in range(i*i, n, i): nums[j] = 1 return [2] + [i for i in range(3, n, 2) if nums[i] == 0]

На моей машине sieve(10**8) занимает 2,28 с, а sieve_var(10**8) 2,67 с. Я не думаю, что время разогрева pypy – это преступник, так почему же не sieve_var , который итерации меньше, быстрее? В стандартном python 3.3 sieve_var работает быстрее, чем ожидалось. Использование pypy 4.0.1 32bit в Windows 8.1.

Edit: В качестве теста я добавил count = 0 в начале функции и count += 1 во внутреннем цикле (где nums[j] = 1 is). sieve(10**8) насчитывает 242570202, тогда как sieve_var(10**8) насчитывает 192570204. Таким образом, хотя счетчик не уменьшен вдвое для sieve_var , он делает меньше «работы».

2 Solutions collect form web for “Почему это улучшенное сито медленнее с pypy?”

Я не уверен, почему он немного медленнее в Windows. В Linux скорость такая же. Однако я могу ответить, почему мы получаем в основном ту же скорость. Ответ будет таким же, если программа была написана на C, а ответ – только на уровне процессора. Эта программа связана с вводом-выводом памяти, доступ к списку, размер которого составляет 400 или 800 МБ. Во второй версии вы в основном избегаете одной дополнительной проверки if nums[i] == 0 . Эта дополнительная проверка ничего не стоит, потому что CPU только что набрал nums[i - 1] в своих кэшах во время предыдущей итерации и потребует nums[i + 1] во время следующей итерации. CPU все равно ждет память.

Чтобы проверить, что я говорю, попробуйте сделать массив nums более компактным. Я попытался получить к нему доступ с помощью nums[i // 2] , считая, что i всегда нечетно, и результат был в два раза быстрее. Вы, вероятно, можете выиграть еще больше, не используя список Python (хранящийся как массив из 32-битных целых чисел в 32-разрядном PyPy), но вместо этого массив бит (но это намного больше кода, потому что нет стандартного встроенного массив бит).

TL, DR;

В качестве C-программы это будет алгоритм, связанный с памятью. Тем не менее, даже jit-скомпилированный pypy-code имеет значительно больше накладных расходов, и операции больше не «бесплатны». Удивительно (или, может быть, нет), rhese две версии sieve имеют разные jit-коды, вероятно, просто неудача, что вторая версия приводит к более медленному коду.

Если бы это был C, ответ @ Armin был бы правильным. Хорошо известно, что для современных компьютеров / кэшей и кода, привязанного к памяти, не имеет значения, перепрыгиваем ли мы через целое число – тем не менее все значения должны извлекаться из памяти, а это бутылочная шее. См. Эту статью для отличного объяснения.

Однако мои эксперименты показывают, что неоптимизированная версия ( sieve ) немного быстрее, чем оптимизированная версия ( sieve_var ). Сроки также показали, что последняя строка sieve т. sieve [i for i in range(2, n) if nums[i] == 0] выполняется быстрее, чем строка sieve_var – return [2] + [i for i in range(3, n, 2) if nums[i] == 0] .

На моей машине это составляло 0.45 секунды против 0.65 секунды для 10^8 элементов. Эти числа могут отличаться от машины к машине, поэтому вполне возможно, что кто-то с более быстрым процессором и более медленной памятью вообще не увидит никакой разницы. Если это можно объяснить с точки зрения «памяти доминирует над всеми», то мы должны уметь видеть, что более медленная версия имеет больше промахов в кешках, чем более быстрая версия.

Однако, запустив valgrind --tool=cachegrind pypy sieveXXX.py мы видим, что почти нет разницы в количестве промахов в кэше, по крайней мере, ничего, что могло бы объяснить наблюдаемую разницу.

Давайте рассмотрим несколько более простую версию, которая проявляет точно такое же поведение – мы не сохраняем простые числа, а просто считаем их:

 def sieve(n): ... res=0 for i in range(2, n): if nums[i] == 0: res+=1 return res def sieve_var(n): ... res=1 for i in range(3, n,2): if nums[i] == 0: res+=1 return res

Первая версия еще быстрее: 0.35 сек. против 0.45 секунды (чтобы разность во времени не была случайностью и не из-за некоторого разгонного джиттера, я поставил последнюю часть кода в цикл for и получил всегда одни и те же тайминги).

Прежде чем идти дальше, давайте посмотрим на C-реализацию и ее сборку

 long long int sum(long long int *a, int n){ long long int res=0; for(int i=2;i<n;i++) if(a[i]==0) res++; return res; }

скомпилированный с gcc и -Os мы получаем :

  movl $2, %edx xorl %eax, %eax .L4: cmpl %edx, %esi jle .L1 cmpq $0, (%rdi,%rdx,8) jne .L3 incq %rax .L3: incq %rdx jmp .L4 .L1: ret

Довольно маленький и прямой и занимает всего 0.08 секунды на моей машине. Моя память может идти со скоростью 10 ГБ / с и 8*10^8 байтов – поэтому все время было необходимо для получения данных.

Но из этого мы также видим, что pypy-версия имеет накладные расходы на 0.25 секунды по сравнению с C-кодом. От куда это? Используя модуль vmprof, мы можем видеть jit-код и:

для одной итерации цикла существует намного больше операций, чем в C-версии
версии для sieve и sieve_par очень разные. Мы можем использовать отладчик для подсчета числа инструкций итерации: 24 для sieve и 76 sieve_var для sieve_var который обрабатывает только каждый второй элемент, поэтому отношение фактически 24:38 .

Трудно сказать, почему jit-код настолько отличается для обеих версий без отладки pypy. Наверное, это просто неудача, что sieve_par медленнее.