Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

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

about.gitlab.com

Post reply on HN
Print view View original

181–190 of 273 posts

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

#181

Post by morepedantic »

sneak wrote: post #115
msgodel wrote: post #28

Earlier quoted context omitted.

I disagree. Misuse of the word "exponential" is a major pet peeve of mine. It's a particular case of the much more common "use mathematically precise phrasing to sound careful/precise" that you often find in less than honest writing. Here they are actually using it to refer to growth functions (which is rare for this error) and being honest (which is also rare IMO) but it's still wrong. They should have written about…

My personal pet peeve is when the term “exponentially” is used to refer to a change between precisely two data points. It’s a very specific subset of the one you’re describing. “Tell me you don’t know what you’re talking about without telling me you don’t know what you’re talking about.”

>My personal pet peeve

Just be glad you have only one.

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

#182

Post by morepedantic »

IshKebab wrote: post #71
pjmlp wrote: post #39

A very good example that writing code in C doesn't help for performance, when the algorithms or data structures aren't properly taken into consideration.

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.

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

#183

Post by SkiFire13 »

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

I have yet to finish the article, but this means they improved the complexity to something like O(logN), right? I hate when people confuse quadratic improvement for exponential ones.

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

#184

Post by DamonHD »

taftster wrote: post #96
DamonHD wrote: post #32

Earlier 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...)

Which term is appropriate here? What would you suggest? (honest question)

"hugely" or "a lot" or "to O(XXX)" whatever the new XXX complexity is.

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

#185

Post by globular-toast »

SkiFire13 wrote: post #183

> 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. I have yet to finish the article, but this means they improved the complexity to something like O(logN), right ? I hate when people confuse quadratic improvement for exponential ones.

Really annoying to see someone use exponential wrong when they're talking about performance of algorithms. We're supposed to know what this means! They went from quadratic to linear.

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

#186

Post by globular-toast »

IshKebab wrote: post #70
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.

You should if you expect your readers to be normal humans who understand obvious context, and not pedantic HN readers who understand obvious context but delight in nit-picking it anyway.

Ah yes because "normal humans" know what O(n^2) means but damnit they are going to use exponential wrong.

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

#187

Post by globular-toast »

blharr wrote: post #68
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.

I somewhat agree, but for lack of a better word, what would you use? Quadratically doesn't have the same punch

Runtimes dropped precipitously.

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

#189

Post by endgame »

hinkley wrote: post #164
dieortin wrote: post #119

Earlier quoted context omitted.

They’re too ridiculous… unless a more optimal solution does not exist

Absolutely not. If the cost of doing something goes above quadratic, you shouldn't do it at all. Because essentially every customer interaction costs you more than the one before. You will never be able to come up with ways to cover that cost faster than it ramps. You are digging a hole, filling it with cash and lighting it on fire. If you can't do something well you should consider not doing it at all. If you can on…

I feel this is too hardline and e.g. eliminates the useful things people do with SAT solvers.
Post reply on HN