Caching

[johansten]

Caching between calls

Currently there's no caching, as the tree traversals are dependent on the destination amount provided, and amounts are not very likely to be re-occur across calls from different users, while the results are still valid. Within each call there's a bit of dynamic programming, used to skip traversal of sub-trees that are known to be pointless, but that's it.

If we look at each source asset in a search individually, we can rewrite

findPaths([source1, source2, ...], destination, amount)

as

[
	findPath(source1, destination, amount),
	findPath(source2, destination, amount),
	...
]

where findPath will search for the cheapest path going from one asset to another asset, for a specific amount.

The majority of accounts only hold XLM, so most path finding calls will be either from or to XLM.

A large part will be both, but these are trivial, assuming we're not going to spend any effort of looking for arbitrage opportunities:

findPath(asset, asset, amount) = ([asset, asset], amount) // (path, cost)

Cost Functions

We define the cost function, cost_A,B(x), to be the amount of units of A it takes to buy x units of B

The cost function is calculated by taking the sell-side orders from B to A, ordering them according to their price, as a step function, and integrating.

​ cost_A,B(0) = 0

​ cost_A,B(x₂) > cost_A,B(x₁), if x₂ > x₁

​ cost'_A,B(x₂) ≥ cost'_A,B(x₁), if x₂ > x₁

It's a monotonically increasing function, it's a piecewise linear function

Comparing costs vs. comparing cost functions

Instead of comparing costs on an individual basis at specific points, what if we compared cost functions with each other across their entire domains?

If possible, we would be able to break out the amount parameter from findPath, and cache the full result until an order modifies order books along the path.

findPath(source, destination) would basically return a list of amount ranges, and the best path within each range.