How we decreased GitLab repo backup times from 48 hours to 41 minutes

Post by saagarjha » Sat, Jun 07, 2025, 11:06 AM UTC

throwaway2037 wrote: post #153

anttihaapala wrote: post #56

Earlier quoted context omitted.

This is not a complicated algorithm. A hash map (dictionary) or a hash set is how you would always do deduplication in Python, because it is easiest to write / least keystrokes anyway. That is not the case in C though, as it is much easier to use arrays and nested loops instead of hash maps.

> That is not the case in C though, as it is much easier to use arrays and nested loops instead of hash maps. I am confused. There are plenty of open source, fast hash map impls in C.

Post by masklinn » Sat, Jun 07, 2025, 11:15 AM UTC

morepedantic wrote: post #182

IshKebab wrote: post #71

Earlier quoted context omitted.

I would say C makes this sort of thing far more likely because it's usually a ton of effort to obtain suitable containers. In C++ or Rust they have plenty of things like `unordered_set`/`HashSet` built in, so people are much more likely to use it and not go "eh, I'll use a for loop". In this case Git already had a string set, but it's still not standard so there's a good chance the original author just didn't know ab…

I've seen this exact problem in C code many times in my life, especially in kernel space where data structures and memory allocations are fun. Ironically, this is much _faster_ for small sets. Sometimes the error is intentional, because the programmer believes that all inputs will be small. IME, those programmers were wrong, but that's the inverse of survival bias.

Post by ndriscoll » Sat, Jun 07, 2025, 12:14 PM UTC

sn9 wrote: post #134

hiddew wrote: post #6

"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.

The algorithm complexity went down in the function they patched (6x improvement in their benchmark), but in the context of how they benefited with how they were using the algorithm the impact was much larger (improved to taking 1% of the time), which is plausibly exponential (and figuring out the actual complexity is neither relevant nor an economic use of time).

Post by kevincox » Sat, Jun 07, 2025, 12:41 PM UTC

esprehn wrote: post #147

LgWoodenBadger wrote: post #18

IME, 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.

Modern computers are pretty great at scanning small blocks of memory repeatedly, so n^2 can be faster than the alternative using a map in cases for small N. I spent a lot of time fixing n^2 in blink, but there were some fun surprises: https://source.chromium.org/chromium/chromium/src/+/main:thi... For large N without a cache :nth-child matching would be very slow doing n^2 scans of the siblings to compute the index.…

Post by rovr138 » Sat, Jun 07, 2025, 1:38 PM UTC

MyFedora wrote: post #196

cvoss wrote: post #47

Earlier quoted context omitted.

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.

We simplify the big O notation in computer science. This is standard practice.