Senior software developer
44,0
рейтинг
30 мая 2015 в 02:44

Разработка → Sexy primes, «медленный питон» или как я бился о стену непонимания

Многие разработчики, особенно принимающие активное участие в проектировании системы, наверняка сталкивались с подобной ситуацией: приходит коллега (разраб, проектлид или продажник не суть важно) с очередной идеей-фикс: давай перепишем все на java, scala и т.д. (любимое подставить).

Вот и мне в очередной раз «спустили» такую идею в немаленьком-таком legacy проекте. Не совсем переписать, не совсем все (ну в перспективе). В общем перейти с питона (а у нас там еще и тикль модульно присутствует) на scala. Речь пока шла о разработке новых модулей и сервисов, т.е. начинать с наименее привязанных к middle-level и front-nearby API's. Как я понял в перспективе возможно совсем.

Человек — не разработчик, типа нач-проекта и немного продажник (для конкретного клиента) в одном лице.

Я не то, чтобы против. И скалу уважаю и по-своему люблю. Обычно я вообще открыт ко всему новому. Так, например, местами кроме тикля и питона у нас появляются сервисы или модули на других языках. Так, например, мы переехали с cvs на svn, а затем на git (а раньше, давно-давно, вообще MS-VSS был). Примеров на самом деле масса, объединяет их один момент — так решили или как минимум одобрили сами разработчики (коллективно ли, или была группа инициаторов — не суть важно). Да и дело в общем в аргументах за и против.

Проблема в том, что иногда для аргументированной дискуссии «Developer vs. Anybody-Else» у последнего не дотягивает уровень знаний «материи» или просто невероятно сложно донести мысль — т.е. как-бы разговор на разных языках. И хорошо если это кто-нибудь типа software architect. Хуже, если имеем «беседу» например с чистым «продажником», огласившим например внезапные «требования» заказчика.

Ну почему никто не предписывает, например, плиточнику — каким шпателем ему работать (типа с зубцами 10мм клея же больше уйдет, давайте может все же 5мм. А то что там полы-стены кривущие никого не волнует). И шуруп теоретически тоже можно «закручивать» молотком, но для этого же есть отвертка, а позже был придуман шуруповёрт. Утрирую конечно, но иногда действительно напоминает такой вот абсурд.

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

Но что-то я отвлекся. В моей конкретной истории аргументов — за scala, у человека как всегда почти никаких.
Хотя я мог бы долго говорить про вещи, типа наличие разрабов, готовые наработки, отточенную и отлаженную систему и т.д. и т.п. Но зацепился за его «Питон очень медленный». В качестве примера он в меня кинул ссылкой на Interpreting a benchmark in C, Clojure, Python, Ruby, Scala and others — Stack Overflow, которую он даже до конца не прочитал (ибо там почти прямым текстом есть — не так плохо все с питоном).

Имелось ввиду именно вот это (время указано в секундах):
  Sexy primes up to:        10k      20k      30k      100k
  ---------------------------------------------------------
  Python2.7                1.49     5.20    11.00       119     
  Scala2.9.2               0.93     1.41     2.73     20.84
  Scala2.9.2 (optimized)   0.32     0.79     1.46     12.01


Разговаривать с ним на уровне, про чисто техническую сторону, нет ни малейшего желания. Т.е. про выделение памяти/пул объектов, GC (у нас не чистый CPython, скорее похож на RPython или pypy с собственным Jit, MemMgr, GC), про всякий сахар, с которым человек, писавший бенчь, немного переборщил и т.д.

Мой ответ был «любят разрабатывать на питоне не за это» и «на нем так не пишут, по крайней мере критичный к скорости код». Я немного слукавил и естественно понимаю, что этот пример для benchmark искусственный, ну т.е. значит чисто померить скорость. Но и болячки, которые при таком тесте повыскакивают в CPython, мне тоже известны.
Поэтому все же постарался на этом конкретном примере показать почему этот тест не целесообразен, ну или почему не совсем объективный что ли.

Начал с того, что показал ему этот тест и результаты исполнения (помечены звездой) в PyMNg (что есть наша сборка), pypy2, pypy3 и python3 (который то же был по тем же понятным причинам медленный). Железо, конечно, другое, но порядок, думаю, примерно одинаков.
  Sexy primes up to:        10k      20k      30k      100k
  ---------------------------------------------------------
  PyMNg                *   0.10        -        -      2.46
  pypy2                *   0.13        -        -      5.44
  pypy3                *   0.12        -        -      5.69
  ---------------------------------------------------------
  scala 2.10.4 (warmed up) *           -        -      6.57
  scala 2.10.4 (cold)      *           -        -      7.11
  ---------------------------------------------------------
  Python3.4            *   1.41        -        -    117.69
  ---------------------------------------------------------
  Python2.7                1.49     5.20    11.00    119.00
  Scala2.9.2               0.93     1.41     2.73     20.84
  Scala2.9.2 (optimized)   0.32     0.79     1.46     12.01

Дальше можно было в принципе не продолжать, просто хотелось сделать попытку объяснить человеку, в чем он не прав, что выбор языка не оценивается по бенчмаркам типа «Hello, world» и т.д.

Итак, задача — ищем «сексуальные» пары простых чисел на питоне. Много и быстро.

Для тех кому разбор полетов не интересен, ссылка на скрипт на github, если есть желание поиграться.

Результаты исполнения каждого варианта под спойлером соответственно.
100K для всех вариантов.
pypy3 sexy-primes-test.py 100K
  org =  5.69000 s =   5690.00 mils | 2447 sp: [5, 11], [7, 13], ... [99901, 99907], [99923, 99929]

 mod1 =  2.45500 s =   2455.00 mils | 2447 sp: [5, 11], [7, 13], ... [99901, 99907], [99923, 99929]

 mod2 =  1.24300 s =   1243.00 mils | 2447 sp: [5, 11], [7, 13], ... [99901, 99907], [99923, 99929]

 org2 =  3.46800 s =   3468.00 mils | 2447 sp: [5, 11], [7, 13], ... [99901, 99907], [99923, 99929]

  max =  0.03200 s =     32.00 mils | 2447 sp: [5, 11], [7, 13], ... [99901, 99907], [99923, 99929]

 orgm =  0.13000 s =    130.00 mils | 2447 sp: [5, 11], [7, 13], ... [99901, 99907], [99923, 99929]

siev1 =  0.01200 s =     12.00 mils | 2447 sp: [5, 11], [7, 13], ... [99901, 99907], [99923, 99929]

siev2 =  0.01000 s =     10.00 mils | 2447 sp: [5, 11], [7, 13], ... [99901, 99907], [99923, 99929]

osie1 =  0.01200 s =     12.00 mils | 2447 sp: [5, 11], [7, 13], ... [99901, 99907], [99923, 99929]

osie2 =  0.00200 s =      2.00 mils | 2447 sp: [5, 11], [7, 13], ... [99901, 99907], [99923, 99929]

python34 sexy-primes-test.py 100K
  org = 120.75802 s = 120758.02 mils | 2447 sp: [5, 11], [7, 13], ... [99901, 99907], [99923, 99929]

 mod1 = 132.99282 s = 132992.82 mils | 2447 sp: [5, 11], [7, 13], ... [99901, 99907], [99923, 99929]

 mod2 = 76.65101 s =  76651.01 mils | 2447 sp: [5, 11], [7, 13], ... [99901, 99907], [99923, 99929]

 org2 = 53.42527 s =  53425.27 mils | 2447 sp: [5, 11], [7, 13], ... [99901, 99907], [99923, 99929]

  max =  0.44004 s =    440.04 mils | 2447 sp: [5, 11], [7, 13], ... [99901, 99907], [99923, 99929]

 orgm =  0.39003 s =    390.03 mils | 2447 sp: [5, 11], [7, 13], ... [99901, 99907], [99923, 99929]

siev1 =  0.04000 s =     40.00 mils | 2447 sp: [5, 11], [7, 13], ... [99901, 99907], [99923, 99929]

siev2 =  0.04250 s =     42.50 mils | 2447 sp: [5, 11], [7, 13], ... [99901, 99907], [99923, 99929]

osie1 =  0.04500 s =     45.00 mils | 2447 sp: [5, 11], [7, 13], ... [99901, 99907], [99923, 99929]

osie2 =  0.04250 s =     42.50 mils | 2447 sp: [5, 11], [7, 13], ... [99901, 99907], [99923, 99929]

10M начиная с варианта max (остальные просто медленные на таком массиве).
pypy3 sexy-primes-test.py 10M max
  max =  5.28500 s =   5285.00 mils | 117207 sp: [5, 11], [7, 13], ... [9999931, 9999937], [9999937, 9999943]

 orgm = 12.65600 s =  12656.00 mils | 117207 sp: [5, 11], [7, 13], ... [9999931, 9999937], [9999937, 9999943]

siev1 =  0.51800 s =    518.00 mils | 117207 sp: [5, 11], [7, 13], ... [9999931, 9999937], [9999937, 9999943]

siev2 =  0.23200 s =    232.00 mils | 117207 sp: [5, 11], [7, 13], ... [9999931, 9999937], [9999937, 9999943]

osie1 =  0.26800 s =    268.00 mils | 117207 sp: [5, 11], [7, 13], ... [9999931, 9999937], [9999937, 9999943]

osie2 =  0.22700 s =    227.00 mils | 117207 sp: [5, 11], [7, 13], ... [9999931, 9999937], [9999937, 9999943]

python34 sexy-primes-test.py 10M max
  max = 288.81855 s = 288818.55 mils | 117207 sp: [5, 11], [7, 13], ... [9999931, 9999937], [9999937, 9999943]

 orgm = 691.96458 s = 691964.58 mils | 117207 sp: [5, 11], [7, 13], ... [9999931, 9999937], [9999937, 9999943]

siev1 =  4.02766 s =    4027.66 mils | 117207 sp: [5, 11], [7, 13], ... [9999931, 9999937], [9999937, 9999943]

siev2 =  4.05016 s =    4050.16 mils | 117207 sp: [5, 11], [7, 13], ... [9999931, 9999937], [9999937, 9999943]

osie1 =  4.69519 s =    4695.19 mils | 117207 sp: [5, 11], [7, 13], ... [9999931, 9999937], [9999937, 9999943]

osie2 =  4.43018 s =    4430.18 mils | 117207 sp: [5, 11], [7, 13], ... [9999931, 9999937], [9999937, 9999943]

100M начиная с варианта siev1 (по той же причине).
pypy3 sexy-primes-test.py 100M siev1
siev1 =  7.39800 s =   7398.00 mils | 879908 sp: [5, 11], [7, 13], ... [99999617, 99999623], [99999821, 99999827]

siev2 =  2.24500 s =   2245.00 mils | 879908 sp: [5, 11], [7, 13], ... [99999617, 99999623], [99999821, 99999827]

osie1 =  2.53500 s =   2535.00 mils | 879908 sp: [5, 11], [7, 13], ... [99999617, 99999623], [99999821, 99999827]

osie2 =  2.31000 s =   2310.00 mils | 879908 sp: [5, 11], [7, 13], ... [99999617, 99999623], [99999821, 99999827]

python34 sexy-primes-test.py 100M siev1
siev1 = 41.87118 s =  41871.18 mils | 879908 sp: [5, 11], [7, 13], ... [99999617, 99999623], [99999821, 99999827]

siev2 = 40.71163 s =  40711.63 mils | 879908 sp: [5, 11], [7, 13], ... [99999617, 99999623], [99999821, 99999827]

osie1 = 48.08692 s =  48086.92 mils | 879908 sp: [5, 11], [7, 13], ... [99999617, 99999623], [99999821, 99999827]

osie2 = 44.05426 s =  44054.26 mils | 879908 sp: [5, 11], [7, 13], ... [99999617, 99999623], [99999821, 99999827]

Кстати, такой разброс между CPython и PyPy и является часто одной из причин, почему люди переходят на PyPy, пишут собственные алокаторы, менеджеры памяти, GC, stackless и иже с ними, используют сторонние модули (например NumPy) и делают собственные сборки. Например, когда важна скорость исполнения и как здесь, имеем «агрессивное» использование пула объектов / множественные вызовы и т.д. Так же было когда-то давно и в нашем случае, когда мы переехали с чистого питона. Там еще было много чего, и тормозящий multithreding, и refcounting и т.д. Но сам переезд был обдуманным решением всей команды, а не «спущенной» сверху причудой. Если есть интерес и найду время, можно будет попробовать тиснуть про это статью.

Для этой же конкретной «задачи» можно было бы написать собственный C-binding, использовать модули типа numpy и т.д. Я же попробовал убедить коллегу, что оно на коленке за незначительное время решается практически «алгоритмически», если знаешь, как питон тикает внутри.

Итак, начнем доказывать человеку, что и питон умеет быстро «бегать», если все-таки решается поставленная задача, а не искусственный тест.

Оригинальный скрипт, немного измененный мной для читабельности и поддержки третьего питона, этот вариант у меня в скрипте-примере называется org. (Только, плз, не надо здесь про «xrange vs range» — я прекрасно представляю, в чем различие, и здесь конкретно оно не суть важно, тем более в 3-м питоне, кроме того, и итерация как-бы «завершенная»).
def is_prime(n):
  return all((n % i > 0) for i in range(2, n))
# def sexy_primes_below(n):
#   return [[j-6, j] for j in range(9, n+1) if is_prime(j) and is_prime(j-6)]
def sexy_primes_below(n):
  l = []
  for j in range(9, n+1):
    if is_prime(j-6) and is_prime(j):
      l.append([j-6, j])
  return l

Т.к. даже на 10M имеем всего 100K sexy пар, изменение оригинальной primes_below на мой вариант с прямым циклом не сильно влияет на время исполнения, просто оно наглядней для изменений в последующих вариантах (например сито). Весь цимес в реализации is_prime, во всяком случае пока.

1. Во-первых, использование такого «сахара» как в оригинале (тем более в «сборках» типа PyPy, ну или нашего PyMNg) не поощряется, ну или как минимум, как и в этом случае, больно бьет отдачей в виде снижения скорости. Перепишем это как вариант mod1
def is_prime(n):
  i = 2
  while True:
    if not n % i:
       return False
    i += 1
    if i >= n:
       return True
  return True

Уже быстрее, как минимум в PyPy. Но дело не в этом…

2. Код стал сразу наглядней и видно, что его можно переписать как mod2 в половину быстрее, если не проверять четные номера (которые, кроме двойки, изначально не prime).
def is_prime(n):
  if not n % 2:
    return False
  i = 3
  while True:
    if n % i == 0:
       return False
    i += 2
    if i >= n:
       return True
  return True

Поправим это в оригинале — org2 это то же самое что и mod2, но в одну строчку используя «сахар».
def is_prime(n):
  return n % 2 and all(n % i for i in range(3, n, 2))

3. Если проверять делители до значения квадратного корня (правильно было бы до округленного, но мы сделаем проще — это же просто тест), то все можно сделать еще намного быстрее, получим вариант max:
def is_prime(n):
  if not n & 1:
    return 0
  i = 3
  while 1:
    if not n % i:
       return 0
    if i * i > n:
       return 1
    i += 2
  return 1
Намного быстрее, правда.

Опять правим это в оригинале — orgm.
def is_prime(n):
  #return ((n & 1) and all(n % i for i in range(3, int(math.sqrt(n))+1, 2)))
  return ((n & 1) and all(n % i for i in range(3, int(n**0.5)+1, 2)))

И видим, что как минимум в PyPy оно опять выполняется медленнее (хотя частично, возможно, и из-за прямого подсчета «корня», который в range).

4. Тут у коллеги загораются глаза, и он как в том мультфильме (по-моему, «Жадный богач») про скорняка и 7 шапок выдает: «А можешь еще быстрее?». Т.к. по памяти ограничения нет (не emdedded и т.д.) решил ему быстро переделать, используя «половинчатое» сито — half sieve, что есть подготовленный массив флажков по смещению для нечетных чисел, т.е. разделенных на 2. Тем более, что на питоне организовать такое сито на раз-два.
Ну и сразу видоизменяем sexy_primes_below, вызвав в нем генерацию сита ну и чтобы не править is_prime и не вызывать его в цикле, спрашиваем сразу sieve.
Получаем вариант siev1.
def primes_sieve(n):
  """ temporary "half" mask sieve for primes < n (using bool) """
  sieve = [True] * (n//2)
  for i in range(3, int(n**0.5)+1, 2):
    if sieve[i//2]:
      sieve[i*i//2::i] = [False] * ((n-i*i-1)//(2*i)+1)
  return sieve
def sexy_primes_below(n):
  l = []
  sieve = primes_sieve(n+1)
  #is_prime = lambda j: (j & 1) and sieve[int(j/2)]
  for j in range(9, n+1):
    i = j-6
    #if (i & 1) and is_prime(i) and is_prime(j):
    if (i & 1) and sieve[int(i/2)] and sieve[int(j/2)]:
      l.append([i, j])
  return l
Этот вариант настолько быстрый, что в PyPy, например, он на 100M выдает практически то же время, что оригинал на 100K. Т.е. проверяя в 2000 раз больше чисел и генерируя на несколько порядков больший список сексуально-простых пар.

Сразу переписал в вариант siev2, потому что вспомнил о несколько «туповатой» обработке bool в PyPy. Т.е. заменив булевы флажки на 0/1. Этот пример отрабатывает на 100M уже вдвое-трое быстрее оригинала на 100K!

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

Для этого изменил сито смещений на прямое сито хранящее не флаги, а уже сами значения:
sieve = [1, 1, 1, 0, 1, 1 ...]; # для 3, 5, 7, 9, 11, 13 ...
osieve = [3, 5, 7, 0, 11, 13, ...]; # для 3, 5, 7, 9, 11, 13 ...

Вариант osiev1.
def primes_sieve(n):
  """ temporary odd direct sieve for primes < n """
  sieve = list(range(3, n, 2))
  l = len(sieve)
  for i in sieve:
    if i:
      f = (i*i-3) // 2
      if f >= l:
        break
      sieve[f::i] = [0] * -((f-l) // i)
  return sieve
def sexy_primes_below(n):
  l = []
  sieve = primes_sieve(n+1)
  #is_prime = lambda j: (j & 1) and sieve[int((j-2)/2)]
  for j in range(9, n+1):
    i = j-6
    #if (i & 1) and is_prime(i) and is_prime(j):
    if (i & 1) and sieve[int((i-2)/2)] and sieve[int((j-2)/2)]:
      l.append([i, j])
  return l

Ну и второй вариант osiev2 просто «чуть» быстрее, т.к. инициирует сито гораздо оптимальнее.
def primes_sieve(n):
  """ temporary odd direct sieve for primes < n """
  #sieve = list(range(3, n, 2))
  l = ((n-3)//2)
  sieve = [-1] * l
  for k in range(3, n, 2):
    o = (k-3)//2
    i = sieve[o]
    if i == -1:
      i = sieve[(k-3)//2] = k
    if i:
      f = (i*i-3) // 2
      if f >= l:
        break
      sieve[f::i] = [0] * -((f-l) // i)
  return sieve

Эти два метода можно было переделать на итеративное сито (например, искать пары блочно по 10K или 100K). Это позволило бы значительно сэкономить память при подсчете. Например, если сейчас попробовать оба osieve варианта с 1G или 10G, мы практически гарантировано сразу получим MemoryError исключение (ну или вы богатый буратино — и у вас очень много памяти и 64-х битный питон.

Я не стал доделывать блочный способ (его нет в скрипте-примере, пусть это будет как бы «домашним заданием», если вдруг кто-нибудь захочет.), т.к. мой коллега уже раскаялся, в восхищении откланявшись, и я надеюсь как минимум не будет больше забивать голову мне (и команде) такой ерундой.

А на исходных 100K время исполнения последнего уже невозможно было подсчитать — 0.00 mils (я подсчитал его, только увеличив количество итераций исполнения times до 10).

В чем я практически уверен — это то, что увеличить скорость еще на один порядок вряд ли удастся не только на scala, но и на чистом C. Если только снова алгоритмически…

Сам скрипт, буде кто собирается поэкспериментировать, можно спросить помощь, например, так:
sexy-primes-test.py --help

Если что, про простые числа довольно неплохо и очень подробно написано в wikihow.

По просьбам трудящихся добавил опрос…
Python implementations, чем пользуетесь вы?

Проголосовало 286 человек. Воздержалось 298 человек.

Только зарегистрированные пользователи могут участвовать в опросе. Войдите, пожалуйста.

Serg G. Brester @sebres
карма
126,5
рейтинг 44,0
Senior software developer
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама

Самое читаемое Разработка

Комментарии (54)

  • +1
    У меня два соображения на этот счет:
    1. Если тому человеку видится, как переписать тот легаси код на scala и видится, что это просто — пусть покажет пример простого переписывания какой-нибудь функции по вашему выбору на скала.
    2. Со времен написания легаси кода скорее всего много воды утекло, и даже может быть сильно изменились всякие компоненты и модули. Если взглянуть на тот код по крупному, то можно поискать более совершенные фреймворки для того легаси кода, чтобы переписать его с минимальным напрягом? Иногда можно сделать новую структуру и даже лучше старой.
    А по крупному — ну ведь работает же? Это самое главное! Так что вы должны настаивать, что имеете права выбора, вам же работать.
    • НЛО прилетело и опубликовало эту надпись здесь
  • +1
    Спасибо за статью!
    А можете вкратце рассказать, чего вам не хватало в стандартных решениях, почему решили запилить PyMNg?
    • 0
      Пожалуйста… А про собственный «форк» долго рассказывать если честно. Просто тогда pypy сильно сырой был, например у него тогда стабильный только refcounting (вместо реального GC) стоял (при циклических связях — имеем или mem-leak или тупой до ужаса delete на множественных reference). Да много чего было. А в принципе — питон о питон и есть… Думаю если появится когда желание на тот же pypy заменить — меньше чем за неделю обойдется, тестировать только дольше потом…
  • +1
    PyMNg?
    • 0
      ну а чего, «моя» сборка как хочу, так и назову… :) сначала был просто PyMod, вторую же версию просто решили NG (next generation) обозвать…
      • 0
        хотелось бы пощупать
  • +2
    Как ни странно, иногда язык — забота не только разработчика.

    Несколько раз уже сталкивался с тем, что инвесторов или партнеров интересует платформа, и к Java относятся намного лучше, чем, например, к .Net
    • +1
      Или наоборот — тоже частая ситуация. Или, например, человек, который в первый и в последний раз что-то прогал на С в 93-м говорит, что «вон ту задачу можно решить только на С» и хоть трава не расти, процентов 70 ресурсов уходят на переубеждение.
    • 0
      С инвесторами просто, Java одно из самых распространенных энтерпрайз решений, а люди вливающие бабло хотят какой-то надежности.
      Такая же ситуация с linux системами в банках, в основном там всякие ред хаты встречаются, потому что они на тех.саппорте, имееются бумажечки(свидетельства и лицензии всякие) и это инвесторам сильно больше по душе, чем какой-нить gentoo.
      Никакой магии.
      • 0
        имееются бумажечки(свидетельства и лицензии всякие)

        Эти всякие бумажечки для банка чуть не лицензии стоить могут :)
  • +1
    Хорошая статья, спасибо!
    Вы бы еще опросник добавили, кто какой вариант интерпретатора пользует: cpython, stackless, pypy, etc…
    Например, мне было бы интересно посмотреть, стоит ли заморачиваться и подгонять свои open source пакеты под pypy =)
    • +1
      Добавил…
      • +5
        Там специально нет обычного CPython?
        • 0
          это была очепятка, но я думаю все поняли под этим «CPython», да и cython в действительности superset над ним, поэтому просто поправил…
  • +10
    Всё-таки вы так и не ответили на исходную статью — там всё же приводятся бенчмарки для более-менее одного алгоритма, реализованного в терминах разных языков. Вы же говорите, «эту задачу можно решать лучшим способом, тогда и результат будет лучше!». Но вы не удосужились реализовать ваш другой способ на других языках и провести в таком виде тест, так что ваш результат имеет смысл не в контексте сравнения языков, а в контексте сравнения программистов ;)
    • –1
      А то что оригинальный тест (хоть даже и с «сахаром») рвет на PyPy ту же scala в клочья — это вы видимо пропустили…
      • +5
        Кто-нибудь подскажет, где мне, изучающему python, почитать о том, почему так происходит? Каковы внутренние отличия?
      • +6
        Чтобы уж совсем корректно «сшить» ваш тест с тестами из исходной статьи надо было бы еще добавить исполнение оригинального теста на Python2.7 на вашем железе — оно ведь все таки другое…
        • 0
          Или просто попробовать на scala, что я и сделал кстати (в моем случае только версии 2.10.4) — совпадение практически полное. (Я из второго питона держу только pypy.)
    • +1
      Добавил Scala тест. Никаких оптимизаций не делал, код практически один в один. Сразу скажу, что на максимально эффективных алгоритмах Scala немного проигрывает из-за boxing/unboxing. Оптимизацию делать не стал, т.к. в реальной жизни такого рода оптимизации делают редко. Также siev2 не имеет смысла в Scala, т.к. не существует неявного эффективного преобразования из целочисленного в булевое.

      Результаты для "$ script 100000 max 1000":
      • pypy3: max — 21.24 ms, orgm — 35.82 ms, siev1 — 2.13 ms, siev2 — 1.18 ms, osie1 — 1.28 ms, osie2 — 1.23 ms
      • scala: max — 6.81 ms, orgm — 14.40 ms, siev — 1.66 ms, osie1 — 2.43 ms, osie2 — 2.26 ms
      • python3: max — 322.58 ms, orgm — 283.06 ms, siev1 — 26.48 ms, siev2 — 27.89 ms, osie1 — 30.57 ms, osie2 — 28.85 ms
      • 0
        Спасибо, практически ожидаемые результаты. Один вопрос — вы пробовали только несколько итераций? Если одну, но 10M?
        • 0
          Попробовал с 10M. Пришлось выделить больше памяти для Scala (вылетает с OutOfMemory потому что по умолчанию выделяется только 128 Mb или что-то типа того, не хочу врать), так что использовал скрипт как «scala -J-Xmx2g sexy-primes-test.scala 10000000 max»:
          • pypy3: max — 11153.52 ms, orgm — 16668.04 ms, siev1 — 482.62 ms, siev2 — 223.11 ms, osie1 — 208.16 ms, osie2 — 203.30 ms
          • scala: max — 3425.13 ms, orgm — 9491.97 ms, siev — 2149.22 ms, osie1 — 2141.02 ms, osie2 — 1612.79 ms
          • 0
            хм, не то чтобы очень неожиданно, но… какая у вас скала? и что за железо?
            • 0
              MacBook Pro: OS X Yosemite 10.10.3 (14D136), Processor: 2.3 GHz Intel Core i7, Memory: 16 GB 1600 MHz DDR3
              PyPy3: Python 3.2.5 [PyPy 2.4.0 with GCC 4.2.1]
              Scala: 2.11.6 (Java HotSpot(TM) 64-Bit Server VM, Java 1.8.0_40)

              Я перезапустил скрипты с большим количеством итераций (100 итераций), чтобы минимизировать разброс:
              • pypy3: max — 10339.21 ms, orgm — 16056.41 ms, siev1 — 430.27 ms, siev2 — 190.77 ms, osie1 — 202.00 ms, osie2 — 201.17 ms
              • scala: max — 3176.92 ms, orgm — 9100.62 ms, siev — 645.46 ms, osie1 — 671.52 ms, osie2 — 602.37 ms


              Еще хочу попробовать на своем старом ноуте, есть подозрение, что операционная система может влиять тоже. Отпишусь позже.
              • 0
                У меня i5 2.3GHz (не ноут), pypy тот же, но скала — 2.10.4 (тест пускал на работе, там win7 x64, JVM вроде тоже 1.8)
                Т.к. вот «max» на pypy3 = 5.2s, scala = 6.5s. На сите же у скала, все как и у вас в три раза медленнее pypy. Может JVM чем отличаются или на win он чуть хуже. Хотя у меня pypy на «max» в 2-а раза быстрее вашего. Мне просто порядок не понятен.
            • 0
              Протестировал на старом железе (Pentium T4500 @ 2.30GHz, 3Gb RAM). В целом распределение такое же для других операционных систем, но относительные величины немного разные. Из-за ограничений в скорости использовал «script 100000 max 100».

              Linux Mint 17.1 (3.13.0-37-generic #64-Ubuntu SMP):
              • PyPy3: max — 49.95 ms, orgm — 92.91 ms, siev1 — 6.41 ms, siev2 — 4.81 ms, osie1 — 5.06 ms, osie2 — 4.75 ms
              • Scala: max — 11.71 ms, orgm — 33.12 ms, siev — 6.87 ms, osie1 — 7.44 ms, osie2 — 6.64 ms


              Windows 7 (7601.win7sp1_gdr.140303-2144):
              • PyPy3: max — 35.17 ms, orgm — 119.14 ms, siev1 — 9.36 ms, siev2 — 4.83 ms, osie1 — 5.77 ms, osie2 — 4.85 ms
              • Scala: max — 21.85 ms, orgm — 48.55 ms, siev — 10.74 ms, osie1 — 13.08 ms, osie2 — 10.82 ms


              В обоих тестах были использованы ванильные версии: Python 3.2.5 [PyPy 2.4.0], Scala 2.11.6 (Java 1.8.0_45).
  • +8
    Если вы защищаете свою существующую разработку от переписывания, то тут естественно надо учитывать и риски, и целесообразность в условиях того, что уже достигнуто на данный момент.

    Если вы пытаетесь доказать, что Питон на самом деле быстрый, то все таки это несостоятельно — сами же говорите, что выкинули почти все стандартные компоненты и по сути собрали собственную систему исполнения.

    Если кто-то будет выбирать Питон или Скалу для старта проекта — какой смысл брать питон, рассчитанный вроде бы на использование не-системщиками, зная, что для достижения приличной скорости надо залезать в дебри и обладать очень хорошей именно системной и компиляторной экспертизой. Опять же, лишние риски
    • –2
      Вот поэтому, мы и разговариваем на разных языках…

      В тестах же (кроме одного) использовал стандартные сборки (да pypy уже давно дефакто стандарт)…
      • +3
        Я говорю не про дурацкие простые числа, а про вашу реальную продакшен-систему. Если со стандартным питоном все хорошо, зачем вам перебирать и затачивать систему исполнения? Если кто-то начинает писать аналогичную систему с нуля, может ли он выбрать Питон рассчитывать, что ему не придется повторять ваш путь?
        • +1
          Автор уже коментировал что-то подобное тут. Если я правильно понял, то раньше они дошли до ситуации, когда стандартного питона им уже не хватало, а переписывать на что-то другое было нецелесообразно, и pypy был перспективный, но сырой, так-что они сделали свой python
    • +2
      Pypy достаточно быстр.
      • +3
        Тогда зачем автору в принципе «собственный Jit, MemMgr, GC»?
        • –3
          потому что могу ©
          это на самом деле не совсем касается темы статьи…
  • +2
    … А пока вы практиковались в занимательной арифметике чуть менее амбициозный джуниор тихо кивнул на «команду свыше» и молча начал пилить на скалке.
    Есть такая тема, что когда отдел большой, то со временем «неудобные» вопросы начинают уходить к тихим сговорчивым лидам.
    • +4
      А потом вдруг оказывается, что люди тихо и сговорчиво написали тормозного монстра, освоили бабло и умыли руки, а заказчик обанкротился, потому что у конкурента всё летает ;)
  • +2
    Хотелось бы добавить несколько ссылок. Автор явно любит свое PyMNg творение, так что никакие бенчмарки не повлияют на его мнение, однако для других это может быть полезно:


    Что касается PyPy и то, что он где-то «стандарт де-факто» — здесь надо наверное уточнять область. Лично я вижу, что в основном используется CPython, из-за того, что он 100%-совместим со всеми библиотеками, плюс если надо какую-то часть ускорить, всегда можно написать расширение на C (например с использованием Cython). Python выбирают не из-за скорости, тут даже говорить не о чем, а из-за количества доступных библиотек. И в этом плане использование PyPy рискованно, но опять-таки это зависит от области применения.

    И наконец насчет Legacy. Я знаю несколько примеров, когда полностью меняли технологический стек, в основном из-за скорости. Одно из хороший решений — использование ZeroMQ, можно разделить приложение на несколько частей (микро-сервисы) и организовать коммуникации между ними (даже если это простой Request-Reply). После этого любой микро-сервис можно переписать на другой язык программирования и уже имея две версии, делать сравнения и анализ.
  • +3
    Я не поленился скачал pypy3 запустил на нем оригинальный пример поменяв на range: 3,6-4 с, взял С пример и перенес на яву 1.7 1-в-1: 1,7 с. Разумеется, тесты не по кананонам, без прогревов jvm, усреднений и тп. У меня ssd диск и i72600k, а у вас может ява стартанет медленнее, тут слишком много нюансов для таких утверждений.

    Еще надо внимательно смотреть, что делаем и зачем. С пример делает принт каждый раз как найдено число, остальные собирают массив и потом один раз делают принт, это все же разные вещи. Сама реализация выделения дополнительной памяти для массива может быть разная, что тогда мы сравниваем? Есть настройки JIT компиляции в jvm, тоже можно покрутить, только что это покажет?
    • 0
      С пример делает принт каждый раз как найдено число, остальные собирают массив и потом один раз делают принт, это все же разные вещи.

      В сях наверняка буферизован ввод-вывод.
      • +2
        Он везде буферизован, но дело не в этом — просто «положить результат в лукошко» или таки запустить целую функцию, которая делает явно больше, чем собирает результат (например, конвертация числа в строку, что для больших чисел уже «длинная» операция, и положить уже этот распухший результат в буфер).
    • +1
      Попробовал тоже самое на PureBasic (его компилятор вообще не умеет оптимизировать) ~ 4 сек. Не хуже, чем pypy3. Чтобы добавить комизма ситуации, я написал тоже самое на ActionScript3, без ввода вывода его время 3,8 сек.
      • +1
        А яваскрипт показал 2 сек легко печатая в консоль файрбага) Это без всяких asm.js.
  • +3
    Похоже это просто пиар своей платформы. Впрочем не вижу в этом ничего плохого. ))
    Странный способ убеждать продажника. Обычно им достаточно на бумажке подсчитать сколько времени займёт набор новой команды и переписывание. И пояснить, что развитие проекта на это время придётся полностью остановить…
    • –2
      Ага. Как вы тролли достали — ведь даже на хабре…
      • 0
        Тролли? А что вас так заусило?
        Оптимизация за счет использования более специфических, не библиотечных алгоритмов, оптимизированнных под конкретную реализацию языка, это новость разве что для новичков…
        Опять же не вижу в этом ничего плохого. Кто-то новичкам должен рассказать про разницу между использованием библиотечных функций и самописных, оптимизированных под конкретную задачу и конкретный транслятор…
        Но опять же, чтобы новичкам например знать о «туповатой реализации bool в pypy» надо наверное написать свою реализацию python'a.
        И? Какова мораль? Для новичков мораль конкретная: учите asm (дабы понимать разницу между туповатой реализацией и «нетуповатой») и учите классические алгоритмы.
        А для не новичков?
        • 0
          По пунктам:
          1. Пиар чего? (где скачать, где ссылка, где я вообще работаю?)
          2. Я убеждал нач-проекта и немного продажника (по совместительству)… И это все что вы из статьи вынесли?
          3. По поводу вашего последнего же коммента я лучше промолчу. Хотя нет — учите asm.
  • –1
    sebres, спасибо за статью, c performance все более менее понятно. А вы не думали, что есть другие плюсы Scala по сравнению с Python? Например, статическая типизация. Какой размер вашей кодовой базы? (количество функций, количество классов, модули) Если расширяемость вашей кодовой базы (в смысле добавления новых функций пользовательского уровня) примерно происходит в виде «написал(три) одну новую фунцию на Питоне, которая ни от чего особо не зависит», то может быть, разницы вы не почувствуете. Но если приходится менять структуры классов, проводить рефакторинги, да и вообще, понимать, где в программе какие данные, где начала и где концы, образно говоря, верифицировать код до его запуска, то поддерживать такие программы на языках типа Python — есть не очень приятное занятие, ИМХО, если не назвать это оверхэдом.
    • +4
      кому статическая типизация плюс, кому минус…
      поддерживать такие программы на языках типа Python — есть не очень приятное занятие, ИМХО, если не назвать это оверхэдом.
      Ни разу не чувствовал дискомфорт, даже на тикле, у которого с типизацией еще «хуже».
      • +1
        Прошу прощения, но у вас постоянно этот «тикл». Это Tcl что ли?
        • 0
          А что такого?

          Классная штука, очень обидно, что он незаслуженно забыт.
    • +2
      Пример на scala — без прогрева, как минимум. Значит результат можно отправлять в помойку. На JVM JIT начинает оптимизировать методы, если количество вызовов конкретного метода превышает некоторый порог (на JVM в server mode это порядко 10к, если не ошибаюсь). Если это происходит во время «бенчмарка» — результат оказывается хуже, т. к. измерялось ещё и время компиляции и замены метода.

      Если метод ещё не успел скомпилироваться — то измерялось время работы кода в интерпретируемом режиме (и для сравнения стоит выкинуть из остальных JIT вообще).
  • 0
    Подправил тут кое-что для сито-вариантов (см. commit): а именно деление сразу целочисленное без cast-а в int и итератор в sexy_primes_below сразу только по нечетным (9, 11, 13...) т.е. с шагом 2.

    В результате для pypy время исполнения практически не изменилось; CPython же исполняет теперь sieve-варианты в два быстрее.
  • +1
    Согласен с автором, что только «быстрота» и результаты бенчмарков, где сравнивают теплое с мягким, — это плохой критерий для выбора языка.

    Чисто для контраста процитирую пост(*) недельной давности:

    >… мы много занимаемся машинным обучением на очень больших массивах данных. Раньше для разработки прототипов мы использовали связку IPython + Pyhs2 (hive драйвер для Python) + Pandas + Sklearn. В конце лета 2014 года приняли принципиальное решение перейти на Spark, так как эксперименты показали, что мы получим 3-4 кратное повышение производительности на том же парке серверов.

    Есть конкретная задача из жизни. Есть мотивация улучшить проект. Люди рассматривали разные варианты, анализировали плюсы/минусы. В итоге:

    > Мы решили выбрать Scala, так как именно на нем написан Spark, то есть можно анализировать его исходный код и при необходимости исправлять ошибки, плюс — это JVM, на котором крутится весь Hadoop.

    *Ссылка на полную версию: habrahabr.ru/company/retailrocket/blog/258543
  • –1
    #return ((n & 1) and all(n % i for i in range(3, int(math.sqrt(n))+1, 2)))


    Тут все проще, resolve операции (.) просто будут потихоньку притормаживать, рекомендуется просто обрезать по возможности, например до sqrt(n).
    C pypy реализацией не знаком, но как минимум для cpython это справедливо.

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.