Sunday, May 20, 2007

Unsigned Advantage

This is an impromptu Sunday afternoon post. Today, I've been looking a bit at the differences between the assembly code produced when using signed and unsigned integers in .NET (int and uint). Consider the following C# program:

using System; using System.Collections.Generic; using System.Text; namespace ConsoleApplication1 { class Program { static void Main(string[] args) { //signed values int i = GetValue(); int j = i * 4; int k = i % 32; int l = i / 8; //unsigned values uint q = GetUnsignedValue(); uint r = q * 4; uint s = q % 32; uint t = q / 8; //avoid being optimized away Console.Write("", j, k, l, r, s, t); } private static int GetValue() { return new System.Random().Next(-100, 100); } private static uint GetUnsignedValue() { return (uint) new System.Random().Next(0, 100); } } }

The code does some simple integer calculations (multiplication, modulus and division, all by powers of two), first with signed integers and then with unsigned. The resultant assembly code is examined in the sections below.

Multiplication

Here is the assembly code for signed multiplication:

int j = i * 4; 00000050 mov eax,ebp 00000052 shl eax,2 00000055 mov dword ptr [esp+4],eax

The JITter is smart enough to use a shift left (shl) instruction instead of an imul instruction (which is much slower). Here is the assembly code for unsigned multiplication:

uint r = q * 4; 00000087 mov eax,dword ptr [esp+10h] 0000008b shl eax,2 0000008e mov dword ptr [esp+14h],eax

As you can see, there's no difference apart from the fact that q wasn't readily available in the ebp register, and the result is obviously stored to r's stack offset instead of j's. This lack of difference makes sense given that signed integers are encoded as Two's Complement.

Modulus

Next up, we take the modulus of a signed and unsigned integer. Here's the assembly for the signed modulus:

int k = i % 32; 00000059 mov eax,ebp 0000005b and eax,8000001Fh 00000060 jns 00000067 00000062 dec eax 00000063 or eax,0FFFFFFE0h 00000066 inc eax 00000067 mov dword ptr [esp+8],eax

And here's the assembly for the unsigned modulus:

uint s = q % 32; 00000092 mov eax,dword ptr [esp+10h] 00000096 and eax,1Fh 00000099 mov dword ptr [esp+18h],eax

The latter certainly contains less code. A simple and instruction is used to isolate the 5 low order bits of q. Doing so yields the modulus of a divide by 32 (2^5).

The former is more convoluted, which is a direct result of working with a signed integer rather than unsigned. Special treatment must be given to taking the modulus of a negative number. As such, taking the modulus of a signed integer will be slower than taking the modulus of an unsigned integer when dealing with powers of two.

Division

Lastly, let's take a quick look at dividing by powers of two. Firstly, signed integers:

int l = i / 8; 00000067 mov eax,ebp 00000069 test eax,eax 0000006b jns 00000070 0000006d add eax,7 00000070 sar eax,3 00000073 mov dword ptr [esp+0Ch],eax

Now unsigned integers:

uint t = q / 8; 0000009f mov eax,dword ptr [esp+10h] 000000a3 shr eax,3 000000a6 mov dword ptr [esp+1Ch],eax

Again we can see that the latter code is significantly shorter than the former. Of course, shorter doesn't always mean faster, but it sure does in these cases.

A simple shift right (shr) is sufficient to implement division by a power of two when using unsigned integers. However, signed integers must again have special-case handling of negative numbers. A simple shift right on a negative number will not yield the desired result.

Conclusion

This is a very quick post about a very specific scenario (signed vs unsigned integers in common arithmetic operations when using powers of two). It's really just a thought provoker.

I am in the habit of simply using signed integers almost everywhere, even for looping constructs and private members. Perhaps this stems from the fact that unsigned types are not CLS-compliant when used in your public API (tip: you can mandate CLS compliance simply by marking your assembly with a [CLSCompliant(true)] attribute) and they are less commonly used as a result. Whatever the case, it's a habit I intend to break. Generally speaking, the more type information available to the compiler, the greater the chances of optimizations being performed under the covers. 

kick it on DotNetKicks.com

1 comment:

Anonymous said...

Thanks for this post - it is what I was looking for!