performance - 在这种情况下，为什么 'all(itr) do' block 比 for 循环慢？

Question

我的代码做了什么

我们的目标是构建一个函数，用 julia 检查给定字符串中的所有括号是否正确打开和关闭。所以，

"{abc()([[def]])()}"

应该返回 true，而类似的东西

"{(bracket order mixed up here!})[and this bracket doesn't close!"

应该返回 false。

问题

我有两个版本的函数。 为什么版本 I 快了大约 10%？

版本一

function matching_brackets_old(s::AbstractString)
    close_open_map = Dict('}' => '{', ')' => '(', ']' => '[')
    order_arr = []
    for char in s
        if char in values(close_open_map)
            push!(order_arr, char)
        elseif (char in keys(close_open_map)) &&
            (isempty(order_arr) || (close_open_map[char] != pop!(order_arr)))
            return false
        end
    end
    return isempty(order_arr)
end

第二版

在这里，我用一个 do block 替换了 for 循环:

function matching_brackets(s::AbstractString)
    close_open_map = Dict('}' => '{', ')' => '(', ']' => '[')
    order_arr = []
    all_correct = all(s) do char
        if char in values(close_open_map)
            push!(order_arr, char)
        elseif (char in keys(close_open_map)) &&
            (isempty(order_arr) || (close_open_map[char] != pop!(order_arr)))
            return false
        end
        return true
    end
    return all_correct && isempty(order_arr)
end

时间

对字符串 "{()()[()]()}" 和 "{()()[())]()} 使用 BenchmarkTools 的 @benchmark "，当比较最短执行时间时，两个字符串的速度都降低了大约 10%。

附加信息

版本信息:

Julia Version 1.3.1
Commit 2d5741174c (2019-12-30 21:36 UTC)
Platform Info:
  OS: macOS (x86_64-apple-darwin18.6.0)
  CPU: Intel(R) Core(TM) i5-4260U CPU @ 1.40GHz
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-6.0.1 (ORCJIT, haswell)

时间代码:

using BenchmarkTools

benchmark_strings = ["{()()[()]()}", "{()()[())]()}"]
for s in benchmark_strings
    b_old = @benchmark matching_brackets_old("$s") samples=100000 seconds=30
    b_new = @benchmark matching_brackets("$s") samples=100000 seconds=30
    println("For String=", s)
    println(b_old)
    println(b_new)
    println(judge(minimum(b_new), minimum(b_old)))
    println("Result: ", matching_brackets(s))
end

结果:

For String={()()[()]()}
Trial(8.177 μs)
Trial(9.197 μs)
TrialJudgement(+12.48% => regression)
Result: true
For String={()()[())]()}
Trial(8.197 μs)
Trial(9.202 μs)
TrialJudgement(+12.27% => regression)
Result: false

编辑

我混淆了 Trialjudgmentment 的顺序，所以版本 I 更快，正如 François Févotte 所建议的那样。我的问题仍然是:为什么？

Answer 1

现在 judge 的错误已经解决，答案可能是通常的警告:函数调用，在本例中由传递给 all 的闭包产生，是非常优化，但不是免费的。

为了获得真正的改进，我建议，除了使堆栈类型稳定(这在这里没什么大不了的)之外，通过调用 in 来摆脱你隐式执行的迭代在 values 和 keys 上。只需执行一次即可，无需字典:

const MATCHING_PAIRS = ('{' => '}', '(' => ')', '[' => ']')

function matching_brackets(s::AbstractString)
    stack = Vector{eltype(s)}()
    for c in s
        for (open, close) in MATCHING_PAIRS
            if c == open
                push!(stack, c)
            elseif c == close
                if isempty(stack) || (pop!(stack) != open)
                    return false
                end
            end
        end
    end
    return isempty(stack)
end

通过在元组上展开内循环可以挤出更多时间:

function matching_brackets_unrolled(s::AbstractString)
    stack = Vector{eltype(s)}()
    for c in s
        if (c == '(') || (c == '[') || (c == '{')
            push!(stack, c)
        elseif (c == ')')
            if isempty(stack) || (pop!(stack) != '(')
                return false
            end
        elseif (c == ']')
            if isempty(stack) || (pop!(stack) != '[')
                return false
            end
        elseif (c == '}')
            if isempty(stack) || (pop!(stack) != '{')
                return false
            end
        end
    end
    return isempty(stack)
end

不过，这有点难看，而且肯定不能很好地扩展。我的基准测试(matching_brackets_new 是你的第二个版本，matching_brackets 我的第一个):

julia> versioninfo()
Julia Version 1.3.1
Commit 2d5741174c (2019-12-30 21:36 UTC)
Platform Info:
  OS: Linux (x86_64-pc-linux-gnu)
  CPU: Intel(R) Core(TM) i7 CPU         960  @ 3.20GHz
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-6.0.1 (ORCJIT, nehalem)


# NOT MATCHING
julia> @benchmark matching_brackets_new("{()()[())]()}")
BenchmarkTools.Trial: 
  memory estimate:  784 bytes
  allocs estimate:  16
  --------------
  minimum time:     674.844 ns (0.00% GC)
  median time:      736.200 ns (0.00% GC)
  mean time:        800.935 ns (6.54% GC)
  maximum time:     23.831 μs (96.16% GC)
  --------------
  samples:          10000
  evals/sample:     160

julia> @benchmark matching_brackets_old("{()()[())]()}")
BenchmarkTools.Trial: 
  memory estimate:  752 bytes
  allocs estimate:  15
  --------------
  minimum time:     630.743 ns (0.00% GC)
  median time:      681.725 ns (0.00% GC)
  mean time:        753.937 ns (6.41% GC)
  maximum time:     23.056 μs (94.19% GC)
  --------------
  samples:          10000
  evals/sample:     171

julia> @benchmark matching_brackets("{()()[())]()}")
BenchmarkTools.Trial: 
  memory estimate:  112 bytes
  allocs estimate:  2
  --------------
  minimum time:     164.883 ns (0.00% GC)
  median time:      172.900 ns (0.00% GC)
  mean time:        186.523 ns (4.33% GC)
  maximum time:     5.428 μs (96.54% GC)
  --------------
  samples:          10000
  evals/sample:     759

julia> @benchmark matching_brackets_unrolled("{()()[())]()}")
BenchmarkTools.Trial: 
  memory estimate:  112 bytes
  allocs estimate:  2
  --------------
  minimum time:     134.459 ns (0.00% GC)
  median time:      140.292 ns (0.00% GC)
  mean time:        150.067 ns (5.84% GC)
  maximum time:     5.095 μs (96.56% GC)
  --------------
  samples:          10000
  evals/sample:     878


# MATCHING 
julia> @benchmark matching_brackets_old("{()()[()]()}")
BenchmarkTools.Trial: 
  memory estimate:  800 bytes
  allocs estimate:  18
  --------------
  minimum time:     786.358 ns (0.00% GC)
  median time:      833.873 ns (0.00% GC)
  mean time:        904.437 ns (5.43% GC)
  maximum time:     29.355 μs (96.88% GC)
  --------------
  samples:          10000
  evals/sample:     106

julia> @benchmark matching_brackets_new("{()()[()]()}")
BenchmarkTools.Trial: 
  memory estimate:  832 bytes
  allocs estimate:  19
  --------------
  minimum time:     823.597 ns (0.00% GC)
  median time:      892.506 ns (0.00% GC)
  mean time:        981.381 ns (5.98% GC)
  maximum time:     47.308 μs (97.84% GC)
  --------------
  samples:          10000
  evals/sample:     77

julia> @benchmark matching_brackets("{()()[()]()}")
BenchmarkTools.Trial: 
  memory estimate:  112 bytes
  allocs estimate:  2
  --------------
  minimum time:     206.062 ns (0.00% GC)
  median time:      214.481 ns (0.00% GC)
  mean time:        227.385 ns (3.38% GC)
  maximum time:     6.890 μs (96.22% GC)
  --------------
  samples:          10000
  evals/sample:     535

julia> @benchmark matching_brackets_unrolled("{()()[()]()}")
BenchmarkTools.Trial: 
  memory estimate:  112 bytes
  allocs estimate:  2
  --------------
  minimum time:     160.186 ns (0.00% GC)
  median time:      164.752 ns (0.00% GC)
  mean time:        180.794 ns (4.95% GC)
  maximum time:     5.751 μs (97.03% GC)
  --------------
  samples:          10000
  evals/sample:     800

---

更新:如果你在第一个版本中插入 break，真的避免不必要的循环，时间几乎无法区分，代码很好:

function matching_brackets(s::AbstractString)
    stack = Vector{eltype(s)}()
    for c in s
        for (open, close) in MATCHING_PAIRS
            if c == open
                push!(stack, c)
                break
            elseif c == close
                if isempty(stack) || (pop!(stack) != open)
                    return false
                end
                break
            end
        end
    end
    return isempty(stack)
end

与

julia> @benchmark matching_brackets_unrolled("{()()[())]()}")
BenchmarkTools.Trial: 
  memory estimate:  112 bytes
  allocs estimate:  2
  --------------
  minimum time:     137.574 ns (0.00% GC)
  median time:      144.978 ns (0.00% GC)
  mean time:        165.365 ns (10.44% GC)
  maximum time:     9.344 μs (98.02% GC)
  --------------
  samples:          10000
  evals/sample:     867

julia> @benchmark matching_brackets("{()()[())]()}") # with breaks
BenchmarkTools.Trial: 
  memory estimate:  112 bytes
  allocs estimate:  2
  --------------
  minimum time:     148.255 ns (0.00% GC)
  median time:      155.231 ns (0.00% GC)
  mean time:        175.245 ns (9.62% GC)
  maximum time:     9.602 μs (98.31% GC)
  --------------
  samples:          10000
  evals/sample:     839