如果从生成的代码分支,二进制搜索比硬编码慢？

Question

这个人非常声称二进制搜索(在C编译器中)比从生成的代码中分支的硬编码要慢.(请原谅Clojure代码和古怪的标题 - 这个声称这个人与一般的编译器有关).

他写

我偶尔会在黑暗的角落看到这种代码.当一个人知道他的处理器如何工作,知道他的C编译器如何工作,知道他的数据结构,并且真的,真的需要他的循环快,然后他偶尔会写这种东西.

这是Real Programmers编写的一些代码.

这是二进制搜索示例(请原谅Clojure)

Start: (1 2 3 4 6 8 9 10 11 12)
Finish: ((((1) (2)) ((3) ((4) (6)))) (((8) (9)) ((10) ((11) (12)))))

然后,如果基于硬编码值,他将生成的代码替换为二进制搜索:

(defn lookup-fn-handwritten [x]
  (if (< x 6) 
    (if (< x 3)                         ; x is < 6
      (if (< x 2)                       ; x is < 3
        (if ( < x 1)                    ; x is < 2
          0                             ; < 1
          1)                            ; 1 <= x < 2
        3)                              ; 2 <= x < 3
      (if (< x 4)                       ; 3 <= x < 6
        4                               ; 3 <= x < 4
        2))                             ; 4 <= x < 6
    (if (< x 10)                        ; 6 <= x < 10
      (if (< x 9)                       ; 6 <= x < 9
        (if (< x 8) 
          2                             ; 6 <= x < 8
          3)                            ; 8 <= x < 9
        3)                              ; 9 <= x < 10
      (if (< x 11)                      ; 10 < x
        (if (< x 12)                    ; 11 <= x
          1                             ; 11 <= x < 12
          0)
        0))))                           ; 12 <= x

http://www.learningclojure.com/2010/09/clojure-faster-than-machine-code.html

我的问题是 - 如果生成的代码和硬编码值比二进制搜索更有效,那么分支硬编码会不会？(在任何语言中 - 但作者声称这适用于C - 然后似乎只在JVM上演示它).

(请再次原谅链接帖子的古怪标题 - 那只是疯狂.)

Answer 1

好吧,if-cascade可能与二进制搜索完全相同,这意味着它进行相同的比较,但没有相关的"二进制搜索管理".这是一个展开的循环,确实存在编译器展开循环的原因.所以是的,它会更快.

但它真的会更快吗？现在有一个叫做"缓存"的问题.无论是展开循环还是其他任何东西,代码都会变大,因此运行代码的内存访问可能会抵消好处.

此外,您永远不知道编译器可能使用哪种指令来优化代码,当您手动展开循环时,它可能不会使用这些指令.或者另一种方式'圆,谁知道.在具有"内置"二进制搜索的语言中更是如此,因此编译器知道它正在处理什么.

因此,仅仅计算诸如"我拥有所有比较而没有其他任何东西"之类的操作可能是不够的; 还有其他因素会影响执行时间.如果你在一个CPU上查找"我的展开版本更快",另一个CPU可能仍然不同意.

优化是一个b字,不知道我是否可以拼写出来:-)