Efficient way to to generate a random Hex string of a fixed length in Golang?

Question

I need to generate a lot of a random hex string of a fixed length. I find this solution How to generate a random string of a fixed length in golang?

I'm doing something like this:

const letterBytes = "abcdef0123456789"
const (
    letterIdxBits = 6                    // 6 bits to represent a letter index
    letterIdxMask = 1<<letterIdxBits - 1 // All 1-bits, as many as letterIdxBits
    letterIdxMax  = 63 / letterIdxBits   // # of letter indices fitting in 63 bits
)

var src = rand.NewSource(time.Now().UnixNano())

// RandStringBytesMaskImprSrc ...
// Src: https://stackoverflow.com/a/31832326/710955
func RandStringBytesMaskImprSrc(n int) string {
    b := make([]byte, n)
    // A src.Int63() generates 63 random bits, enough for letterIdxMax characters!
    for i, cache, remain := n-1, src.Int63(), letterIdxMax; i >= 0; {
        if remain == 0 {
            cache, remain = src.Int63(), letterIdxMax
        }
        if idx := int(cache & letterIdxMask); idx < len(letterBytes) {
            b[i] = letterBytes[idx]
            i--
        }
        cache >>= letterIdxBits
        remain--
    }

    return string(b)
}

var tryArr = make([]string, 10000)
for i := 0; i < 10000; i++ {
    tryArr[i] = RandStringBytesMaskImprSrc(8)
}

But I got this panic error

panic: runtime error: index out of range

goroutine 36 [running]:
math/rand.(*rngSource).Int63(0x11bb1300, 0x8, 0x8)
    D:/Applications/Go/src/math/rand/rng.go:231 +0xa0
main.RandStringBytesMaskImprSrc(0x8, 0x11f81be8, 0x8)
    main.go:60 +0x5f

The errror seem to be in for i, cache, remain := n-1, src.Int63(), letterIdxMax; i >= 0;, but I don't find why there is this error.

What is the fastest and simplest way to generate a lot of a random hex string of a fixed length in Go?

Benchmark

package bench

import (
    "encoding/hex"
    "math/rand"
    "testing"
    "time"
)

const letterBytes = "abcdef0123456789"
const (
    letterIdxBits = 4                    // 4 bits to represent a letter index
    letterIdxMask = 1<<letterIdxBits - 1 // All 1-bits, as many as letterIdxBits
    letterIdxMax  = 63 / letterIdxBits   // # of letter indices fitting in 63 bits
)

var src1 = rand.NewSource(time.Now().UnixNano())
var src2 = rand.New(rand.NewSource(time.Now().UnixNano()))

// RandStringBytesMaskImprSrc returns a random hexadecimal string of length n.
func RandStringBytesMaskImprSrc1(n int) string {
    b := make([]byte, n)
    for i, cache, remain := n-1, src1.Int63(), letterIdxMax; i >= 0; {
        if remain == 0 {
            cache, remain = src1.Int63(), letterIdxMax
        }
        if idx := int(cache & letterIdxMask); idx < len(letterBytes) {
            b[i] = letterBytes[idx]
            i--
        }
        cache >>= letterIdxBits
        remain--
    }

    return string(b)
}

func RandStringBytesMaskImprSrc2(n int) string {
    b := make([]byte, (n+1)/2) // can be simplified to n/2 if n is always even

    if _, err := src2.Read(b); err != nil {
        panic(err)
    }

    return hex.EncodeToString(b)[:n]
}

func BenchmarkRandStringBytesMaskImprSrc1(b *testing.B) {
    for n := 0; n < b.N; n++ {
        _ = RandStringBytesMaskImprSrc1(8)
    }
}

func BenchmarkRandStringBytesMaskImprSrc2(b *testing.B) {
    for n := 0; n < b.N; n++ {
        _ = RandStringBytesMaskImprSrc2(8)
    }
}


goos: windows
goarch: 386
BenchmarkRandStringBytesMaskImprSrc1-4          20000000               116 ns/op              16 B/op          2 allocs/op
BenchmarkRandStringBytesMaskImprSrc2-4          10000000               231 ns/op              24 B/op          3 allocs/op
PASS
ok      command-line-arguments  5.139s

=> icza RandStringBytesMaskImprSrcsolution is more efficient

Peter · Accepted Answer · 2020-07-30 07:41:17Z

7

*math/rand.Rand is an io.Reader, so it is trivial to read N random bytes and then hexencode them:

package main

import (
    "encoding/hex"
    "fmt"
    "math/rand"
    "time"
)

var src = rand.New(rand.NewSource(time.Now().UnixNano()))

func main() {
    fmt.Println(RandStringBytesMaskImprSrc(4))
}

// RandStringBytesMaskImprSrc returns a random hexadecimal string of length n.
func RandStringBytesMaskImprSrc(n int) string {
    b := make([]byte, (n+1)/2) // can be simplified to n/2 if n is always even

    if _, err := src.Read(b); err != nil {
            panic(err)
    }

    return hex.EncodeToString(b)[:n]
}

edited Jul 30, 2020 at 7:41

answered Oct 24, 2017 at 11:49

Peter

32.1k6 gold badges57 silver badges68 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

LeMoussel Over a year ago

Dont' run ! Error: src.Read undefined (type rand.Source has no field or method Read) Go Playground

LeMoussel Over a year ago

solution is to replace rand.NewSource(time.Now().UnixNano()) by rand.New(rand.NewSource(time.Now().UnixNano()))

EB2127 Over a year ago

Also, this needs the library "time"

Community · Accepted Answer · 2020-06-20 09:12:55Z

3

Actually the code you posted runs, as even though there's a mistake in it (see below), it still doesn't cause a panic (just makes performance worse).

The stack trace you posted indicates error in the math/rand package, I did not experience it. Please post full code and Go version + env (go version and go env).

Reason for panic / Solution:

As it turns out, the asker was calling RandStringBytesMaskImprSrc() concurrently, from multiple goroutines. RandStringBytesMaskImprSrc() uses a shared rand.Source instance which is not safe for concurrent use, hence the panic from the math/rand package. Fix is to create a separate rand.Source() for each goroutines, and pass that to RandStringBytesMaskImprSrc().

There is a mistake in the "configuration" constants at the beginning:

const letterBytes = "abcdef0123456789"
const (
    letterIdxBits = 6                    // 6 bits to represent a letter index
    letterIdxMask = 1<<letterIdxBits - 1 // All 1-bits, as many as letterIdxBits
    letterIdxMax  = 63 / letterIdxBits   // # of letter indices fitting in 63 bits
)

The constant letterIdxBits should contain how many bits are required to represent a symbol index. Since you're using an alphabet of 16 elements (the length of letterBytes), 16 combinations require only 4 bits:

letterIdxBits = 4                    // 4 bits to represent a letter index

Example testing it:

var tryArr = make([]string, 10)
for i := range tryArr {
    tryArr[i] = RandStringBytesMaskImprSrc(8)
}
fmt.Println(tryArr)

Output (try it on the Go Playground):

[d3e7caa6 a69c9b7d c37a613b 92d5a43b 64059c4a 4f08141b 70130c65 1546daaf fe140fcd 0d714e4d]

(Note: since the starting time on the Go playground is fixed and output is cached, you will always see these random generated strings. Run it on your machine to see random results.)

edited Jun 20, 2020 at 9:12

CommunityBot

11 silver badge

answered Oct 24, 2017 at 7:32

icza

423k78 gold badges1k silver badges905 bronze badges

6 Comments

LeMoussel Over a year ago

I got same panic error with correction if I do var tryArr = make([]string, 100000). I use go version go1.8.3 windows/386. Rem No error on Go Playground, strange ....

icza Over a year ago

@LeMoussel As stated in the answer, the panic does not originate from the code you posted, but from the math/rand package. Maybe your installation is corrupted? Can you try it with Go 1.9.1?

LeMoussel Over a year ago

Same with Go v1.9.1. No error with RandStringBytesMaskImpr thant don't use rand.Source.

icza Over a year ago

@LeMoussel In that case I suggest to file a bug report, as this is definitely not normal: github.com/golang/go/issues

icza Over a year ago

@LeMoussel One last question: you don't call RandStringBytesMaskImprSrc() concurrently from multiple goroutines right? As the code uses a "shared" rand.Source which is not safe for concurrent use. If you need concurrent use, create a separate rand.Source for each goroutines.

|

Art · Accepted Answer · 2017-10-24 07:59:09Z

3

First, replace your rand source with a proper generator, with:

var rnd = rand.New(src)

Then just use a standard solutions to format numbers:

fmt.Sprintf("%x", rnd.Uint64())

alternatively;

strconv.FormatUint(rnd.Uint64(), 16)

Both those methods are faster than yours (after it has been bugfixed):

BenchmarkRandStringBytesMaskImprSrc-4       10000000           196 ns/op
BenchmarkFmt-4                              10000000           148 ns/op
BenchmarkStrconv-4                          20000000            89.8 ns/op

answered Oct 24, 2017 at 7:59

Art

20.5k1 gold badge40 silver badges66 bronze badges

2 Comments

LeMoussel Over a year ago

Does BenchmarkFm() is bench of fmt.Sprintf("%x", rnd.Uint64()) & BenchmarkStrconv() is bench of strconv.FormatUint(rnd.Uint64(), 16) Can you post benchmark code?

Art Over a year ago

@LeMoussel Standard benchmarks from the testing package.

Collectives™ on Stack Overflow

Efficient way to to generate a random Hex string of a fixed length in Golang?

3 Answers 3

3 Comments

Reason for panic / Solution:

6 Comments

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

3 Comments

Reason for panic / Solution:

6 Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related