Breakwater

Codeflash / json_repair#113

⚡️ Speed up method ObjectComparer.is_same_object by 109%

mangiucugna/json_repair#113 · merged 2025-05-16 · base ec462b47b3 → head cbfa7a1c6f · ran on Sandboxes

BLOCK

The “faster” code does up to 363× the work on valid inputs, growing with input size (complexity regression).

Performance · ObjectComparer.is_same_object

Worst family with mostly valid inputs: 363.31× the instructions of base (swap position of the mismatched key within dict ordering).

head slowerhead faster0.5×1×2×4×8×16×32×64×1.3e+02×2.6e+02×1001,00010,000100,000input size (characters)R1R1: 1.26× at ~72 charsR1: 4.10× at ~176 charsR1: 30.48× at ~2,012 charsR1: 160.06× at ~32,636 charsR2R2: 0.36× at ~71 charsR2: 1.51× at ~175 charsR2: 14.32× at ~2,012 charsR2: 79.27× at ~32,636 charsR2: 363.31× at ~603,957 charsR3R3: 0.64× at ~43 charsR3: 1.07× at ~79 charsR3: 2.20× at ~318 charsR3: 3.00× at ~1,374 charsR3: 3.46× at ~6,221 charsR3: 3.66× at ~26,284 charsR3: 3.73× at ~118,444 charsR4R4: 0.36× at ~75 charsR4: 1.08× at ~143 charsR4: 1.37× at ~576 charsR4: 2.18× at ~2,319 charsR4: 1.37× at ~9,619 charsR4: 3.39× at ~39,680 charsR4: 1.29× at ~162,562 charsF4F4: 0.58× at ~16 charsF4: 0.58× at ~28 charsF4: 0.57× at ~112 charsF4: 0.56× at ~496 charsF4: 0.56× at ~2,344 charsF4: 0.58× at ~10,072 charsF4: 0.58× at ~46,936 chars
  • R1
  • R2
  • R3
  • R4
  • F4
Head/base cachegrind instructions per call, by input size (log-log). Each line is one input family Nemotron proposed; points above 1× are where the "faster" code does more work.
FamilyInputsRatio range Slope base → headVerdict
R1large dicts with identical length but one key swapped, and deep equal values on the shared keyssuspected slowdown · archive1.26× – 160.06×0.31 → 1.08complexity-regression
R2swap position of the mismatched key within dict orderingsuspected slowdown · archive0.36× – 363.31×0.34 → 1.08complexity-regression
R3Large dictionaries with same length but almost no common keyssuspected slowdown · archive0.64× – 3.73×0.74 → 0.95complexity-regression
R4Dicts with numeric string keys where only the first matchessuspected slowdown · archive0.36× – 3.39×0.77 → 0.92complexity-regression
F4large flat listsclaimed speedup · plan0.56× – 0.58×0.89 → 0.89faster

Receipt

TargetBackendImageRun AuditAdjudication
json_repair.object_comparer:ObjectComparer.is_same_objectToken Factory Sandboxes44ce7ab3-2490-4df1-96bc-08c7d76584d1bt-json_repair#113-ba5cd1$0.23$0.000

Nemotron cost on Nebius Token Factory. Backend: where the untrusted code ran. Token Factory Sandboxes (a microVM branched from a kept image, cited by its UUID). Every image is content-addressed (repo at each commit + harness), so every card re-runs from the image and seed 0. Raw data: audit.