My Engineyard Contest Odyssey
alan.dipert.org
alan.dipert.org
- __builtin_popcount() and __builtin_popcountll() are great gcc builtins which perform bit population counts, useful for hamming distances (after the XOR operation, of course). [1]
- avoid scanf(), which is costly. My approach was to generate a header file with the char * words[] array, and also a int words_len[] with, you guessed it, the pre-computed lengths. Then go for the memcpy() route and you're in a much better position.
- speaking of memcpy, gcc provides one that should be optimal in most cases, but for really short words, it might be easiest to write your own. I came across a good article on it [2] but this is what I ended up using:
void
c_memcpy (char * dst, char * src, size_t len)
{
__builtin_prefetch(dst, 1, 3);
while (len--) {
*dst++ = *src++;
}
}
[2] http://www.embedded.com/columns/technicalinsights/19205567
I'm curious about your scanf point though. I'm using scanf/strdup before the check loop to load the words into memory. Are subsequent memcpy calls on an implicitly loaded *char dict[] array faster on non-malloc'd memory for some reason?
My hope and understanding are that the compiler's static analysis skills will best align the given data, whereas something like malloc() would try to allocate on the heap as best it can with the open possibility of other data needing to be on the heap as well.
The point I was driving at, and what I tried to do, was to hard-code in as many known variables as possible such that the compiler could do its thing and try to be as efficient as it could with the given data. This includes the word list, the list of lengths, the target hash -- none of which has to be done by hand, but rather a higher-level script called before compilation.
Good times.
From the results of the contest, I would have concluded that the platform of choice was CUDA. Do you think otherwise? Is there a reason you'd choose to use a flotilla of Rackspace servers for a problem like this rather than a graphics card? If you are going to be programming in C anyway, it seems like a much simpler approach.
I think using cloud resources was the way to go though, because it's easy to search for keys concurrently, and you can summon an effectively unlimited amount of computing power pretty cheaply. You can add as many cloud servers as you want to your cluster without worrying about locking or divvying up work, and the number of keys your cluster is able to check per second increases linearly with the number of machines.
The winning team, awesome guys with a cluster of 8 very powerful computers and a CUDA program, were able to check just over 400 million keys per second. If I would have used 400 Rackspace cloud servers, it would have cost me about $100 to run them for the duration of the contest and I would have been achieving similar speeds.
"With all the machines running we got up to a total of 3079431974 hashes/second" (via http://www.win.tue.nl/cccc/sha-1-challenge.html)
Presuming your costs are accurate, this would imply that the card would be a cheaper solution if run for more than a week. Considering the ~100x speed advantage of the card, it's rather surprising that their cloud solution is as affordable as it is.