perf(builtins): optimize listToArray implementation and costing#7468
perf(builtins): optimize listToArray implementation and costing#7468
Conversation
Improve listToArray builtin performance and costing precision: - Use Vector.fromListN instead of Vector.fromList to allocate exact array size upfront, avoiding incremental resizing overhead - Implement batched ExMemoryUsage for lists that processes spine in chunks of 100 elements for more efficient cost computation - Expand benchmark coverage to 1-5000 element lists for better cost model fitting across a wider range of input sizes
Update listToArray cost model based on new benchmark results. The new implementation has lower base cost (intercept: 1000 vs 307802) but higher per-element cost (slope: 24619 vs 8496), reflecting the optimized algorithm that processes elements more efficiently with lower overhead.
Add interactive cost model visualization pages for the three array builtin functions: ListToArray, LengthOfArray, and IndexArray. Each page displays benchmark data alongside fitted cost model predictions, following the established pattern for existing function visualizations.
Update expected CPU budgets for listToArray conformance tests to reflect the updated cost model parameters (lower intercept, higher slope).
|
effectfully
left a comment
effectfully
left a comment
There was a problem hiding this comment.
The data here still only shows lists of lengths up to 100? And the formula is the old one?
plutus-core/plutus-core/src/PlutusCore/Evaluation/Machine/ExMemoryUsage.hs
Outdated
Show resolved
Hide resolved
plutus-core/plutus-core/src/PlutusCore/Evaluation/Machine/ExMemoryUsage.hs
Outdated
Show resolved
Hide resolved
How could the slope increase so dramatically? These numbers imply that for |
Its important to use proper branch in the data source: The link in the PR description does specify the branch to use, so if you follow that link it should be set automatically. |
The old benchmark only tested lists up to 100 elements, so the high intercept (307802) was compensating for an underestimated slope. With 1-5000 elements, the regression captures the actual per-element cost. Break-even is around n≈19, so yes, longer lists cost more than before, but that's because the old model was undercharging by extrapolating from too little data. |
Extract Peano numbers, NatToPeano type family, and static unrolling utilities into a dedicated module. This consolidates type-level machinery for compile-time loop unrolling previously duplicated in StepCounter. Provides Drop class for statically unrolled list operations and UpwardsM class for statically unrolled effectful iteration.
Remove duplicated Peano, NatToPeano, and UpwardsM definitions from StepCounter and import them from PlutusCore.Unroll instead. Reduces code duplication while maintaining identical runtime behavior.
Replace splitAt with dropN in the ExMemoryUsage instance for lists. The dropN function uses compile-time instance resolution to unroll the drop operation, avoiding tuple and prefix list allocation that splitAt requires.
…timation - Changed the slope value from 24619 to 24838 in builtinCostModelA.json - Changed the slope value from 24619 to 24838 in builtinCostModelB.json - Changed the slope value from 24619 to 24838 in builtinCostModelC.json
Adjust budget expectation for listToArray-02 test case to reflect the updated CPU slope in the cost model (286671 → 288642 cpu).
Unisay
force-pushed
the
yura/list-to-array-improvements
branch
from
8ce3c78 to
baf0499
Compare
Match R's models.R which uses Opaque (Nop*o) benchmarks for overhead calculation. The JS visualization was incorrectly using Nop*b pattern.
These values were incorrect since commit 69cb3d9. Regenerated using generate-cost-model tool from current benching-conway.csv data.
I was confused by this as well, and the link in the PR description is only displaying sizes up to 100. It looks as if it's still displaying the old data because the new data doesn't have many points with x <= 100. Maybe I've missed out some step? |
5 participants
Context
listToArraybuiltin implementation and update cost model parametersApproach
This PR makes two key optimizations to the
listToArraybuiltin:1. Implementation Optimization: Changed from
Vector.fromListtoVector.fromListNwhich avoids repeated array resizing during conversion. Since we already traverse the list to calculate memory usage, we know the length upfront and can allocate the exact size needed.2. Memory Usage Costing: Changed list memory costing from eager full-spine traversal to batched incremental costing. Instead of computing
length lupfront (which forces the entire list spine), we now process the list in batches of 100 elements, producingCostRosenodes incrementally. This is more efficient for large lists while maintaining accurate costing.The benchmark range was also expanded from 1-100 to 1-5000 elements to capture the linear cost behavior across a wider range of inputs, resulting in updated cost model parameters (lower intercept, higher slope).
Changes
Core Implementation
Vector.fromListNinstead ofVector.fromListfor more efficient array allocationCostRosetree structureCost Model Updates
listToArrayCPU cost parameters based on new benchmarksindexArrayandlengthOfArrayCPU costs (were stale since 69cb3d9)Cost Model Visualization Fix
Nop*opattern (matching R's models.R)Cost Model presented visually
https://plutus.cardano.intersectmbo.org/pr-preview/cost-models/pr-7468/listtoarray/index.html?branch=yura%2Flist-to-array-improvements
Benchmarking
Documentation
ListToArray(linear cost model)LengthOfArray(constant cost)IndexArray(constant cost)How to Test
Implementation Testing
cabal test plutus-core-testCost Model Verification
cd doc/cost-models && python -m http.server 8000Benchmark Reproduction
Author's Checklist
Vector.fromListNindexArray/lengthOfArraycost models