объясните про std::vector от фейсбука

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

это понятно. так а почему лучше выделять с фактором «1.5», а не «2»?

Потому что с «2» это фатальный недостаток.

Я думаю, они вот о чём.

Допустим, изначальный объем памяти под вектор - 2 байта. Добавляя в него элементы, он будет периодически переаллоцироваться такими шагами:

2, 4, 8, 16

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

2 + 4 + 8 + 16 = 30

30 байт, поэтому мы не можем их использовать повторно, нам нужны новые 32. 2 байта, как начальный размер - плохой пример, с 1024 байтами уже всё становится наглядней :)

С множителем «1.5» имеем (округляя до целого):

2, 3, 5, 8

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

Я не знаю, как происходит выделение памяти на самом деле, тут уже специалисты по libc/ядру лучше подскажут.

Ага. См. раздел «Коэффицент К». 1.5 это уже с учётом доп. памяти на заголовки чанков, т.к. идеальное значение равно золотой пропорции.

Спасибо! В таком случае вопрос: если была возможность выделить после двух байт еще 4, почему не был сделан realloc? А если realloc случился, то проблемы с «пробелами» как будто нет

Вектор - контейнер общего назначения, элементы в котором могут быть чем угодно, в т.ч. объектами классов со своими конструкторами копирования/операторами присваивания, от realloc-а не-POD-типы могут офигеть.

Но это, опять же, мои соображения, Мейерсов-Саттеров уже лет пять не открывал :)

Совершенно верно мыслишь.

will be never satisfiable by coalescing all previously-used chunks

Что, кстати, плохо, только если во всей программе только один вектор и есть, а вся суть программы состоит в увеличении этого вектора. И то, перерасход памяти составляет 100%, что плохо, но не катастрофично. Я ожидаю, что реальные программы будут использовать сотни векторов и сотни тысяч мелких объектов, которые с радостью будут переиспользовать освободившиеся куски от царь-вектора.

Что, кстати, плохо, только если во всей программе только один вектор и есть, а вся суть программы состоит в увеличении этого вектора.

Вектор не виноват )
Он только использует аллокатор, который ему дали, да!

царь-вектора

Царь-вектор - это вектор, написанный не какими-то нулячими phpшниками, а лично, и С?:) А также с обязательным использованием интринсиков и GCC-специфичных костылей.

Царь-пушка, Царь-колокол, Царь-вектор. А недавние веяния попросту опошлили слово царь.

Царь-царь!

Tsa'erlang

Я представил его интринсики в Эрланге...