There seems to be a lesson here about the balance between premature vs. anticipatory optimization. We’re generally warned against premature optimization but perhaps, as a rule of thumb, we should look for optimizations in frequently-called functions that are obvious and not onerous to implement.
How we decreased GitLab repo backup times from 48 hours to 41 minutes
41–50 of 273 posts
Re: How we decreased GitLab repo backup times from 48 hours to 41 minutes
#42Earlier quoted context omitted.
Thank you. (I don't think that anyone should use "exponentially" that way: it is an art term with a specific and particular meaning, so find another word if you mean something else! Like misusing specific legal or sporting terms...)
Art term?
Re: How we decreased GitLab repo backup times from 48 hours to 41 minutes
#43Well done, next maybe make the web ui usable because right now there’s absolutely no distinction between the UI itself and the user content, which IMHO combined with action buttons in the middle of the page makes for a really poor ux.
Re: How we decreased GitLab repo backup times from 48 hours to 41 minutes
#44Re: How we decreased GitLab repo backup times from 48 hours to 41 minutes
#45IME, it has always turned out to be the correct decision to eliminate any n^2 operation in anything I’ve written. I don’t write exotic algorithms, but it’s always astounding how small n needs to be to become observably problematic.
Good call. O(N^2) is the worst time complexity because it's fast enough to be instantaneous in all your testing, but slow enough to explode in prod.
I've seen it several times before, and it's exactly what happened here.
Re: How we decreased GitLab repo backup times from 48 hours to 41 minutes
#46looks like the commit is here: https://github.com/git/git/commit/a52d459e72b890c192485002ec...
Thanks, this helped me find the submission and related discussion thread - https://lore.kernel.org/git/20250401-488-generating-bundles-...
Re: How we decreased GitLab repo backup times from 48 hours to 41 minutes
#47"fixed it with an algorithmic change, reducing backup times exponentially" If the backup times were O(n^2), are they now O(n^2 / 2^n)? I would guess not.
This is not the precise mathematical definition of exponential, but rather the colloquial one, where it just means "a lot".
You shouldn't use a word that can carry a precise mathematical meaning in a sentence that literally uses mathematical notation in order to speak precisely and then expect readers not to interpret the word in the precise mathematical way.
Re: How we decreased GitLab repo backup times from 48 hours to 41 minutes
#48Cool discovery but the article could have been about 1/10 as long and still communicated effectively. At least they didn't post it as a video, so it was easy to skim to the important details.
Re: How we decreased GitLab repo backup times from 48 hours to 41 minutes
#49Earlier quoted context omitted.
https://en.wiktionary.org/wiki/term_of_art
Ah, thanks. I could only think of art as in literal, artistic art.
If you have that tendency, you just need to think of TAOCP, this industry's best distillation of intellectual achievement, with the word "art" in its name.
Re: How we decreased GitLab repo backup times from 48 hours to 41 minutes
#50I'm confused why you wouldn't simply snapshot the block-level device if the protocol of the information on top is going to cause this much headache. Quiescing git operations for block level activity is probably not trivial, but it sounds like an easier problem to solve to me.
This is the approach I've taken with SQLite in production environments. Turn on WAL and the problem gets even easier to solve. Customer configures the VM for snapshots every X minutes. Git presumably doesn't have something approximating a WAL, so I understand the hesitation with this path. But, I still think the overall strategy is much more viable and robust to weird edges within git.