Introduction
Not so long ago, I WAS accidentally faced with a code snippet in a web which validates ISBN-10 number (if you are not familiar with what ISBN is, please refer to wiki page). This code works great. I wrote several unit tests to verify the algorithm's correctness and all of them passed. But when I started to delve deeper into details, I found out a broad room for improvements regarding performance optimization. I used Visual Studio profiler and WinDbg to catch the root cause of a bottleneck. I also used BenchmarkDotNet
library (https://github.com/PerfDotNet/BenchmarkDotNet) to perform benchmarking. Below, I describe all the steps I took to significantly boost algorithm's performance.
The Algorithm
The problem that an algorithm is trying to solve is given a string
input (for example 0-201-53082-1), answer the question if it is a valid ISBN-10 number or not.
According to wiki ISBN-10, validation algorithm can be expressed as follows:
Quote:
The final character of a ten digit International Standard Book Number is a check digit computed so that multiplying each digit by its position in the number (counting from the right) and taking the sum of these products modulo 11 is 0. The digit the farthest to the right (which is multiplied by 1) is the check digit, chosen to make the sum correct. It may need to have the value 10, which is represented as the letter X. For example, take the ISBN 0-201-53082-1: The sum of products is 0×10 + 2×9 + 0×8 + 1×7 + 5×6 + 3×5 + 0×4 + 8×3 + 2×2 + 1×1 = 99 ≡ 0 (mod 11). So the ISBN is valid. Note that positions can also be counted from left, in which case the check digit is multiplied by 10, to check validity: 0×1 + 2×2 + 0×3 + 1×4 + 5×5 + 3×6 + 0×7 + 8×8 + 2×9 + 1×10 = 143 ≡ 0 (mod 11).
While this may seem more complicated than the first scheme, it can be validated simply by adding all the products together then dividing by 11. The sum can be computed without any multiplications by initializing two variables, t
and sum
, to 0 and repeatedly performing t = t + digit; sum = sum + t;
(which can be expressed in C as sum += t += digit;
). If the final sum
is a multiple of 11, the ISBN is valid.
Pretty simple, isn't it.
Initial Solution
This is how initial code looks like:
public static class Isbn
{
public static bool IsValid(string isbn)
{
bool result = false;
if (!string.IsNullOrEmpty(isbn))
{
if (isbn.Contains("-")) isbn = isbn.Replace("-", "");
long j;
if (isbn.Length != 10 || !long.TryParse(isbn.Substring(0, isbn.Length - 1), out j))
return false;
char lastChar = isbn[isbn.Length - 1];
int sum = 0;
for (int i = 0; i < 9; i++)
sum += int.Parse(isbn[i].ToString()) * (i + 1);
int remainder = sum % 11;
if (lastChar == 'X')
{
result = (remainder == 10);
}
else if (int.TryParse(lastChar.ToString(), out sum))
{
result = (remainder == int.Parse(lastChar.ToString()));
}
return result;
}
return false;
}
}
I also wrote a console app which invokes Isbn.IsValid
method.
namespace Console
{
class Program
{
static void Main(string[] args)
{
Isbn.IsValid("99921-58-10-7");
}
}
}
I decided to run this code under Visual Studio memory profiler and to look at memory allocations made by the algorithm. Here are the results:
Oh my God! 195 memory allocations for a simple method. It is evident that we should somehow deal with that.
The same issues can be found with the help of a hard core tool - WinDbg
. To do this:
- Run the app under
WinDbg
- Execute
sxe ld clrjit
command to wait for CLR to be loaded into process address space - Run
g
command to continue program's execution - Load sos extension. To to that, just execute
.loadby sos clr
- Load sosex extension. To to that, just execute
.loadby sosex clr
- Create a breakpoint at the beginning of the
Main
method. Here is the command: !bpmd Console Console.Program.Main
- Run
g
command. Program's execution will break at the beginning of the Main
method. - Run
!dumpheap -stat -type System.String
. It will print out the number of string
objects allocated on heap. On my machine, the output looks like the following: -
Statistics:
MT Count TotalSize Class Name
60baab9c 2 104 System.Object[]
60bfacc4 38 2366 System.String
Total 40 objects
- There are 38 objects of type
System.String
at the moment when method Main
starts - Create breakpoint at the line of source code after
Isbn.IsValid
method invocation. We can use sosex extension and its !mbp
command in the following way - !mbp Program.cs 34
- Run
g
command again. Program execution will break at the end of Main
method. - Run
!dumpheap -stat -type System.String
again. In my case, the output is: -
Statistics:
MT Count TotalSize Class Name
60bfd6ac 1 12 System.Collections.Generic.GenericEqualityComparer`1[[System.String, mscorlib]]
60812348 1 48 System.Collections.Generic.Dictionary`2
[[System.String, mscorlib],[System.Globalization.CultureData, mscorlib]]
60bfd7b8 1 60 System.Collections.Generic.Dictionary`2+Entry
[[System.String, mscorlib],[System.Globalization.CultureData, mscorlib]][]
60baab9c 19 736 System.Object[]
60bfacc4 185 5822 System.String
Total 207 object
There are 185 objects of type System.String
allocated on the heap! Very inefficient. It seems obvious that the ISBN validation algorithms, ideally, should not allocate System.String
objects at all.
I decided to rewrite the algothms to minimize the number of memory allocations.
Optimized Solution
I created a class named IsbnEx
with the optimized version of an algorithm.
using System.Text;
using Utils;
public static class IsbnEx
{
unsafe public static bool IsValid(object value)
{
if (value == null)
{
return true;
}
string val = (string)value;
if (!string.IsNullOrEmpty(val))
{
long length = 0;
char[] array = val.ToCharArray();
fixed (char* left = array)
{
char* right = left;
char* mLeft = left;
while (*right != '\0')
{
if (*right == '-')
{
right++;
}
else
{
*mLeft = *right;
mLeft++;
right++;
length++;
}
}
*mLeft = '\0';
}
if (length == 10)
{
return IsValidIsbn10(array);
}
return false;
}
return false;
}
private static bool IsValidIsbn10(char[] isbn)
{
int sum = 0;
int val;
for (int i = 0; i < 9; ++i)
{
char c = isbn[i];
if (c.TryParse(out val))
{
sum += (i + 1) * val;
}
else
{
return false;
}
}
int remainder = sum % 11;
char lastCharacter = isbn[9];
if (lastCharacter == 'X')
{
return remainder == 10;
}
if (lastCharacter.TryParse(out val))
{
return remainder == val;
}
return false;
}
}
I extracted character's parsing algorithm into a separate Utils
class.
namespace Utils
{
public static class Utils
{
public static bool TryParse(this char c, out int val)
{
if (c < '0' || c > '9')
{
val = 0;
return false;
}
val = (c - '0');
return true;
}
}
}
I also rewrite my console app to invoke IsbnEx.IsValid
method.
namespace Console
{
class Program
{
static void Main(string[] args)
{
IsbnEx.IsValid("99921-58-10-7");
}
}
}
Let's check whether we gained performance benefits.
Results
Here are the results of Visual Studio memory profiling:
There is only one memory allocation. It is made by the line of code below:
char[] array = val.ToCharArray();
And WinDbg
output:
Before Isbn.IsValid
invocation:
Statistics:
MT Count TotalSize Class Name
60baab9c 2 104 System.Object[]
60bfacc4 38 2366 System.String
Total 40 objects
After Isbn.IsValid
invocation:
Statistics:
MT Count TotalSize Class Name
60baab9c 2 104 System.Object[]
60bfacc4 38 2366 System.String
Total 40 objects
Thus, method Isbn.IsValid
hasn't allocated System.String
objects at all. Fab!
Now, it is time to measure and compare execution time of 2 methods. I created a benchmark (thanks Andrey Akinshin for his fantastic BenchmarkDotNet
library)
using BenchmarkDotNet;
using BenchmarkDotNet.Tasks;
[BenchmarkTask(platform: BenchmarkPlatform.X86, jitVersion: BenchmarkJitVersion.LegacyJit)]
public class IsbnBenchmark
{
[Benchmark]
public void IsbnTest()
{
Isbn.IsValid("99921-58-10-7");
}
[Benchmark]
public void IsbnExTest()
{
IsbnEx.IsValid("99921-58-10-7");
}
}
namespace Console
{
class Program
{
static void Main(string[] args)
{
new BenchmarkRunner().Run<IsbnBenchmark>();
}
}
}
And the output:
180.9 versus 1719.9. Not so bad.
Further Optimization
After a while, I realised that it is possible to go further and tune the algorithm a little bit. The obvious way for improvement is to completely remove any memory allocations. Thus, I decided to eliminate the following line of code and change the algorithm accordingly.
char[] array = val.ToCharArray();
Apart from that, I investigated the assembly code generated by JIT and found out that the method Utils.TryParse
wasn't inlined. I don't know the reason for that - it is a black magic how JIT makes decisions about whether to inline methods or not. I assume that it is due to out
parameter. So I split Utils.TryParse
method into 2 separate methods - the one which checks if a character is a digit and another one which converts a character into an integer. And voila - both methods were inlined during JIT compilation. My final code looks like the following:
IsbnEx
class:
using Utils;
public static class IsbnEx
{
public static bool IsValid(string val)
{
if (!string.IsNullOrEmpty(val))
{
int length = 0;
for (int i = 0; i < val.Length; ++i)
{
if (val[i] == '-')
{
continue;
}
length++;
}
if (length == 10)
{
return IsValidIsbn10(val);
}
return false;
}
return false;
}
private unsafe static bool IsValidIsbn10(string isbn)
{
int i = 0, sum = 0, val;
char lastCharacter = '\0';
fixed (char* left = isbn)
{
char* right = left;
while (*right != '\0')
{
if (*right == '-')
{
right++;
continue;
}
if (i < 9)
{
char c = *right;
if (c.TryParse())
{
val = c.Parse();
sum += (i + 1) * val;
++i;
}
else
{
return false;
}
}
else
{
lastCharacter = *right;
}
right++;
}
}
int remainder = (sum) % 11;
if (lastCharacter == 'X')
{
return remainder == 10;
}
if (lastCharacter.TryParse())
{
val = lastCharacter.Parse();
return remainder == val;
}
return false;
}
}
Utils
class:
namespace Utils
{
public static class Utils
{
public static bool TryParse(this char c)
{
if (c < '0' || c > '9')
{
return false;
}
return true;
}
public static int Parse(this char c)
{
return (c - '0');
}
}
}
And finally - benchmark output:
76.6 ns. Better!
The source code is available here Download Isbn.zip
History
- Version 1 - December 2015
- Version 2 - December 2015 - Further optimization section was added
This member has not yet provided a Biography. Assume it's interesting and varied, and probably something to do with programming.