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

251–260 of 273 posts

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

#251

Post by hinkley »

ashishb wrote: post #40

O(n^2) is fast enough to end up I'm production and slow enough to cause problems at scale. The worst troublesome cases of inefficient production are almost always O(n^2).

Had a modular monorepo back when UML was still a thing people did. People were having trouble opening a TogetherJ project - it was taking 30 minutes. I dug into it, and I don’t recall how I timed it but I kept adding more submodules and the runtime went up ridiculously fast. I stopped at a project that took 18 hours to load. Started it before going home one day and timed it the next morning.

When I plotted the runtime, I got n^5 for the fitting curve. That’s the largest polynomial I’ve encountered in the wild. Second place has always been cubic.

Their response was that it had something to do with processing config files per module, and a suggestion to rearrange them as a workaround. They fixed the problem in the next patch and the load time went from 18 hours to a couple minutes.

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

#252

Post by hinkley »

judofyr wrote: post #2

See also: https://www.tumblr.com/accidentallyquadratic Quadratic complexity sits in an awkward sweet spot: Fast enough for medium-sized n to pass first QA, but doomed to fail eventually as n grows.

We have a habit of taking our eye off of old problems by trying to juggle several new ones. By the time someone notices that we have a problem, the dogleg in the graphs where the n² solution stopped fitting into the CPU cache has been obvious for months but nobody was looking, and we dance around that fact that we had time to take a reasonable approach to fix the problem if we had noticed it when it became measurable, by adding anxiety to the cleanup work.

And then someone learns from this experience, gets the bright idea to set up an alert for such things, but the alert doesn’t factor in things like customer base growth or feature creep slowly pushing up the expected runtime. Eventually organic load gets close to the alarm and then the fucking thing goes off on a three day weekend (why is it always a long weekend or just before one?) and then we wage war on alarm overreach and the whole cycle repeats itself.

We like to think of ourselves as blazing trails in the wilderness but most of the time we are doing laps around the parking lot.

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

#253

Post by hinkley »

Someone wrote: post #246
refulgentis wrote: post #150

Earlier quoted context omitted.

Considerably more than a few percent, IMHO. :) But I also don't dabble in this area nearly enough to know whether there's years of tears and toil finding out repeatedly that O(n) is ~impossible to implement and verify :) | n | n log n | | 5 | 8.0472 | | 10 | 23.0259 | | 25 | 80.4719 | | 50 | 195.6012 | | 100 | 460.5170 |

Depends on the constants and on the value of n . If the constant for the O(n log n) algorithm is five times that of the O(n) algorithm, the O(n) algorithm is faster for n . If you expect that n will always hold, it may be better to implement the O(n) algorithm and add a logging warning if n > 250 or so (and, maybe, a fatal error if n > 1000 or so), instead of spending time to write both versions of the algorithm and…

Fatal errors tend to blow up in production rather than test.

One of the simplest solutions for detecting cyclic graphs is instead of collecting a lookup table or doing something non-concurrent like marking the nodes, is to count nodes and panic if the encountered set is more than an order of magnitude more than you expected.

I came onto a project that had done that before and it blew up during my tenure. The worst case graph size was several times the expected case, and long term customers were growing their data sets vertically rather than horizontally (eg, ever notice how much friction there is to making new web pages versus cramming more data into the existing set?) and now instead of 10x never happening it was happening every Tuesday.

I was watching the same thing play out on another project recently but it got cancelled before we hit that threshold for anything other than incorrect queries.

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

#254

Post by hinkley »

Tepix wrote: post #242
hinkley wrote: post #164

Earlier quoted context omitted.

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…

So, how would you write a solver for tower of Hanoi then? Are you saying you wouldn't?

As a business? Would you try to sell a product that behaved like tower of Hanoi or walk away?

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

#255

Post by hinkley »

delusional wrote: post #239
hinkley wrote: post #222

Earlier quoted context omitted.

I read that as a typo given the next sentence. I’m on the fence about cubic time. I was mostly thinking of exponential and factorial problems. I think some very clever people can make cubic work despite my warnings. But most of us shouldn’t. General advice is to be ignored by masters when appropriate. That’s also the story arc of about half of kung fu movies. Did chess solvers really progress much before there was a…

> I read that as a typo given the next sentence. Thank you for the courtesy. > I think some very clever people can make cubic work despite my warnings. I think you're selling yourself short. You don't need to be that clever to make these algorithms work, you have all the tools necessary. Asymptotic analysis is helpful not just because it tells us a growth, but also because it limits that growth to being in _n_. If yo…

Right but back up at the top of the chain the assertion was that if n grows as your company does then IME you’re default dead. Because when the VC money runs out you can’t charge your customers enough to keep the lights on and also keep the customers.

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

#256

Post by [deleted] »

IshKebab wrote: post #232
hinkley wrote: post #212

Earlier quoted context omitted.

The first SAT solver case that comes to mind is circuit layout, and then you have a k vs n problem. Because you don’t SAT solve per chip, you SAT solve per model and then amortize that cost across the first couple years’ sales. And they’re also “cheating” by copy pasting cores, which means the SAT problem is growing much more slowly than the number of gates per chip. Probably more like n^1/2 these days. If SAT solver…

That's quite a contortion to avoid losing the argument! "Oh well my algorithm isn't really O(N^2) because I'm going to print N copies of the answer!" Absurd!

[deleted]

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

#257

Post by hinkley »

IshKebab wrote: post #232
hinkley wrote: post #212

Earlier quoted context omitted.

The first SAT solver case that comes to mind is circuit layout, and then you have a k vs n problem. Because you don’t SAT solve per chip, you SAT solve per model and then amortize that cost across the first couple years’ sales. And they’re also “cheating” by copy pasting cores, which means the SAT problem is growing much more slowly than the number of gates per chip. Probably more like n^1/2 these days. If SAT solver…

That's quite a contortion to avoid losing the argument! "Oh well my algorithm isn't really O(N^2) because I'm going to print N copies of the answer!" Absurd!

What I’m saying is that the gate count problem that is profitable is in m³ not n³. And as long as m I would argue that this is essentially part of why Intel is flagging now. They had a model of ever increasing design costs that was offset by a steady inflation of sales quarter after quarter offsetting those costs. They introduced the “tick tock” model of biting off a major design every second cycle and small refinements in between, to keep the slope of the cost line below the slope of the sales line. Then they stumbled on that and now it’s tick tick tock and clearly TSM, AMD and possibly Apple (with TSM’s help) can now produce a better product for a lower cost per gate.

Doesn’t TSM’s library of existing circuit layouts constitute a substantial decrease in the complexity of laying out an entire chip? As grows you introduce more precalculated components that are dropped in, bringing the slope of the line down.

Meanwhile NVIDIA has an even better model where they spam gpu units like mad. What’s the doubling interval for gpu units?

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

#258

Post by dfc »

Nemo_bis wrote: post #240
dfc wrote: post #234

Earlier quoted context omitted.

I dont know how you came to that conclusion. Just looking at the top 4 contributors over the last 2 years[1] it looks like one works for google(gitster), two work at Github and one works at GitLab(pks-t). [1]: https://github.com/git/git/graphs/contributors?from=6%2F3%2F...

I had looked at the monthly activity. Indeed on a longer timespan it looks different, thanks.

That's weird I looked at the monthly and did not see any Gitlab employees. Were you looking at a different repo?

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

#259

Post by EdwardCoffin »

johnisgood wrote: post #241
swyx wrote: post #238

Earlier quoted context omitted.

more from table please?

I would rather have the table and related content. Name of the book?

It's probably The Algorithm Design Manual 2ed by Steven S. Skiena, figure 2.4

The second table on this [1] page is pretty similar, though not the same.

[1] https://a1120.cs.aalto.fi/notes/round-efficiency--bigoh.html

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

#260

Post by nayak »

dfc wrote: post #258
Nemo_bis wrote: post #240

Earlier quoted context omitted.

I had looked at the monthly activity. Indeed on a longer timespan it looks different, thanks.

That's weird I looked at the monthly and did not see any Gitlab employees. Were you looking at a different repo?

OP here. As of recently, GitLab has a dedicated Git team [1]. So our contributions to the project will hopefully increase a lot more :)

[1]: https://handbook.gitlab.com/handbook/engineering/infrastruct...

Post reply on HN