Repository navigation
Runtime performance: ~700× slower than native on a geo benchmark; analysis and a 2× prototype fix #66
Description
Activity
The attached patch (~220 lines) lowers primitive field reads through shared references to
Freezetypes to a single scalar load at a constant offset. It makesbufferandclassify2× faster, andpython3 Tester.py --releasepasses.The attached zip has the full write-up (
geo_buffer_bench/docs/FINDINGS.md), the patch, the benchmark and the probes, with commands to reproduce everything.I'm not sure if it's just me, but I don't see any attached files. Did you mean to attach them here or somewhere else?
The important caveat when comparing this project to Chicory is where the conversion between native data and java data happens. Chicory exposes native-like functions where arguments are i32, i64 etc. So the conversion mostly happens on these boundaries: for example, I found myself doing a lot of "serialize into json, print into string, pass as pointer + length, deseriaize from that". With this compiler you it happens inside, when pointers and references are made.
I previously said that it's strange to me that Pointer is created anywhere where
&Tis, so&Tisn't just a java object passed around by reference. It turns out my Rust is a bit rusty (pun intended) and I forgot one can do this:fn mutate(x: &mut i32) { *x = 43; } fn main() { let mut y = 42; mutate(&mut y); println!("{}", y); // 43 }
, that the reference in Rust is just a glorified pointer.
However, here's a little trick Kotlin does with
noinlinelambdas. In analyzes whether a captured value is a var or val (would be mut or not in Rust):1: fun measure(body: () -> Unit): Long { 2: val t0 = System.nanoTime() 3: body() 4: val t1 = System.nanoTime() 5: return t1 - t0 6: } 8: fun main() { 9: var x = 42 10: val time = measure { 11: x = 43 12: } 13: println(x) // Prints 43 14: println(time) 15: }and here's roughly what it compiles to, skipping basic leg work about nullability checks:
import kotlin.jvm.functions.Function0 import kotlin.Unit import kotlin.jvm.internal.Ref.IntRef import java.lang.invoke.LambdaMetafactory import java.lang.invoke.MethodHandles.Lookup import java.lang.invoke.MethodHandle import java.lang.invoke.MethodType import java.lang.invoke.CallSite public class ExampleKt { public final static long measure(Function0<Unit> a0) { 2: long l1 = System.nanoTime(); 3: Object _ = a0.[interface]invoke(); 4: long l3 = System.nanoTime(); 5: return l3 - l1; } public final static void main() { 9: Uninitialized tmp0 = new IntRef; tmp.[special]<init>(); IntRef a0 = tmp0; a0.element = 42; 10: Function0 tmp1 = INVOKEDYNAMIC { bootstrap = static LambdaMetafactory.metafactory( /* MethodHandles.Lookup caller, */ /* String interfaceMethodName = */ "invoke", /* MethodType factoryType = */ (IntRef) -> Function0, /* MethodType interfaceMethodType = */ () -> Object, /* MethodHandle implementation = */ static ExampleKt::main$lambda$0(IntRef) -> Unit, /* MethodType dynamicMethodType = */ () -> Unit ) arguments = [a0] }; long l1 = ExampleKt.measure(tmp1); 13: System.out.[interface]println(a0.element); 14: System.out.[interface]println(l1); 15: return } private final static Unit main$lambda$0(IntRef a0) { 11: a0.element = 43; 12: return Unit.INSTANCE; } }Int is wrapped into IntRef object and put on heap. The same would go for object types: ObjectRef is just providing a second indirection. And as these *Ref classes are never put in anything type-erased and are never assigned nulls, jit can usually optimize out their allocation and convert to just carrying pointers to stack, as Rust, C++ and alike do it.
I am not completely sure, but I think most of what can be done with
&muts without some sort of unsafe, can be achieved with this trick. And it is my hope that unsafe is usually limited to few spaces where it's either not that bad or can be configured to have different code for jvm backend specifically. Well, you can convert a ref to a pointer without unsafe, but you'll then have to use unsafe to do anything with that pointer. Hope you get what I mean.Sorry, my fault. Just forgot the attachement.
rustc_codegen_jvm-geo-benchmark.zip@LDemetrios For interfacing Kotlin with Rust I have successfully used CBOR serialization in the past. It can be used with Kotlin serialization out of the box, is a standard, is binary and has therefore much better performance than JSON. There is also a Rust crate which can directly handle CBOR too.
Thank you both for your performance improvement suggestions, I really appreciate it! Sorry for being inactive the last few days, the school holidays are almost up (sad!) so I was working a LOT on trying to increase the performance of the generated bytecode. I sort-of applied the patch, but in a way that was more suitable on top of current WIP changes. I've put my WIP work up now here (which should work in release, but there's still some stuff with debug), can you let me know how much it improves this
geobenchmark on your end (I also really appreciate finding new useful tasks to test the performance on, so thanks for that!): #73I ran my
geobenchmark against this PR (heada6a6716), compared with its base5ed31a3:geo0.33.1 buffering a line string, then point-in-polygon tests, JBR 25 on Apple Silicon, release builds only. Results are identical to native in every run.--points 20 --queries 1000 --warmup 10 --iterations 30, base and PR run alternately, two rounds each:median [ms] native base 5ed31a3PR speed-up generate 0.001 0.83–0.84 0.41–0.44 2× buffer 0.073–0.090 72.7–73.1 18.7–19.0 3.9× classify 0.37–0.45 253–255 129–133 1.9× total 0.44–0.55 330–338 152–159 2.2× With a long warm-up (500 iterations,
-XX:-DontCompileHugeMethods), total goes from 334 to 140 ms and buffer from 67.4 to 12.8 ms (5.3×). The jar shrinks from 34.3 MB to 2.3 MB (23,378 → 1,193 classes), and one short run starts in 0.57 s instead of 1.0 s.Classify is now 86% of the run time. A JFR profile puts about half of it in two runtime paths that feed each other:
-
sliceGetObjectin geo'scoord_pos_relative_to_ring, 28% of classify.linestring.lines()iswindows(2).map(|w| Line::new(w[0], w[1])), and each endpoint compiles tosliceGetObject(slice, i) checkcast j/C15d // Coord: decodes and registers a memory view copyManagedValue(...) checkcast j/C15d // copies it at onceBelow it:
decodedMemoryViewLocked20%,registerMemoryViewOrigin12%,WeakIdentityMap.put8%. The direct path insliceGetObjectthat skips the view isn't taken here. I didn't check which of its conditions fails. -
loadScalarFieldinget_bounding_rect, 26% of classify. The bounding-box loop now readsx/yas scalar loads on theVec<Coord>byte storage, which is good. But 23 of those 26 points areflushMemoryViewsOverlapping/removeOverlappingMemoryViews, tearing down the views that (1) just left on the same storage.
Because of (1), the weak references processed per young GC are back up to ~660k, close to the base's ~810k.
So decoding a detached copy at (1), without registering a view (the value is copied straight away), looks like it would remove most of both costs.
projectStructFieldhas dropped to 6% of classify but is still the largest runtime entry point in buffer (14%).I haven't tested debug builds, since the PR description says they don't work yet.
-
Thank you so much! I've just worked on it a bit more and pushed some new commits to
experimental2that should help make it a bit faster again (they did in my testing). It's really useful to have like a 2nd pair of eyes - from both of you so thanks!! - that can see the really useful ways forward on how to improve things (as sometimes I get a bit stuck!). If you could try it again and see if the speed up occurs on your end too and let me know if there's anything you think could be better still I would really appreciate it :)Re-ran the same benchmark against the new head
48f2727, with base5ed31a3anda6a6716measured again in the same session. Results are still identical to native in every run, and classify got a big jump this time:--points 20 --queries 1000 --warmup 10 --iterations 30, all variants run alternately, two rounds each:median [ms] native base 5ed31a3a6a671648f2727speed-up vs base generate 0.001 0.82 0.43–0.44 0.41 2× buffer 0.073–0.096 70.2–71.7 18.7–19.0 16.3 4.4× classify 0.37–0.48 250–251 128–135 30–32 8× total 0.45–0.58 322 150–156 47–49 6.7× With a long warm-up (500 iterations,
-XX:-DontCompileHugeMethods), total goes from 343 ms (base) and 148 ms (a6a6716) to 41 ms. Buffer goes from 68.0 to 11.1 ms (6.1×) and classify from 236.5 to 29.5 ms (8×). The 500 warm-up iterations take 22 s instead of 163 s. The jar shrinks from 34.3 MB to 2.3 MB (23,418 → 1,181 classes), and one short run starts in 0.40 s instead of 0.95 s (a6a6716: 0.53–0.58 s).The view churn I described above for classify is gone.
coord_pos_relative_to_ringno longer decodes, registers and then flushes a view for everyCoordit reads. Memory-view frames are now in 18% of classify samples, down from about half. The weak references processed per young GC fell from ~660k to ~55k (52k–82k).In a JFR profile (1 ms sampling,
--warmup 10 --iterations 60), classify is now 64% of the samples and buffer 32%. Most of what is left in classify is the bounding-box pre-check, not the point-in-ring test.MultiPolygon: Intersects<Coord>callshas_disjoint_bboxesfirst.MultiPolygon::bounding_rectisget_bounding_rect(self.iter().flat_map(|poly| &poly.exterior().0)), so every query walks all 331 exterior coordinates. That walk is 71% of classify (inclusive), against 28% for the actual test. Every level of the iterator still calls into the runtime per coordinate:- innermost
next(Mono_68.next$m$7bain my jar):directStorageAggregate12.5%,commitStorageLocation9.0%; Flatten'sand_then_or_clear:loadTypedStorage8.6%,field7.8%,loadStorageLocation4.1%;FlatMap::next:projectStructField6.9%;get_bounding_rectitself:loadScalarField7.5%.
So iterating a
&Vec<Coord>throughflat_mapnow costs more than the geometry. In buffer, 60% of the samples are in the runtime (63% witha6a6716). Its largest entry points are nowloadLocationBits(9.4%) andprojectStructField(8.7%, down from 14%).- innermost
You asked whether anything could be better still. Here is where the
48f2727profile points, in the order I'd expect the most from. It's the same JFR recording as in my last comment, and percentages are of classify samples unless noted.-
Iterator state behind a field cell, about half of classify. In the bounding-box walk from my last comment, the
slice::Iterbeing advanced isFlatten'sfrontiter. Sonext's&mut selfis aPointerto a field of the enclosingFlatMap, aFieldCell, and every access to the iterator goes through that cell:slice::Iter::nextresolves the iterator object twice per element, once to read and once to write back:directStorageAggregate→directAggregate→directCellValueOrSelf→FieldCell.get. ThencommitStorageLocation→commitMemoryViewwalks the cell's owners again (commitOwners). Together that's 21.5%.Flatten::and_then_or_cleargoes throughloadTypedStorage→readElement→FieldCell.getandloadStorageLocation→getObjectAs→getObjectAsSlow→FieldCell.get. Together that's 20.5%.FlatMap::nextadds 6.9% inprojectStructField.
FieldCell.getisaccess.getter.invokeExact(owner), with the getter held in an instance field, so HotSpot can't inline it.Invokers$Holder.invokeExact_MTalone is 16% of classify, almost all of it inside the two methods above.As far as I can see there are two levels of fix:
- Make the field access inlinable: a constant
MethodHandleorVarHandleper field, or a directgetfieldwhere the owner class is known at the call site. The generated code already doescheckcast+getfieldon its fast path. - Better, scalar-replace iterator adapters that don't escape the loop (
FlatMap,Flattenandslice::Iterhere), so that their fields become JVM locals. LLVM does that natively, and iterator chains overVecs are everywhere in typical Rust code.
-
The flush takes a lock before it knows there's nothing to flush, 8.5% of classify.
flushMemoryViewsOverlappingruns before the scalar loads incoord_pos_relative_to_ringandget_bounding_rect. Its first check (directCellHasNoMemoryViews/mayBeInIdentityFilter) doesn't rule out views for the ring'sVec<Coord>. So it enterssynchronized (atomicStripe(this)), and only inside the lock doesMEMORY_VIEW_ABSENCEfind there is nothing to do. All 122 classify samples under the flush are inatomicStripe/atomicStripeIndex, and none in the locked part.Two possible fixes:
- Check the absence cache before the
synchronized, if the epoch can be read safely there. You'll know that better than I do. - Find out why the filter still says "maybe" for this allocation.
Either should remove all of it.
- Check the absence cache before the
-
Lookups that could be resolved once per call site. These cost little in classify (about 3%) but more in buffer:
- In buffer, 60% of samples are in the runtime.
projectStructField(8.7% of buffer) still resolves class and field by name, mostly ini_overlay'slist_split.loadLocationBits(9.4% of buffer) comes mostly fromis_under_segment_order. - In classify,
sharedConstantandfieldAccessgo through aConcurrentHashMap.geton every call.
A static field,
ConstantDynamicorinvokedynamicper call site would turn these into constants for the JIT. - In buffer, 60% of samples are in the runtime.
For context: the bounding-box walk on every query is geo's algorithm, not something the backend introduces. Natively it is almost free, which makes it a good test of how iterator chains get lowered.
-
Thank you again! I've just pushed the next set of updates to
experimental2that I was working on today which should make it even faster again. It's ~11ms after long warm-up in my testing (though your device may differ). If you could test and maybe some suggestions again (again) I'd really appreciate it! I really do think with some more improvements we should be really get closer to native runtime, prehaps closer than Chicory.Re-ran the benchmark against the new head
99ff1bd, with base5ed31a3and48f2727measured again in the same session. Results are identical to native in every run, and I can confirm your number: after the long warm-up the total is 9.1 ms here.--points 20 --queries 1000 --warmup 10 --iterations 30, all variants run alternately, two rounds each:median [ms] native base 5ed31a348f272799ff1bdvs 48f2727vs base generate 0.001 0.84 0.39–0.41 0.48–0.49 0.8× 1.7× buffer 0.073–0.096 73–74 16.0–16.5 8.5–8.9 1.9× 8.5× classify 0.37–0.46 257–262 28.9–31.0 5.2–6.1 5.6× 46× total 0.44–0.56 331–345 45.7–48.1 14.6–15.3 3.1× 22× With the long warm-up (500 iterations, 100 measured,
-XX:-DontCompileHugeMethods):median [ms] native base 5ed31a348f272799ff1bdvs 48f2727vs base generate 0.001 0.764 0.355 0.148 2.4× 5.2× buffer 0.073 68.7 11.0 4.34 2.5× 16× classify 0.373 264.0 30.1 4.60 6.5× 57× total 0.447 336.8 41.5 9.09 4.6× 37× That's about 20× native, down from 93× at
48f2727. Chicory runs the same program (compiled towasm32-wasip1) at 1.13–1.14 ms, so the gap to it went from 36× to 8×. The 500 warm-up iterations take 5.5 s, against 22 s for48f2727and 162 s for the base. The jar is 2.2 MB (1,077 classes, down from 1,181), and one short run starts in 0.34 s instead of 0.40 s (base: 0.98 s). The only thing that got slower isgeneratein the short configuration; it needs more warm-up now and is 2.4× faster than before once warmed up.Both suggestions from my last comment show up in the profile. The
FlatMap/slice::Iterchain in the bounding-box walk is gone (get_bounding_rectis now one loop with aloadScalarFieldper coordinate). The flush no longer takes a lock:flushFilteredMemoryViewsreturns on its epoch check. In buffer,projectStructFieldhas been replaced byprojectResolvedField(3.5% of buffer, down from 8.7%).Profile at
99ff1bdJFR, 1 ms sampling,
--warmup 10 --iterations 400(3,132 samples).countis now inlined intorun_once, so classify shows up as its two parts:part share of samples in runtime support buffer 44% 70% classify: point-in-ring test ( calculate_coordinate_position)27% 87% classify: bounding-box pre-check ( has_disjoint_bboxes)23.5% 64% GC is no longer a factor: 16 young collections in 5 s for 410 iterations, 55 ms of pauses in total.
The memory-view check on every element read, about 30% of classify
The top self-time entry in both parts of classify is
flushFilteredMemoryViews: 49% of the point-in-ring samples and 34% of the bounding-box samples. It is called per element from two places:ownedSliceOffset, behind theinvokedynamiccall site incoord_pos_relative_to_ring, once for every ring coordinate;loadUnsignedAt, underloadScalarFieldinget_bounding_rect, for everyxandy.
JFR attribution inside inlined code isn't fully reliable (it also gives
ownedSliceBytes, a cast and a field read, 28.5%), so I checked this with an instrumented copy of the runtime and two variants:- Counted: per 1,000 queries, classify calls the flush 308k times via
ownedSliceOffsetand 391k times vialoadUnsignedAt. More than 99% return on the epoch check, and none of them ever finds a view to write back. - Plain read: reading the epoch with
getPlaininstead of the volatilegetchanges nothing. - No flush: removing the flush call at just those two sites (only as an experiment, I know it's not a valid change) gives, with the long warm-up, three rounds alternating with the unmodified jar:
median [ms] 99ff1bdflush removed at those two sites buffer 4.25–4.37 4.03–4.11 classify 4.61–4.86 3.22–3.38 total 9.09–9.38 7.41–7.64 So the check itself costs about 30% of classify and about 20% of the total, not because of the volatile read but because it runs on every element of a hot loop. Without it, classify would be about 9× native instead of 12×.
You'll know better than I do what is safe here, but two directions:
- Decide it once per slice instead of per element: when the loop over the ring starts, check once that the allocation has no memory views, then read without checking. That needs either a guarantee that nothing in the loop body can create a view of that allocation, or a cheap re-check that the compiler can hoist.
- Decide it statically: an owned
Vec<Coord>that is only ever read by value (ownedSliceOffset's fast path) or by scalar loads might never get a view at all, and then the backend could emit the read without the call.
Buffer
Buffer has no single hotspot any more. 70% of its samples are in the runtime, spread over many entry points:
loadLocationBits9.3% (fromi_overlay'slist_split,cross,retain_mut,insert_tailand others, none above 3%),directStorageAggregate6.5%,loadStorageLocation4.8% (find_contour),getObjectAs4.3% andcommitMemoryView3.8% (both mostlylist_split),projectResolvedField3.5%. The same flush check is the largest self-time entry here too, at 7.4%, but removing it at the two sites above saves only ~0.25 ms of buffer.I think I found a problem, Dr. Palmer. You left a bullet in his head!
So I was playing with a compiled project trying to do something useful with it. By the way, it took me a while to find a compiler able to comprehend what's going on... Fernflower gives up. And for some reason IDEa is refusing to open
org.rustlang.alloc.string.String.Anyway, here's what the native code looks like:
FontCollection::new(true, true, vec!["~/Downloads/custom_fonts".to_string()])
And, ugh...
fun main() { val vec = Vec_alloc_string_String_alloc_alloc_Global.new() val path = org.rustlang.alloc.string.String.new() "~/Downloads/custom_fonts".toCharArray().map { it.code }.forEach(path::push) vec.push(path) FontCollection.new(true, true, vec) }
This would probably work?
Separate issue, the code displays errors:Cannot access 'SpecNewImpl$6d60894fca089f47' which is a supertype of 'String'. Check your module classpath for missing or conflicting dependencies.. Not sure what's that about, perhaps it doesn't likenewin a package name. It compiles (with compiler memlimit extended to 4g), at least.That gave me an idea to see how Vecs are implemented. And, ugh... Here we go.
pub struct Vec< T, #[stable(feature = "allocator_api", since = "CURRENT_RUSTC_VERSION")] A: Allocator = Global, > { buf: RawVec<T, A>, len: usize, } #[allow(missing_debug_implementations)] pub(crate) struct RawVec<T, A: Allocator = Global> { inner: RawVecInner<A>, _marker: PhantomData<T>, } #[allow(missing_debug_implementations)] struct RawVecInner<A: Allocator = Global> { ptr: NonNull<u8>, /// Never used for ZSTs; it's `capacity()`'s responsibility to return usize::MAX in that case. /// /// # Safety /// /// `cap` must be in the `0..=isize::MAX` range. cap: Cap, alloc: A, } type Cap = core::num::niche_types::UsizeNoHighBit; define_valid_range_type! { // ... pub struct UsizeNoHighBit(usize is 0..=HALF_USIZE); // ... }
... you see the issue, right? NonNull is a Pointer; allocator, ugh, exists; UsizeNoHighBit is a concrete jvm object... And it's all like that. All stdlib relies on an architecture being raw-pointer, but we have objects here. So rust stdlib tries to safely lower vectors and everything to pointer operations, and then rustc_codegen_jvm tries to make sense of that in high-level jvm. One might argue, Chicory does the same, but the truth is it really doesn't -- low-level operations stay low-level by heavy use of VarHandles and other close-to-hardware things, and they are never get exposed to the end user. So unfortunately I don't see big performance improvements with current state of things.
I understand that it may sound as an overkill, but I would suggest not trying to compile stdlib with the same logic as everything else, but instead write an entire substitutory stdlib in JVM. This, I believe, will both improve the performance and the ffi friendliness.
Also, I've investigated how allocator works on your Pointer API, and I don't see it blazing much faster, because all these concurrent map operations are really taxing on cache lines. I would suggest spitting support for different javas: on earlier versions use
sun.misc.Unsafeto allocate and operate memory segments, on more recent there's Panama FFI (it doesn't havegrowanalog out of the box, but I think relying onreallocbeing linked at jvm runtime is a valid assumption). The current Pointer impl can still remain as a "sanitizer" though.I'm sorry my contributions so far are mostly yapping, I'd do more but I don't know Rust much... With Java, however, I might, so let me know if you're interested
I thought I could elaborate more on what I mean by implementing entire stdlib in jvm. In Rust, drop glue is essential to not leave resources behind. However, in JVM "memory is not a resource"^TM, so having drops all around isn't usual. For example, you don't need to free space when you no longer need a List, you just abandon a ref to it, GC will eventually collect the list and then the underlying array. The exception, of course, would be resource pools: when you have a List of resources: threads, connections, file streams etc -- in which case of course you have to close them manually. That's what Closeable is usually for.
Honestly, some part of me, when I read about struct->object and other mappings, somewhat expected Vecs to be compiled to just Lists. Now that I've sat on the thought for a while, I'm not entirely sure now it's possible (because of ownership and all that), but it would be a huge improv for interop if you can pull this off, or at least generate a synthetic bridges for functions. The same goes for conversion between all sorts of Rust strings and java String or CharSequence (for immutable) and StringBuilder (for mutable) ones.
After a long time of silence I evaluated rustc_codegen_jvm (
5ed31a3) again on a real-world crate:geo0.33 buffering a line string and doing point-in-polygon tests. The results are identical to native in every run, including thei_overlaybuffer construction. Very impressive!Performance is about 700× native. It's not the JVM: a line-by-line Java port of the kernel runs at 1.5× native, and the same program compiled to Wasm and run through Chicory on the same JVM reaches about 3× native. Profiles put ~90% of the time in
org.rustlang.runtime, mainly memory views (field reads through&TintoVec/Boxstorage decode and register whole structs),projectStructField's by-name lookups andRange::nextallocations.The attached patch (~220 lines) lowers primitive field reads through shared references to
Freezetypes to a single scalar load at a constant offset. It makesbufferandclassify2× faster, andpython3 Tester.py --releasepasses.The attached zip has the full write-up (
geo_buffer_bench/docs/FINDINGS.md), the patch, the benchmark and the probes, with commands to reproduce everything.This analysis was conducted with the help of Claude Opus 5.5.