How we decreased GitLab repo backup times from 48 hours to 41 minutes
1–10 of 273 posts
Re: How we decreased GitLab repo backup times from 48 hours to 41 minutes
#2See 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.
Re: How we decreased GitLab repo backup times from 48 hours to 41 minutes
#3Are there any reimplementations of git, by professional programmers using real tools? The source in question — object.c — is "banging rocks together" material.
Re: How we decreased GitLab repo backup times from 48 hours to 41 minutes
#4Are there any reimplementations of git, by professional programmers using real tools? The source in question — object.c — is "banging rocks together" material.
Re: How we decreased GitLab repo backup times from 48 hours to 41 minutes
#5See 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.
This particular change was not accidental. It was announced as quadratic.
Re: How we decreased GitLab repo backup times from 48 hours to 41 minutes
#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.
Re: How we decreased GitLab repo backup times from 48 hours to 41 minutes
#7Are there any reimplementations of git, by professional programmers using real tools? The source in question — object.c — is "banging rocks together" material.
Ignoring your inaccurate flamebait and answering the underlying question: there are several reimplementations of git, including "got" (Game of Trees) from the OpenBSD developers, jgit (reimplementation in Java), the Haskell git package, the gitoxide rust crate (and I assume several more half-finished Rust hobby projects), and probably others; that's just what I found with a cursory google.
Re: How we decreased GitLab repo backup times from 48 hours to 41 minutes
#8"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".
Re: How we decreased GitLab repo backup times from 48 hours to 41 minutes
#9looks like the commit is here: https://github.com/git/git/commit/a52d459e72b890c192485002ec...
Re: How we decreased GitLab repo backup times from 48 hours to 41 minutes
#10"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.
[deleted]