opshin icon indicating copy to clipboard operation
opshin copied to clipboard

Optimization: Fast List Traversal

Open nielstron opened this issue 1 year ago • 0 comments

Is your feature request related to a problem? Please describe. List accesses in uplc are linear in n. While you can not reduce the number of tailList operations, you can reduce the number of index comparisons to reduce the cost of execution.

Describe the solution you'd like A similar to solution to list_at_index could be implemented in the opshin implementation of list[x]. The step size could be configurable but likely 5 is a good heuristic for most data that is on-chain.

Describe alternatives you've considered None

Additional context This could go together with #168 in one of the higher optimization levels.

Bug bounty: 700 ADA

nielstron avatar Feb 07 '24 14:02 nielstron