迭代数组与列表的性能

Question

受这个问题的启发,我想看看迭代一个数组与一个List之间是否有任何性能差异.

由于我们将迭代整个集合,我最初的想法是两者之间不应该存在性能差异.此外,我认为使用尾递归函数进行计数应该与使用可变变量一样快.但是,当我编写一个简单的脚本来测试差异时,我发现了以下内容(在VS2015的发布模式下运行):

add_k_list, elapsed 15804 ms, result 0L
add_k_list_mutable, elapsed 12800 ms, result 0L
add_k_array, elapsed 15719 ms, result 0L

我想知道为什么使用可变变量的列表添加实现比尾递归版本和使用可变变量和数组的版本快得多.

这是我的代码:

open System.Diagnostics

let d = 100000
let n = 100000

let stopWatch = 
  let sw = Stopwatch ()
  sw.Start ()
  sw

let testList = [1..d]
let testArray = [|1..d|]

let timeIt (name : string) (a : int ->  int list -> 'T) : unit = 
  let t = stopWatch.ElapsedMilliseconds
  let v = a 0 (testList)
  for i = 1 to (n) do
    a i testList |> ignore
  let d = stopWatch.ElapsedMilliseconds - t
  printfn "%s, elapsed %d ms, result %A" name d v

let timeItArr (name : string) (a : int -> int [] -> 'T) : unit = 
  let t = stopWatch.ElapsedMilliseconds
  let v = a 0 (testArray)
  for i = 1 to (n) do
    a i testArray |> ignore
  let d = stopWatch.ElapsedMilliseconds - t
  printfn "%s, elapsed %d ms, result %A" name d v

let add_k_list x (k_range: int list) =
    let rec add k_range x acc =  
        match k_range with
        | [] -> acc
        | k::ks -> let y = x ^^^ k
                   if (y < k || y > d) then
                       add ks x (acc + 1L)
                   else
                       add ks x acc
    add k_range x 0L


let add_k_list_mutable x (k_range: int list) = 
    let mutable count = 0L
    for k in k_range do
        let y = x ^^^ k
        if (y < k || y > d) then
            count <- count + 1L
    count

let add_k_array x (k_range: int []) =
    let mutable count = 0L
    for k in k_range do
        let y = x ^^^ k
        if (y < k || y > d) then
            count <- count + 1L
    count

[<EntryPoint>]
let main argv = 
    let x = 5
    timeItArr "add_k_array" add_k_array
    timeIt "add_k_list" add_k_list
    timeIt "add_k_list_mutable" add_k_list_mutable
    printfn "%A" argv
    0 // return an integer exit code

编辑:上述测试在VS2015的32位发布模式下运行.在s952163的建议中,我以64位运行它,发现结果有很大不同:

add_k_list, elapsed 17918 ms, result 0L
add_k_list_mutable, elapsed 17898 ms, result 0L
add_k_array, elapsed 8261 ms, result 0L

我特别惊讶的是,使用尾递归与累加器和可变变量之间的差异似乎已经消失.

Answer 1

当运行略微修改的程序(下面发布)时,这些是我收到的数字:

x64发布.NET 4.6.1

TestRun: Total: 1000000000, Outer: 100, Inner: 10000000
add_k_array, elapsed 1296 ms, accumulated result 495000099L
add_k_list, elapsed 2675 ms, accumulated result 495000099L
add_k_list_mutable, elapsed 2678 ms, accumulated result 495000099L
TestRun: Total: 1000000000, Outer: 1000, Inner: 1000000
add_k_array, elapsed 869 ms, accumulated result 499624318L
add_k_list, elapsed 2486 ms, accumulated result 499624318L
add_k_list_mutable, elapsed 2483 ms, accumulated result 499624318L
TestRun: Total: 1000000000, Outer: 10000, Inner: 100000
add_k_array, elapsed 750 ms, accumulated result 507000943L
add_k_list, elapsed 1602 ms, accumulated result 507000943L
add_k_list_mutable, elapsed 1603 ms, accumulated result 507000943L

x86发布.NET 4.6.1

TestRun: Total: 1000000000, Outer: 100, Inner: 10000000
add_k_array, elapsed 1601 ms, accumulated result 495000099L
add_k_list, elapsed 2014 ms, accumulated result 495000099L
add_k_list_mutable, elapsed 1835 ms, accumulated result 495000099L
TestRun: Total: 1000000000, Outer: 1000, Inner: 1000000
add_k_array, elapsed 1495 ms, accumulated result 499624318L
add_k_list, elapsed 1714 ms, accumulated result 499624318L
add_k_list_mutable, elapsed 1595 ms, accumulated result 499624318L
TestRun: Total: 1000000000, Outer: 10000, Inner: 100000
add_k_array, elapsed 1363 ms, accumulated result 507000943L
add_k_list, elapsed 1406 ms, accumulated result 507000943L
add_k_list_mutable, elapsed 1221 ms, accumulated result 507000943L

(像往常一样,重要的是不要运行附加的调试器,因为这会改变JIT:er的工作方式.附加调试器的JIT:er会生成更容易调试器但速度更慢的代码.)

这种方式的工作方式是迭代总数保持不变,但它会改变外部循环的计数和列表/数组的大小.

对我来说,奇怪的唯一测量是阵列循环在某些情况下比列表循环更糟糕.

如果总工作量相同,为什么当外/内变化时我们会看到不同的结果？

答案很可能与CPU缓存有关.当我们迭代一个大小为10,000,000的数组时,它在内存中的实际大小为40,000,000字节.我的机器"只有"6,000,000字节的L3缓存.当数组大小为1,000,000时,数组的大小为4,000,000字节,可以适合L3.

F#中的列表类型本质上是单链表,列表元素的粗略估计是4(数据)+8(64位指针)+8(vtable指针)+4(堆开销)= 24字节.根据此估计,具有10,000,000个元素的列表的大小为240,000,000个字节,大小为1,000,000个元素,大小为24,000,000.两者都不适合我机器上的L3缓存.

当元素数为100,000时,数组的大小为400,000字节,列表大小为2,400,000.两者都紧密地适应L3缓存.

这种推理可以解释较小的阵列/列表与较大的阵列/列表之间的性能差异.

如果列表的元素没有按顺序分配(即堆碎片或GC移动它们),如果它不适合缓存,则预计列表的性能会更差,因为CPU预取策略不再然后工作.数组中的元素保证始终是顺序的,因此如果按顺序迭代,预取将正常工作.

为什么尾递归比可变for循环慢？

在F#3中实际上并非如此,其中for循环预期比尾递归慢得多.

为了提示答案,我使用ILSpy来查看生成的IL代码.

我发现FSharpList<>::get_TailOrNull()在使用尾递归时每个循环调用两次.一次检查我们是否到达结束并且一次获得下一个元素(冗余调用).

for循环版只调用FSharpList<>::get_TailOrNull()一次.

这个额外的调用可能解释了为什么尾递归较慢但是你在x64位模式中注意到这两个列表版本的速度一样快.这是怎么回事？

我检查了JIT:ed汇编代码并注意到x64 JIT:er消除了额外的调用FSharpList<>::get_TailOrNull().x86 JIT:呃无法消除呼叫.

最后,为什么数组版本比x86上的列表版本慢？

一般来说,我希望数组在.NET中所有集合的开销最小.原因是它紧凑,顺序,并且ILAsm中有特殊指令来访问元素.

因此,令我感到惊讶的是,列表在某些情况下表现更好.

再次检查汇编代码似乎来自数组版本需要额外的变量来执行其工作,而x86 CPU几乎没有可用的寄存器导致每次迭代从堆栈中额外读取.x64具有明显更多的寄存器,导致数组版本每次迭代只需从内存中读取一次,其中列表版本读取两次(头部和尾部).

任何结论？

• 说到CPU性能x64是要走的路(这并非总是如此)
• 对于阵列操作为O(1)的操作,期望数组的性能优于.NET中的任何数据结构(插入很明显)
• 魔鬼具有细节意义,为了获得真正的洞察力,我们可能需要检查汇编代码.
• 缓存局部性对于大型集合非常重要.由于阵列紧凑且保证顺序,因此它们通常是一个不错的选择.
• 预测性能非常困难,总是要衡量
• 如果你真的渴望性能,那么在可能的情况下迭代为零.这可以节省一次内存读取.

编辑:OP想知道为什么看起来x86列表表现更好的x64列表

我重新进行了perf测试,列表/数组大小设置为1,000.这将确保整个数据结构适合我的L1缓存(256kB)

x64发布.NET 4.6.1

TestRun: Total: 1000000000, Outer: 1000000, Inner: 1000
add_k_array, elapsed 1062 ms, accumulated result 999499999L
add_k_list, elapsed 1134 ms, accumulated result 999499999L
add_k_list_mutable, elapsed 1110 ms, accumulated result 999499999L

x86发布.NET 4.6.1

TestRun: Total: 1000000000, Outer: 1000000, Inner: 1000
add_k_array, elapsed 1617 ms, accumulated result 999499999L
add_k_list, elapsed 1359 ms, accumulated result 999499999L
add_k_list_mutable, elapsed 1100 ms, accumulated result 999499999L

我们看到,对于这个大小,似乎x64的表现与x86一样好或更好.为什么我们在其他测量中看到相反的情况？我推测这是因为x64版本中列表元素的大小更大,这意味着我们使用更多带宽将数据从L3移动到L1.

因此,如果您可以尝试确保您的数据适合L1缓存.

最后的沉思

在处理这些问题时,我有时想知道整个冯·诺依曼架构是否是一个大错误.相反,我们应该有一个数据流架构,因为数据很慢而且指令很快.

引擎盖下的AFAIK CPU:具有数据流架构.汇编语言虽然看起来像Von Neumann架构所期望的,但在某种意义上它是数据流架构的高级抽象.但是为了提供合理的性能代码,CPU芯片主要由高速缓存占用(~95%).使用纯数据流体系结构,人们可以预期更高比例的CPU芯片可以完成实际工作.

希望这很有趣,我修改后的程序如下:

open System.Diagnostics

let stopWatch =
  let sw = Stopwatch ()
  sw.Start ()
  sw

let timeIt (name : string) (outer : int) (a : int -> int64) : unit =
  let t = stopWatch.ElapsedMilliseconds
  let mutable acc = a 0
  for i = 2 to outer do
    acc <- acc + a i
  let d = stopWatch.ElapsedMilliseconds - t
  printfn "%s, elapsed %d ms, accumulated result %A" name d acc

let add_k_list x l (k_range: int list) =
    let rec add k_range x acc =
        match k_range with
        | [] -> acc
        | k::ks -> let y = x ^^^ k
                   if (y < k || y > l) then
                       add ks x (acc + 1L)
                   else
                       add ks x acc
    add k_range x 0L


let add_k_list_mutable x l (k_range: int list) =
    let mutable count = 0L
    for k in k_range do
        let y = x ^^^ k
        if (y < k || y > l) then
            count <- count + 1L
    count

let add_k_array x l (k_range: int []) =
    let mutable count = 0L
    for k in k_range do
        let y = x ^^^ k
        if (y < k || y > l) then
            count <- count + 1L
    count
[<EntryPoint>]
let main argv =
  let total = 1000000000
  let outers = [|100; 1000; 10000|]

  for outer in outers do
    let inner = total / outer
    printfn "TestRun: Total: %d, Outer: %d, Inner: %d" total outer inner

    ignore <| System.GC.WaitForFullGCComplete ()

    let testList  = [1..inner]
    let testArray = [|1..inner|]

    timeIt    "add_k_array"         outer <| fun x -> add_k_array         x inner testArray
    timeIt    "add_k_list"          outer <| fun x -> add_k_list          x inner testList
    timeIt    "add_k_list_mutable"  outer <| fun x -> add_k_list_mutable  x inner testList

  0