RFR: 8316704: Regex-free parsing of Formatter and FormatProcessor specifiers
Claes Redestad
redestad at openjdk.org
Mon Oct 16 16:18:10 UTC 2023
On Sun, 17 Sep 2023 16:01:33 GMT, Shaojin Wen <duke at openjdk.org> wrote:
> @cl4es made performance optimizations for the simple specifiers of String.format in PR https://github.com/openjdk/jdk/pull/2830. Based on the same idea, I continued to make improvements. I made patterns like %2d %02d also be optimized.
>
> The following are the test results based on MacBookPro M1 Pro:
>
>
> -Benchmark Mode Cnt Score Error Units
> -StringFormat.complexFormat avgt 15 1862.233 ? 217.479 ns/op
> -StringFormat.int02Format avgt 15 312.491 ? 26.021 ns/op
> -StringFormat.intFormat avgt 15 84.432 ? 4.145 ns/op
> -StringFormat.longFormat avgt 15 87.330 ? 6.111 ns/op
> -StringFormat.stringFormat avgt 15 63.985 ? 11.366 ns/op
> -StringFormat.stringIntFormat avgt 15 87.422 ? 0.147 ns/op
> -StringFormat.widthStringFormat avgt 15 250.740 ? 32.639 ns/op
> -StringFormat.widthStringIntFormat avgt 15 312.474 ? 16.309 ns/op
>
> +Benchmark Mode Cnt Score Error Units
> +StringFormat.complexFormat avgt 15 740.626 ? 66.671 ns/op (+151.45)
> +StringFormat.int02Format avgt 15 131.049 ? 0.432 ns/op (+138.46)
> +StringFormat.intFormat avgt 15 67.229 ? 4.155 ns/op (+25.59)
> +StringFormat.longFormat avgt 15 66.444 ? 0.614 ns/op (+31.44)
> +StringFormat.stringFormat avgt 15 62.619 ? 4.652 ns/op (+2.19)
> +StringFormat.stringIntFormat avgt 15 89.606 ? 13.966 ns/op (-2.44)
> +StringFormat.widthStringFormat avgt 15 52.462 ? 15.649 ns/op (+377.95)
> +StringFormat.widthStringIntFormat avgt 15 101.814 ? 3.147 ns/op (+206.91)
It might be reasonable to add a few more common patterns to the `FormatSpecifier` fast-path, but where to draw the line?
FWIW the intent of micros like `complex` and `widthString` wasn't necessarily to invite further optimizations, but to explore the cost of failure, i.e., make sure that the fast-path doesn't add a substantial cost when it doesn't help or only helps somewhat. Since you now specialize for most of the patterns in the micros I think you need to explore some variants that you _don't_ optimize for, such as `"%10.3f"`.
Orthogonal optimizations like the `FormatSpecifier` fast-path extension and the `print` fast-path should generally be separate PRs.
I think it would make sense to make the testing a bit more exhaustive, especially w.r.t argument indexes and specifiers taking multiple flags. Looking at test/jdk/java/util/Formatter/Basic-X.java.template we seem to test each flag, but lack tests combining many flags and permutations thereof. Could you take a stab at increasing coverage a bit here?
I'm also curious what performance numbers you get with the latest patch. If we go all the way like this some of the added microbenchmarks is a bit pointless so after checking you might want to cut back on some of those (just keep one of the floating point tests maybe)
I think this is shaping up nicely. Some unused code, then I think we can move ahead.
The new `FormatSpecifierParser` utility class adds a bit of boilerplate for something that could be a static utility: https://github.com/wenshao/jdk/pull/6 - but perhaps splitting it up a bit more helps JIT inlining further. I can take this on as a follow-up RFE if you prefer.
A few nits, otherwise I think this looks OK
I was worried this would sprawl out more, but perhaps ~230 lines of code is a reasonable extra weight to make the long tail of `String.format`'s regex-free.
I was going to comment that the flag parsing was broken in f303f29 but it seems that it was fixed in the latest. I think we need to make a review pass over all existing tests to make sure all imaginable variants are covered.
The parser code also ought to be shared between `Formatter` and `FormatProcessor` so that there's a single source of truth going forward.
I think it makes sense to file an RFE and do a full review of this. "Regex-free parsing of Formatter and FormatProcessor specifiers"?
Please don't pile on new refactorings and improvements on a PR that has been opened for review. Better to let things brew as a draft for a bit if you're not sure you're done before opening the PR for review, then once it's been opened (like this one) consider preparing follow-up PR instead of refactoring as you go.
Specifically I'm not sure 0d977b2 is a good idea and would like you to roll those changes back. Object pooling for trivial, short-lived objects are considered an anti-pattern, as they add references to old GC generations and share many of the same drawbacks as lookup tables, such as increased cache traffic. Showing great wins on microbenchmarks while being a wash or even regressing real applications.
src/java.base/share/classes/java/util/Formatter.java line 2944:
> 2942: ++off;
> 2943: argSize = size + 1;
> 2944: size = 0;
pointless `size = 0`
src/java.base/share/classes/java/util/Formatter.java line 2949:
> 2947: }
> 2948: } else {
> 2949: if (first == '0') {
While it's clever to avoid re-parsing I think it muddies the control flow. It would be simpler if we always reset to `off = start; c = first` in this `else` block then unconditionally call `parseFlags(); parseWidth();` outside in `parse`. The few extra calls to `s.charAt(..)` this might add a little overhead on some tests, but the JIT might like the brevity and less branchy structure overall and on larger benchmarks.. Maybe worth experimenting with.
src/java.base/share/classes/java/util/Formatter.java line 2964:
> 2962: widthSize = size;
> 2963: }
> 2964: size = 0;
Pointless `size = 0`
src/java.base/share/classes/java/util/Formatter.java line 2977:
> 2975: if (!Flags.isFlag(c)) {
> 2976: flagSize = size;
> 2977: size = 0;
pointless `size = 0`
src/java.base/share/classes/java/util/Formatter.java line 3011:
> 3009:
> 3010: static boolean isConversion(char c) {
> 3011: return (c >= 'a' && c <= 'z') || (c >= 'A' || c <= 'Z') || c == '%';
Logical error:
Suggestion:
return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || c == '%';
src/java.base/share/classes/java/util/Formatter.java line 3140:
> 3138: }
> 3139:
> 3140: FormatSpecifier(char conv, int flag, int width, int precision) {
This appears to be unused.
src/java.base/share/classes/java/util/Formatter.java line 3420:
> 3418: && fmt.a instanceof StringBuilder sb
> 3419: ) {
> 3420: sb.append(value);
There's a lot of `if`s here, and this doesn't take into account locales with non-ASCII digits:
Locale ar = new Locale.Builder().setLanguageTag("ar-SA-u-nu-arab").build();
Locale.setDefault(ar);
System.out.println("%d".formatted(10000)); // should print "١٠٠٠٠" but prints "10000"
test/jdk/java/util/Formatter/Basic-X.java.template line 1748:
> 1746: // perhaps an IllegalFormatArgumentIndexException should be defined?
> 1747: tryCatch("%<%", IllegalFormatFlagsException.class);
> 1748:
After adding test-cases to this template you need to run `genBasic.sh` (in the same folder) to regenerate all the `Basic*` tests. These changes then need to be added to the PR.
FWIW these new and existing tests that provoke `IllegalFormatPrecisionException` and `UnknownFormatConversionException` are common to all types, meaning there seems to be little point in generating them out into each and every `BasicByte`, `BasicInt` et.c.. Perhaps it would make more sense to add such tests directly to Basic.java to avoid some redundancy here - or a new `BasicCommon` test to put common tests into?
-------------
PR Review: https://git.openjdk.org/jdk/pull/15776#pullrequestreview-1630133740
PR Review: https://git.openjdk.org/jdk/pull/15776#pullrequestreview-1639452604
Changes requested by redestad (Reviewer).
PR Review: https://git.openjdk.org/jdk/pull/15776#pullrequestreview-1641781843
Marked as reviewed by redestad (Reviewer).
PR Review: https://git.openjdk.org/jdk/pull/15776#pullrequestreview-1641961236
PR Comment: https://git.openjdk.org/jdk/pull/15776#issuecomment-1728424181
PR Comment: https://git.openjdk.org/jdk/pull/15776#issuecomment-1730173405
PR Comment: https://git.openjdk.org/jdk/pull/15776#issuecomment-1732562759
PR Review Comment: https://git.openjdk.org/jdk/pull/15776#discussion_r1335806486
PR Review Comment: https://git.openjdk.org/jdk/pull/15776#discussion_r1335817101
PR Review Comment: https://git.openjdk.org/jdk/pull/15776#discussion_r1335817800
PR Review Comment: https://git.openjdk.org/jdk/pull/15776#discussion_r1335779111
PR Review Comment: https://git.openjdk.org/jdk/pull/15776#discussion_r1335234147
PR Review Comment: https://git.openjdk.org/jdk/pull/15776#discussion_r1335667901
PR Review Comment: https://git.openjdk.org/jdk/pull/15776#discussion_r1328152682
PR Review Comment: https://git.openjdk.org/jdk/pull/15776#discussion_r1350933399
More information about the core-libs-dev
mailing list