“Ultimately, we traced the issue to a 15-year-old Git function with O(N²) complexity and fixed it with an algorithmic change, reducing backup times exponentially.”
A nested loop added to Git in 2009 took 80% of the runtime on repos with many refs. Swapping it for a map cut GitLab’s own backup from 48 hours to 41 minutes. The fix went upstream, so everyone gets it. The post calls an O(N²) fix exponential, which is the wrong word.