Optimizing a decimal to hexadecimal conversion algorithm and performance comparison. +500% faster over fmt.Sprintf and +150% faster over strconv.FormatInt
Table of Content
Hexadecimal format
Hexadecimal is the name of the numbering system that is base 16. This system, therefore, has numerals 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, and 15. That means that two-digit decimal numbers 10, 11, 12, 13, 14, and 15 must be represented by a single numeral to exist in this numbering system. To address the two-digit decimal values, the alphabetic characters A, B, C, D, E, and F are used to represent these values in hexadecimal and are treated as valid numerals.
Goal
Understand and evaluate whether community used ways of converting a decimal number to hexadecimal string are performance optimized or not.
Decimal to Hexadecimal conversion algorithm
Assuming no idea of its algorithm, a simple Google search result show us following top referenced websites.
A review of their content shows that declared ways to execute this conversion are based on:
fmt.Sprintf
strconv.FormatInt
For completeness, I also search if any library on Github was available for this task, and this is what I found.
For our test and comparison, I prepare following implementation based on most common referenced methods of converson.
strconv.FormatInt based conversion
1
2
3
4
5
// WithFormatInt make uses of Go std FormatInt() to convert from
// decimal to hexadecimal
funcWithFormatInt(vint64)string{returnstrconv.FormatInt(v,16)}
fmt.Sprintf based conversion
1
2
3
4
5
// WithFmt make uses of Go std fmt.Sprintf() to convert from
// decimal to hexadecimal
funcWithFmt(vint64)string{returnfmt.Sprintf("%x",v)}
// WithGithubCode1 makes uses of github algorithm at
// https://github.com/TDCQZD/GoDev/blob/982ca325329baab67489d7f3d4f43dcdc8bdf561/utils/convert.go#L53
funcWithGithubCode1(vint64)string{ifv<0{log.Println("Decimal to hexadecimal error: the argument must be greater than zero.")return""}ifv==0{return"0"}hex:=map[int64]int64{10:65,11:66,12:67,13:68,14:69,15:70}s:=""forq:=v;q>0;q=q/16{m:=q%16ifm>9&&m<16{m=hex[m]// NOTE$: minor tweak applied here!!
// ./dec2hex_impl_test.go:39:28: conversion from int64 to string yields a string of one rune, not a string of digits (did you mean fmt.Sprint(x)?)
m2:=string(rune(m))s=fmt.Sprintf("%v%v",m2,s)continue}s=fmt.Sprintf("%v%v",m,s)}returns}
Algorithms evaluation
After selecting our 3 candidate algorithms, we need to write some test benchmarks. The designed benchmark is as follows:
To run the benchmark of different algorithms, we run our benchmark implementations with following command to have more consistent results and less noise.
As seen, the best way to convert a decimal number to hexadecimal is using strconv.FormatInt. But, can be improved?
Optimizing conversion of Decimal to Hex in Go
To optimize the conversion of a decimal number to hexadecimal string, we will try to stick to conversion algorithm simplicity. To do so, we implement following format conversion function
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// FormatDst converts uint64 to Hex value
// using provided byte destination slice
funcFormatDst(dst*HexWrap,nuint64)Hex{ifn==0{returnHex("0")}varidxuint8=16// we are assuming 'dst' wont be never nil
_=dst[15]forq:=n;q>0;q>>=4{m:=q%16dst[idx-1]=uint8(48+m)ifm>9{dst[idx-1]+=7}idx--}returndst[idx:]}
Performance evaluation
As earlier, we run same go test benchmarking command and collect the results. In my case, resuls are shown below.
Google tends to provide good search results most of the times. However, when designing systems and algorithms you should take some time to thing the best way to achieve some specific taks In this case, the base conversion of decimal number to hexadecimal is a trivial case. Doing it the right way, is proven to be 150-500% memory faster than standard solutions provided by Google and top Github search results. So as always, DYOR!
Subscribe, donate or become premium
You like it? Help making this blog better and subscribe to get advantages or make a one-time donation.
Thanks for checking this out and I hope you found the info useful! If you have any questions, don't hesitate to write me a comment below. And remember that if you like to see more content on, just let me know it and share this post with your colleges, co-workers, FFF, etc.