Fast Conversion of Hex String Into Decimal Number

Today's post will be about performance. More specifically about converting hex string into decimal number faster than using built-in .NET Framework methods.

I will compare performance of three methods used to convert hex into decimal number. Two of those methods are built into .NET Framework.

1) Convert.ToInt32(hexNumberString, 16)
2) int.Parse(hexNumber, NumberStyles.HexNumber);
3) Custom method using pre-populated table. Let us call it TableConvert.

Here's the code for the TableConvert class. This class just illustrates the idea behind pre-populated table - it is not production code.

class TableConvert
  {
      static sbyte[] unhex_table =
      { -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1
       ,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1
       ,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1
       , 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,-1,-1,-1,-1,-1,-1
       ,-1,10,11,12,13,14,15,-1,-1,-1,-1,-1,-1,-1,-1,-1
       ,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1
       ,-1,10,11,12,13,14,15,-1,-1,-1,-1,-1,-1,-1,-1,-1
       ,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1
      };
                                 
      public static int Convert(string hexNumber)
      {
          int decValue = unhex_table[(byte)hexNumber[0]];
          for (int i = 1; i < hexNumber.Length; i++)
          {
              decValue *= 16;
              decValue += unhex_table[(byte)hexNumber[i]];
          }
          return decValue;
      }
  }

The approach uses simple technique of pre-populated table of  hex-to-decimal values and some simple math. To measure performance of these three methods I've wrote small test application that performed conversion in the loop and measured time.

Tests were made using Intel Core i7 2.80 GHz, .NET Framework 4.0. Time measurements were made in ticks using Stopwatch class.

Results:
Hex string: FF01

Iterations	TableConvert	Convert Method	Parse Method
100	28	35	63
10000	2134	2593	5915
1000000	191935	252252	433490

Hex string: 4AB201

Iterations	TableConvert	Convert Method	Parse Method
100	26	27	47
10000	1930	2775	4284
1000000	192801	269016	481308

Conclusions

Not surprisingly Parse method has the worst performance of all methods. While TableConvert method is the fastest. Usually about 1.2 - 1.4 times faster (20%-40%) than Convert Method.

If you ever happen to do a lot of  convert operations of hex string into decimal number and want to perform it as fast as possible - you can use TableConvert method.

Fastest Way To Retrieve Custom Attributes for a Type Member

In my previous posts (Performance Issues When Comparing Strings in .NET and When string.ToLower() is Evil) string related operations were discussed.

In this post we'll examine performance issues when querying for type member's custom attributes.
Let us define two attributes and a class. Class will have its single method decorated with an attribute. Here's the code:

class FooAttribute : Attribute
{ }

class BarAttribute : FooAttribute
{ }

class Item
{
    [Bar]
    public int Action()
    {
        return 0;
    }
}

Now the question is what is the fastest way to check Action method for Bar custom attribute. Custom attributes can be queried using instance of a type that implements ICustomAttributeProvider interface. In our case we shall use Assembly class and MethodInfo.

The code below queries custom attributes using Assembly class and then using MethodInfo instance. Query operation executes 10000 times and duration is measured using Stopwatch class. Code below also measures time required to check if attribute is applied.

int count = 10000;
Type tBar = typeof(Item);
MethodInfo mInfo = tBar.GetMethod("Action");
//warm up
mInfo.IsDefined(typeof(FooAttribute), true);
object[] attribs = null;
Stopwatch sw = new Stopwatch();

sw.Start();
for (int i = 0; i < count; i++)
{
 attribs = Attribute.GetCustomAttributes(mInfo, typeof(FooAttribute), true);
}
sw.Stop();

Console.WriteLine("Attribute(specific): {0}, Found: {1}", sw.ElapsedMilliseconds, 
 attribs.Length);
sw.Reset();

sw.Start();
for (int i = 0; i < count; i++)
{
 attribs = mInfo.GetCustomAttributes(typeof(FooAttribute), true);
}
sw.Stop();
Console.WriteLine("MethodInfo: {0}, Found: {1}", sw.ElapsedMilliseconds, 
 attribs.Length);
sw.Reset();

sw.Start();
for (int i = 0; i < count; i++)
{
 attribs = Attribute.GetCustomAttributes(typeof(FooAttribute), true);
}
sw.Stop();

Console.WriteLine("Attribute(general): {0}, Found: {1}", sw.ElapsedMilliseconds, 
 attribs.Length);
sw.Reset();
   
sw.Start();
for (int i = 0; i < count; i++)
{
 Attribute.IsDefined(mInfo, typeof(FooAttribute), true);
}
sw.Stop();

Console.WriteLine("Attribute::IdDefined: {0}", sw.ElapsedMilliseconds);
sw.Reset();

sw.Start();
for (int i = 0; i < count; i++)
{
 mInfo.IsDefined(typeof(FooAttribute), true);
}
sw.Stop();

Console.WriteLine("MethodInfo::IdDefined: {0}", sw.ElapsedMilliseconds);
sw.Reset();

Code above produces the output:

Attribute(specific): 137, Found: 1
MethodInfo: 130, Found: 1
Attribute(general): 569, Found: 1
Attribute::IdDefined: 40
MethodInfo::IdDefined: 33

Results indicate that the fastest method is querying custom attributes via MethodInfo class. To generalize the results above we can say that the fastest way to get custom attributes - is to use the closest reflection equivalent of type member. (e.g. Method - MethodInfo, Property - PropertyInfo etc)

Last two results show the time of IsDefined operation. Use this operation in cases when only a check is needed whether attribute is applied to a type member.

How To Go Slow: Summing Arrays

In this entry I'll talk about thrashing when iterating over complex arrays.

Consider a square array with the size of N = 10000;
Now, consider the code that summs elements of the square array

for (int row = 0; row < N;, ++row)
      for (int col = 0; col < N; ++col)
         sum += A[row, col];

Or on the other hand:

for (int col = 0; col < N; ++col)
      for (int row = 0; row < N; ++row)
         sum += A[row, col];

How do you think is there any difference between these two approaches?
The answer is yes - difference is quite noticeable... in terms of performance.

First approach takes about 1 second to complete, while the second - nearly 14 seconds! How can this be you may ask?

The answer is memory layout, caching and thrashing.

In .NET much like in C++ arrays are stored row-wise in contiguous memory. So, if you will access array rows first you will access contiguous memory. That means that the next data item you need will be be in pipeline, cache, RAM, and the next hard drive sector before you need it will be in the cache.

But if you go through columns first then you will be repeatedly reading just one item from each row before reading from the next row. As a result your system's caching mechanism and lookahead will fail to give you recent items, and you will waste a lot of time waiting for RAM, which is about three to five times slower than cache. It can get even worse, you may end up waiting for the hard drive. HDD can be millions of times slower than RAM if accessed in large random jumps.

The moral: the less sequential your data access, the slower your program will run :)

When string.ToLower() is Evil

Did you know how evil string.ToLower() can sometimes be?

Let me explain...

Very often I see code similar to this:

void DoBadAction (string val)
{
if (val.ToLower() == "someValue")
{ //do something
}
}

The code above can lead up to 4 times in performance loss when doing string comparison operations.

Best method to do such kind of case insensitive comparison is using string.Equals(...) method.

void DoGoodAction(string val)
{
if (val.Equals("someValue", StringComparison.OrdinalIgnoreCase))
{ //do something
}
}

Why is it so? The reason lies in the string type peculiarity - it is immutable.

Since it is an immutable - string.ToLower() will always return new string instance. Thus generating extra instance of string on every ToLower() call.

Detailed information about string.Equals with StringComparison enumeration can be found here.
Other performance related tips and tricks can be found here.