Стратегия роста буфера

У меня есть общий растущий буфер, который, как ожидается, накапливает "случайные" строковые фрагменты, а затем извлекает результат. Код для обработки этого буфера написан на простой C.

API псевдокода:

void write(buffer_t * buf, const unsigned char * bytes, size_t len);/* appends */
const unsigned char * buffer(buffer_t * buf);/* returns accumulated data */

Я думаю о стратегии роста, которую я должен выбрать для этого буфера.

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

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

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

Давным-давно Herb Sutter написал (ссылаясь на Эндрю Кенига), что лучшая стратегия - это, вероятно, экспоненциальный рост с коэффициентом 1.5 (поиск для "Стратегии роста" ). Это лучший выбор?

Любые советы? Что говорит ваш опыт?

Ответ 1

Если у вас нет веских оснований для этого, экспоненциальный рост, вероятно, лучший выбор. Использование 1.5 для экспоненты на самом деле не волшебное, и на самом деле это не то, что первоначально сказал Эндрю Кениг. Первоначально он сказал, что фактор роста должен быть меньше (1 + sqrt (5))/2 (~ 1.6).

~~Пит Беккер говорит, когда он был в Dinkumware~~ P.J. Plauger, владелец Dinkumware, говорит, что они провели некоторое тестирование и обнаружили, что 1.5 работал хорошо. Когда вы выделяете блок памяти, распределитель обычно выделяет блок, который, по крайней мере, немного больше, чем вы просили предоставить ему место для небольшой бухгалтерской информации. Мое предположение (хотя и не подтверждено каким-либо тестированием) заключается в том, что уменьшение коэффициента немного позволяет реальному размеру блока по-прежнему соответствовать пределу.

Литература: Я считаю, что Эндрю первоначально опубликовал это в журнале (журнал объектно-ориентированного программирования, IIRC), который не был опубликован уже много лет, поэтому получение перепечатки, вероятно, будет довольно сложным.

Andrew Koenig Usenet post, P.J. Сообщение Plauger Usenet.

Ответ 2

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

Ответ 3

Я обычно использую комбинацию добавления небольшого фиксированного количества и умножения на 1,5, потому что он эффективен для реализации и приводит к разумной ширине шага, которые вначале больше и имеют большую память, когда буфер растет. Как фиксированное смещение, я обычно использую начальный размер буфера и начинаю с довольно небольших начальных размеров:

new_size = old_size + ( old_size >> 1 ) + initial_size;

В качестве initial_size я использую 4 для типов коллекций 8, 12 или 16 для типов строк и от 128 до 4096 для буферов ввода/вывода в зависимости от контекста.

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

Итак, если вы начали с 100, вам понадобится, например, 6 увеличений, чтобы разместить 3000 элементов, а умножить только на 1,5 потребуется 9.

При больших размерах влияние добавления становится незначительным, что приводит к тому, что оба подхода одинаково хорошо масштабируются в 1,5 раза. Это эффективные факторы роста, если вы используете начальный размер как фиксированную сумму для добавления:

2.5
1.9
1.7
1.62
1.57
1.54
1.53
1.52
1.51
1.5
...

Ответ 4

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

Ответ 5

Ответ, как всегда, "зависит".

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

Итак, если у вас есть 8-байтовый буфер, и вам нужно больше выделять дополнительные 8 байтов, значит, выделение дополнительных 16 байтов - это, вероятно, хорошая идея - кто-то с 16-байтовым буфером вряд ли потребует дополнительный 1 байт. И если они это сделают, все, что происходит, вы теряете небольшую память.

Я думал, что лучшим фактором роста было 2 - т.е. удвоить ваш буфер, но если Koenig/Sutter скажут, что 1.5 является оптимальным, то я соглашаюсь с ними. Вы можете настроить свой темп роста после получения статистики использования.

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

Ответ 6

Двойной размер до порога (~ 100 МБ?), а затем уменьшите экспоненциальный рост до 1,5, 1.3
Другим вариантом является настройка размера буфера по умолчанию во время выполнения.

Ответ 7

Никто не может дать хороший совет, не зная о распределении, среде выполнения, характеристиках исполнения и т.д. и т.д.

Код, который работает, является более важным, чем высоко оптимизированный код... который находится в разработке. Выберите какой-нибудь алгоритм - любой работоспособный алгоритм - и попробуйте! Если он окажется субоптимальным, измените стратегию. Размещение этого элемента управления пользователем библиотеки часто не дает им никакой пользы. Но если у вас уже есть какая-то схема опций, добавление ее может быть полезно, если вы не нажмете на хороший алгоритм (а n ^ 1.5 - довольно хороший).

Кроме того, использование функции с именем write в C (не С++) конфликтует с < io.h > и < stdio.h > . Это прекрасно, если ничего не использует, но их также будет сложно добавить позже. Лучше всего использовать более описательное имя.

Ответ 8

Точка использования экспоненциального роста (будь то коэффициент 1,5 или 2) заключается в том, чтобы избежать копирования. Каждый раз, когда вы перераспределяете массив, вы можете вызвать неявную копию элемента, что, конечно, становится дороже, чем больше получается. Используя экспоненциальный рост, вы получаете амортизированное постоянное количество повторений - т.е. Вы редко заканчиваете копирование.

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

Ответ 9

Как дикая идея, для этого конкретного случая вы можете изменить API, чтобы потребовать caller выделить память для каждого фрагмента, а затем запомнить куски вместо копирования данных.

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

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

Недостаток заключается в том, что вызывающему абоненту придется динамически распределять каждый фрагмент. Чтобы обойти это, вы могли бы выделить память для каждого фрагмента и помнить об этом, а не хранить один большой буфер, который будет изменяться по мере его заполнения. Таким образом, вы будете копировать данные дважды (один раз в выделенный фрагмент, в другой раз в результирующую строку), но не более того. Если вам нужно изменить размер несколько раз, вы можете получить более двух копий.

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