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

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

Это зависит от типа элементов массива

для какого-то типа намного медленнее получается?

Если копирование может быть выполнено одной процессорной инструкцией, то зависит уже от реализации процессора и его размеров регистров

Не факт, что однобайтовые элементы будут копироваться медленнее, чем 8-ми байтовые. Зависит от процессора

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

иммутабельные структуры, кстати, хранятся прямо в массиве

по крайней мере должны :)

Abc[] явно не будет компактно упакован

ну, Vector внутри - значит по факту мутабельная структура

Abc как раз будет очень компактный :-)

Он будет просто указатели хранить.

Да, но как оно в памяти ляжет - надо бы проверить

кстати, есть ещё пакет BangBang, бывает прям очень удобно для постепенного роста вектора: он позволяет не указывать тип элементов сразу, а увеличивает его по необходимости

и скорость по сути не страдает:


julia> using BangBang
julia> function f(n)
      vec = Union{}[]
      for i in 1:n
          vec = push!!(vec, (;i, j=n-i))
      end
      return vec
end

julia> @btime f(10^3);
 7.648 μs (12 allocations: 32.59 KiB)

julia> @btime f(10^6);
 7.102 ms (22 allocations: 17.00 MiB)

Вы путаете эти вещи, Abc будет упакован компактно и линейно в массиве потому что структура иммутабельна)

То что сама структура содержит объекты по ссылке это уже другой вопрос

Я не путаю, я не знаю как Джулия принимает решение об упаковке структур в массив 🙂

Если есть ссылка на эту тему - поделитесь

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