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

Ответ 1

Я не уверен, почему он немного медленнее в 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), но вместо этого массив бит (но это намного больше кода, потому что нет стандартного встроенного массив бит).

Ответ 2

TL, DR;

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

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

Однако мои эксперименты показывают, что неоптимизированная версия (sieve) немного быстрее оптимизированной версии (sieve_var). Сроки также показывают, что последняя строка sieve i.e. [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 сек. vs. 0.45 sec (чтобы убедиться, что разница во времени не случайна, а не из-за некоторого jit-warmup, я поставил последнюю часть кода в цикл 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-module, мы можем увидеть jit-код и:

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

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