arrays - 使用数组 View 时出现意外的内存分配 (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

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

不幸的是，一些SubArray当前(截至 2017 年末)对象必须存储在堆上。原因是因为 Julia 是 garbage-collected语言，这意味着如果 A是一个不再使用的堆分配对象，则 A可能会从内存中释放。关键点是:目前，引用 A仅当其他变量存储在堆上时，才会计算这些变量的值。因此，如果全部 SubArray s 存储在堆栈上，这样的代码会遇到问题:

function create()
    A = rand(1000)
    getfirst(view(A, 1:10))
end

function getfirst(v)
    gc()   # this triggers garbage collection
    first(v)
end

因为create不使用A再次调用 getfirst 后，这不是“保护”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)

这个问题有一个“明显”的解决方案:更改垃圾收集器，以便堆栈分配的变量可以保护堆分配的内存。这有一天会发生，但要正确支持这是一项极其复杂的操作。因此，目前的规则是任何包含堆分配内存引用的对象都必须存储在堆上。

最后还有一个微妙之处:Julia 的编译器非常智能，在某些情况下会忽略 SubArray 的创建。包装器(基本上，它以分别使用父数组对象和索引的方式重写代码，以便它永远不需要包装器本身)。为此，Julia 必须能够 inline任何函数都会调用创建 view 的函数。不幸的是，这里==对于编译器来说稍微太大而不愿意内联它。如果您手动写出将要执行的操作，那么编译器将忽略 view并且您还可以避免分配。