Почему обрабатывается отсортированный массив не быстрее, чем несортированный массив в Python?

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

Но я просто попробовал пример с помощью Python; и я думаю, что нет никакой разницы между отсортированными и случайными массивами (я пробовал как bytearray, так и массив, а также использовать line_profile для профилирования вычислений).

Я что-то пропустил?

Вот мой код:

from array import array
import random
array_size = 1024
loop_cnt = 1000
# I also tried 'array', and it almost the same
a = bytearray(array_size)
for i in xrange(array_size):
    a.append(random.randint(0, 255))
#sorted                                                                         
a = sorted(a)
@profile
def computation():
    sum = 0
    for i in xrange(loop_cnt):
        for j in xrange(size):
            if a[j] >= 128:
                sum += a[j]

computation()
print 'done'

Ответы

Ответ 1

Возможно, я ошибаюсь, но я вижу принципиальное различие между связанным вопросом и вашим примером: Python интерпретирует байт-код, С++ компилируется в собственный код.

В коде С++, который if преобразуется непосредственно в последовательность cmp/jl, которая может рассматриваться предиктором ветвления процессора как одно "пятно предсказания", специфичное для этого цикла.

В Python сравнение на самом деле представляет собой несколько вызовов функций, поэтому там (1) больше накладных расходов и (2) я полагаю, что код, который выполняет это сравнение, является функцией в интерпретаторе, используемом для каждого другого целочисленного сравнения - так это "предсказание spot", не относящегося к текущему блоку, что дает предсказателю ветки гораздо более трудное время для правильной угадывания.

Изменить: также, как указано в этой статье, в интерпретаторе есть пути более косвенных ветвей, поэтому такая оптимизация в вашем коде Python, вероятно, будет похожа на все по неверным предсказаниям ветвей в самом интерпретаторе.

Ответ 2

Две причины:

Размер вашего массива слишком мал, чтобы показать эффект.
Python имеет больше накладных расходов, чем C, поэтому эффект будет менее заметным в целом.

Ответ 3

Я портировал исходный код на Python и запускал его с PyPy. Я могу подтвердить, что отсортированные массивы обрабатываются быстрее, чем несортированные массивы, и что нераспаковываемый метод также работает, чтобы исключить ветвь с временем выполнения, аналогичным отсортированному массиву. Я считаю, что это потому, что PyPy является компилятором JIT, и поэтому происходит предсказание ветвей.

[править]

Вот код, который я использовал:

import random
import time

def runme(data):
  sum = 0
  start = time.time()

  for i in xrange(100000):
    for c in data:
      if c >= 128:
        sum += c

  end = time.time()
  print end - start
  print sum

def runme_branchless(data):
  sum = 0
  start = time.time()

  for i in xrange(100000):
    for c in data:
      t = (c - 128) >> 31
      sum += ~t & c

  end = time.time()
  print end - start
  print sum

data = list()

for i in xrange(32768):
  data.append(random.randint(0, 256))

sorted_data = sorted(data)
runme(sorted_data)
runme(data)
runme_branchless(sorted_data)
runme_branchless(data)

Ответ 4

sorted() возвращает отсортированный массив, а не сортировку на месте. Вы фактически измеряете один и тот же массив дважды.

Ответ 5

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