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

Question

У меня есть общий растущий буфер с отступом, чтобы накапливать «случайные» кусочки строк и затем извлекать результат. Код для обработки этого буфера записан простым 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 */

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

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

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

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

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

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

Answer 1

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

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

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

пост Эндрю Кенига в Usenet и P.J. Почта Usenet от Plauger .

Answer 2

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

Answer 3

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

new_size = old_size + ( old_size >> 1 ) + 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
...

Answer 4

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

Answer 5

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

Answer 6

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

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

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

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

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

Answer 7

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

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

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

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

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

Answer 8

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

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

Answer 9

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

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

---

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