LINUX.ORG.RU

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

 ,


0

4

https://github.com/facebook/folly/blob/master/folly/docs/FBVector.md здесь написано, что выделять память для вектора по степени двойки - плохо. Но вот причину я не могу понять:

What that really means is that the new request for a chunk will be never satisfiable by coalescing all previously-used chunks. We would of course want the vector to not crawl forward in memory, but instead to move back to its previously-allocated chunks. Any number smaller than 2 guarantees that you'll be able at some point to reuse the previous chunks



Последнее исправление: jcdr (всего исправлений: 1)

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

UVV ★★★★★
()
Ответ на: комментарий от jcdr

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

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

2, 4, 8, 16

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

2 + 4 + 8 + 16 = 30

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

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

2, 3, 5, 8

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

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

yoghurt ★★★★★
()
Последнее исправление: yoghurt (всего исправлений: 1)
Ответ на: комментарий от yoghurt

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

jcdr
() автор топика
Ответ на: комментарий от jcdr

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

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

yoghurt ★★★★★
()

will be never satisfiable by coalescing all previously-used chunks

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

i-rinat ★★★★★
()
Последнее исправление: i-rinat (всего исправлений: 1)
Ответ на: комментарий от i-rinat

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

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

AF ★★★
()
Ответ на: комментарий от i-rinat

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

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

Pavval ★★★★★
()
Ответ на: комментарий от i-rinat

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

Pavval ★★★★★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.