Back
Featured image of post Dec2hex: optimizing decimal to hexadecimal conversion algorithms for speed

Dec2hex: optimizing decimal to hexadecimal conversion algorithms for speed

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.

Github search results for ‘Decimal to Hexadecimal’ query string
Github search results for ‘Decimal to Hexadecimal’ query string

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
func WithFormatInt(v int64) string {
    return strconv.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
func WithFmt(v int64) string {
    return fmt.Sprintf("%x", v)
}

Github sample based conversion

See original implementation at: https://github.com/TDCQZD/GoDev/blob/982ca325329baab67489d7f3d4f43dcdc8bdf561/utils/convert.go#L53

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// WithGithubCode1 makes uses of github algorithm at
// https://github.com/TDCQZD/GoDev/blob/982ca325329baab67489d7f3d4f43dcdc8bdf561/utils/convert.go#L53
func WithGithubCode1(v int64) string {
    if v < 0 {
        log.Println("Decimal to hexadecimal error: the argument must be greater than zero.")
        return ""
    }
    if v == 0 {
        return "0"
    }
    hex := map[int64]int64{10: 65, 11: 66, 12: 67, 13: 68, 14: 69, 15: 70}
    s := ""
    for q := v; q > 0; q = q / 16 {
        m := q % 16
        if m > 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)
    }
    return s
}

Algorithms evaluation

After selecting our 3 candidate algorithms, we need to write some test benchmarks. The designed benchmark is as follows:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

const (
    maxInt64 int64 = math.MaxInt64
)

func BenchmarkFormat(b *testing.B) {
    b.Run("$name", func(b *testing.B) {
        var v string
        b.ReportAllocs()
        b.SetBytes(1)
        b.ResetTimer()
        for i := 0; i < b.N; i++ {
            v = f(maxInt64)
        }
        assert.Equal(b, v, "7fffffffffffffff")
    })
}

in where f is the function to be evaluated.

Running the benchmark

To run the benchmark of different algorithms, we run our benchmark implementations with following command to have more consistent results and less noise.

1
go test -bench=. -count 10 -run=^# -benchtime=10s

strconv.FormatInt performance

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
BenchmarkFormat/method-12  145798183  42.94 ns/op  23.29 MB/s  16 B/op  1 allocs/op
BenchmarkFormat/method-12  149771547  39.91 ns/op  25.05 MB/s  16 B/op  1 allocs/op
BenchmarkFormat/method-12  147820340  40.39 ns/op  24.76 MB/s  16 B/op  1 allocs/op
BenchmarkFormat/method-12  148916902  40.31 ns/op  24.81 MB/s  16 B/op  1 allocs/op
BenchmarkFormat/method-12  147492764  40.28 ns/op  24.83 MB/s  16 B/op  1 allocs/op
BenchmarkFormat/method-12  148211959  40.15 ns/op  24.91 MB/s  16 B/op  1 allocs/op
BenchmarkFormat/method-12  147424143  40.92 ns/op  24.44 MB/s  16 B/op  1 allocs/op
BenchmarkFormat/method-12  149000188  40.93 ns/op  24.43 MB/s  16 B/op  1 allocs/op
BenchmarkFormat/method-12  150341578  40.25 ns/op  24.84 MB/s  16 B/op  1 allocs/op
BenchmarkFormat/method-12  148663681  40.20 ns/op  24.88 MB/s  16 B/op  1 allocs/op

fmt.Sprintf performance

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
BenchmarkFormat/method-12  54556720  103.5 ns/op  9.66 MB/s  24 B/op  2 allocs/op
BenchmarkFormat/method-12  50335326  103.5 ns/op  9.66 MB/s  24 B/op  2 allocs/op
BenchmarkFormat/method-12  57254042  103.3 ns/op  9.68 MB/s  24 B/op  2 allocs/op
BenchmarkFormat/method-12  56824764  103.3 ns/op  9.68 MB/s  24 B/op  2 allocs/op
BenchmarkFormat/method-12  57379758  103.2 ns/op  9.69 MB/s  24 B/op  2 allocs/op
BenchmarkFormat/method-12  48998893  103.7 ns/op  9.64 MB/s  24 B/op  2 allocs/op
BenchmarkFormat/method-12  57366576  103.8 ns/op  9.63 MB/s  24 B/op  2 allocs/op
BenchmarkFormat/method-12  56660234  103.1 ns/op  9.70 MB/s  24 B/op  2 allocs/op
BenchmarkFormat/method-12  57384453  103.4 ns/op  9.67 MB/s  24 B/op  2 allocs/op
BenchmarkFormat/method-12  57449592  103.6 ns/op  9.65 MB/s  24 B/op  2 allocs/op

Github sample performance

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
BenchmarkFormat/method-12  2276696  2637 ns/op  0.38 MB/s  704 B/op  60 allocs/op
BenchmarkFormat/method-12  2268352  2637 ns/op  0.38 MB/s  704 B/op  60 allocs/op
BenchmarkFormat/method-12  2284990  2653 ns/op  0.38 MB/s  704 B/op  60 allocs/op
BenchmarkFormat/method-12  2267804  2641 ns/op  0.38 MB/s  704 B/op  60 allocs/op
BenchmarkFormat/method-12  2266641  2645 ns/op  0.38 MB/s  704 B/op  60 allocs/op
BenchmarkFormat/method-12  2261485  2633 ns/op  0.38 MB/s  704 B/op  60 allocs/op
BenchmarkFormat/method-12  2259590  2651 ns/op  0.38 MB/s  704 B/op  60 allocs/op
BenchmarkFormat/method-12  2256315  2632 ns/op  0.38 MB/s  704 B/op  60 allocs/op
BenchmarkFormat/method-12  2254988  2646 ns/op  0.38 MB/s  704 B/op  60 allocs/op
BenchmarkFormat/method-12  2273128  2640 ns/op  0.38 MB/s  704 B/op  60 allocs/op

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
func FormatDst(dst *HexWrap, n uint64) Hex {
    if n == 0 {
        return Hex("0")
    }
    var idx uint8 = 16
    // we are assuming 'dst' wont be never nil
    _ = dst[15]
    for q := n; q > 0; q >>= 4 {
        m := q % 16
        dst[idx-1] = uint8(48 + m)
        if m > 9 {
            dst[idx-1] += 7
        }
        idx--
    }
    return dst[idx:]
}

Performance evaluation

As earlier, we run same go test benchmarking command and collect the results. In my case, resuls are shown below.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
BenchmarkFormat/method-12  400862162  14.98 ns/op  66.76 MB/s  0 B/op  0 allocs/op
BenchmarkFormat/method-12  401325345  15.05 ns/op  66.47 MB/s  0 B/op  0 allocs/op
BenchmarkFormat/method-12  401947982  14.90 ns/op  67.11 MB/s  0 B/op  0 allocs/op
BenchmarkFormat/method-12  395986663  14.91 ns/op  67.09 MB/s  0 B/op  0 allocs/op
BenchmarkFormat/method-12  400444760  14.98 ns/op  66.75 MB/s  0 B/op  0 allocs/op
BenchmarkFormat/method-12  400612969  14.93 ns/op  67.00 MB/s  0 B/op  0 allocs/op
BenchmarkFormat/method-12  402221857  14.90 ns/op  67.12 MB/s  0 B/op  0 allocs/op
BenchmarkFormat/method-12  399473108  14.99 ns/op  66.70 MB/s  0 B/op  0 allocs/op
BenchmarkFormat/method-12  401921162  14.94 ns/op  66.93 MB/s  0 B/op  0 allocs/op
BenchmarkFormat/method-12  393383830  14.99 ns/op  66.72 MB/s  0 B/op  0 allocs/op

Final score

Finally, we can compare the improvement with benchstat utility and we get

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
benchstat fmt.txt ours.txt
name              old time/op    new time/op     delta
Format/method-12     103ns ± 0%       15ns ± 1%   -85.54%  (p=0.000 n=10+10)

name              old speed      new speed       delta
Format/method-12  9.67MB/s ± 0%  66.86MB/s ± 1%  +591.75%  (p=0.000 n=10+10)

name              old alloc/op   new alloc/op    delta
Format/method-12     24.0B ± 0%       0.0B       -100.00%  (p=0.000 n=10+10)

name              old allocs/op  new allocs/op   delta
Format/method-12      2.00 ± 0%       0.00       -100.00%  (p=0.000 n=10+10)

benchstat formatint.txt ours2.txt 
name              old time/op    new time/op    delta
Format/method-12    40.4ns ± 1%    15.0ns ± 1%   -62.95%  (p=0.000 n=9+10)

name              old speed      new speed      delta
Format/method-12  24.8MB/s ± 1%  66.9MB/s ± 1%  +169.92%  (p=0.000 n=9+10)

name              old alloc/op   new alloc/op   delta
Format/method-12     16.0B ± 0%      0.0B       -100.00%  (p=0.000 n=10+10)

name              old allocs/op  new allocs/op  delta
Format/method-12      1.00 ± 0%      0.00       -100.00%  (p=0.000 n=10+10)

benchstat github1.txt ours2.txt 
name              old time/op    new time/op     delta
Format/method-12    2.64µs ± 0%     0.01µs ± 1%     -99.43%  (p=0.000 n=10+10)

name              old speed      new speed       delta
Format/method-12   380kB/s ± 0%  66865kB/s ± 1%  +17496.05%  (p=0.000 n=10+10)

name              old alloc/op   new alloc/op    delta
Format/method-12      704B ± 0%         0B         -100.00%  (p=0.000 n=10+10)

name              old allocs/op  new allocs/op   delta
Format/method-12      60.0 ± 0%        0.0         -100.00%  (p=0.000 n=10+10)

Use cases

After reading all this you might be wondering…why?

Well, the first reason is obvious, better coding, better performance, less resources, and hence, less billing on cloud services.

Seconds, because now, I can efficiently convert the EVM PC instruction pointer from decimal to hexadecimal format, as seen in Converting EVM bytecode to OPCODES in microseconds

1
2
-> 0x00AA PUSH1 0x40
-> 0x00AA this is the instruction pointer of EVM

If wanted, you can use this library too. It is published at https://github.com/zerjioang/dec2hex

Conclusion

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!



💬 Share this post in social media

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.

Please, don't try to hack this website servers. Guess why...