arrays - Julia 的 Vector{Vector{T}} 是否连续存储在内存中？

Question

为了激发我的问题，请考虑处理 jagged arrays 时的情况。 (为了简单起见)Julia 中的元素类型 Int。有两种存储方式:

1. 作为 Vector{Vector{Int}}
2. As Vector{Union{Vector{Int}, Int}}(特别是，如果希望存储足够多的 1 元素向量)

我的问题是哪一个更高效/更快/更好？

为了回答这个问题，我需要知道每个问题是如何存储在内存中的。即:

1. 我认为 Vector{Vector{Int}} 类型的变量将被视为同类类型数组，因此我希望它连续存储 在内存中，因此对 cpu 缓存更加友好。我对吗？或者连续性仅适用于元素数据类型为原始的数组？

2. Vector{Union{Vector{Int}, Int}} 类型的变量是否会被视为异构数组，因此不连续存储 在内存中？

3. 内存中连续表示的优点与没有用于 1 元素数组成员的数组容器的优点相比如何，即将它们存储为原始数据类型(在本例中为 Int) ？哪一种效率更高？

Answer 1

如果 isbits(T) 为 true，Julia 的数组将仅存储未装箱的 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

想象一下如果后者返回一个连续的 Int block 会发生什么。它怎么知道要制作多大呢？或者一个向量停止而下一个向量开始的地方？这将取决于向量的大小，目前尚不清楚。

A Vector{Union{Vector{Int}, Int}} 类似地将其元素存储为指针；这次是因为 Julia 不知道如何内联解释每个元素(它应该像整数还是像数组一样读取内存？)。它还有一个额外的缺点，即 Julia 不再知道索引会返回什么类型。这是一种类型不稳定，并且肯定会比仅使用单元素向量的性能更差。

可以创建自己的参差不齐的数组类型来内联存储其元素，但是使其像普通数组一样与标准库一起使用非常棘手，因为它打破了关于索引如何工作的许多假设。你可以看看我最新的尝试:RaggedArrays.jl 。您可以看到我如何将其与 Issue#2 中之前的工作进行比较。 .