I usually think of scaling in 3 methods: horizontal (add more machines), vertical (get a bigger machine) and inward (improve your algorithms).

The largest performance gains I've seen are most often of the inward type -- like multi-thousands of percent, just by rethinking the code or the approach.

Bonus, improving inward scaling multiplies investments in horizontal and vertical scaling.