为什么分配一个Union{T, Missing}类型的数组比T类型的数组慢一个数量级？

Question

在Julia中，分配一个Union{T, Missing}数组的代价非常昂贵。是否有任何绕过它的方法？

julia> @time Vector{Union{Missing, Int}}(undef, 10^7);
  0.031052 seconds (2 allocations: 85.831 MiB)

julia> @time Vector{Union{Int}}(undef, 10^7);
  0.000027 seconds (3 allocations: 76.294 MiB)

- هنروقتان

---

你对于更详细的回答有什么具体要求吗？ - Oscar Smith

我正在寻找一种解决方法，但在SOF中没有选项，所以我只能选择这个选项。 - هنروقتان

Answer 1

因为如果你把一个 Missing 类型与 Int 这样的位类型进行 Union 操作，那么 Julia 将设置这样一个向量的标志，表示该向量最初在每个条目中存储 missing：

julia> Vector{Union{Missing, Int}}(undef, 10^7)
10000000-element Vector{Union{Missing, Int64}}:
 missing
 missing
 ⋮
 missing
 missing

如果您使用的是非比特类型（non-bitstype），则不必设置每个条目的此类标志，如下所示：

julia> Vector{Union{Missing, String}}(undef, 10^7)
10000000-element Vector{Union{Missing, String}}:
 #undef
 #undef
   ⋮
 #undef
 #undef

因此性能相同：

julia> @btime Vector{Union{String}}(undef, 10^7);
  11.672 ms (3 allocations: 76.29 MiB)

julia> @btime Vector{Union{Missing, String}}(undef, 10^7);
  11.480 ms (2 allocations: 76.29 MiB)

- Bogumił Kamiński

---

fill(missing, 10^7) 返回一个 Vector{Missing}，它与 Vector{Union{Missing, Int}} 不同。由于 Vector{Missing} 只能保存一个值，因此可以更有效地存储。 - Kristoffer Carlsson

如果您有一个像Missing或Nothing这样的单例，并且eltype仅允许此类型，则无需执行fill。这正是例如Set作为带有Nothing值的Dict实现的方式。请检查例如Base.summarysize(fill(missing, 10^6))。 - Bogumił Kamiński

好的，很有道理。但是，没有填充怎么工作？一些COW / calloc魔法吗？ - phipsgabler

只有当数组是 Vector{Missing} 时，您才需要跟踪其长度，因为您知道每个元素都将是 Missing。 - Kristoffer Carlsson

也许你可以在这里更详细地回答：https://dev59.com/K8Pra4cB1Zd3GeqPeFpW。 - phipsgabler

Answer 2

区别在于联合数组会获得零初始化。您可以在此处查看决定此行为的代码：

https://github.com/JuliaLang/julia/blob/3f024fd0ab9e68b37d29fee6f2a9ab19819102c5/src/array.c#L191

这最终变成了对memset的调用：

https://github.com/JuliaLang/julia/blob/3f024fd0ab9e68b37d29fee6f2a9ab19819102c5/src/array.c#L144-L145

作为检查，我们可以比较 zeros 和分配联合数组：

julia> @time Vector{Union{Missing, Int}}(undef, 10^7);
  0.020609 seconds (2 allocations: 85.831 MiB)

julia> @time zeros(Int, 10^7);
  0.018375 seconds (2 allocations: 76.294 MiB)

时间相当可比。

然而，我认为这种性能差异在您的应用程序中不应该成为问题，除非您以相当奇怪的方式构建了它。在分配时间变得微不足道之前，您几乎无法对该数组进行任何操作。例如，仅设置未初始化数组的值就使其与联合数组的时间相似：

julia> function f()
           a = Vector{Int}(undef, 10^7)
           for i in eachindex(a)
               a[i] = 1
           end
           a
       end;

julia> function f_union()
           a = Vector{Union{Missing, Int}}(undef, 10^7)
           for i in eachindex(a)
               a[i] = 1
           end
           a
       end;

julia> @time f();
  0.015566 seconds (2 allocations: 76.294 MiB)

julia> @time f_union();
  0.026414 seconds (2 allocations: 85.831 MiB)

- Kristoffer Carlsson

---

如果我们深入细节，那么请注意，尽管当前的 Vector{Union{Missing, Int}}(undef, 10^7) 用 missing 填充数组，但这种行为并不保证（它被认为是实现细节）- 保证的是它将被填充为某个值。使用 Vector{Union{Missing, Int}}(missing, 10^7) 确保向量填充为 missing。与 Nothing 的联合也是如此。 - Bogumił Kamiński

但这可能成为瓶颈。例如，在我的系统上，如果我分配一个有10^9个元素的数组，并且（出于任何原因）这样做了100次，那么将浪费400秒钟来分配我需要用其他东西填充的东西。 - هنروقتان

不是真的。在400秒内，您无法对这10^11个元素进行任何有意义的计算。即使将它们初始化为一个值也需要大约400秒的时间。 - Oscar Smith

Answer 3

我们遇到了相同的问题，解决方法是使用以下方法：

x = Vector{Union{T,Missing}}(undef,1)
resize!(x, newlen)

- sl-solution