14

Reading through Cactus Kev's Poker Hand Evaluator, I noticed the following statements:

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.

I have a hard time believing this.

Cactus Kev represents each card as a 4-byte integer, and evaluates hands by calling eval_5cards( int c1, int c2, int c3, int c4, int c5 ). We could represent cards as one byte, and a poker hand as a 5-byte array. Sorting this 5-byte array to get a unique hand must be pretty fast. Is it faster than his approach?

What if we keep his representation (cards as 4-byte integers)? Can sorting an array of 5 integers be faster than multiplying them? If not, what sort of low-level optimizations can be done to make sorting a small number of elements faster?

Thanks!

Good answers everyone; I'm working on benchmarking the performance of sorting vs multiplication, to get some hard performance statistics.

Rudiger
  • 6,634
  • 9
  • 40
  • 57
  • He doesn't even need to use multiplication - addition could be made to work equally well (with a different selection of numbers to represent the ranks). It is essentially just a hash function that is invariant under reordering of the input item. – caf Jun 29 '10 at 02:20
  • remember that multiplication is a primitive operation performed on hardware, his story may have merit. Note that this is essentially hashing (his hashing function is one-to-one that can be computed really fast) – ldog Jun 29 '10 at 06:57
  • I was skeptical when I read this, too. The optimal sorting network is definitely slower, but he could've just used a bitmask and ORed the cards together, which would have been simpler. He could also use Combinadics, which are more complicated to calculate, but result in a contiguous range for all valid poker hands, meaning you can look up the hand in an array, rather than needing a hashtable. – Nick Johnson Mar 25 '11 at 02:38

11 Answers11

6

Without testing, I'm sympathetic to his argument. You can do it in 4 multiplications, as compared to sorting, which is n log n. Specifically, the optimal sorting network requires 9 comparisons. The evaluator then has to at least look at every element of the sorted array, which is another 5 operations.

Matthew Flaschen
  • 278,309
  • 50
  • 514
  • 539
6

Of course it depends a lot on the CPU of your computer, but a typical Intel CPU (e.g. Core 2 Duo) can multiply two 32 Bit numbers within 3 CPU clock cycles. For a sort algorithm to beat that, the algorithm needs to be faster than 3 * 4 = 12 CPU cycles, which is a very tight constraint. None of the standard sorting algorithms can do it in less than 12 cycles for sure. Alone the comparison of two numbers will take one CPU cycle, the conditional branch on the result will also take one CPU cycle and whatever you do then will at least take one CPU cycle (swapping two cards will actually take at least 4 CPU cycles). So multiplying wins.

Of course this is not taking the latency into account to fetch the card value from either 1st or 2nd level cache or maybe even memory; however, this latency applies to either case, multiplying and sorting.

Mecki
  • 125,244
  • 33
  • 244
  • 253
  • He needs to fetch the card value and do a lookup into a list of 13 primes. Still faster than sorting. – phkahler Jun 28 '10 at 19:31
  • Considering the fact, that the 13 primes are most likely in 1st level cache after one or two lookups, this will add another 3 clock cycles for the lookup of each card. But you are right, this is still definitely faster. – Mecki Jun 28 '10 at 20:01
  • 1
    While the point is good, your cycle counting seems to be a bit off. For the multiply case, one of the multiplies can be pipelined, so latency is 9 cycles. Conditional branches will on average take significantly more than 1 cycle due to mispredictions. CMOV's could turn control-flow into data-dependencies, but even accounting for pipelining, best case is 1 cycle for CMP + 5*2 cycles for CMOV's = 11 cycles for the optimal sorting network. – Ants Aasma Jun 29 '10 at 11:39
  • Yeah, I left pipeline out, because in reality its speculative what can really be pipelined (unless you have raw assembly code in front of you to look at). Regarding branching, conditional branching is only slow, if it mispredicts, but it might as well predict correctly ;-) – Mecki Jun 29 '10 at 17:29
5

Sorting is not intrinsically harder than multiplying numbers. On paper, they're about the same, and you also need a sophisticated multiplication algorithm to make large multiplication competitive with large sort. Moreover, when the proposed multiplication algorithm is feasible, you can also use bucket sort, which is asymptotically faster.

However, a poker hand is not an asymptotic problem. It's just 5 cards and he only cares about one of the 13 number values of the card. Even if multiplication is complicated in principle, in practice it is implemented in microcode and it's incredibly fast. What he's doing works.

Now, if you're interested in the theoretical question, there is also a solution using addition rather than multiplication. There can only be 4 cards of any one value, so you could just as well assign the values 1,5,25,...,5^12 and add them. It still fits in 32-bit arithmetic. There are also other addition-based solutions with other mathematical properties. But it really doesn't matter, because microcoded arithmetic is so much faster than anything else that the computer is doing.

Greg Kuperberg
  • 3,995
  • 22
  • 24
2

5 elements can be sorted using an optimized decision tree, which is much faster than using a general-purpose sorting algorithm.

However, the fact remains that sorting means lots of branches (as do the comparisons that are necessary afterwards). Branches are really bad for modern pipelined CPU architectures, especially branches that go either way with similar likelihood (thus defeating branch prediction logic). That, much more than the theoretical cost of multiplication vs. comparisons, makes multiplication faster.

But if you could build custom hardware to do the sorting, it might end up faster.

Michael Borgwardt
  • 342,105
  • 78
  • 482
  • 720
1

That shouldn't really be relevant, but he is correct. Sorting takes much longer than multiplying.

The real question is what he did with the resulting prime number, and how that was helpful (since factoring it I would expect to take longer than sorting.

zebediah49
  • 7,467
  • 1
  • 33
  • 50
  • If I remember correctly, he used it as a lookup into a gigantic table. – AShelly Jun 28 '10 at 18:42
  • 1
    He's mapping each of the 2,598,960 unique five-card poker hands to one of only 7462 distinct values. Kind of like an [equivalence relation](http://en.wikipedia.org/wiki/Equivalence_relation). – Rudiger Jun 28 '10 at 18:47
  • Asymptotically, sorting takes much longer than multiplying. This is pretty much the opposite of asymptotic performance! – Rudiger Jun 28 '10 at 18:51
  • For example, see http://stackoverflow.com/questions/1276716/fast-stable-sort-for-small-arrays-under-32-or-64-elements or http://stackoverflow.com/questions/2748749/fast-algorithm-implementation-to-sort-very-small-set – Rudiger Jun 28 '10 at 18:51
  • There are only 134,459 unique hands when you ignore suit. That's small enough to fit into a look-up table. It's even smaller if you just consider the numbers that result in a hand with a pair or better. – Niki Yoshiuchi Jun 28 '10 at 18:56
  • Also, factoring isn't hard when you know the only valid primes that could make up your composite number ahead of time. – Nick Johnson Mar 25 '11 at 02:36
1

It's hard to think of any sorting operation that could be faster than multiplying the same set of numbers. At the processor level, the multiplication is just load, load, multiply, load, multiply, ..., with maybe some manipulation of the accumulator thrown in. It's linear, easily pipelined, no comparisons with the associated branch mis-prediction costs. It should average about 2 instructions per value to be multiplied. Unless the multiply instruction is painfully slow, it's really hard to imagine a faster sort.

AShelly
  • 34,686
  • 15
  • 91
  • 152
  • +1 the memory access pattern of a sort (and mov/load will generally be far slower than multiply) is unlikely to be as fast as just multiplying 5 integrals together. – stinky472 Jun 29 '10 at 03:29
1

One thing worth mentioning is that even if your CPU's multiply instruction is dead slow (or nonexistent...) you can use a lookup table to speed things even further.

Roddy
  • 66,617
  • 42
  • 165
  • 277
  • The 7-card evaluator does exactly this to load a tree representing hand ranks for every single combination of 7 cards possible (about 130,000,000 combinations). It's super fast but takes several hundred megs of RAM and a load time to initialize. – stinky472 Jun 29 '10 at 03:33
1

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.

That's a example of a non-positional number system.

I can't find the link to the theory. I studied that as part of applied algebra, somewhere around the Euler's totient and encryption. (I can be wrong with terminology as I have studied all that in my native language.)

What if we keep his representation (cards as 4-byte integers)? Can sorting an array of 5 integers be faster than multiplying them?

RAM is an external resource and is generally slower compared to the CPU. Sorting 5 of ints would always have to go to RAM due to swap operations. Add here the overhead of sorting function itself, and multiplication stops looking all that bad.

I think on modern CPUs integer multiplication would pretty much always faster than sorting, since several multiplications can be executed at the same time on different ALUs, while there is only one bus connecting CPU to RAM.

If not, what sort of low-level optimizations can be done to make sorting a small number of elements faster?

5 integers can be sorted quite quickly using bubble sort: qsort would use more memory (for recursion) while well optimized bubble sort would work completely from d-cache.

Dummy00001
  • 16,630
  • 5
  • 41
  • 63
  • 2
    "Sorting 5 of ints would always have to go to RAM due to swap operations." - what sort of CPU are you using, that only has 5 32-bit registers? Not to mention, the next step down from registers is L1 cache, not RAM. – Nick Johnson Jun 28 '10 at 20:45
  • @Nick, no compiler would try to cache an array with variable length in registers. Unless custom function with fixed array length is used. And, yes, I have slightly brushed over the details of memory organization. Going into cache-line-alignment/i$/d$/L1/L2/L3/TLB/branch-prediction/cache-write-through would over-complicate the explanation unnecessary. General rule holds: less the expensive resources are used, better. And memory is expensive. At very small array lengths, qsort()'s recursion memory overhead simply outweigh the benefits of dichotomy. – Dummy00001 Jun 28 '10 at 21:52
  • Nobody said you had to use an array and a general sorting algorithm, though. In fact, several people have suggested sorting networks. And as I said, next level down is cache, not RAM. – Nick Johnson Jun 29 '10 at 07:46
0

As others have pointed out, sorting alone isn't quicker than multiplying for 5 values. This ignores, however, the rest of his solution. After disdaining a 5-element sort, he proceeds to do a binary search over an array of 4888 values - at least 12 comparisons, more than the sort ever required!

Note that I'm not saying there's a better solution that involves sorting - I haven't given it enough thought, personally - just that sorting alone is only part of the problem.

He also didn't have to use primes. If he simply encoded the value of each card in 4 bits, he'd need 20 bits to represent a hand, giving a range of 0 to 2^20 = 1048576, about 1/100th of the range produced using primes, and small enough (though still suffering cache coherency issues) to produce a lookup table over.

Of course, an even more interesting variant is to take 7 cards, such as are found in games like Texas Holdem, and find the best 5 card hand that can be made from them.

Nick Johnson
  • 100,655
  • 16
  • 128
  • 198
  • Binary search with a fixed number of steps does not require any comparisons. It can be done entirely with arithmetic and bitwise operations which yield the result. If the number of steps (size of the table to search) is not fixed then you need a loop/counter which is one (very predictable) conditional jump per iteration, but otherwise the same arithmetic approach still applies. – R.. GitHub STOP HELPING ICE Jun 28 '10 at 21:19
  • @R Say what? You have to compare the value of the current node to the value you're searching for at each step. If you have a way to optimize away that, I'd love to hear it. – Nick Johnson Jun 28 '10 at 21:21
  • Well by comparisons I meant conditional jumps based on result of a comparison. If instead you do arithmetic (making use of sign extension) to update the current node at each step, there are no jumps, and it comes out to just several opcodes per step. – R.. GitHub STOP HELPING ICE Jun 28 '10 at 21:41
  • 1
    The code is something like this. `for (a=0, n=(table_len+1)>>1; n>1; n=n+1>>1) a+=n&(table[a+n].key-key-1)>>(8*sizeof key - 1)` With constant table length, the loop is easily unrolled and the value of n at each step is a constant. Thus you have something like: `a=0; a+=8&(table[a+8].key-key-1)>>31; a+=4&(table[a+4].key-key-1)>>31; a+=2&(table[a+2].key-key-1)>>31;` ... – R.. GitHub STOP HELPING ICE Jun 28 '10 at 21:48
  • Fair enough. The arithmetic, especially after pipeline stalls because of dependencies (the load depends on the outcome of the arithmetic), it's still a substantial amount of work - comparable to the original sorting network he disdained. Throw in cache misses because of the large lookup table, and it's probably much worse. – Nick Johnson Jun 28 '10 at 21:50
0

The multiplication is faster.

Multiplication of any given array will always be faster than sorting the array, presuming the multiplication results in a meaningful result, and the lookup table is irrelevant because the code is designed to evaluate a poker hand so you'd need to do a lookup on the sorted set anyway.

Chris
  • 49
  • 1
0

An example of a ready made Texas Hold'em 7- and 5-card evaluator can be found here with documentation and further explained here. All feedback welcome at the e-mail address found therein.

You don't need to sort, and can typically (~97% of the time) get away with just 6 additions and a couple of bit shifts when evaluating 7-card hands. The algo uses a generated look up table which occupies about 9MB of RAM and is generated in a near-instant. Cheap. All of this is done inside of 32-bits, and "inlining" the 7-card evaluator is good for evaluating about 50m randomly generated hands per second on my laptop.

Oh, and multiplication is faster than sorting.

Ken
  • 30,811
  • 34
  • 116
  • 155