Friday, September 25, 2009

Print byte in hex -- comparison of two algorithms

One byte contains 8 bits, or two nibbles. To represents a byte in hex, each nibble is given a hexadecimal digit in 0-9 and A-F. For example, character 'Z' whose binary value is "0101 1010" is presented as "5A".

The most obvious way to print a byte in hex format is to first grab the most significant nibble and print it as the corresponding hexadecimal digit. And then do the same thing to the least significant nibble. This will lead to the following piece of code (in Java):


static String[] hexChar = {
"0", "1", "2", "3", "4", "5", "6", "7",
"8", "9", "A", "B", "C", "D", "E", "F"};

public static String byteToHex(byte b)
{
String result = hexChar[(b >> 4) & 0x0f] + hexChar[b & 0x0f];

return result;
}


It looks so simple and straightforward, who would want to improve it? Well, there is something we can play with.

You may realize that there are totally 256 bytes. After we call the byteToHex() function 256 times, we know we would do some repeated work to split the byte into nibbles and find out the value of each nibble. If we can remember what we have done before, we can tell immediately that character 'Z' will be represent as "5A" without splitting the byte into two nibble to find out that the most significant nibble can be printed as '5' and the least significant nibble can be printed as 'A'. Based on the idea, we have another piece of code:

static String[] hexStr = {
"00","01","02","03","04","05","06","07","08","09","0A","0B","0C","0D","0E","0F",
"10","11","12","13","14","15","16","17","18","19","1A","1B","1C","1D","1E","1F",
"20","21","22","23","24","25","26","27","28","29","2A","2B","2C","2D","2E","2F",
"30","31","32","33","34","35","36","37","38","39","3A","3B","3C","3D","3E","3F",
"40","41","42","43","44","45","46","47","48","49","4A","4B","4C","4D","4E","4F",
"50","51","52","53","54","55","56","57","58","59","5A","5B","5C","5D","5E","5F",
"60","61","62","63","64","65","66","67","68","69","6A","6B","6C","6D","6E","6F",
"70","71","72","73","74","75","76","77","78","79","7A","7B","7C","7D","7E","7F",
"80","81","82","83","84","85","86","87","88","89","8A","8B","8C","8D","8E","8F",
"90","91","92","93","94","95","96","97","98","99","9A","9B","9C","9D","9E","9F",
"A0","A1","A2","A3","A4","A5","A6","A7","A8","A9","AA","AB","AC","AD","AE","AF",
"B0","B1","B2","B3","B4","B5","B6","B7","B8","B9","BA","BB","BC","BD","BE","BF",
"C0","C1","C2","C3","C4","C5","C6","C7","C8","C9","CA","CB","CC","CD","CE","CF",
"D0","D1","D2","D3","D4","D5","D6","D7","D8","D9","DA","DB","DC","DD","DE","DF",
"E0","E1","E2","E3","E4","E5","E6","E7","E8","E9","EA","EB","EC","ED","EE","EF",
"F0","F1","F2","F3","F4","F5","F6","F7","F8","F9","FA","FB","FC","FD","FE","FF",
};

public static String fasterByteToHex(byte b)
{
String result = hexStr[(short)b & 0x00ff];

return result;
}


The hexStr[] array is big so I use a small program to generate it. Once it has been generated, it is there. We also want to declare it as static because if it were temparory inside the fasterByteToHex() function, it would be built each time the function is called. That would give out worse performance.

Now, let's test whether the so call faster something is really faster with the program below:

public static void main(String arg[])
{
String s = "This is a test string.";

byte[] bytes = s.getBytes();

for (int i = 0; i < 10000000; i++)
{
String res = "";

for (int j = 0; j < bytes.length; j++)
{
String inHex =
byteToHex(bytes[j]);
//fasterByteToHex(bytes[j]);

if (0 == i)
res += inHex;
}

if (0 == i)
System.out.println(res);
}
}


It turned out that with the first straightforward solution, the running time was:

real 0m25.696s
user 0m25.339s
sys 0m0.170s


And the "faster" algorithm had the running time of:

real 0m0.691s
user 0m0.664s
sys 0m0.025s


The so called faster something is really much faster.

Read my other post of Even parity with the similar idea to speed things up.

No comments:

Post a Comment