„We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil. Yet we should not pass up our opportunities in that critical 3%.“
– Donald Knuth
In my 2021 post titled „Leitweg ID – Ihre Nummer für die Behörde“, I presented a Java implementation for an identifier that is rarely discussed outside the context of electronic invoicing. The task was straightforward: recognize a Leitweg-ID, extract its components, verify the checksum, and generate a correct text representation.
A regular expression handled the parsing, and BigInteger handled the checksum calculation. This was easy to follow and fit the purpose of the post. However, upon taking another look at the implementation, a different question arose: How much of the work is the computer actually doing that isn’t even necessary for the result?
The opening quote essentially says: We generally shouldn’t worry about small efficiency gains. Nevertheless, we should take advantage of the important opportunities. The quote comes from Knuth’s essay in Computing Surveys, Volume 6, Number 4, pages 261–301, Section 1. The second sentence in particular applies to this revision: First understand and measure, then improve in a targeted manner.
A short post with a surprising amount of additional material
The structure of the Leitweg-ID is the same as in the original post:
Coarse Addressing—Fine Addressing—Checksum
Fine-level addressing is optional. Coarse-level addressing consists of either a federal code with a platform identifier or a state code with optional, hierarchical administrative codes. For Bielefeld University, for example, this results in:
LeitwegId leitwegId = LeitwegId.parse("05711-06001-79");
GermanFederalState bundesland = leitwegId.getGrobAdressierung()
.asLandesAdressierung()
.orElseThrow()
.getBundesland();
I didn’t have to change anything in how I used the library for optimization. What was interesting was the logic behind this API. Version 1.3.3 created a matcher during parsing, extracted groups, built address objects from them, and generated the text representation of the coarse addressing again for the checksum verification. Next, letters were converted to numbers, the entire decimal representation was assembled, and a BigInteger instance was created from it.
The result of all this preparation was ultimately a remainder from division by 97. For a number between 0 and 96, that was a remarkably long journey.
The big number that I don’t need at all
The key improvement lies in the math, not in some special Java trick. If I only need the remainder of a decimal number modulo 97, I don’t need to store the entire number.
When appending a digit, this increment is sufficient:
remainder = (remainder * 10 + digit) % 97;
This is easy to understand using 123 as an example: First, the 1 is processed; then the 2 is appended; and finally, the 3. After each step, I can already reduce the intermediate value to its remainder. In the end, the modulo calculation yields the same remainder as dividing the entire number by 97.
In fine-tuning, letters are added. A and a stand for 10, B and b for 11, and so on up to Z and z for 35. Here, two decimal places are appended, so the factor 10 becomes a factor of 100:
if (c >= '0' && c <= '9') {
rest = (rest * 10 + c - '0') % 97;
} else if (c >= 'A' && c <= 'Z') {
rest = (rest * 100 + c - 'A' + 10) % 97;
} else if (c >= 'a' && c <= 'z') {
rest = (rest * 100 + c - 'a' + 10) % 97;
} else {
throw new IllegalArgumentException("invalid fine address");
}
The remainder is always less than 97. Even when appending the largest letter value, the intermediate value is at most 96 * 100 + 35, or 9635. An int is therefore more than sufficient, regardless of the length of the converted decimal representation.
To generate the checksum, the two placeholder digits 00 must be appended:
int checksum = 98 - (rest * 100) % 97; String result = checksum < 10 ? "0" + checksum : Integer.toString(checksum);
This eliminates the need for the decimal buffer, the character array created with toCharArray(), and the large integers from the production code. The calculation remains linear with respect to the input length, but requires less work per character and creates fewer temporary objects.
Validation and calculation share the workload
While making this change, I stumbled upon a second unnecessary repetition. Since the factory checks the fine-addressing for valid characters anyway, it might as well calculate the modulo remainder at the same time. This would eliminate the need for an additional pass when getChecksum() is first called.
Version 1.4.0 therefore stores the calculated remainder in the final field addressRemainder. The actual checksum string is still generated and cached only when needed.
This is a deliberate shift from the original approach. Anyone who creates just one instance now pays the cost of the format check and the updating of the remainder up front. In return, the input is checked immediately, and a subsequent checksum call does not have to read the address characters again. The benchmark for generation, including the checksum, already includes this additional validation.
A parser for exactly one format
I also replaced the regular expression. It had already been statically precompiled, so recompiling wasn’t the problem. The work involved matching, extracting the groups, and then reassembling the checksum input.
The format is small and clearly defined: a maximum of twelve digits in the coarse addressing, a maximum of thirty alphanumeric characters in the fine addressing, and exactly two checksum digits. A total of no more than 46 characters are possible. A direct parser can recognize this structure without a regular expression:
- Check the total length and the position of the checksum separator.
- Validate the coarse addressing up to the first hyphen.
- If present, check the length and characters of the fine addressing.
- Update the modulo remainder directly across the character ranges of the input.
- Check the appended checksum and only then generate the address objects.
The hyphens are part of the representation but are not included in the checksum calculation. The parser therefore processes the corresponding character ranges individually. The originally read text representation and checksum are already known and continue to be stored.
The trade-off for this change is more explicit validation code. A compact regular expression is replaced by visible conditions and index limits. That is why it was important to me to check not only successful examples but also the transitions between valid and invalid formats.
Sixteen federal states do not need a new stream
A minor improvement involves searching for a state code. The previous implementation was pleasantly brief:
return Stream.of(values()).filter(x -> id.equals(x.id)).findFirst();
values() returns a copy of the enum array each time it is called. On top of that, there’s the stream pipeline and a search through up to sixteen entries. The mapping itself, however, never changes.
That’s why I build it once when initializing the enum and then read from an immutable map:
return Optional.ofNullable(BY_ID.get(id));
The Optional remains part of the API. So the goal here is not to remove every abstraction, but to set up the immutable mapping once.
The text representations of the state address and federal address are also generated and stored once. The Leitweg-ID stores its coarse address as a string instead of requesting it again for checksums and output. This additional storage is a trade-off: it is particularly worthwhile for reused addresses, while a state address used only once still carries its cached representation.
Work Faster and Find Errors Sooner
The performance review also revealed error cases that had not previously been handled consistently. Unknown state codes could trigger a NoSuchElementException, while an incomplete federal address could trigger a NullPointerException. However, the Jackson module catches IllegalArgumentException to report invalid representations as mapping errors.
The parser now consistently throws an IllegalArgumentException for invalid representations and unknown codes. An incorrect checksum remains distinguishable from a format error due to the “invalid checksum” message.
The factories now also check the format. Previously, a detailed address with 31 characters could be generated, even though its text representation could not be parsed afterward. Now, such inputs are rejected immediately. For state-level addresses, the components must also match: a municipality requires a county, and a county requires an administrative district.
This is a change in behavior for invalid factory inputs, which I have documented in the README. For valid IDs, the format, letter handling, and checksum method remain unchanged.
Not only did we calculate it correctly, but we also tested it
After optimization, the old BigInteger approach still serves an important purpose: it acts as an independent reference in the test. For 20,000 deterministically generated valid IDs, the new checksum is compared with this reference. The generated IDs are then read in again, and their components are verified. In addition, the checksum is modified to ensure that the parser verifiably detects an error.
The test cases include federal and state addresses, all supported lengths of administrative keys, as well as empty, short, and thirty-digit detailed addresses containing digits and both uppercase and lowercase letters. Additional tests check, among other things, unknown codes, extra hyphens, invalid characters, whitespace, and the Jackson error-handling mechanism.
In total, there are 53 tests and the configured coverage check. The mathematical derivation explains why the algorithm works; the tests additionally verify that I have implemented it and the formatting rules correctly.
What JMH Actually Measured
A faster individual method does not necessarily mean a faster library. That is why I ran the same compiled JMH benchmarks once using the current classes from version 1.4.0 and once using the existing JAR from version 1.3.3. The runs were performed one after the other on the same computer.
The testing environment was Windows 11 with OpenJDK 25.0.2 and JMH 1.37. The setup used one thread, two JVM forks, three warm-up iterations and three measurement iterations (each lasting one second), and a heap size of 256 MiB. The GC profiler tracked allocations; JaCoCo was not active in the benchmark JVMs. The current implementation being compared is Commit 2b5e1b5.
| Operation | Input | 1.3.3 ns/op | 1.4.0 ns/op | Faktor | 1.3.3 Byte/op | 1.4.0 Byte/op |
|---|---|---|---|---|---|---|
| Parsing | Land | 403,49 | 119,38 | 3,38× | 1208 | 408 |
| Parsing | Bund | 295,12 | 92,34 | 3,20× | 832 | 256 |
| Parsing | Long ID | 952,40 | 250,52 | 3,80× | 1912 | 496 |
| Generate, including checksum | Land | 171,72 | 62,39 | 2,75× | 688 | 136 |
| Generate, including checksum | Bund | 162,16 | 48,29 | 3,36× | 688 | 136 |
| Generate, including checksum | Long ID | 508,79 | 177,75 | 2,86× | 1512 | 136 |
| Search by State | All 16 States | 56,98 | 8,41 | 6,77× | 312 | 16 |
The state ID is 05711-06001-79, and the federal ID is 992-80150-88. To generate the long ID, the coarse address 161234567890 was combined with the fine address "aZ09BC".repeat(5). The times are averages over six measurement iterations; the allocation values are rounded. The factor is the runtime of 1.3.3 divided by the runtime of 1.4.0 and was calculated from the unrounded values.
During generation, from(address, fine).getChecksum() is called with an existing coarse address. The generation of the coarse address itself is therefore not part of this measurement. The new factory validation, however, is included. The state search cycles through all sixteen codes and is independent of the selected Leitweg-ID.
I particularly like the result for the long ID: parsing takes about 74 percent less time and generates about 74 percent fewer temporary bytes. When generating the ID including the checksum, allocations even drop from 1,512 to 136 bytes per call—a reduction of about 91 percent.
Access to a pre-cached toString() was also measured. Both versions take less than one nanosecond and generate virtually no allocations. These values are highly sensitive to JIT optimizations; therefore, the differences that interest me most are shown in the table for the operations that actually process characters and create objects.
These figures describe these local benchmarks. They do not automatically make a single calculation several times faster: in an application, JSON processing, database accesses, or network communication may account for the larger share of performance. However, with a large number of IDs, both computation time and allocations can be reduced with less work per call.
My conclusion: The remainder is enough
The first implementation explained the problem well. The revision asked more precisely which parts of this explanation the computer actually needs to execute.
For the checksum, I only need a large number in my head. In the program, a small remainder is enough. For a fixed mapping, I don’t have to prepare a new search for every call. And when parsing, I don’t have to first break down characters that are already in the input and then reassemble them for the same check.
The improvements are thus primarily the result of work that was avoided. I get a faster parser, fewer temporary objects, and more consistent validation. The additional complexity of the direct parser remains a responsibility, however: it must be supported by understandable conditions and meaningful tests.
Knuth’s warning against premature optimization is therefore no reason for me to never revisit working code. It is a reminder to invest effort in the right places. In this case, that was a number between 0 and 96.