使用数组视图时意外的内存分配 (julia)

Question

我正在尝试在数组 X 中搜索所需的模式（可变模板）。模板的长度为 9。

我在做类似的事情：

function check_alloc{T <: ZeroOne}(x :: AbstractArray{T}, temp :: AbstractArray{T})
    s = 0
    for i in 1 : 1000
        myView = view(x, i : i + 9)
        if myView == temp
            s += 1
        end
    end
    return s
end

并在此短循环中获得意外的内存分配（46 KB）。为什么会发生这种情况以及如何防止内存分配和性能下降？

Answer 1

这至少适用于任意大小的 temp 和 x 但仍然有 ~KB 分配。

function check_alloc{T}(x :: AbstractArray{T}, temp :: AbstractArray{T})
    s = 0
    pl = length(temp)
    for i in 1:length(x)-pl+1
        @views if x[i:i+pl-1] == temp
            s += 1
        end
    end
    return s
end

编辑：正如@Sairus 在评论中所建议的那样，可以本着这种精神做一些事情：

function check_alloc2{T}(x :: AbstractArray{T}, temp :: AbstractArray{T})
    s = 0
    pl = length(temp)
    plr = 1:pl
    for i in 1:length(x)-pl+1
        same = true
        for k in plr
            @inbounds if x[i+k-1] != temp[k]
                same = false
                break
            end
        end
        if same
            s+=1
        end
    end
    return s
end

这没有分配：

julia> using BenchmarkTools

julia> a = collect(1:1000);

julia> b = collect(5:12);

julia> @btime check_alloc2($a,$b);
  1.195 μs (0 allocations: 0 bytes)

Answer 2

您获得分配的原因是因为 view(A, i:i+9) 创建了一个名为 SubArray 的小对象。这只是一个 "wrapper"，本质上存储了对 A 的引用和您传入的索引 (i:i+9)。因为包装器很小（一维对象大约 40 字节），所以有两个合理的存储选择：on the stack or on the heap。 "Allocations" 仅指堆内存，因此如果 Julia 可以将包装器存储在堆栈上，它将报告没有分配（并且也会更快）。

不幸的是，目前（截至 2017 年底）一些 SubArray 对象必须存储在堆上。原因是因为 Julia 是一种 garbage-collected 语言，这意味着如果 A 是一个不再使用的堆分配对象，那么 A 可能会从内存中释放出来。关键点在于：目前，仅当这些变量存储在堆上时，才会计算来自其他变量的对A 的引用。因此，如果所有 SubArray 都存储在堆栈中，您将遇到这样的代码问题：

function create() A = rand(1000) getfirst(view(A, 1:10)) end function getfirst(v) gc() # this triggers garbage collection first(v) end

因为 create 在调用 getfirst 之后不再使用 A，所以它不是 "protecting" A。风险是 gc 调用最终可能会释放与 A 关联的内存（从而破坏 v 本身中条目的任何使用，因为 v 依赖于 A)，除非 v 保护 A 不被垃圾收集。但是目前，堆栈分配的变量无法保护堆分配的内存：垃圾收集器仅扫描堆上的变量。

您可以使用原始函数观看此操作，通过删除（无关紧要的，出于这些目的）T<:ZeroOne 并允许任何 T.

function check_alloc(x::AbstractArray{T}, temp::AbstractArray{T}) where T s = 0 for i in 1 : 1000 myView = view(x, i : i + 9) if myView == temp s += 1 end end return s end a = collect(1:1010); # this uses heap-allocated memory b = collect(1:10); @time check_alloc(a, b); # ignore the first due to JIT-compilation @time check_alloc(a, b) a = 1:1010 # this doesn't require heap-allocated memory @time check_alloc(a, b); # ignore due to JIT-compilation @time check_alloc(a, b)

从第一个（a = collect(1:1010)），你得到

julia> @time check_alloc(a, b) 0.000022 seconds (1.00 k allocations: 47.031 KiB)

（注意这是每次迭代约 47 个字节，与 SubArray 包装器的大小一致）但是从第二个（使用 a = 1:1010）你得到

julia> @time check_alloc(a, b) 0.000020 seconds (4 allocations: 160 bytes)

这个问题有一个 "obvious" 修复：更改垃圾收集器，使堆栈分配的变量可以保护堆分配的内存。总有一天会发生这种情况，但要正确支持它是一项极其复杂的操作。所以现在，规则是任何包含对堆分配内存的引用的对象都必须存储在堆上。

还有一个最后的微妙之处：Julia 的编译器非常聪明，在某些情况下省略了 SubArray 包装器的创建（基本上，它以一种使用父数组对象和索引的方式重写您的代码分开以便它永远不需要包装器本身）。为此，Julia 必须能够 inline 任何函数调用创建 view 的函数。不幸的是，这里的 == 有点太大了，编译器不愿意将它内联。如果您手动写出将要执行的操作，那么编译器将省略 view，您也将避免分配。

Answer 3

从 Julia 1.7.0 开始（甚至更早），来自@carstenbauer 的第一个带有视图的代码不再分配（在堆上）：

function check_alloc(x :: AbstractArray{T}, temp :: AbstractArray{T}) where T
     s = 0
     pl = length(temp)
     for i in 1:length(x)-pl+1
          @views if x[i:i+pl-1] == temp
             s += 1
           end
     end
     return s
end
using BenchmarkTools
a = collect(1:1000);
b = collect(5:12);
@btime check_alloc($a,$b);
# returns
#  8.495 μs (0 allocations: 0 bytes)

使用数组视图时意外的内存分配 (julia)

Unexpected memory allocation when using array views (julia)

arrays

performance

allocation

julia