Вектор Джулии {Vector{T}} хранится в памяти непрерывно?

Question

Чтобы мотивировать мой вопрос, рассмотрим случай, когда имеем дело с неровными массивами (для простоты) типа элемента Int в юли. Есть два способа их хранения:

1. Как Vector{Vector{Int}}
2. Как Vector{Union{Vector{Int}, Int}} (особенно, если предполагается хранить достаточно большое количество 1-элементных векторов)

У меня вопрос, какой из них более эффективен / быстрее / лучше?

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

1. Я предполагаю, что переменная типа Vector{Vector{Int}}, будет считаться массивом однородного типа, и поэтому я ожидаю, что он будет храниться непрерывно в памяти и, как таковой, будет более дружественным к процессору кеш-кэша. Я прав? Или смежность применяется только к массивам, у которых тип данных элементов является примитивным?

2. Будет ли переменная типа Vector{Union{Vector{Int}, Int}} считается неоднородным массивом, и как таковой хранится не непрерывно в памяти?

3. Как преимущество непрерывного представления в памяти сравнивается с преимуществом отсутствия контейнера массива для одноэлементных элементов массивов, то есть хранения их как примитивного типа данных (Int в этом случае)? Какой из них дает больше эффективности?

Answer 1

Массивы Юлии будут хранить только элементы типа T без коробки, если isbits(T) правда. То есть элементы должны быть как неизменяемыми, так и без указателей. Простой способ проверить, сохраняются ли элементы немедленно, - выделить неинициализированный массив. Непрерывные массивы распакованных (непосредственных) значений будут иметь бред:

julia> Array(Int, 3)
3-element Array{Int64,1}:
 4430901168
 4470602000
 4430901232

в то время как массивы типов не-isbits будут иметь #undef указатели:

julia> Array(Vector{Int}, 3)
3-element Array{Array{Int64,1},1}:
 #undef
 #undef
 #undef

Представьте, что произойдет, если последний вернет один непрерывный кусок Ints. Как бы он знал, насколько большой, чтобы сделать это? Или где остановился один вектор, а начался следующий? Это будет зависеть от размеров векторов, которые пока не известны.

Vector{Union{Vector{Int}, Int}} аналогично будет хранить свои элементы как указатели; на этот раз это потому, что Джулия не знает, как интерпретировать каждый элемент в строке (должен ли он читать память как целое число или как массив?). У него есть дополнительный недостаток, заключающийся в том, что Джулия больше не знает, какой тип будет возвращен из индексации. Это нестабильность типа и, безусловно, будет намного хуже для производительности, чем просто использование одноэлементных векторов.

Можно создать свой собственный тип рваного массива, который хранит свои элементы встроенными, но очень сложно заставить его работать со стандартной библиотекой, как с обычным массивом, поскольку он нарушает многие предположения о том, как работает индексирование. Вы можете взглянуть на мою последнюю попытку: RaggedArrays.jl. Вы можете увидеть, как я сравниваю это с предыдущими усилиями в выпуске № 2.