uuid: performance (random generators, allocations, etc)

[rabbbit]

Proposal Details

Ref #62026 (not sure how to make this a sub-issue).

Apologies for being late or perhaps missing the earlier discussion. I didn't findmentions of "performance", "io.Reader", "efficiency", "cost", as well as the API mentioned below in #62026.

We have recently (over the last few weeks) run a performance analysis of uuid at my workplace, and we found that UUIDs can be surprisingly expensive. We mostly use gofrs and google versions. In particular:

New()

Around 25% of the cost was attributed to New UUID, or rather random data generation.

This is mitigatable in both packages we use:

• Google offers pooled rand - https://pkg.go.dev/github.com/google/uuid#EnableRandPool, which deliveres 8x win out of the box.
• gofrs supports https://pkg.go.dev/github.com/gofrs/uuid/v5#WithRandomReader, and with their DefaultGenerator we're able to override this globally.

Copying from local benchmarks as an indication

BenchmarkNewV4/Gofrs_NewV4-48                    1323788               902.5 ns/op            16 B/op          1 allocs/op
BenchmarkNewV4/Google_NewRandom-48               1307914               918.3 ns/op            16 B/op          1 allocs/op
BenchmarkNewV4/Google_NewRandom_WithPool-48     10306299               115.6 ns/op             0 B/op          0 allocs/op
BenchmarkNewV4/Pborman_NewRandom-48              1273472               937.6 ns/op            16 B/op          1 allocs/op

We also tested this briefly with

BenchmarkUUIDPooledGeneration/CryptoRand-48                     32500659                36.99 ns/op            0 B/op         0 allocs/op
BenchmarkUUIDPooledGeneration/MathRandChaCha8-48                82932555                13.41 ns/op 

We also planned to experiment with thread-local random generator, but we didn't get to it yet.

Which brings questions:

• Is the performance benefit worth complicating the stdlib version?
• Does the API take a stance on new uuid generation (is it guaranteed to be "secure"), or is pooling allowed? Should this be specified?

parsing invalid uuid

Could the new Parse() API guarantee no allocations? This was surprisingly impactful.

This was recently improved in gofrs/uuid#241

Antipatterns - Unnecessary strings

We see quite a lot of uuid1.String() == uuid2.String(), including in loops, as well as myMap[uuid.String()] = user.

I'm not sure what's the best place to catch these today (go vet? gopls?) but could the proposal be extended to support catching obvious problems like the first one, or would that be a separate proposal?

[mateusz834]

New does not have to allocate any memory, since the random source is not configurable.
Also in case of Parse errors it seems possible not to cause allocs and only return a sentinel (global) error.

[mateusz834]

We also planned to experiment with thread-local random generator, but we didn't get to it yet.

Maybe we could use the same internal per-process chacha8 source from runtime, but not sure whether this is a good idea, instead of using the system randomness, especially considering the support of getrandom vdso on linux.

go/src/runtime/rand.go

Lines 153 to 180 in b7db570

	// rand returns a random uint64 from the per-m chacha8 state.
	// This is called from compiler-generated code.
	//
	// Do not change signature: used via linkname from other packages.
	//
	//go:nosplit
	//go:linkname rand
	func rand() uint64 {
	// Note: We avoid acquirem here so that in the fast path
	// there is just a getg, an inlined c.Next, and a return.
	// The performance difference on a 16-core AMD is
	// 3.7ns/call this way versus 4.3ns/call with acquirem (+16%).
	mp := getg().m
	c := &mp.chacha8
	for {
	// Note: c.Next is marked nosplit,
	// so we don't need to use mp.locks
	// on the fast path, which is that the
	// first attempt succeeds.
	x, ok := c.Next()
	if ok {
	return x
	}
	mp.locks++ // hold m even though c.Refill may do stack split checks
	c.Refill()
	mp.locks--
	}
	}

[gabyhelp]

Related Issues

• proposal: crypto/rand: add UUIDv4 and UUIDv7 #76319 (closed)
• uuid: add API to generate and parse UUID #62026
• proposal: add uuid generator to stdlib #23789 (closed)

_{(Emoji vote if this was helpful or unhelpful; more detailed feedback welcome in this discussion.)}

[seankhliao]

I think you should just help review CL 725602.

[neild]

(I won’t have a chance to respond for a bit, but this is worthy of more of a response.)

[neild]

Generation performance

The accepted proposal includes this statement:

// Random components of new UUIDs are generated with a
// cryptographically secure random number generator.

So we guarantee (essentially) that the package will use crypto/rand. This is currently quite a bit slower than math/rand on most platforms; on my laptop, generating a UUIDv4 with crypto/rand as the randomness source is ~170ns vs. ~9s using math/rand/v2.

I think generating UUIDs with a non-secure random source is out of scope for this package. Most users will be fine with the current, naive implementation which just reads the needed number of bytes from crypto/rand.Read.

The google/uuid package optionally batches calls to crypto/rand.Read (uuid.EnablePooledRand). The documentation claims "since the pool is stored on the Go heap, this feature may be a bad fit for security sensitive applications", but I have to say I don't understand the threat model here. (An attacker with access to read the process memory space can predict which UUIDs will be generated?) This seems like an optimization that we could just put into the uuid package.

However, if we need better performance for generating small numbers of secure bytes, perhaps we should be looking at just making crypto/rand faster.

Parsing

Parsing in the current implementation makes no allocations.

An interesting question is whether parse errors should return the string which failed to parse. This will cause allocations on error returns, since we need to allocate an error and may need to copy the input string. The current implementation does not return an error that contains the input, but most standard library parse functions (e.g., in strconv) do. This is worth thinking about.