This PR uses the staking script optimization suggested by @micahkendall. It increased the number of price updates that could fit in a single transaction by 5x (5 -> 24).
I also tried using the optimization for swap executions but that came with some drawbacks. For starters, the current implementation has very little redundant executions. In pseudocode, this is effectively what happens:
for i in inputs;
for o in outputs;
if o corresponds to i;
check the swap is valid;
else;
continue to next o;
The key takeaway here is that the outputs will be traversed until the corresponding swap output is found. But this still means the outputs are partially traversed for each input. The only possible optimization is to eliminate the extra traversals of the outputs.
The only way to do this (even with the staking script) is to have the outputs exactly lined up with the inputs. For example, the first swap output must correspond to the first swap input, the second swap output must correspond to the second swap input, etc. If the swaps are not ordered properly, the transaction is guaranteed to fail. The current swap implementation is order agnostic.
The resulting performance increase by using this optimization for swap execution was basically 14 -> 17 swaps per transaction. In other words, only three additional swaps were possible in the transaction. Again, this is because the current swap execution implementation already has very little redundant executions. So the trade-off is effectively: require the outputs to be ordered precisely for an additional 3 swaps per tx.
IMO the benefit is not worth the cost. The main issue is that maximum, trustless composability requires the logic to be as local as possible. In other words, the transaction's validity should depend on the swap itself and nothing more. Not following this requirement can break the composability of Cardano-Swaps (or make it hard to reason about). For example, what if there was another DApp that required the outputs to be ordered differently? If swap outputs must be ordered precisely based on inputs (whose ordering is not controllable), that DApp would not be able to compose with Cardano-Swaps. This would be a major loss for only a 3 swap/tx gain.
If it is absolutely necessary to get that extra bit of performance, I can add another redeemer for using this method; that way both approaches are still possible. But I don't want to add this unless absolutely necessary, and ideally, I want to wait until after plutus v3 is released (it may offer better approaches). As it is, I don't think the current performance bottleneck to Cardano-Swaps is swaps/tx; I think it is the collision risk of trying to use a swap that has been claimed by another arbitrager. Using 10 swaps per tx is already very risky due to the collision risk.
The above drawbacks do not exist for price updates since the staking script optimization can provide a major throughput increase for this action without requiring outputs to be ordered in a certain way.
Other optimizations in this PR:
Instead of parsing the datums of each outputs to compare the individual fields to the swap input's datum, the swap input is used to create the exact datum that is required by the corresponding output, then this datum is compared against the output datums without having to parse them.
Moved away from using Rational internally since simple things, like comparisons, require additional arithmetic that simply isn't necessary for this use case.
Moved away from using Value internally for determining which assets were taken/deposited. Value has a lot of invariants that are checked at run-time and these checks use up a lot of memory. This change accounts for the vast majority of the performance gains in swap executions from this PR.
Summary
These changes only increased performance. Benchmark highlights:
Action
Before -> After
Executing Swaps
14 -> 25
Updating Swaps
5 -> 31
This PR also includes UX improvements for both the smart contracts and the CLI.
This PR uses the staking script optimization suggested by @micahkendall. It increased the number of price updates that could fit in a single transaction by 5x (5 -> 24).
I also tried using the optimization for swap executions but that came with some drawbacks. For starters, the current implementation has very little redundant executions. In pseudocode, this is effectively what happens:
The key takeaway here is that the outputs will be traversed until the corresponding swap output is found. But this still means the outputs are partially traversed for each input. The only possible optimization is to eliminate the extra traversals of the outputs.
The only way to do this (even with the staking script) is to have the outputs exactly lined up with the inputs. For example, the first swap output must correspond to the first swap input, the second swap output must correspond to the second swap input, etc. If the swaps are not ordered properly, the transaction is guaranteed to fail. The current swap implementation is order agnostic.
The resulting performance increase by using this optimization for swap execution was basically 14 -> 17 swaps per transaction. In other words, only three additional swaps were possible in the transaction. Again, this is because the current swap execution implementation already has very little redundant executions. So the trade-off is effectively: require the outputs to be ordered precisely for an additional 3 swaps per tx.
IMO the benefit is not worth the cost. The main issue is that maximum, trustless composability requires the logic to be as local as possible. In other words, the transaction's validity should depend on the swap itself and nothing more. Not following this requirement can break the composability of Cardano-Swaps (or make it hard to reason about). For example, what if there was another DApp that required the outputs to be ordered differently? If swap outputs must be ordered precisely based on inputs (whose ordering is not controllable), that DApp would not be able to compose with Cardano-Swaps. This would be a major loss for only a 3 swap/tx gain.
If it is absolutely necessary to get that extra bit of performance, I can add another redeemer for using this method; that way both approaches are still possible. But I don't want to add this unless absolutely necessary, and ideally, I want to wait until after plutus v3 is released (it may offer better approaches). As it is, I don't think the current performance bottleneck to Cardano-Swaps is swaps/tx; I think it is the collision risk of trying to use a swap that has been claimed by another arbitrager. Using 10 swaps per tx is already very risky due to the collision risk.
The above drawbacks do not exist for price updates since the staking script optimization can provide a major throughput increase for this action without requiring outputs to be ordered in a certain way.
Other optimizations in this PR:
Rationalinternally since simple things, like comparisons, require additional arithmetic that simply isn't necessary for this use case.Valueinternally for determining which assets were taken/deposited.Valuehas a lot of invariants that are checked at run-time and these checks use up a lot of memory. This change accounts for the vast majority of the performance gains in swap executions from this PR.Summary
This PR also includes UX improvements for both the smart contracts and the CLI.