c - 哪个更快 - 排序或乘以一个小的元素数组？

Question

通读Cactus Kev's Poker Hand Evaluator ，我注意到以下语句:

At first, I thought that I could always simply sort the hand first before passing it to the evaluator; but sorting takes time, and I didn't want to waste any CPU cycles sorting hands. I needed a method that didn't care what order the five cards were given as.
...
After a lot of thought, I had a brainstorm to use prime numbers. I would assign a prime number value to each of the thirteen card ranks... The beauty of this system is that if you multiply the prime values of the rank of each card in your hand, you get a unique product, regardless of the order of the five cards.
...
Since multiplication is one of the fastest calculations a computer can make, we have shaved hundreds of milliseconds off our time had we been forced to sort each hand before evaluation.

我很难相信这一点。

Cactus Kev 将每张牌表示为一个 4 字节整数，并通过调用 eval_5cards( int c1, int c2, int c3, int c4, int c5 ) 评估手牌。我们可以将纸牌表示为一个字节，将一手扑克牌表示为一个 5 字节的数组。对这个 5 字节数组进行排序以获得独特的手牌一定非常快。它比他的方法更快吗？

如果我们保留他的表示(卡片为 4 字节整数)会怎么样？对包含 5 个整数的数组进行排序是否比将它们相乘更快？如果不是，可以进行什么样的低级优化来加快对少量元素的排序？

谢谢!

每个人都很好的回答；我正在对排序与乘法的性能进行基准测试，以获得一些硬性能统计数据。

Answer 1

当然这在很大程度上取决于您计算机的 CPU，但典型的 Intel CPU(例如 Core 2 Duo)可以在 3 个 CPU 时钟周期内将两个 32 位数字相乘。排序算法要打败它，算法需要比 3 * 4 = 12 个 CPU 周期更快，这是一个非常严格的约束。没有一个标准的排序算法可以肯定地在少于 12 个周期内完成。单独比较两个数字将花费一个 CPU 周期，结果的条件分支也将花费一个 CPU 周期，然后无论您做什么都至少需要一个 CPU 周期(交换两张卡实际上至少需要 4 个 CPU 周期)。所以乘法取胜。

当然，这并没有考虑从一级或二级缓存甚至内存中获取卡值的延迟；然而，这种延迟适用于任何一种情况，乘法和排序。