Это сайт — моя персональная записная книжка. Интересна мне, по большей части, история, своя жизнь и немного программирование.

Производительность различных реализаций стека в ПХП

разработка СЭД (36.14КиБ)

Я совсем перестал писать на технические темы в блоге. Это объяснимо: я много разрабатываю, но поделиться нечем, всё это весьма специфично для системы документооборота. Недавно, например, я думал над тем какой бы язык применить для описания фильтров в системе. Они должны срабатывать много и часто, и опосредованно управлять движением документов. Пользователь писать самостоятельно их не будет (или почти не будет), они будут составяться «конструктором», но система как-то должна на них срабатывать.

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

# традиционная запись:
(5 + 7) * 3
# обратная польская:
5 7 + 3 *
# а можно так:
3 5 7 + *

Так как упор на производительность, я реализовал простенькую стековую машинку с операциями сложения, вычитания, умножения, проверки на равенство и дублирования вершины стека с использованием простых массивов, ArrayObject и SplStack, чтобы проверить как в ПХП (на котором пишется наша система) дела с производительностью стека. ArrayObject тут скорее для полноты картины, так как у него нет метода pop, который доставал бы элемент с вершины, так что пришлось заменить его на отдельную функцию.

Результаты следующие:

mac@mac ~/Sites/test  $ php autoc/stack.php 
Array: 0.27216792106628
Array Object: 0.7418909072876
SplStack: 0.29819416999817

Как видно, примитивные типы всё-таки быстрее специализированного типа для организации стека из SPL, что печально, по крайней мере пока (у меня ПХП 5.3.10).

Для интереса, релизовал примерно то же самое на Пайтоне (только DUP немного иначе работает, для скорости):

from __future__ import print_function
import time

input = '10 20 100 + - 20 * DUP 10 20 + * =';
operations = {
    '+': lambda: stack.append(stack.pop() + stack.pop()),
    '-': lambda: stack.append(stack.pop() - stack.pop()),
    '*': lambda: stack.append(stack.pop() * stack.pop()),
    '=': lambda: stack.append(stack.pop() == stack.pop()),
    'DUP':  lambda: stack.append(stack[0]),
    'DUMP': lambda: print(stack)
}

t = time.time()

for x in xrange(0, 10000):
    stack = []

    for chunk in input.split(' '):
        operations.get(chunk, lambda: stack.append(int(chunk)))()

print('Python list: %f' % (time.time() - t))

Время выполнения — 0,56 секунды, то есть на ПХП быстрее. Зато, если запустить этот код через PyPy (это интерпретатор с JIT), то результат куда более впечатляет — 0,10 секунды.

14 комментариев
Павел Власов 2012

А мой python сравним с php, даже чуть быстрее. Железо — младший Core i3.

php 5.3.8

Array: 0.23640203475952
Array Object: 0.59683394432068
SplStack: 0.27202200889587

python 2.7.3

Python list: 0.223000

Евгений Степанищев (bolknote.ru) 2012

У меня ПХП 5.3.10 с патчем Suhosin, Пайтон 2.7.1, CPU — Core 2 Duo (1,86 ГГц). А попробуйте PyPy для интереса?

Dmitry V.Abramov (imap.livejournal.com) 2012

Годы мчат, технологии плодятся и матереют, а FORTH живее всех живых! Искренне порадовало. Спасибо за приятные вспоминания!

Павел Власов 2012

Core i3 2,13 GHz, Windows 7:

php-5.3.8.exe stack.php
Array: 0.23838210105896
Array Object: 0.58771395683289
SplStack: 0.29830312728882

python-2.7.3.exe stack.py
Python list: 0.220000

pypy-1.8.exe stack.py
Python list: 0.089000

Intel 6 cores, 3+ GHz, Ubuntu:

php stack.php 2> /dev/null
Array: 0.10121583938599
Array Object: 0.34955596923828
SplStack: 0.10594296455383

python-2.7.1 stack.py
Python list: 0.071310

pypy-1.8 stack.py
Python list: 0.033843

Евгений Степанищев (bolknote.ru) 2012

Комментарий для Павел Власов:

Странно, что у меня на «Маке» такой медленный Пайтон. С чем это связано, интересно?

masterspammer (masterspammer.livejournal.com) 2012

так как у него __?__ операции pop

Евгений Степанищев (bolknote.ru) 2012

Комментарий для masterspammer.livejournal.com:

Спасибо, поправил!

Евгений Степанищев (bolknote.ru) 2012

А вот пример на Google Go (у меня выполняется примерно за 0.046)
http://pastebin.com/VCQYkDqY

hshhhhh (hshhhhh.name) 2012

Комментарий для Евгения Степанищева:

Больше всего меня поразило в данной заметке что в комментарии можно вставлять код из пастебина. Это для всех или только для админа?р

Евгений Степанищев (bolknote.ru) 2012

Комментарий для hshhhhh.name:

Для всех :) Я просто об этом в подсказку не написал ещё :)

Евгений Степанищев (bolknote.ru) 2012

Комментарий для imap.livejournal.com:

FORTH живее всех живых! Искренне порадовало. Спасибо за приятные вспоминания!

Меня ещё в детстве этот язык поразил в самое сердце. Правда, я на нём и не программировал почти :)

Линар 2012

кстати, в php вместо array_push лучше использовать $stack[] = ...
http://www.php.net/manual/ru/function.array-push.php
действительно, работает чуть быстрее

Евгений Степанищев (bolknote.ru) 2012

Комментарий для Линар:

Кстати да, я как-то и позабыл об этом факте, спасибо!

DejaVu 2012

PHP 5.4.3 (cli) (built: May 8 2012 00:51:31)

P:\Workspace>php -f stack.txt
Array: 1.5796949863434
SplStack: 1.5660779476166

P:\Workspace>php -f stack.txt
Array: 1.5798320770264
SplStack: 1.5635960102081

P:\Workspace>php -f stack.txt
Array: 1.5831360816956
SplStack: 1.5718700885773