Является ли поддельный стек быстрее реального

Question

Я делаю рекурсивный разбор.

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

Было бы быстрее иметь стек с идентификатором состояния, например:

 int* stack = 0
 int top = 0;
 // ...
 // drill down bit
 if (stack == 0)
     stack = (int*)malloc(STACK_JUMP_SIZE);
 else if (top % STACK_JUMP_SIZE == 0)
     stack = (int*)realloc(stack, (top+STACK_JUMP_SIZE) * sizeof(int));
 stack[top++] = currentState;
 // ...
 // pop up later
 {currentState = stack[--top]; {
 if (top == 0) {
     free(stack);
     stack = 0;
 } else if ((top+1) % STACK_JUMP_SIZE == 0) {
     stack = (int*)realloc(stack, (top+1)*sizeof(int));
 }

Или было бы быстрее разделить это на правильные функции и позволить C ++ беспокоиться о стеке.

(я знаю, что кто-то скажет мне: «это C, это не c ++», поэтому я с превентивным ответом отвечаю, моя программа c ++, но в ней много c).

Answer 1

Это зависит от реализации - заранее сказать нельзя. На машине, где вызовы функций дешевы (например, SPARC), функция стек, вероятно, будет быстрее, но даже там, такие проблемы, как локализация вмешиваются. (Стек машины занимает больше места, потому что он укладывает больше информация, чем ваш смоделированный стек.) Я бы разбил вещь на правильные рекурсивные функции, и только попробуйте ручное управление стека, если это оказывается узким местом. Если ... Ручное управление стека не имеет одно важное преимущество: обработка ошибок. Переполнение стека машин неопределенное поведение: если malloc или realloc вернет нулевой указатель, вы может, по крайней мере, сообщить об ошибке чисто.

Если вы имитируете стек, вам следует рассмотреть возможность использования std::vector, а не malloc / realloc / free. Это спасет вас, если есть исключение, и это также, вероятно, будет немного быстрее. Если ты можешь установить верхний предел размера стека, и он не слишком большой, объявление стека как массива стиля C в стеке будет даже быстрее.