为什么标准库中的 IsSorted 会反向迭代切片？

Question

出于好奇，我一直在查看sort标准库中的包和slices即将添加到标准库中的实验包的源代码。这两个包都定义了一个IsSorted函数，通过验证相邻元素是否有序来检查列表是否已排序。然而，这是相反的。

我创建了一个小的复制品，松散地基于通用slices包。我的实验确实表明反向版本更快。

func IsSortedForward[T any](slice []T, compare func(a, b T) int) bool {
    for i := 0; i < len(slice) - 1; i++ {
        if compare(slice[i], slice[i+1]) > 0 {
            return false
        }
    }
    return true
}

func IsSortedForward2[T any](slice []T, compare func(a, b T) int) bool {
    n := len(slice) - 1
    for i := 0; i < n; i++ {
        if compare(slice[i], slice[i+1]) > 0 {
            return false
        }
    }
    return true
}

func IsSortedReverse[T any](slice []T, compare func(a, b T) int) bool {
    for i := len(slice) - 1; i > 0; i-- {
        if compare(slice[i], slice[i-1]) < 0 {
            return false
        }
    }
    return true
}

我最初的想法是，前向版本会更加“缓存友好”。然而，我确实注意到反向版本的一个优点，因为len(slice) - 1只计算一次。而在前向版本中，它是在每次迭代时计算的。我的假设是，这就是反向版本稍微快一些的原因。

然后，我len(slice) - 1在前向版本中将其提取到循环之外，以便仅计算一次，这确实提高了其性能。然而，它仍然比反向版本慢一些。i > 0我的猜测是，反向版本（零）中的比较比i < n正向版本中的比较更快？

为什么你认为反向版本更快？为什么调整后的正向版本仍然不如反向版本快？

编辑：我不知道编译器资源管理器（Godbolt）可以与 Go 一起使用...这里是这个问题中提到的功能的一些复制。看来Go有自己的汇编语言？

Answer 1

简而言之：因为可以从向下循环生成更高效的代码，特别是对于条件部分。

个人说明：您应该在自己的代码中使用它吗？如果性能不重要的话就不会。使用更具可读性且更有意义的循环。使用标准库中更快的版本有明显的好处（因为每个人都在使用它），但仅仅几微秒就不会牺牲代码的可读性。

IsSortedForward2()和IsSortedReverse()大致相同，只是前者使用递增运算符 ( i++) 并且i+1在主体内部，后者使用递减运算符 ( i--) 并且i-1在主体内部，它们在性能方面是等效的。

显着的差异来自条件：前向变体使用i < n，而反向变体使用i > 0。第一个需要比较 2 个变量，后者需要将一个变量与一个非常特殊的值进行比较：0。

一般来说，第一个条件需要将 2 个变量（内存位置）加载到寄存器并比较它们的值。后者需要将 1 个变量加载到寄存器中并将其与特殊的 0 值进行比较。请注意，实际上这些变量可能位于寄存器中，因此可能不必发生实际的内存加载。

您可以通过运行以下命令来检查生成的汇编代码：

go tool compile -S play.go > play.s

我使用的源行：

20 func IsSortedForward2[T any](slice []T, compare func(a, b T) int) bool {
21     n := len(slice) - 1
22     for i := 0; i < n; i++ {
23          if compare(slice[i], slice[i+1]) > 0 {
24              return false
25          }
26     }
27     return true
28 }
29 
30 func IsSortedReverse[T any](slice []T, compare func(a, b T) int) bool {
31     for i := len(slice) - 1; i > 0; i-- {
32         if compare(slice[i], slice[i-1]) < 0 {
33             return false
34         }
35     }
36     return true
37 }

有趣的行是 22 和 31，以下是这些行生成的程序集：

play.go:22) JMP     77
play.go:22) MOVQ    main.n+16(SP), DI
play.go:22) MOVQ    main.compare+80(SP), SI
play.go:22) MOVQ    main.slice+64(SP), CX
play.go:22) MOVQ    main.slice+56(SP), BX
play.go:22) MOVQ    main..autotmp_9+24(SP), AX
play.go:22) CMPQ    AX, DI
play.go:22) JGE     136

play.go:31) DECQ    CX
play.go:31) JMP     53
play.go:32) MOVQ    main.i+16(SP), CX
play.go:32) DECQ    CX
play.go:32) MOVQ    main.slice+48(SP), BX
play.go:32) MOVQ    main.compare+72(SP), SI
play.go:31) TESTQ   CX, CX
play.go:31) JLE     100
play.go:31) MOVQ    CX, main.i+16(SP)

IsSortedForward2()i将和加载n到AX和DI寄存器中，并使用 进行比较CMPQ。

IsSortedReverse()只需加载i到CX，并使用 测试它是否为零TESTQ。

Answer 2

除了icza 的答案（非常好，并且适用于一般情况）之外，反向操作更有可能允许在特定的半常见用例中提前短路（并且当它没有帮助时不需要任何成本）。许多高级语言，包括 Go，不提供排序的容器类型，因此仅使用内置 + 标准库来维护排序的数据结构是很痛苦的（即使您为任何连续的数据序列类型提供了二进制搜索包）提供，例如Go的slice，它只是将搜索工作减少到O(log n)，插入仍然存在O(n)）。

为了解决这个问题，假设当用户需要一个不经常修改的排序数据结构时，他们只会附加新数据而不是按排序顺序插入，并且如果自上次排序以来添加了任何新数据，它将在下一个需要排序的操作之前对其进行排序。该语言的排序算法通常会对此进行优化，例如，Python 的Timsort在接近时间的情况下处理“大部分已排序，有一些未排序的元素” O(n)，而 Go 的现代算法sort.Sort（基于pdqsort（消除模式的快速排序））是O(n)如果单个元素已添加到末尾（尽管我不清楚这是否是一种特殊情况，还是当多个元素不合适时利用现有排序的一般能力）。

在这些“大部分已排序，有时末尾有一些未排序元素”的场景中，当IsSorted调用时，有两种可能性：

1. 已经slice排序（自上次排序以来没有添加任何内容，或者新元素碰巧保持顺序），或者
2. 的开头slice（可能是大部分）slice已排序，但末尾有少量（通常很少）未排序的元素。

在情况 #1 中，slice无论您向哪个方向操作，在最终返回 true 之前都必须检查整个内容，因此您检查的顺序并不重要。但在情况 #2 中，假设新元素是半随机排序的，反向操作意味着您将能够短路并几乎立即返回 false，而按正向顺序操作意味着您必须重新检查 (在最后到达较少数量的未排序元素之前，已排序的元素数量会保持排序，并缩短更少的工作量。

为了澄清一个误解，缓存方面，按正向或反向顺序依次操作通常不会产生任何影响；无论方向如何，顺序访问模式在现代系统上都能得到很好的处理。