Производительность различных реализаций стека в ПХП
Я совсем перестал писать на технические темы в блоге. Это объяснимо: я много разрабатываю, но поделиться нечем, всё это весьма специфично для системы документооборота. Недавно, например, я думал над тем какой бы язык применить для описания фильтров в системе. Они должны срабатывать много и часто, и опосредованно управлять движением документов. Пользователь писать самостоятельно их не будет (или почти не будет), они будут составяться «конструктором», но система как-то должна на них срабатывать.
Выбрал обратную польскую запись. Она компактна, просто парсится, для неё не нужно строить дерево, там нет скобок, но при этом по мощности польностью эквивалентна привычной всем со школы записи. Идея в том, что сначала на стек записываются операнды, а потом указывается операция, которая берёт их со стека и записывает обратно результат:
# традиционная запись:
(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 секунды.
А мой python сравним с php, даже чуть быстрее. Железо — младший Core i3.
php 5.3.8
python 2.7.3
У меня ПХП 5.3.10 с патчем Suhosin, Пайтон 2.7.1, CPU — Core 2 Duo (1,86 ГГц). А попробуйте PyPy для интереса?
Годы мчат, технологии плодятся и матереют, а FORTH живее всех живых! Искренне порадовало. Спасибо за приятные вспоминания!
Core i3 2,13 GHz, Windows 7:
Intel 6 cores, 3+ GHz, Ubuntu:
Комментарий для Павел Власов:
Странно, что у меня на «Маке» такой медленный Пайтон. С чем это связано, интересно?
Комментарий для masterspammer.livejournal.com:
Спасибо, поправил!
А вот пример на Google Go (у меня выполняется примерно за 0.046)
http://pastebin.com/VCQYkDqY
Комментарий для Евгения Степанищева:
Больше всего меня поразило в данной заметке что в комментарии можно вставлять код из пастебина. Это для всех или только для админа?р
Комментарий для hshhhhh.name:
Для всех :) Я просто об этом в подсказку не написал ещё :)
Комментарий для imap.livejournal.com:
Меня ещё в детстве этот язык поразил в самое сердце. Правда, я на нём и не программировал почти :)
кстати, в php вместо array_push лучше использовать $stack[] = ...
http://www.php.net/manual/ru/function.array-push.php
действительно, работает чуть быстрее
Комментарий для Линар:
Кстати да, я как-то и позабыл об этом факте, спасибо!