Лучший способ реализовать динамический тип стека? или я злоупотребляю realloc?

Question

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

Это моя реализация (код psuedo)

//push method
function Push(int)
{
    Increase (realloc) stack by 4 bytes;
    Push int into the new memory area;
}

//pop method
function Pop()
{
    collect int from the top of the stack;
    reallocate (realloc) the stack to shrink it by 4 bytes;
    return int;
}

Теперь некоторые люди говорят, что использование вызова realloc () для изменения размера стека после получения значения отрицательно сказывается на производительности, поэтому у меня есть несколько вопросов:

1. Лучше всего просто увеличить стек с помощью malloc, а затем освободить его в конце программы?
2. Для изменения размера стека (push) лучше всего увеличить его на 4 байта или более?
3. Лучше ли увеличивать стек, удваивая объем памяти, выделяемой при его заполнении?
4. Что вы думаете о приведенном выше коде?

Answer 1

Стандартный метод состоит в том, чтобы увеличивать размер только в 2 раза и сокращать его только тогда, когда эффективное использование памяти меньше четверти.

Таким образом, вы можете быть уверены, что никогда не используете больше O (нужной вам памяти), а также можете доказать, что стек амортизируется постоянным временем.

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

Ссылка на статью в Википедии с более подробным объяснением

Answer 2

Почти каждая структура переменного размера, реализованная в популярных библиотеках, выполняет небольшую оптимизацию, чтобы избежать повторного использования. Помните, что обычно для того, чтобы увеличить их, нужно скопировать данные.

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

OTOH, некоторые реализации realloc () уже делают это за вас. увы, я сомневаюсь, что ваш «неясный язык» делает это ...

Answer 3

Определенно не увеличивайте и не уменьшайте 4 байта за раз. Ваша куча станет очень фрагментированной, и вы будете проводить слишком много времени в распределителе. Даже в архитектуре с ограниченным объемом памяти вы не хотите так микроуправлять памятью.

Выберите «размер страницы» и увеличьте на эту величину. Обычно рекомендуется удваивать размер, но я не уверен, почему это так. Возможно, вы знаете больше о том, как будет использоваться стек, чтобы понять, как лучше всего увеличить размер.