Performance comparison of various base62 encoder techniques in Go

b62.go

package main

import (
	"fmt"
	"math"
	"reflect"
	"runtime"
	"sort"
	"time"
)

// (62^i)-1 | i = 1..11
var limits = [...]uint64{61, 3843, 238327, 14776335, 916132831, 56800235583, 3521614606207, 218340105584895, 13537086546263551, 839299365868340199, math.MaxUint64}

const abc = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789"

type b62encoder func(uint64) string

func b62Encode1(n uint64) string {
	const Log62 = 4.127134385045091555346396446
	l := 1
	if n > 0 {
		l = 1 + int(math.Log(float64(n))/Log62)
	}
	result := make([]byte, l)
	for i := l - 1; i >= 0; i-- {
		result[i] = abc[n%62]
		n = n / 62
	}
	return string(result)
}

func b62Encode2(n uint64) string {
	var l int
	var v uint64
	for l, v = range limits {
		if n <= v {
			break
		}
	}
	result := make([]byte, l+1)
	for i := l; i >= 0; i-- {
		result[i] = abc[n%62]
		n = n / 62
	}
	return string(result)
}

func b62Encode3(n uint64) string {
	l := sort.Search(len(limits), func(i int) bool { return limits[i] > n })
	result := make([]byte, l+1)
	for i := l; i >= 0; i-- {
		result[i] = abc[n%62]
		n = n / 62
	}
	return string(result)
}

func b62Encode4(n uint64) string {
	lo, hi := 0, len(limits)-1
	for lo <= hi {
		m := (lo + hi) / 2
		if limits[m] <= n {
			lo = m + 1
		} else {
			hi = m - 1
		}
	}
	result := make([]byte, lo+1)
	for i := lo; i >= 0; i-- {
		result[i] = abc[n%62]
		n = n / 62
	}
	return string(result)
}

func b62Encode5(n uint64) string {
	result := make([]byte, 0)
	for {
		result = append([]byte{abc[n%62]}, result...)
		n = n / 62
		if n == 0 {
			break
		}
	}
	return string(result)
}

func b62Encode6(n uint64) string {
	result := make([]byte, 11)
	i := 10
	for {
		result[i] = abc[n%62]
		n = n / 62
		if n == 0 {
			break
		}
		i--
	}
	return string(result[i:])
}

func b62Decode(a string) (uint64, error) {
	if len(a) == 0 {
		return 0, fmt.Errorf("base62 string must not be empty")
	}
	var v uint64
	for i := 0; i < len(a); i++ {
		c := int(a[i])
		p := 0
		switch {
		case int('a') <= c && c <= int('z'):
			p = c - int('a')
		case int('A') <= c && c <= int('Z'):
			p = c - int('A') + 26
		case int('0') <= c && c <= int('9'):
			p = c - int('0') + 52
		default:
			return 0, fmt.Errorf("invalid base62 symbol: '%c'", a[i])
		}
		v *= 62
		v += uint64(p)
	}
	return v, nil
}

func test(fn b62encoder) bool {
	const N uint64 = 1000000
	fmt.Printf("\n***%v\n", runtime.FuncForPC(reflect.ValueOf(fn).Pointer()).Name())
	startValues := make([]uint64, 0)
	for v := 0; v < 12; v++ {
		startValues = append(startValues, uint64(math.Pow(62, float64(v)))-1, uint64(math.Pow(62, float64(v))))
	}
	startValues = append(startValues, math.MaxUint64/32, math.MaxUint64/16, math.MaxUint64/8, math.MaxUint64/4, math.MaxUint64/2, math.MaxUint64-N-1)
	nPassed := 0
	passed := true
	for _, a := range startValues {
		fmt.Printf("Starting from %25d ...", a)
		t0 := time.Now()
		for i := a; i < N+a; i++ {
			b62 := fn(i)
			r, err := b62Decode(b62)
			if r != i || err != nil {
				fmt.Printf("ERROR: %v != %v (%v) (%v)", r, i, b62, b62Encode6(i))
				passed = false
				break
			}
		}
		if passed {
			nPassed++
		}
		fmt.Printf(" %v\n", time.Since(t0))
	}
	return nPassed == len(startValues)
}

func main() {
	tests := [...]b62encoder{b62Encode1, b62Encode2, b62Encode3, b62Encode4, b62Encode5, b62Encode6}
	nPassed := 0
	for _, t := range tests {
		if test(t) {
			fmt.Println("PASSED.")
			nPassed++
		} else {
			fmt.Println("FAILED.")
		}
	}
	fmt.Println()
	if nPassed == len(tests) {
		fmt.Println("ALL TESTS PASSED.")
	} else {
		fmt.Println("%d OF %d TESTS FAILED.", len(tests)-nPassed, len(tests))
	}
}

results on iMac (Retina 5K, 27-inch, Late 2015), 3,2 GHz Intel Core i5:

***main.b62Encode1
Starting from                    0 ... 76.80953ms
Starting from                 3843 ... 75.305622ms
Starting from             14776336 ... 79.205526ms
Starting from            916132832 ... 85.435636ms
Starting from          56800235584 ... 87.047344ms
Starting from        3521614606208 ... 89.172259ms
Starting from      218340105584896 ... 98.338359ms
Starting from    13537086546263552 ... 105.4439ms
Starting from   839299365868340200 ... 104.379733ms
Starting from  4611686018427387903 ... 105.541866ms
Starting from  9223372036854775807 ... 109.477682ms
Starting from 18446744073708551615 ... 110.756922ms
PASSED.

***main.b62Encode2
Starting from                    0 ... 47.105133ms
Starting from                 3843 ... 47.059043ms
Starting from             14776336 ... 51.543959ms
Starting from            916132832 ... 56.388687ms
Starting from          56800235584 ... 58.531553ms
Starting from        3521614606208 ... 61.215698ms
Starting from      218340105584896 ... 71.114184ms
Starting from    13537086546263552 ... 75.034375ms
Starting from   839299365868340200 ... 77.628942ms
Starting from  4611686018427387903 ... 82.086609ms
Starting from  9223372036854775807 ... 81.967777ms
Starting from 18446744073708551615 ... 78.466384ms
PASSED.

***main.b62Encode3
Starting from                    0 ... 56.862113ms
Starting from                 3843 ... 56.563899ms
Starting from             14776336 ... 64.492549ms
Starting from            916132832 ... 66.214648ms
Starting from          56800235584 ... 72.204317ms
Starting from        3521614606208 ... 75.073796ms
Starting from      218340105584896 ... 85.435767ms
Starting from    13537086546263552 ... 92.156562ms
Starting from   839299365868340200 ... 97.371184ms
Starting from  4611686018427387903 ... 97.853327ms
Starting from  9223372036854775807 ... 97.536706ms
Starting from 18446744073708551615 ... 97.190639ms
PASSED.

***main.b62Encode4
Starting from                    0 ... 45.555972ms
Starting from                 3843 ... 45.779771ms
Starting from             14776336 ... 52.21584ms
Starting from            916132832 ... 56.310418ms
Starting from          56800235584 ... 56.501235ms
Starting from        3521614606208 ... 59.756093ms
Starting from      218340105584896 ... 70.212201ms
Starting from    13537086546263552 ... 71.901454ms
Starting from   839299365868340200 ... 75.824486ms
Starting from  4611686018427387903 ... 76.806413ms
Starting from  9223372036854775807 ... 75.297612ms
Starting from 18446744073708551615 ... 75.923931ms
PASSED.

***main.b62Encode5
Starting from                    0 ... 141.222642ms
Starting from                 3843 ... 141.575011ms
Starting from             14776336 ... 192.844252ms
Starting from            916132832 ... 228.268212ms
Starting from          56800235584 ... 276.388178ms
Starting from        3521614606208 ... 322.981137ms
Starting from      218340105584896 ... 354.248697ms
Starting from    13537086546263552 ... 397.27327ms
Starting from   839299365868340200 ... 435.955213ms
Starting from  4611686018427387903 ... 432.863876ms
Starting from  9223372036854775807 ... 434.176335ms
Starting from 18446744073708551615 ... 434.691165ms
PASSED.

***main.b62Encode6
Starting from                    0 ... 31.515409ms
Starting from                 3843 ... 29.939257ms
Starting from             14776336 ... 32.123169ms
Starting from            916132832 ... 34.487676ms
Starting from          56800235584 ... 37.678908ms
Starting from        3521614606208 ... 39.337093ms
Starting from      218340105584896 ... 46.336886ms
Starting from    13537086546263552 ... 47.30094ms
Starting from   839299365868340200 ... 49.999747ms
Starting from  4611686018427387903 ... 51.950922ms
Starting from  9223372036854775807 ... 51.805403ms
Starting from 18446744073708551615 ... 50.529426ms
PASSED.

results on iMac (27-inch, Mid 2011), 2,7 GHz Intel Core i5

***main.b62Encode1
Starting from                         0 ... 96.893369ms
Starting from                         1 ... 95.036671ms
Starting from                        61 ... 91.887143ms
Starting from                        62 ... 93.275593ms
Starting from                      3843 ... 94.945998ms
Starting from                      3844 ... 93.168139ms
Starting from                    238327 ... 93.560604ms
Starting from                    238328 ... 92.763351ms
Starting from                  14776335 ... 98.986055ms
Starting from                  14776336 ... 105.620174ms
Starting from                 916132831 ... 104.337817ms
Starting from                 916132832 ... 120.297851ms
Starting from               56800235583 ... 131.732775ms
Starting from               56800235584 ... 129.999121ms
Starting from             3521614606207 ... 121.894706ms
Starting from             3521614606208 ... 112.734937ms
Starting from           218340105584895 ... 141.858388ms
Starting from           218340105584896 ... 138.820845ms
Starting from         13537086546263551 ... 141.76977ms
Starting from         13537086546263552 ... 135.262998ms
Starting from        839299365868340223 ... 150.576824ms
Starting from        839299365868340224 ... 143.706217ms
Starting from       9223372036854775807 ... 133.820066ms
Starting from       9223372036854775808 ... 135.499959ms
Starting from        576460752303423487 ... 129.233574ms
Starting from       1152921504606846975 ... 132.321622ms
Starting from       2305843009213693951 ... 135.96954ms
Starting from       4611686018427387903 ... 131.592081ms
Starting from       9223372036854775807 ... 160.659302ms
Starting from      18446744073708551614 ... 138.636694ms
PASSED.

***main.b62Encode2
Starting from                         0 ... 62.558479ms
Starting from                         1 ... 63.105362ms
Starting from                        61 ... 62.00151ms
Starting from                        62 ... 63.274352ms
Starting from                      3843 ... 64.430899ms
Starting from                      3844 ... 64.631427ms
Starting from                    238327 ... 63.339465ms
Starting from                    238328 ... 62.91729ms
Starting from                  14776335 ... 69.557839ms
Starting from                  14776336 ... 69.537795ms
Starting from                 916132831 ... 80.084096ms
Starting from                 916132832 ... 79.173115ms
Starting from               56800235583 ... 82.763031ms
Starting from               56800235584 ... 81.544921ms
Starting from             3521614606207 ... 82.501715ms
Starting from             3521614606208 ... 83.692893ms
Starting from           218340105584895 ... 100.794766ms
Starting from           218340105584896 ... 100.541605ms
Starting from         13537086546263551 ... 105.857854ms
Starting from         13537086546263552 ... 105.388343ms
Starting from        839299365868340223 ... 108.625289ms
Starting from        839299365868340224 ... 109.9219ms
Starting from       9223372036854775807 ... 112.608176ms
Starting from       9223372036854775808 ... 115.328756ms
Starting from        576460752303423487 ... 105.836857ms
Starting from       1152921504606846975 ... 108.990835ms
Starting from       2305843009213693951 ... 111.320917ms
Starting from       4611686018427387903 ... 110.871939ms
Starting from       9223372036854775807 ... 112.519222ms
Starting from      18446744073708551614 ... 110.435684ms
PASSED.

***main.b62Encode3
Starting from                         0 ... 76.890485ms
Starting from                         1 ... 76.427225ms
Starting from                        61 ... 77.744073ms
Starting from                        62 ... 76.829587ms
Starting from                      3843 ... 75.600772ms
Starting from                      3844 ... 75.404603ms
Starting from                    238327 ... 79.868084ms
Starting from                    238328 ... 78.177445ms
Starting from                  14776335 ... 85.167944ms
Starting from                  14776336 ... 85.346287ms
Starting from                 916132831 ... 89.513521ms
Starting from                 916132832 ... 88.009558ms
Starting from               56800235583 ... 96.639191ms
Starting from               56800235584 ... 98.142092ms
Starting from             3521614606207 ... 101.693157ms
Starting from             3521614606208 ... 102.342378ms
Starting from           218340105584895 ... 114.584559ms
Starting from           218340105584896 ... 117.6759ms
Starting from         13537086546263551 ... 124.404997ms
Starting from         13537086546263552 ... 124.298837ms
Starting from        839299365868340223 ... 129.635581ms
Starting from        839299365868340224 ... 131.69402ms
Starting from       9223372036854775807 ... 132.165246ms
Starting from       9223372036854775808 ... 131.89274ms
Starting from        576460752303423487 ... 125.648566ms
Starting from       1152921504606846975 ... 131.958671ms
Starting from       2305843009213693951 ... 130.895026ms
Starting from       4611686018427387903 ... 131.389677ms
Starting from       9223372036854775807 ... 134.26721ms
Starting from      18446744073708551614 ... 136.01488ms
PASSED.

***main.b62Encode4
Starting from                         0 ... 61.161928ms
Starting from                         1 ... 61.146284ms
Starting from                        61 ... 59.194954ms
Starting from                        62 ... 62.063606ms
Starting from                      3843 ... 60.577233ms
Starting from                      3844 ... 60.879463ms
Starting from                    238327 ... 61.71699ms
Starting from                    238328 ... 60.897385ms
Starting from                  14776335 ... 68.188286ms
Starting from                  14776336 ... 66.224461ms
Starting from                 916132831 ... 74.134003ms
Starting from                 916132832 ... 76.693181ms
Starting from               56800235583 ... 74.019857ms
Starting from               56800235584 ... 76.329336ms
Starting from             3521614606207 ... 79.99038ms
Starting from             3521614606208 ... 80.723541ms
Starting from           218340105584895 ... 96.501998ms
Starting from           218340105584896 ... 96.04163ms
Starting from         13537086546263551 ... 98.450139ms
Starting from         13537086546263552 ... 97.648309ms
Starting from        839299365868340223 ... 99.769619ms
Starting from        839299365868340224 ... 101.594853ms
Starting from       9223372036854775807 ... 101.892875ms
Starting from       9223372036854775808 ... 102.706065ms
Starting from        576460752303423487 ... 96.27508ms
Starting from       1152921504606846975 ... 102.359755ms
Starting from       2305843009213693951 ... 104.116262ms
Starting from       4611686018427387903 ... 101.321722ms
Starting from       9223372036854775807 ... 102.973425ms
Starting from      18446744073708551614 ... 101.762993ms
PASSED.

***main.b62Encode5
Starting from                         0 ... 192.241233ms
Starting from                         1 ... 198.348548ms
Starting from                        61 ... 195.739122ms
Starting from                        62 ... 195.53803ms
Starting from                      3843 ... 195.836476ms
Starting from                      3844 ... 193.24429ms
Starting from                    238327 ... 211.04581ms
Starting from                    238328 ... 214.81166ms
Starting from                  14776335 ... 277.80321ms
Starting from                  14776336 ... 269.421008ms
Starting from                 916132831 ... 335.4605ms
Starting from                 916132832 ... 340.974002ms
Starting from               56800235583 ... 409.275862ms
Starting from               56800235584 ... 437.480029ms
Starting from             3521614606207 ... 511.954351ms
Starting from             3521614606208 ... 483.1728ms
Starting from           218340105584895 ... 523.84368ms
Starting from           218340105584896 ... 517.250989ms
Starting from         13537086546263551 ... 546.662379ms
Starting from         13537086546263552 ... 574.005079ms
Starting from        839299365868340223 ... 644.395893ms
Starting from        839299365868340224 ... 624.082572ms
Starting from       9223372036854775807 ... 638.924163ms
Starting from       9223372036854775808 ... 628.63822ms
Starting from        576460752303423487 ... 602.60671ms
Starting from       1152921504606846975 ... 639.698271ms
Starting from       2305843009213693951 ... 622.305627ms
Starting from       4611686018427387903 ... 617.75024ms
Starting from       9223372036854775807 ... 650.857004ms
Starting from      18446744073708551614 ... 620.455071ms
PASSED.

***main.b62Encode6
Starting from                         0 ... 41.154835ms
Starting from                         1 ... 41.253938ms
Starting from                        61 ... 42.223955ms
Starting from                        62 ... 41.22228ms
Starting from                      3843 ... 43.121477ms
Starting from                      3844 ... 41.774318ms
Starting from                    238327 ... 44.123868ms
Starting from                    238328 ... 44.347157ms
Starting from                  14776335 ... 46.43934ms
Starting from                  14776336 ... 47.103212ms
Starting from                 916132831 ... 51.652239ms
Starting from                 916132832 ... 54.465507ms
Starting from               56800235583 ... 52.69759ms
Starting from               56800235584 ... 52.347966ms
Starting from             3521614606207 ... 57.784937ms
Starting from             3521614606208 ... 55.216814ms
Starting from           218340105584895 ... 66.28819ms
Starting from           218340105584896 ... 65.322688ms
Starting from         13537086546263551 ... 68.022662ms
Starting from         13537086546263552 ... 68.82593ms
Starting from        839299365868340223 ... 72.64384ms
Starting from        839299365868340224 ... 71.608233ms
Starting from       9223372036854775807 ... 72.986644ms
Starting from       9223372036854775808 ... 73.848592ms
Starting from        576460752303423487 ... 71.850713ms
Starting from       1152921504606846975 ... 73.745715ms
Starting from       2305843009213693951 ... 72.216667ms
Starting from       4611686018427387903 ... 72.849287ms
Starting from       9223372036854775807 ... 73.017454ms
Starting from      18446744073708551614 ... 73.575404ms
PASSED.

ALL TESTS PASSED.