118 lines
6.3 KiB
Markdown
118 lines
6.3 KiB
Markdown
# ParadoxSaveParser.Benchmarks
|
|
|
|
Compares the query engine of this repo (`SearchExpression` + `SaveParserEU4`) against
|
|
regex engines and `jq` on one realistic task:
|
|
|
|
> extract the `technology` block (adm/dip/mil level) of every country from an EU4 save
|
|
|
|
| engine | query |
|
|
|---|---|
|
|
| this repo | `countries.*.technology` |
|
|
| jq | `.countries \| map_values(.technology)` |
|
|
| .NET `Regex` / PCRE.NET | see `Extractors.PathAwarePattern` / `Extractors.CountriesBlockPattern` |
|
|
| `Utf8JsonReader` / `JsonDocument` | hand written navigation |
|
|
|
|
## Corpus
|
|
|
|
* `gamestate` — a real 109 MB EU4 1.37 save (text format, 6.0M lines, 2803 country blocks,
|
|
1870 of which have a `technology` block).
|
|
* `gamestate.min.json` — 92 MB compact JSON twin, produced from the save by this project's
|
|
own parser. It exists because jq and the `System.Text.Json` engines cannot read the
|
|
Paradox format at all.
|
|
|
|
The save is **not** in the repository. Point `PSP_BENCH_DATA` at the directory holding it,
|
|
or drop it in `ParadoxSaveParser.CLI/bin/Debug/net10.0/` (the default location).
|
|
|
|
## Usage
|
|
|
|
```sh
|
|
dotnet build ParadoxSaveParser.Benchmarks -c Release
|
|
cd ParadoxSaveParser.Benchmarks/bin/Release/net10.0
|
|
|
|
./ParadoxSaveParser.Benchmarks.exe prepare # build the JSON twin (once)
|
|
./ParadoxSaveParser.Benchmarks.exe verify # one run of every engine + correctness check
|
|
./ParadoxSaveParser.Benchmarks.exe --filter '*' # full BenchmarkDotNet run
|
|
```
|
|
|
|
Every engine returns the checksum `countries * 1_000_000 + sum_of_tech_levels`, so `verify`
|
|
shows immediately when an engine finds something different from the others.
|
|
|
|
## Fairness notes
|
|
|
|
* All in-process engines read from memory; file I/O is excluded. jq is an external process,
|
|
so its numbers include process start (measured separately by the `jq startup only`
|
|
benchmark) and reading the JSON from the OS page cache.
|
|
* The regex engines work on the save text, which is 109 MB; jq works on 92 MB of JSON.
|
|
* jq is the only engine here that is a general query language: it can do arithmetic,
|
|
filtering and reshaping, which neither the regexes nor `SearchExpression` can.
|
|
|
|
## Results
|
|
|
|
AMD Ryzen 7 5700X, 8 physical cores (16 logical), Windows 10 21H2, .NET 10.0.12, jq 1.8.2,
|
|
109 MB save / 92 MB JSON twin, BenchmarkDotNet `RunStrategy.Monitoring`,
|
|
3 warmups and 10 iterations for the in-process engines, 5 for jq.
|
|
|
|
| engine | mean | vs this project | allocated | correct? |
|
|
|---|---:|---:|---:|---|
|
|
| **SearchExpression (this project)** | **49.6 ms** | **1.00x** | **1.46 MB** | yes |
|
|
| .NET Regex balanced block + inner scan | 114.0 ms | 2.30x | 213 MB | yes |
|
|
| PCRE.NET path aware, JIT compiled | 123.4 ms | 2.49x | 0.90 MB | 1869/1870 |
|
|
| .NET Regex path aware, compiled | 135.1 ms | 2.72x | 1.34 MB | 1869/1870 |
|
|
| Utf8JsonReader over JSON twin | 155.5 ms | 3.13x | 16 KB | yes |
|
|
| JsonDocument over JSON twin | 323.2 ms | 6.51x | 72 B (native) | yes |
|
|
| .NET Regex path aware, NonBacktracking | 440.5 ms | 8.87x | 30.6 MB | 1869/1870 |
|
|
| Full parse, then select | 1204 ms | 24.3x | 962 MB | yes |
|
|
| jq `empty` (parse the file, emit nothing) | 4188 ms | 84.4x | n/a | n/a |
|
|
| jq `.countries \| map_values(.technology)` | 4339 ms | 87.4x | n/a | yes |
|
|
| jq `--stream` | 17497 ms | 352x | n/a | n/a |
|
|
| jq process startup only | 4.1 ms | 0.08x | n/a | n/a |
|
|
|
|
Reading the save from disk instead of a preloaded `byte[]` costs the parser ~9 ms more:
|
|
58.4 ms via `FileStream` (`ParserInputBenchmarks`).
|
|
|
|
### Reading the table
|
|
|
|
* **This parser is the fastest engine measured here.** It is 2.3x faster than the only
|
|
regex approach that enforces the path, 3.1x faster than a hand written `Utf8JsonReader`
|
|
over the equivalent JSON, 6.5x faster than `JsonDocument`, and 87x faster than jq — while
|
|
allocating 1.46 MB for a 109 MB input.
|
|
* **jq is ~87x slower and 97% of that is JSON parsing, not the query**: `jq empty` on the
|
|
same file costs 4188 ms of the 4339 ms. Process startup is negligible (4 ms). jq's
|
|
`--stream` mode, often recommended for large inputs, is 4x *slower* still. jq also cannot
|
|
read the Paradox format, so it first needs the save converted to JSON — a conversion this
|
|
parser has to perform anyway.
|
|
* **Only one regex approach here is actually correct**, and it is the expensive one: cut the
|
|
`countries={...}` block out with a balancing-group pattern (a .NET-only feature; PCRE would
|
|
need recursion), then scan inside it. It allocates 213 MB, because stage one materialises
|
|
the whole block as a string.
|
|
* **The cheaper path-aware pattern pairs a country tag with the next technology block over a
|
|
lazy gap, and silently gets it wrong**: 1869 of 1870 countries, because the tag class
|
|
`[A-Z0-9]{3}` drops EU4's `---` pseudo-country. Even that much only holds by luck of the
|
|
file layout — all 933 tech-less country blocks happen to be grouped at the end of the save,
|
|
so the lazy gap never runs across one. A save that interleaved them would report a
|
|
technology block under the wrong country tag, with no error.
|
|
* **`RegexOptions.NonBacktracking`** guarantees linear time but is 3.3x slower than the
|
|
compiled backtracking engine on this pattern and allocates 31 MB.
|
|
* **PCRE.NET** (the most used non-BCL regex engine in .NET, ~460k downloads) is within ~10%
|
|
of `System.Text.RegularExpressions` on the path-aware pattern (123 ms vs 135 ms). Nothing
|
|
here justifies leaving the BCL engine.
|
|
* **The query is what makes this parser fast.** Same parser, same file: 50 ms with
|
|
`countries.*.technology`, 1204 ms and 962 MB allocated without a query — 24x and 660x.
|
|
|
|
### How the parser got here
|
|
|
|
Three measurements on the same benchmark (`ParserInputBenchmarks`, reading a `FileStream`):
|
|
|
|
| lexer | mean | allocated |
|
|
|---|---:|---:|
|
|
| `Stream.ReadByte()` per byte | 834 ms | 1.55 MB |
|
|
| copy the file into a `MemoryStream` first, still `ReadByte()` | 738 ms | 257 MB |
|
|
| 64 KB buffer + `Tokenizer` with byte-level block skipping | 58 ms | 1.46 MB |
|
|
|
|
The first jump came from removing a virtual call per byte. The large one came from making
|
|
the query prune *work* rather than just data: `Tokenizer.SkipBlock` throws away a rejected
|
|
`{...}` block by scanning raw bytes for brace depth with `SearchValues<byte>.IndexOfAny`,
|
|
so blocks the search expression rejects are never turned into tokens or strings at all.
|
|
Retained tokens are spans into the read buffer, decoded only when their value is kept, and
|
|
numbers are parsed straight from UTF8.
|