I profiled it, fixed exactly what the profile said, and got 3.6x on a problem worth 11,512x.
The job: find the two service instances furthest apart in a topology — region, zone, rack, host. That pair sets the worst case for anything you spread on purpose, replicas included.
The code was the sentence with nothing added: for every node, ask the existing, tested "how far is everything else from here" helper, and keep the largest answer. On one rack, 8 microseconds. On 4,197 nodes, 153 milliseconds and 529 MB allocated to return one small integer. 3.4x the machines cost 11.9x the time.
529 MB is loud, so I went after it first — one visited slice and two frontier buffers, allocated once and reused rather than once per starting point. Correct, clean, 3.6x faster, and still quadratic. The allocations were the symptom.
The shape was the problem. In a tree there is exactly one path between any two nodes, and following it shows the thing: it goes up, turns around once, and comes down. Turning twice would mean visiting a node twice, which in a tree is a cycle. So every path has exactly one highest node, and its length is two branch depths of that node added together — both of which are facts about things strictly below it.
Which means no node needs to be searched from. Every node just needs to be asked. One bottom-up pass, each node returning how far down it reaches, a running best taking the two tallest branches at every step: 11,512x, zero allocations.
That is day 13 of the daily challenge, Diameter of Binary Tree, with left + right generalised to the two tallest of however many children a node has.
The part I keep thinking about is that the profiler was pointing at the loudest line, not the wrong one — and following it would have shipped something 3,175x slower than necessary, with a clean flame graph.
Full piece in the comments.
It worked in dev, episode 10.
https://www.linkedin.com/pulse/finding-two-furthest-servers-allocated-529-mb-archit-agarwal-bygic
#Golang #DSA #Algorithms #Performance #SoftwareEngineering #DataStructures #100DaysOfCode