Faster UUID Generation

[lbloder]

Description

Problem Statement

UUID Strings are used heavily in our SDK and lead to a significant performance impact as reported by some of our users (e.g. #3325).

After some investigation, likely causes are:

• Slow UUID.toString on Java 8 and below
• String replacement to generate a SentryId from a UUID string (.replace("-", ""))

Solution proposal

In addition to making the calls to UUID generation lazy (#3770) the actual generation of the UUID String performance should be improved by:

• Using java.util.Random instead of java.util.SecureRandom as we do not need to generate unguessable UUIDs (Random has been vendored into our SDK in [QA] Replace SecureRandom with vendored Random #3783.
• Use a different method to get rid of - in the UUIDs as .replace uses regex under the hood which also impacts performance

[lbloder]

Here are some preliminary results of my jmh benchmarks comparing the proposed changes with our current implementation:
All Tests are run with 5 clean starts with 5 warmup runs and 5 actual benchmarking runs resulting in 25 benchmark runs per test. Each benchmark is run for 10 seconds and records the throughput achieved during its runtime. The benchmark class can be found here. A first implementation of the proposed SentryUUID class can be found here. Its implementation is based on https://github.com/jchambers/fast-uuid.

Tests run on Java 17 (17.0.4.1 Temurin):

Comparison for just generating the UUID (not toString or - replacement happening):

Benchmark	Score		Error		Comparison
uuidGenerationSecureRandom (<= SDK v7)	2958082,937	±	16076,702	ops/s	100%
uuidGenerationRandom	14315530,295	±	74509,728	ops/s	484%

Converting a UUID to a String:

Benchmark	Score		Error		Comparison
uuidToString (<= SDK v7)	22903068,021	±	104850,277	ops/s

Comparison of ways to replace - in UUIDs (NOTE: FastUUID is generated without - directly and can skip this part):

Benchmark	Score		Error		Comparison
uuidPreparedStringReplace (<= SDK v7)	10889987,830	±	41280,613	ops/s	100%
uuidPreparedStringSubstring	19594602,425	±	230040,384	ops/s	180%

Comparison of converting a UUID to a String without -:

Benchmark	Score		Error		Comparison
uuidToStringAndReplace (<= SDK v7)	9214250,287	±	28206,966	ops/s	100%
uuidToStringAndStringBuilder	13732133,694	±	111230,880	ops/s	149%
uuidToSentryStringFastUUIDString	17356023,448	±	61010,884	ops/s	188%

Comparison of UUID generation plus converting it to a String without -:

Benchmark	Score		Error		Comparison
generateSentryIdSecureRandomToStringAndReplace (<= SDK v7)	2390892,390	±	13769,640	ops/s	100%
generateSentryIdSecureRandomToStringAndStringBuilder	2658536,980	±	13212,528	ops/s	111%
generateSentryIdSecureRandomFastUUIDString	2708014,673	±	18748,408	ops/s	113%
generateSentryIdRandomToStringAndReplace	6853990,548	±	30687,920	ops/s	287%
generateSentryIdRandomToStringAndStringBuilder	9389187,984	±	64342,057	ops/s	393%
generateSentryIdRandomFastUUIDString	10189370,117	±	42963,733	ops/s	426%

Tests run on Java 8:

Comparison for just generating the UUID (not toString or - replacement happening):

Benchmark	Score		Error		Comparison
uuidGenerationSecureRandom (<= SDK v7)	2798558,536	±	10401,878	ops/s	100%
uuidGenerationRandom	14127426,777	±	107914,586	ops/s	505%

Converting a UUID to a String Java 8 vs Java 17:

Benchmark	Score		Error		Comparison
uuidToString Java 8	3756860,393	±	12347,378	ops/s	100%
uuidToString Java 17	22903068,021	±	104850,277	ops/s	610%

Comparison of ways to replace - in UUIDs (NOTE: FastUUID is generated without - directly and can skip this part):

Benchmark	Score		Error		Comparison
uuidPreparedStringReplace (<= SDK v7)	2309449,560	±	7339,713	ops/s	100%
uuidPreparedStringSubstring	17567251,108	±	114376,548	ops/s	761%

Comparison of converting a UUID to a String without -:

Benchmark	Score		Error		Comparison
uuidToStringAndReplace (<= SDK v7)	1491372,618	±	60012,322	ops/s	100%
uuidToStringAndStringBuilder	3420986,460	±	24314,575	ops/s	229%
uuidToSentryStringFastUUIDString	18273547,083	±	164205,482	ops/s	1225%

Comparison of UUID generation plus converting it to a String without -:

Benchmark	Score		Error		Comparison
generateSentryIdSecureRandomToStringAndReplace (<= SDK v7)	986224,878	±	26426,142	ops/s	100%
generateSentryIdSecureRandomToStringAndStringBuilder	1605931,929	±	6780,269	ops/s	163%
generateSentryIdSecureRandomFastUUIDString	2599137,682	±	19991,940	ops/s	264%
generateSentryIdRandomToStringAndReplace	1391606,362	±	32904,345	ops/s	141%
generateSentryIdRandomToStringAndStringBuilder	3103154,423	±	12117,697	ops/s	315%
generateSentryIdRandomFastUUIDString	10406705,970	±	76049,067	ops/s	1055%

Discussion

So, depending on the underlying Java Version used, the proposed changes speed up id generation by x4 (Java 17) to x10 (Java 8).

Java 8 seems to have a much slower implementation of UUID.toString as well as String.replace which explain the big difference ein performance gains vs Java 17.

Both Java versions tested benefit from moving from SecureRandom to Random and getting rid of the String replacement step. This should, in theory, also reduce memory pressure when creating lots of spans and/or events as less Strings need to be allocated.

[lbloder]

Also did a simple comparison for memory allocation by creating 100k UUID Strings.

Java 17

UUID.randomUUID().toString().replace("-", "");

SentryUUID.toSentryIdString(SentryUUID.randomUUID());

Java 8

UUID.randomUUID().toString().replace("-", "");

SentryUUID.toSentryIdString(SentryUUID.randomUUID());

Discussion

Again, we are seeing significant improvements when using the proposed change. Especially in Java 8.

[adinauer]

We have just released 8.0.0-beta.2 of the Java SDK, which improves ID generation.