Оптимизация производительности алгоритма подсчета в Pypy vs Python (Numpy vs List)

Я ожидал, что pypy может быть на порядок быстрее, чем python, но результаты показывают, что pypy на самом деле медленнее, чем ожидалось.

У меня есть два вопроса:

1. Почему pypy значительно медленнее с numpy?
2. Могу ли я что-нибудь сделать, чтобы оптимизировать мой алгоритм, чтобы сделать pypy (или python) быстрее?

Результирующие сроки:

Питон 2.7.5

• # баллов: 16 777 216 (8 ** 3 * 32 ** 3)
• Время Xrange: 1487,15 мс
• Время Xrange Numpy: 2553,98 мс
• Время генерации точки: 6162,23 мс
• Время генерации Numpy: 13894,73 мс

Пипи 2.2.1

• # баллов: 16 777 216 (8 ** 3 * 32 ** 3)
• Время Xrange: 129,48 мс
• Время Xrange Numpy: 4644,12 мс
• Время генерации точки: 4643,82 мс
• Время генерации Numpy: 44168,98 мс

Алгоритм:

Я создаю список точек в пространстве, используя простой алгоритм, и я пытаюсь оптимизировать алгоритм.

def generate(size=32, point=(0, 0, 0), width=32):
    """
    generate points in space around a center point with a specific width and
      number of divisions (size)
    """
    X, Y, Z = point
    half = width * 0.5
    delta = width
    scale = width / size
    offset = scale * 0.5
    X = X + offset - half
    Y = Y + offset - half
    Z = Z + offset - half
    for x in xrange(size):
        x = (x * scale) + X
        for y in xrange(size):
            y = (y * scale) + Y
            for z in xrange(size):
                z = (z * scale) + Z
                yield (x, y, z)

При оптимизации я начал рассматривать использование pypy, а не python. И, сравнивая их, я придумал несколько разных сценариев:

• подсчет с использованием xrange

  rsize = 8    # size of region
  csize = 32   # size of chunk
  number_of_points = rsize ** 3 * csize ** 3
  [x for x in xrange(number_of_points)]
  

• подсчет с использованием xrange с numpy

  rsize = 8    # size of region
  csize = 32   # size of chunk
  number_of_points = rsize ** 3 * csize ** 3
  np.array([x for x in xrange(number_of_points)])
  

• работает по алгоритму выше

  rsize = 8    # size of region
  csize = 32   # size of chunk
  [p
   for rp in generate(size=rsize, width=rsize*csize)
   for p in generate(size=csize, width=csize, point=rp)]
  

• запуск алгоритма выше с numpy

  rsize = 8    # size of region
  csize = 32   # size of chunk
  np.array([p
   for rp in generate(size=rsize, width=rsize*csize)
   for p in generate(size=csize, width=csize, point=rp)])
  

Предыстория:

Я пытаюсь создать воксельный движок и хочу оптимизировать свой алгоритм, чтобы сократить время генерации до управляемого уровня. Хотя я явно не добьюсь ничего близкого к Java/C++, я хотел бы продвинуть python (или pypy) настолько далеко, насколько это возможно.

Я заметил, что поиск по спискам выполняется значительно быстрее, чем словари из некоторых более ранних таймингов. И списки также быстрее, чем кортежи (неожиданно), хотя кортежи генерируются быстрее. Numpy имеет даже более быстрое время чтения, чем non-numpy. Однако время создания numpy может быть на несколько порядков медленнее.

Поэтому, если чтение важнее всего, использование numpy имеет явное преимущество. Однако, если чтение и творчество одинаково важны, то, вероятно, лучше всего использовать прямой список. Тем не менее, у меня нет четкого взгляда на использование памяти, но я подозреваю, что списки гораздо менее эффективны с точки зрения использования памяти, чем кортежи или numpy. Кроме того, хотя это небольшая разница, я обнаружил, что .get в словаре работает немного быстрее, чем использование вызова __ getitem __ (т. е. словарь[lookup] против dicitonary.get(lookup) )

сроки ...

Питон 2.7.5

Чтение

 - Option 1: tuple access... 2045.51 ms
 - Option 2: tuple access (again)... 2081.97 ms    # sampling effect of cache
 - Option 3: list access... 2072.09 ms
 - Option 4: dict access... 3436.53 ms
 - Option 5: iterable creation... N/A
 - Option 6: numpy array... 1752.44 ms

Творчество

 - Option 1: tuple creation... 690.36 ms
 - Option 2: tuple creation (again)... 716.49 ms    # sampling effect of cache
 - Option 3: list creation... 684.28 ms
 - Option 4: dict creation... 1498.94 ms
 - Option 5: iterable creation...  0.01 ms
 - Option 6: numpy creation... 3514.25 ms

Пипи 2.2.1

Чтение

 - Option 1: tuple access... 243.34 ms
 - Option 2: tuple access (again)... 246.51 ms    # sampling effect of cache
 - Option 3: list access... 139.65 ms
 - Option 4: dict access... 454.65 ms
 - Option 5: iterable creation... N/A
 - Option 6: numpy array... 21.60 ms

Творчество

 - Option 1: tuple creation... 1016.27 ms
 - Option 2: tuple creation (again)... 1063.50 ms    # sampling effect of cache
 - Option 3: list creation... 365.98 ms
 - Option 4: dict creation... 2258.44 ms
 - Option 5: iterable creation...  0.00 ms
 - Option 6: numpy creation... 12514.20 ms

Во всех примерах для случайных данных был сгенерирован случайный поиск.

dsize = 10 ** 7   # or 10 million data points
data = [(i, random.random()*dsize)
         for i in range(dsize)]
lookup = tuple(int(random.random()*dsize) for i in range(dsize))

Циклы были очень простыми:

for x in lookup:
    data_of_specific_type[x]

А data_of_specific_type был преобразованием данных в этот тип (например, кортеж(данные), список(данные) и т. д.)