Tell me more ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.
up vote 2 down vote favorite
1

Description:

Write the fastest comparison function for an opaque field containing a double. Here is my example:

// Three-way comparison function:
//   if a < b: negative result
//   if a > b: positive result
//   else: zero result
inline int Compare(const unsigned char* a, const unsigned char* b) const 
{
    if (*(double*)a < *(double*)b) return -1;
    if (*(double*)a > *(double*)b) return +1;
    return 0;
}

Size: 188 characters (excluding the comments)
Speed: N/A

Background:

Google's LevelDB stores keys as opaque fields (i.e. bytes) and it requires the use of a comparator when the keys cannot be compared as bytes, such as the case with doubles. You can read this article to see why Floating-Point binary comparison is tricky, so when LevelDB stores key-value pairs on disk it has to properly compare the opaque keys in order to achieve good data locality.

Correct Submission:

  1. The submission must be written in C/C++.
  2. The submission must correctly compare the opaque fields as doubles.
  3. Given that 1 and 2 are satisfied, the winner should be selected based on the minimum CPU operations ticks (i.e. the fastest comparison).

If there is a tie, then the shortest correct submission will be awarded.

P.S. This is my first time posting, so please let me know if I should correct/improve something in the competition.

share|improve this question
"Minimum CPU operations" isn't well defined unless you specify at minimum an architecture and a compiler, and even then sometimes using fewer operations isn't better. Moreover, with the exception of signed zeros and NaNs comparing doubles as bytes is really easy. – Peter Taylor Nov 11 '11 at 21:20
@PeterTaylor, I should probably change it to CPU ticks... additionally, we could run the code in codepad.org or ideone.com; however, I suspect that the performance may differ depending on the server load at the time. And I'm not exactly sure what's the best way to performance test (i.e. found out the number of CPU cycles). – Lirik Nov 11 '11 at 21:24
@Lirik What you could do is giving a large array of test data and a sorting algorithm. Then you write a test-script where the sorting algorithm's object file is linked with the object files of each candidate code and you run a sort operation on the array. If the array is sorted correctly, the code is right. The time needed for sort is the time that counts. – FUZxxl Nov 12 '11 at 14:19
@FUZxxl, I'll try to come up with a good test data set for performance testing and I appreciate your submission! :) thanks! – Lirik Nov 12 '11 at 19:01
1  
code-golf, code-challenge, and fastest-code all together don't make sense. – muntoo Jan 5 '12 at 8:09
show 5 more comments

2 Answers

up vote 3 down vote

This function is written in MMIX assembly. It should perform the calculation in 2v + 5µ. If you inline it, the call is no longer needed so you can save the POP instruction. This function should be compatible with gcc for MMIX. (Read TAOCP vol 1. fasc 1 for more information):

compareDoubles IS @  ; Declare symbol, @ is the current position
   LDOU $0,$0,0      ; Load first double  (LDOU: load octa unsigned), 1v
   LDOU $1,$1,0      ; Load second double, 1
   FCMP $0,$0,$1     ; Compare floating point values, 4µ
   POP  1,0          ; return, 1µ

If you assemble it, the code is 16 bytes long and may looks this:

8f 00 00 00  8f 01 01 00  01 00 00 01  f8 01 00 00
share|improve this answer
-1, fails spec: not written in C or C++. Still pretty neat, though. – Ilmari Karonen Jan 5 '12 at 15:35
@Ilmari It's unusual to downvote a submission just because the language is wrong. – FUZxxl Jan 5 '12 at 21:54
Yeah, I realized that the downvote was unreasonable after I made it, but it was too late to revoke it. I'd mistakenly thought this was a new challenge, and wondered why people were rushing to upvote an obviously non-compliant answer. FWIW, I did go and find another one of your answers that I liked and upvoted it to make up for the hasty downvote. – Ilmari Karonen Jan 5 '12 at 22:06
Thank you. That can happen to everyone. – FUZxxl Jan 6 '12 at 6:30
Can't you load that into a memory location, then cast it as a function pointer and throw stuff at it? Kind of like how you'd run shell code in C? – GigaWatt Jan 12 '12 at 22:03
show 1 more comment
up vote 1 down vote 
#define compare(X, Y) ((X)<(Y)?-1:((X)>(Y)?1:0)) 
// 48 characters

or want to pass a pointer you can define

#define compare(X, Y) (*((double*)X)<*((double*)Y)?-1:(*((double*)X)>*((double*)Y)?1:0))
// 88 characters
share|improve this answer
Doesn't follow specs. – Thomas Eding Jan 11 '12 at 7:06
@trinithis why? defines just force the compiler to use inline calling, and removes type checking (and both happen in question example) – Gajoo Jan 11 '12 at 9:15
#define does not remove type checking. It's just a macro. In any case, your code will compare char*s as chars, not as doubles. – Thomas Eding Jan 11 '12 at 18:19
@trinithis fixed that, but anyway it's the fastest possible. – Gajoo Jan 11 '12 at 18:55

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.