ShadeSwap router performance upgrade and fixes

It was often reported in the past that ShadeSwap routing does not always select the best route. In the past such reports were mostly attributed to the gas optimization feature working as expected and selecting a seemingly disadvantageous route because the router by design takes into account the gas price for the swap execution.

However, one day in late 2024, thanks to a detailed report by a community member (shout-out to Afrolicios), we were finally able to reproduce a more concerning issue with swap routing. It was discovered that some routes do not ever appear in the routes selection even though they are obviously best. The most notable example I can think of is SCRT -> USDC was not routing through SCRT -> stkdSCRT.

tldr; We fixed swap routes not always being correct and also improved performance by x15, making the app feel MUCH smoother.

Read below to learn the details about about the swap route fix journey

A couple of weeks later, the issue was fixed and the swap router was now including all routes when selecting the best of them. The problem in simple terms, was that the router was acting a bit “optimistically” and would stop finding more routes once it had found “enough” good routes. While this is Ok most of the time, when volatility rises, the most liquid routes are not always the ones that provide the best swap outcome. And that is what users noted at certain times and what made it difficult to reproduce when the volatility subsided.
Along with fixing the route selection bug, we noted that the performance of the swap calculations has now degraded and the app didn’t feel as snappy as it used to. That was easily explaned by the fact that the router now did more calculations than it previously did. It now had to go through every possible route and not just stop in the middle once it had calculated “enough”.
What followed was a long side-quest to squeeze out the maximum performance from the client side routing. The end result is a swap router that is now on average 15x faster.

Here is a detailed follow-up explaining those optimizations for the more technically minded persons:

The first thing we did was to do a CPU profiling on the swap routing in order to discover where the processor spent most time when calculating the best swap. It was quickly discovered that a simple javascript function (Object.entries) was called on the object that holds all the LP pairs. This function alone was responsible for more than half of the CPU time that was used, when routes are calculated.

It is humbling to be reminded that modern languages make code so much easier to write, but they also abstract away a lot of complexity. We always need to be aware of that and think about what is actually happening under the hood.

The fix for that was simple. First we needed to make sure our code no longer used recursion when finding all possible routes. Depth-first search is easily implemented using recursion but that leads to many issues, especially when it comes to reusing variables. So DFS was converted to a simple iterative approach and the expensive Object.entries was now only called a single time. Also a neighborhood matrix was built and reused during the lifetime of the app as a further optimization.
This alone lead to a huge boost of around 10x. It also meant that the app can now calculate all possible routes without this having a huge impact on the UI.
However the app still didn’t feel that snappy. While this first fix increased performance by x10, the previous fix increased the number of calculated routes by almost as much. In the end the app had very similar performance as before and be slower or faster depending on the route. So we thought we should do better and contunud further.

During our research, it was noticed that StableSwap calculations took disproportionately longer time to calculate compared to normal swaps. It is well known that the unique stable swap function that Shade uses is computationally expensive, so this was not a big surprise. Still, after further digging, we found out that the invariant calculation for a particular StableSwap pool would be called whenever it was needed and the same calculation could be performed a bunch of times when calculating the best swap. This was a huge waste of CPU time.
We rewrote a big portion of the swap router logic to allow for those calculations to be calculated only once and “remembered” so to be reused.
This had a noticeable impact, but the final nail in the coffin was to completely rewrite the route finding algorithm and do every possible calculation only once.

This can best be explained with an example.
Let’s say a user wants to swap A to B and they have several options:
A -> D -> C ->B
A -> D -> B
A -> B
We can see that the segment A -> D appears twice. That means A -> D could technically be calculated only once and the result could be reused in two of the three routes. However, the way our algorithm worked was first to discover all possible routes and then to calculate each one of them. On the other hand, we also know from the way DFS works, that A -> D segment is only visited once when the initial discovery is done. So the only thing we needed to do was calculate that route once when it was first discovered. That would naturally fix the issue with multiple calculations. It also lead to a massive code simplification. This brings me to another nice reminder about writing code.

Efficient code doesn’t always look pretty or feel intuitive.

What I mean here is, there is a big difference in how our natural human thought works and what is most efficient in terms of processing. The way we go about thinking when we need to calculate the possible routes in our mind would be to first “discover routes” and then “calculate” each of the discovered routes. However, in practice, it turns out it is best to think about “discovery” and “calculation”, both as “visiting”. From there to be the most efficient in our pathfinding, we only want to “visit” once and never “go back” to the same point twice which is what we do when we separate discovery from calculation.
In conclusion, it was great to work on these performance upgrades. Programming is not just about aligning buttons, building beautiful UI (which is a big art in itself), but it is also about finding the most efficient way to solve complex problems. Often the most natural way a human thinks about a problem is not the most efficient, and it’s great to be reminded about that simple fact.
The Shade team has a plan to release a library that deal with the problem of client side routing to be used by the community. For now enjoy the blazing fast swap calculations in the app.

4 Likes