Repository navigation
Speed up analyzer source reading and hashing with Rust and XXH3-128 #64065
Description
Summary
Investigate moving analyzer source-file reading and content hashing from Dart to a small Rust library accessed through FFI. The Rust operation would open and read one file, calculate an XXH3-128 cache key from the returned bytes, and return the bytes and key to Dart. Dart would continue to decode the bytes as UTF-8 and own all analyzer-specific cache behavior.
This is a performance proposal. The hash is only used as a cache key, so it needs a low collision rate, not cryptographic security.
Motivation
A new analyzer process starts with an empty process-local FileContentCache. Even when its persistent analysis cache is complete, it must read every file requested for analysis, and/or transitively imported from it decode it, and calculate a content hash before cached analyzer artifacts can be validated.
The current Dart path performs a synchronous readAsBytesSync, UTF-8 decoding, and MD5 calculation. A prototype instead performs the read and XXH3-128 calculation in Rust, exposes the returned allocation as an external Uint8List, decodes it in Dart, and immediately releases the Rust allocation.
Prototype results
Isolated read-and-hash benchmark
benchmark_read_hash.sh recursively selects the .dart files below the given directories and compares sequential Dart readAsBytesSync plus MD5, Dart AOT calling the Rust reader through FFI, and standalone Rust fs::read plus XXH3-128. Traversal, compilation, and UTF-8 decoding are outside the timed phase. The FFI timing includes per-file path encoding, the native call, and releasing the returned Rust allocation. The standalone Rust implementation uses a release build.
These are medians of 100 alternating runs after 10 warm-up runs per implementation:
| directories | files | total bytes | total MiB | Dart AOT + MD5 | Dart AOT + Rust FFI | standalone Rust | FFI speedup | FFI reduction |
|---|---|---|---|---|---|---|---|---|
pkg/analyzer/lib, pkg/analyzer/test |
1,564 | 36,537,962 | 34.845 | 132.651 ms | 16.122 ms | 15.397 ms | 8.23x | 87.8% |
pkg/analysis_server/lib, pkg/analysis_server/test |
1,758 | 14,246,045 | 13.586 | 65.179 ms | 15.883 ms | 14.838 ms | 4.10x | 75.6% |
pkg/linter/lib, pkg/linter/test |
562 | 2,650,401 | 2.528 | 14.643 ms | 4.579 ms | 4.168 ms | 3.20x | 68.7% |
pkg |
15,669 | 108,451,611 | 103.428 | 569.919 ms | 174.875 ms | 163.813 ms | 3.26x | 69.3% |
The linter and whole-pkg rows are likely more representative of typical user projects than the analyzer row because their files are smaller on average: 4.6 KiB for linter and 6.8 KiB for pkg, versus 22.8 KiB for analyzer. Smaller files leave less hashing work to accelerate and make fixed per-file costs such as opening the file, path conversion, allocation, and the FFI call proportionally more important. The roughly 3.2x isolated speedup in these rows is therefore a more conservative expectation than the 8.23x analyzer result. End-to-end improvements still depend on how much of an individual analysis workload is spent reading and hashing source files.
For example:
pkg/analyzer/tools/read_all_files_benchmark/benchmark_read_hash.sh \
pkg/analyzer/lib pkg/analyzer/testThe FFI timing includes returning and freeing the Rust allocation but does not decode it. The standalone Rust timing excludes the Dart-to-Rust boundary. The end-to-end analyzer benchmark below includes both FFI and UTF-8 decoding.
End-to-end analyzer benchmark
The following are medians of 10 alternating AOT runs after fully populating the MD5 and XXH3-128 persistent-cache variants:
| analyzed directories | Dart read + MD5 | Rust read + XXH3-128 | reduction |
|---|---|---|---|
pkg/analyzer/lib, pkg/analyzer/test |
1.12 s | 0.86 s | 23.2% |
pkg/analysis_server/lib, pkg/analysis_server/test |
1.23 s | 0.96 s | 22.0% |
pkg/linter/lib, pkg/linter/test |
0.55 s | 0.40 s | 27.3% |
To model repeated broad invalidation, another benchmark renamed the declaration of LineInfo.getOffsetForLine to getOffsetForLine2 before one analysis, restored it before the next, and left all references unchanged. Dart and Rust used separate persistent caches, and both declaration states were warmed in each cache before measurement. These are medians of 10 alternating AOT runs after four warm-up cycles:
| analyzed directories | Dart read + MD5 | Rust FFI read + XXH3-128 | reduction |
|---|---|---|---|
pkg/analyzer/lib, pkg/analyzer/test |
1.212 s | 1.031 s | 14.9% |
Because the two states were already cached, this measures repeatedly switching between two cached dependency graphs, not the first analysis after a unique edit. The Rust reader saved 181 ms; dependency and cache work common to both readers makes the proportional improvement smaller than in the unchanged, fully cached result.
In a follow-up fully cached analyzer profile, the complete Rust-backed source path took 73.5 ms for 3,325 reads totaling 53.9 MB:
| source operation | time |
|---|---|
| Rust open, read, and XXH3-128 | 39.5 ms |
| Dart UTF-8 decoding | 31.0 ms |
| Other FFI and conversion work | about 3 ms |
The uninstrumented AOT process took 0.84 seconds in that profiling run. Source reading is therefore no longer the largest remaining cost, but the prototype's end-to-end improvement is consistent across the three measured packages.
A related implication is that accepting Rust FFI for performance-sensitive Dart code broadens the options for optimizing the persistent cache. The largest remaining cross-cutting cost was reading 7,186 separate FileByteStore files, taking 193 ms. A Rust-backed single-file store could replace those individual opens with indexed reads from one open file. This is a possible follow-up, not part of the source-reading and hashing proposal.
Proposed boundary
Add an optional source-content reader to FileContentCache. Its synchronous operation accepts an absolute path and returns:
(exists, bytes/content, 128-bit cache key)
For the Rust-backed implementation:
- Dart encodes the path and calls the native function.
- Rust opens the file, reads it into one owned allocation, and calculates XXH3-128 over the returned bytes.
- Rust returns the allocation pointer, length, and two 64-bit hash words.
- Dart creates an external byte view and decodes it as UTF-8.
- Dart calls the matching Rust deallocator immediately after decoding.
The calls remain one-file-at-a-time and synchronous. This proposal does not require batching, prefetching, or changes to analyzer artifact serialization.
Cache compatibility
It doesn't matter much what hashing algorithm we use for the cache - what is important is that it gives a good distribution across the 128 bits.
Error and ownership behavior
- Missing, unreadable, or invalid UTF-8 files retain the existing
exists: false, empty-content behavior. - Rust allocations are released by the same library that created them.
- Dart must not retain the external byte view after decoding and freeing it.
- The empty-file XXH3-128 value is checked when loading the library to catch ABI or word-order mismatches.
- The Rust function must not unwind across the FFI boundary.
Open questions
- How should the Rust library be built and distributed for every Dart SDK host platform?
- Should this be enabled by default or initially guarded by an experiment?
- Is the native dependency and platform maintenance cost justified by the measured startup improvement?
Acceptance criteria
- Identical analyzer error results for representative SDK packages.
- Unit coverage for empty, missing, unreadable, invalid UTF-8, and ordinary files, including allocation release and hash word order.
- Supported builds on macOS, Linux, and Windows.
- No native-memory growth across repeated reads.
- Fully cached AOT benchmarks on
analyzer,analysis_server, andlinterretain a material end-to-end improvement. - A documented fallback remains available on unsupported platforms or when the native library cannot be loaded.
Activity
mraleph commentedon Aug 17, 2026
No Rust dependencies for the SDK please. C/C++ is fine. Rust is not allowed.
bwilkerson commentedon Aug 17, 2026
Out of curiosity, what causes the improvement? How much is due to file I/O, how much to the hash computation, etc.
fshcheglov commentedon Aug 17, 2026
The improvement is almost fully caused by the difference in hashing speed.
The speed of hashing of MD5 in Dart is
168.39 MiB/s, while the speed of hashing of XXH128 in Rust is29704.1 MiB/s.Native code and SIMD optimized algorithm really help :)
mraleph commentedon Aug 17, 2026
You can also try to use a Dart implementation of XXH3-64 which (is not as fast as Rust), will be significantly faster than MD5
e.g. this package https://pub.dev/packages/xxh3
fshcheglov commentedon Aug 17, 2026
Unfortunately, https://pub.dev/packages/xxh3 supports only XXH3-64, whereas we would prefer XXH3-128 because its larger hash space significantly reduces the probability of collisions.
davidmorgan commentedon Aug 18, 2026
Hashing twice with a different seed to get a 128 sized key is sufficient to prevent random collisions.
There is a concern with XXH3-64, though: it's easy to create collisions, it's not a "secure" hash. You can mitigate by keeping the seed secret--but that's a tough problem.
Build systems usually go for a secure hash. Although the analyzer is not exactly a build system, it's used directly by tools that are, like build_runner. And, it has a long-lived hash-keyed cache, which brings very similar considerations to build systems.
For example, blaze used SHA-256, and more recently uses BLAKE3. There are a few pure dart implementations available.
One interesting property of BLAKE3 is that it can use more than one core, making it much faster than single core hashing.
julemand101 commentedon Aug 18, 2026
If this we should like get away from MD5? :)
johnniwinther commentedon Aug 18, 2026
cc @jensjoha
davidmorgan commentedon Aug 18, 2026
Yes, we should get away from MD5 for the same reason. But XXH3 would be a step down, it's less secure than MD5, because that was never even a design goal.
fshcheglov commentedon Aug 24, 2026
https://dart-review.googlesource.com/c/sdk/+/538901
Component times in
dart analyzepkg/analyzerlibtestFor the whole
pkg/analyzerworkload:End-to-end results
pkg/analyzerlibtestbwilkerson commentedon Aug 24, 2026
I'm eager to see this land, but I'm curious about the design.
I understand the value of having the hash representation be a re-usable component; that makes sense to me.
I don't understand why
NativeFileReaderisn't integrated withPhysicalResourceProvider. Is there value to having a resource provider that uses (what I assume are) slower read/write calls and only use the C implementations for reading files into the file cache? Is there a reason for the difference that I'm not considering? (Ok, that seems likely; just wondering what it is.)1 remaining item
bwilkerson commentedon Aug 25, 2026
Is it significant enough to justify introducing
NativeFileReader? If not, we should probably remove that part of the change. If so, then ...That doesn't answer my question about integrating it with the resource provider 🙂 , but if we need something in the analysis server it seems like it would be cleaner to have a
NativeResourceProvidersubclass in the analysis server. Server already passes the provider to theAnalysisContextCollectionconstructor, so having a more efficient provider than the one that the analyzer provides would be fine. [1] And like I said, it feels cleaner than introducing a different way of reading that bi-passes the provider (which is how we deal with file overlays).[1] Well, sort of. We also need to improve the performance of the analysis server plugins, and if we can only ship C code with the server that might be a problem.
jensjoha commentedon Aug 25, 2026
I agree with @davidmorgan that it feels weird to pick a new hash but then pick something that's probably not better. Blake3 seems like a good choice (and actual step up) to me.
I don't think the CL includes the given benchmarks. How do we reproduce those?
dcharkes commentedon Aug 25, 2026
Recently we also ran into hashing bottlenecks in the caching for
hook/build.dart(dart-lang/native#3540) andflutter_toolbuild steps (flutter/flutter#190967). We decided there to use file-stat to look at the timestamp and file size. If both are equal we skip reading the file and skip hashing. This can false positive, but that is rather unlikely. Should we consider doing that instead? What speedup would that give?(Some 2024 discussions about different hashing algorithms for background: dart-lang/native#1593 (comment) No mention of Blake3.)
davidmorgan commentedon Aug 25, 2026
For stat-based approaches, "git status" is a nice reference. There is a fun writeup and some links to find out details here https://git-scm.com/docs/racy-git
But it's not sufficient for the analyzer, which heavily uses hashing for content-addressable caching. In this way it's comparable to bazel, which uses a combination of blake3 bazelbuild/bazel#22011 and stat-based checks bazelbuild/bazel#21044
Actually there are interesting questions around how bazel's stat-based checks are mostly safe from malicious input; on Linux it relates to checking ctime+mtime+inode, not sure about other systems; I suggest asking Gemini if interested.
fshcheglov commentedon Aug 25, 2026
These are the findings I got comparing the proposed alternatives in this thread to baseline Dart MD5 and Dart read:
I read about Bazel a little. My understanding is that it has ability to use remote caching, shared between multiple users. In this case, I can see why it might be useful to have cryptographic properties for the cache. The analyzer, however, uses per-user cache. So, I think we need only good accidental collision properties.
For
XXH3-128, assuming its128-bit outputs are distributed approximately uniformly:P(collision)≈1−e^(−n*(n−1)/(2*2^128)), so1.47 × 10^-336.8 × 10^321.47 × 10^-316.8 × 10^301.47 × 10^-296.8 × 10^281.47 × 10^-276.8 × 10^261.47 × 10^-256.8 × 10^241.47 × 10^-236.8 × 10^221.47 × 10^-216.8 × 10^201.47 × 10^-196.8 × 10^181.47 × 10^-151.47 × 10^-910^18)0.00147See also https://github.com/Cyan4973/xxHash/tree/dev/tests/collisions
@mraleph The reason we might want to have native read, is that we can avoid extra allocation and extra copy. We read directly into the native buffer, which we allocate once, and reuse across multiple file read. Then
utf8.decodedecodes from this buffer into a copy in DartString- one copy. When we read using Dart, my understanding is that we allocate freshUint8Listeach time and copy data into it. The benchmark numbers support using native read, we get about0.8%performance hit if switch to Dart read.So, using
blake3-128FFI + Dart read will makedart analyzeabout3%slower thanhhx3-128FFI + native read.In general it looks that blake3 is about
13x(!!!) slower thanxxh3.Paying this cost for cryptographic guarantees that we don't need seems too much.
I also would like to use
xxh3-64for small inputs, likeByteStoreentries checksum, for whichblake3is15times slower.mraleph commentedon Aug 25, 2026
Depends on the API in question.
RandomAccessFile.readIntoSynccan read data into the buffer you give it. In general I'd prefer to keep native code minimal. Hand rolling your own version ofdart:ioneeds to have strong arguments for it. I don't think 0.8% is strong enough.Well, I'd say that that should not be happening to begin with. Analyzer should not be decoding the whole file into a
String- it's a waste of time (andutf8.decodeis actually relatively slow). Analyzer should just parse raw UTF8 bytes like CFE does it. But that's orthogonal to the question of hashing we discuss here.fshcheglov commentedon Aug 25, 2026
I agree with this decision, 0.8% performance is not worth the complexity introduced by rolling reading into native code.
Avoiding decoding the whole file into a
Stringlooks interesting. I believe it is something that I could attempt to address in a future CL.jensjoha commentedon Aug 26, 2026
Wrt the numbers for blake3 vs XXH3-128 let's pretend we used blake3.
The question then becomes "do we want to save 50 ms by not having cryptographic guarantees?" (numbers from above on, I guess,
pkg/analyzer).Yes, this is about 2.6% on the numbers provided here with a full cache, but would percentage-wise be much less with an empty cache for instance.
My gut feeling answer to that question is "no". Not because I can come up with a great example of why it's a bad idea, but because I can't reason about it.
fshcheglov commentedon Aug 26, 2026
I updated the CL to use BLAKE3 when it's available, with a fallback to MD5.
https://dart-review.googlesource.com/c/sdk/+/538901
I'm still adding XXH3 algorithms for my future work.
fshcheglov commentedon Aug 31, 2026
BLAKE3 is now cleanly imported using DEPS, so maybe we could land this CL?
modulovalue commentedon Sep 22, 2026
A vectorized BLAKE3 achieves roughly 2 GB/s on a an M5 core, which is pretty slow. For context, vectorized utf8 decoding can reach >10 GB/s.
@fshcheglov said:
It sounds like the content hash is used for cache invalidation, so most of the properties of BLAKE3 are indeed irrelevant to us, right?
It looks to me like the primary properties we want is fast hashing and hopefully few collisions, but if we hit collisions, they are not catastrophic.
@fshcheglov @scheglov do you think these properties suffice for the use cases BLAKE3 is intended to solve here?
An alternative would be to use a simple checksum. We can very easily achieve 50 GB/s using Int32x4 today on arm64 M-cores (#64170) and the strict ceiling is roughly 120 GB/s on the same cores that BLAKE3 achieves only 2 GB/s on, that is, with a simple vectorized checksum we could possibly >50x BLAKE3 and ~2x XXH3-128 with no third party dependencies.
scheglov commentedon Sep 22, 2026
@modulovalue We need two kinds of hashes.
One, that we use for cache keys, and for which we currently use MD5. This is not validation. This is to associate some analyzer computed values with file contents. We want it to not have collisions in practice (theoretically there are always collisions). Using XXH3-128 would be much, much faster than BLAKE3 here. But it has more collisions.
Second, that we use for checksums of values in
ByteStorecache. We don't plan using BLAKE3 for these. The plan was to use XHH3-64 for this, in en experiment if was, don't remember exactly, maybe5ms- almost nothing. I don't remember exact speeds. We don't need any specific hash here, just something reasonable and faster.modulovalue commentedon Sep 22, 2026
@scheglov I'm curious, did you observe those collisions in practice or in a test setting (and so that's why there are considerations to use the slower BLAKE3, i.e., a trade in speed for fewer observed collisions) or was that more of a general statement about XXH3-128 vs BLAKE3?
@fshcheglov said
Now I'm really curious. If we took let's say 10000 random Dart programs, cached them and randomly mutated bytes, do we really get many collisions? Would that be a fair proxy benchmark for the analyzer cache?
modulovalue commentedon Sep 22, 2026
I let an agent run a small experiment and its conclusion was that collisions are a non-problem. On ~8 million programs derived from ~8k Dart source files all the algorithms discussed here (including md5 and crc32) produced a similar, low collision profile. (I'll spare you from its overly verbose reasoning)
From a high-value-low-effort solution it seems like Slava's suggestion to start with the slower-but-still-significantly-faster-than-md5 implementation seems like a good approach.
Since I'm focusing on SIMD performance right now and a lot of it is overlapping with getting scalar code performant too, I can look into how we could improve the performance of xxh3 if you'd like @scheglov & @fshcheglov.
From what I've seen, I agree with the conclusion here to use an XXH3-style hashing function. The C version reaches 40 GB/s on my machine. I'd expect Dart to be able to reach 80% of that and I'd consider Dart not being able to come close to 80% a bug.
mraleph commentedon Sep 23, 2026
@modulovalue we had a bunch of internal discussions and agreed to use BLAKE3
From this perspective I am totally fine landing this CL which uses native implementation of BLAKE3 - I am not sure what exactly blocking it right now.