Posted by Adam on August 19th, 2009 — Posted in General
A few weeks ago, EngineYard held a programming competition. Basically, the contest was to see who could get a SHA-1 hash closest to a given hash. I thought it might be fun to see how well I could do with a minimal implementation, so I coded up something in C.
My goal was not to write the most efficient program possible, but to see what results I could get from a reasonable design and no major optimizations. So, I wrote about 160 lines of C code, using OpenSSL for the hashing and the old K&R bit counting method. Depending on how long the message plaintext was, this got me about 1 to 1.5 million attempts per second per core on my 3.0 Ghz Core 2 Duo. The winning CPU-based entry, which was written by D. J. Bernstein, contained an optimized SHA-1 implementation and got around 10 million hashes per second per core. So, I was about an order of magnitude off, which seems reasonable to me.
It turns out the really fast implementations were all on GPUs. Both the winner and the runner up used Nvidia’s CUDA for fast GPGPU processing, which was cool to see.
I ran my program for most of the 30 hours of the competition. How did I do? My best result was 37 bits off of the goal, which put me 7 away from the winner.
No Comments »
Posted by Adam on August 18th, 2009 — Posted in General
The Quiz
One of my coworkers recently sent out this C# programming quiz:
static void Main(string[] args)
{
object x = null;
object y = (short)4;
x = (y is System.Int32) ? (System.Int32)y : (System.Int16)y;
Console.WriteLine(x.GetType());
}
What is printed out?
Try it.
Explain why you were wrong.
If you run the code, you get this output:
System.Int32
The code snippet as it stands doesn’t make it clear exactly where the unexpected behavior is. This is a little more clear:
static void Main(string[] args)
{
object x = null;
object y = (short)4;
x = false ? (System.Int32)y : (System.Int16)y;
Console.WriteLine(x.GetType());
}
This code outputs the same thing as the above snippet. So why does this snippet output System.Int32, when x clearly gets set to (System.Int16)4 ? The answer is in the C# implementation of the ternary operator.
The Answer
In line 5 of the second example above, x is set to the result of the expression on the right side of the equals sign. Since the thing on the right is an expression, it must have a single type.
The C# Language Specification, in section 14.13, spells out how the type of the expression is determined:
The second and third operands of the ?: operator control the type of the conditional expression. Let X and Y be the types of the second and third operands. Then,
- If X and Y are the same type, then this is the type of the conditional expression.
- Otherwise, if an implicit conversion exists from X to Y, but not from Y to X, then Y is the type of the conditional expression.
- Otherwise, if an implicit conversion exists from Y to X, but not from X to Y, then X is the type of the conditional expression.
- Otherwise, no expression type can be determined, and a compile-time error occurs.
In our example, since there’s an implicit cast from an Int16 to an Int32, but not an implicit cast from an Int32 to an Int16, the compiler says the type of the expression must be Int32. Then, when our Int16 is returned, it’s typecast to an Int32.
More Types
The spec makes it pretty clear what is supposed to happen if there’s an implicit conversion from one of the operands to the other, but not the other way around. But what happens if there’s an implicit conversion in both directions? According to the spec, none of the first three conditions are met, so the compiler must output an error. There is an implicit conversion from a byte to int, and also one from const int to byte, as long as the int is small enough to fit into the byte. So, let’s try compiling this:
static void Main(string[] args)
{
const int i = 1;
const byte b = 2;
object x = null;
x = true ? i : b;
Console.WriteLine(x.GetType());
}
The Bug
If you compile this with the .NET 3.5 compiler, it compiles without errors. There’s a warning about hardcoding true into the ternary operator, but nothing about the types. So, the compiler does not conform to the C# language spec. That’s a bug, but it’s not that shocking. There are other places where the .NET compiler doesn’t conform to the spec. It seems that Microsoft has a policy to leave such bugs in, so as to not break compatibility with existing code, so it will probably stay that way for the foreseeable future.
Mono
This got me wondering if the Mono compiler properly supports the spec. So, I tried compiling with the Mono 2.0 C# compiler. Here’s what you get:
Program.cs(13,17): error CS0172: Can not compute type of conditional expression as `int’ and `byte’ convert implicitly to each other
Compilation failed: 1 error(s), 0 warnings
So it looks like Mono conforms to the spec in this case. It’s a bit amusing that an open source project supports the spec better than Microsoft itself, but there are probably also cases where it goes the other way. However, this means that the Mono implementation is incompatible with the .NET implementation of C#. Now, this particular incompatibility is unlikely to come up that often, since there aren’t many types that have two-way implicit conversions with each other, but it’s something to consider.
The Law
The legal implications of this bug are perhaps the most interesting part. A few weeks ago, there was a lot of talk about the Mono patent situation. This has now been largely resolved with Microsoft putting C# and the CLR under its Community Promise. However, the Community Promise only applies to a given implementation “to the extent it conforms to one of the Covered Specifications.” If an implementation does not conform to the specification, it is not covered by the promise.
You can probably see where I’m going with this. If Mono decided to support compatibility with the .NET compiler by breaking from the spec and implementing the ternary type bug the same way Microsoft has, it might be giving up its protection against patent lawsuits. In order to be legally safer, it’s probably wiser for Mono to stick to the spec and break compatibility with the .NET compiler. This is significant, because the more situations like this crop up, the harder it will be for programmers to port their .NET code to Mono. There’s not much that the mono project can do about this, but it’s unfortunate that the legal situation forces their hand on compatibility.
9 Comments »