时间戳

首页 > 解决方案 > Julia 数组数组：（行 -> 列）性能

arrays - Julia 数组数组：（行 -> 列）性能

问题描述

在这里完成 Julia 新手。

给定一个数组数组，我想组合每个子数组的对应元素。像这样的东西：

 [2, 7, 9]       [2, 3, 2, 7, 3]
 [3, 5, 4]       [7, 5, 7, 9, 5]
 [2, 7, 7]  ->   [9, 4, 7, 1, 1]
 [7, 9, 1]
 [3, 5, 1]

搜索 stackoverflow 我遇到了几个解决方案，而不是直接循环或列表理解。

julia> a=Vector{Int}[rand(1:10,3) for i=1:5]
5-element Array{Array{Int64,1},1}:
 [2, 7, 9]
 [3, 5, 4]
 [2, 7, 7]
 [7, 9, 1]
 [3, 5, 1]

julia> using BenchmarkTools

julia> @btime a2=mapslices( x -> [x], hcat(a...), dims=2)[:]
  6.174 μs (65 allocations: 3.45 KiB)
3-element Array{Array{Int64,1},1}:
 [2, 3, 2, 7, 3]
 [7, 5, 7, 9, 5]
 [9, 4, 7, 1, 1]

julia> @btime a3=[getindex.(a,i) for i=1:length(a[1])]
  948.087 ns (14 allocations: 768 bytes)
3-element Array{Array{Int64,1},1}:
 [2, 3, 2, 7, 3]
 [7, 5, 7, 9, 5]
 [9, 4, 7, 1, 1]

我的问题是：为什么第二个比第一个快六倍？和hcat有关系吗？

标签： arraysjulia

解决方案

基线和基准测试正确

好的，首先让我们在我的计算机上建立基线。

在我们做任何其他事情之前，我们需要确保我们没有对全局变量进行基准测试。来自BenchmarkTools 自述文件：

如果您要基准测试的表达式依赖于外部变量，您应该使用$将它们“插入”到基准表达式中，以避免使用 globals 进行基准测试的问题。本质上，任何插值变量$x或表达式$(...)在基准测试开始之前都是“预先计算的”......

julia> a=Vector{Int}[rand(1:10,3) for i=1:5];

julia> @btime a2=mapslices( x -> [x], hcat($a...), dims=2)[:];
  6.015 μs (65 allocations: 3.45 KiB)

julia> @btime a3=[getindex.($a,i) for i=1:length($a[1])];
  149.228 ns (6 allocations: 544 bytes)

（如果我没有插值，我会得到和你大致相同的结果a3 999.500 ns (14 allocations: 768 bytes)）。

所以它a3不是快 6 倍，而是实际上快了 33 倍。

为什么有区别？

分配。

与其他操作（所有语言）相比，分配相当慢。我们可以看到a2代码分配的比代码多得多a3。

所以让我们看看分配的位：

a2

  • [x]为每一列分配一个新的 1 元素数组
  • hcat分配一个连接所有内容的新矩阵
  • mapslices为从矩阵中取出的每个切片分配一个数组
  • mapslice分配一个数组来保存输出（有趣的是它不做视图，但我检查了）
  • [:]执行输出的重塑副本。（替代方案是vec返回一个重塑视图）

a3

  • getindex.(a, i)为输出的每一列分配一个数组（与mapslice输入矩阵的内部切片相同）

  • [ ... for ...]为输出分配一个数组（与 mapslices 输出相同）

    所以我们可以看到有一堆额外的分配a2在a3.

    如果我们只有与hcat.

    由于最初的问题询问是否是因为hcat让我们看一下。

我定义了一个新的基准保存到a4. 它使用eachslicewhich 将视图的（惰性）生成器返回到矩阵的切片中。所以那里的分配可以忽略不计。为了阻止它偷懒，我们collect它。this 的最终输出是 an Arrayof SubArrays （而不是 an Arrayof Arrays），但这很好，它会像它仍然是 subtypes 一样工作AbstractArray。

julia> @btime a4 = collect(eachslice(hcat($a...), dims=1));
  734.320 ns (13 allocations: 704 bytes)

这里我们的主要分配是 - hcat -collect它分配输出（与 相同[ ... for ...]）。

所以是的，它hcat有效果，但它与大部分差异相去甚远。

喷溅和reduce(hcat, xs)

喷溅是一种代价。它通常很小，直到你开始喷出数百个项目，但因为这是一个微基准，其他一切都如此之快，让我们看看它是如何删除它的。

Julia 有一个优化的函数，reduce(hcat, xs)可以xs作为数组的数组。

所以让我们看看情况如何：

julia> @btime a2_s=mapslices(x -> [x], reduce(hcat, $a), dims=2);
  5.278 μs (59 allocations: 3.17 KiB)

julia> @btime a4_s=collect(eachslice(reduce(hcat, $a), dims=1));
  337.656 ns (8 allocations: 528 bytes)

我们可以看到这是有区别的。但是在a2它并不多的情况下，因为它只hcat完成一次，x->x而在mapslices复制切片时的缓慢分配hcat会发生很多次。

我们能走得更快吗？

并不真地。 a3这几乎是理想的代码。它不分配任何不返回的内容。

想一想，如果我们愿意转而使用StaticArrays ，我们可以获得真正快得不合理的东西。

julia> b = @SVector [@SVector [rand(1:10) for ii in 1:3] for i=1:5];

julia> @btime b3=[getindex.($b,i) for i in 1:length($b[1])];
  36.055 ns (1 allocation: 208 bytes)

静态数组为编译器提供了更多信息。特别是所有数组的大小，以及它们都不会被改变的承诺。这意味着它可以： - 展开循环 - 编译时的边界检查 - 在堆栈（而不是堆）上分配它们 - 可能是我忘记的其他一些事情。

这让优化器（在 Julia 和 LLVM 中）变得非常疯狂。他们被编译成每个输入列（/输出行）基本上 2 个 SSE/AVX 矢量化移动操作，加上少量的固定开销。

julia> @code_native (b->[getindex.(b,i) for i in 1:length(b[1])])(b)
    .section    __TEXT,__text,regular,pure_instructions
; ┌ @ REPL[83]:1 within `#161'
    subq    $136, %rsp
    vmovups (%rdi), %ymm0
    vmovups 32(%rdi), %ymm1
    vmovups 64(%rdi), %ymm2
    vmovups 88(%rdi), %ymm3
    vmovups %ymm3, 88(%rsp)
    vmovups %ymm2, 64(%rsp)
    vmovups %ymm1, 32(%rsp)
    vmovups %ymm0, (%rsp)
    movabsq $5152370032, %rax       ## imm = 0x1331AED70
; │┌ @ generator.jl:32 within `Generator' @ generator.jl:32
    vmovaps (%rax), %xmm0
    vmovups %xmm0, 120(%rsp)
; │└
    movabsq $collect, %rax
    movq    %rsp, %rdi
    vzeroupper
    callq   *%rax
    addq    $136, %rsp
    retq
    nop
; └

推荐阅读