19 ms·

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

593 points by nayak 1y ago

judofyr 1y ago
See also: https://www.tumblr.com/accidentallyquadratic 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.
- vjerancrnjak 1y ago
  This particular change was not accidental. It was announced as quadratic.
- hinkley 1y ago
  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.
jeffbee 1y ago
Are there any reimplementations of git, by professional programmers using real tools? The source in question — object.c — is "banging rocks together" material.
- landr0id 1y ago
  https://github.com/GitoxideLabs/gitoxide https://github.com/GitoxideLabs/gitoxide
- School-Cotton 1y ago
  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.
- Vilian 1y ago
  Git, but as it was intended to be used
- kgeist 1y ago
  We use go-git in one of our Go projects that relies on Git for version control of its data.
- protonfckff 1y ago
  [dead]
- gonzus 1y ago
  https://github.com/libgit2/libgit2 https://github.com/libgit2/libgit2
- fHr 1y ago
  lmao
hiddew 1y ago
"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.
- School-Cotton 1y ago
  This is not the precise mathematical definition of exponential, but rather the colloquial one, where it just means "a lot".
  - cvoss 1y ago
    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.
    - blharr 1y ago
      I somewhat agree, but for lack of a better word, what would you use? Quadratically doesn't have the same punch
      - School-Cotton 1y ago
        “Dramatically” ?
        deleted 1y ago
        [deleted]
      - remram 1y ago
        "a lot"
      - jjmarr 1y ago
        "by a factor of `n`" also sounds impressive.
gre 1y ago
looks like the commit is here: https://github.com/git/git/commit/a52d459e72b890c192485002ec518bb9e01c19a6 https://github.com/git/git/commit/a52d459e72b890c192485002ec...
- throawayonthe 1y ago
  > * Warning: this function uses an O(N^2) algorithm.
- mortar 1y ago
  Thanks, this helped me find the submission and related discussion thread - https://lore.kernel.org/git/20250401-488-generating-bundles-with-many-references-has-non-linear-performance-v1-2-6d23b2d96557@gmail.com/ https://lore.kernel.org/git/20250401-488-generating-bundles-...
SomaticPirate 1y ago
How was the flame graph created? (Not very familiar with C and the performance tools around it)
- plorkyeran 1y ago
  https://github.com/brendangregg/FlameGraph https://github.com/brendangregg/FlameGraph You record performance data with `perf`, then use the scripts there to turn it into a SVG.
  - immortaljoe 1y ago
    OP here. In this particular case, I used https://github.com/flamegraph-rs/flamegraph https://github.com/flamegraph-rs/flamegraph
  - IshKebab 1y ago
    I strongly recommend not using this. Instead use pprof - it has a MUCH better interactive flamegraph, plus other nice performance visualisations (e.g. a call graph): https://github.com/google/pprof https://github.com/google/pprof go install github.com/google/pprof@latest pprof -http=: prof.out I normally collect the profiles with gperftools (https://github.com/gperftools/gperftools https://github.com/gperftools/gperftools) and then just LD_PRELOAD=/usr/lib/libtcmalloc_and_profiler.so CPUPROFILE=prof.out <your command> I've been meaning to try Samply though. Not sure if it works with pprof.
- landr0id 1y ago
  You can also use https://github.com/mstange/samply https://github.com/mstange/samply to make recording and viewing in the Firefox profiler easier. It will spin up a localhost server after the trace ends, the profiler uses the localhost server and nothing is shared with Firefox servers unless you explicitly choose to upload the data and create a permalink.
edflsafoiewq 1y ago
So they replaced a nested for loop for checking for duplicates with a set data structure. Surprised such a common thing was in git.
tomxor 1y ago
One of the many reasons I moved to self hosting. I use ZFS to backup every 15 minutes, ... could do it even more frequently but that seems a little pointless. Also moved away from Gitlab because it's so damn slow.
- glookler 1y ago
  ZFS is great, getting off gitlab would also be great, what did you switch to?
  - tomxor 1y ago
    Gitea, i can't recommend it enough. Lightening fast compared to the proprietary offerings, clean simple UI like an older Github, and super simple to self host.
    - mdaniel 1y ago
      So long as you have an existing CI/CD story, or are willing to invest in head-to-heading them, to find one that fits your needs. Because both it and Forgejo's "we're deploying act, what could go wrong" give me the heebie-jeebies. And, aside from that, there are so many FLOSS ones they could have chosen that legitimately work making that decision extra opaque to me
- haroldp 1y ago
  This was my thought too, but I figured I just didn't understand the problem. Why use git commands to backup when a file system copy seems like it would do? zfs snapshot takes less than a second on any size repo. zfs send transfers just the changes since the last backup, as fast as your network, more or less.
  - tomxor 1y ago
    Yup, once you've used snapshots for backups once, doing any kind of filesystem level backup just seems absurd. I now use it as the basis for every piece of infrastructure I add that holds valuable data. The only place it doesn't really fit is distributed databases.
treesknees 1y ago
Duplicate of https://news.ycombinator.com/item?id=44197061 https://news.ycombinator.com/item?id=44197061
- mdaniel 1y ago
  Since that one only has one comment, I'm pretty sure that means the HN front-page is luck of the draw and I wouldn't have bothered even commenting about the other one
LgWoodenBadger 1y ago
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.
- parthdesai 1y ago
  My rule of thumb for 80%-90% of the problems is, if you need complicated algorithm, it means your data model isn't right. Sure, you do need complicated algorithms for compilers, db internals, route planning et all, but all things considered, those are minority of the use cases.
  - anttihaapala 1y ago
    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.
    - throwaway2037 1y ago
      > 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.
      - saagarjha 1y ago
        Yes, the problem is getting them into your project.
        account42 1y ago
        That's only a problem if you have never done any C development.
  - 1y ago
Arcuru 1y ago
48 hours is a crazy amount of time to spend just to compress a git folder, it's only a couple GB. 41 minutes still seems like quite a long time. Why aren't they just snapshotting and archiving the full git repo? Does `git bundle` add something over frequent ZFS backups?
- bombela 1y ago
  > Be aware that even with these recommendations, syncing in this way has some risk since it bypasses Git’s normal integrity checking for repositories, so having backups is advised. You may also wish to do a git fsck to verify the integrity of your data on the destination system after syncing. https://git-scm.com/docs/gitfaq#_transfers https://git-scm.com/docs/gitfaq#_transfers It doesn't tell you how to make a backup safely though. On a personal scale, Syncthing and Btrfs snapshots work plenty good enough. It's as fast as the storage/network too.
  - nightfly 1y ago
    Syncthing is the only way I've ever corrupted a git repo before
    - deleted 1y ago
      [deleted]
    - hobofan 1y ago
      I think that's why they specified the "BTRFS snapshots" part. Yes, directly syncing a .git directory seems like a recipe for disaster with how often I've seen individual files lagging to sync, but I guess with BTRFS snaphots one can ensure that only a consistent view of a git directory is being backed up and synced.
      - bombela 1y ago
        Nah I truly do it the wrong way around. Syncthing on the git repos. And one of my device in the Syncthing cluster does btrfs snapshots minutely for recovery and further backups. Because it's at a personal scale, the only time I can corrupt a git repo is if I work on the same repo (and it's workdir) from more than one device in the time it takes for Syncthing to replicate the changes. But even then it's not a big deal because git fsck is quick. And I have my snapshots, and the syncthing versioning, and git defaults to two weeks before pruning. And because of how git works, using hash to identify contents, files are not easily overwritten either. In 10y I only had one git corruption (I ran a command on the same repo on a different machine via ssh, yielding a synctning conflict). Syncthing kept copies of the conflict file. One commit disappeared from the history but not from the database. It was easy to rebase the changes. I think I used git fsck to deleted the syncthing versioned files.
DamonHD 1y ago
Here comes an unpopular nitpick: "... 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." Uh no you didn't. Not possible. At most a polynomial reduction is possible else complexity theory needs a re-write. (OK, yes, k could be doing some heavy lifting here, but I doubt it.) If you are going to quote a maths formula then please don't use "exponetially" to mean "lots". I stopped reading there: I don't want to have to read each word and wonder if they actually meant it, or it's just bad hype.
- nayak 1y ago
  OP here. Feedback is always welcome, I did mean exponentially in the colloquial sense. I do see how it is confusing here, will change it.
  - DamonHD 1y ago
    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...)
    - ctxc 1y ago
      Art term?
      - wizzwizz4 1y ago
        https://en.wiktionary.org/wiki/term_of_art https://en.wiktionary.org/wiki/term_of_art
        ctxc 1y ago
        Ah, thanks. I could only think of art as in literal, artistic art.
Lammy 1y ago
> What this means for GitLab customers — [a bunch of stuff about how customers can now back up more frequently and more robustly] Realtalk: They should rewrite this post's headline to be in a positive tense instead of leading with a negative word. I'm glad I read the post, because it is a cool and good fix, but I saw “Decreasing […] repo backup” and my first thought was that it was an announcement of some service downgrade like some sort of cost-cutting measure.
- serial_dev 1y ago
  I don’t think it’s unreasonable to expect interested people to read five words from the title. I know people don’t always do that, but complaining about it as if they did something wrong is ridiculous.
  - robertlagrant 1y ago
    No one was complaining.
divbzero 1y ago
The performance improvement that GitLab contributed to Git is slated to be released with v2.50.0: https://github.com/git/git/commit/bb74c0abbc31da35be52999569ea481ebd149d1d https://github.com/git/git/commit/bb74c0abbc31da35be52999569...
- Nemo_bis 1y ago
  Nice that GitLab is active upstream! Do I see correctly that the most active contributors to git are currently GitLab employees?
  - dfc 1y ago
    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%2F2023 https://github.com/git/git/graphs/contributors?from=6%2F3%2F...
    - Nemo_bis 1y ago
      I had looked at the monthly activity. Indeed on a longer timespan it looks different, thanks.
      - dfc 1y ago
        That's weird I looked at the monthly and did not see any Gitlab employees. Were you looking at a different repo?
        nayak 1y ago
        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/infrastructure-platforms/data-access/git/ https://handbook.gitlab.com/handbook/engineering/infrastruct...
pjmlp 1y ago
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.
- IshKebab 1y ago
  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 about it.
  - pjmlp 1y ago
    Yeah, not something that WG14 will ever care about.
  - masklinn 1y ago
    > 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 about it. The original commit was made in January 2009 (https://github.com/git/git/commit/b2a6d1c6868b6d5e7d2b4fa9129341220a1e848a https://github.com/git/git/commit/b2a6d1c6868b6d5e7d2b4fa912...), strmap was added in November 2020 (https://github.com/git/git/commit/ae20bf1ad98bdc716879a8da99e7f329e3cc2730 https://github.com/git/git/commit/ae20bf1ad98bdc716879a8da99..., strset was added a few days later: https://github.com/git/git/commit/1201eb628ac753af5751258466df5f964bdc9f17 https://github.com/git/git/commit/1201eb628ac753af5751258466...). It was first proposed in 2018 (https://lore.kernel.org/git/20180906191203.GA26184@sigill.intra.peff.net/ https://lore.kernel.org/git/20180906191203.GA26184@sigill.in... the proposal specifically mentions it fixing possibly quadratic sites). As noted in the comment, git did have a sorted string list with bisection search, and that's from 2008 (and it actually dates back to 2006 as the "path list" API, before it was renamed following the realisation that it was a generalised string list). Though as the hashmap proposal notes, it's a bit tricky because there's a single type with functions for sorted and functions for unsorted operations, you need to know whether your list is sorted or not independent of its type.
ashishb 1y ago
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).
- hinkley 1y ago
  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.
divbzero 1y ago
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.
- Quekid5 1y ago
  If a set-of-strings was trivially available in the source language (at time of implementation) the original programmer would probably have done this (relatively) trivial optimization... This is a symptom of anemic languages like C.
prymitive 1y ago
Well 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.
SoftTalker 1y ago
Cool 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.
- kokada 1y ago
  Yes. I read the whole article thinking that this must have been generated by LLM, because at least the style remembers it.
  - ruuda 1y ago
    That was also my thought.
  - Scaevolus 1y ago
    Em dashes and bullet points!
  - jaygreco 1y ago
    Glad I wasn’t the only one who thought this. The post is also missing one obvious thing that I expect in any technical post: code snippets. Let me see the code. ChatGPT has ruined bullet points for the rest of us… No offense but writing this blog post couldn’t take more than a few minutes, why spoil it with LLM? Shoot, use one to check grammar and recommend edits even.
  - bearjaws 1y ago
    Don't take my bullet points away from me
    - jorvi 1y ago
      They came for the em dashes, and I did not speak up. Then they came for the bullet points, and I did not speak up..
  - djdeutschebahn 1y ago
    Exactly thought the same. Reading experience of the post would have been definitely improved, with less text.
bob1029 1y ago
I'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.
- nonameiguess 1y ago
  Gitlab isn't just a managed service. They release the software for self-hosted instances as well. There is no guarantee or requirement that users all run Gitlab on the same filesystem or even a filesystem that supports block level snapshots at all. Presumably, they want a universal backup system that works for all Gitlabs.
  - bob1029 1y ago
    I've never heard of a .git folder that spanned multiple filesystems. It sounds like we are now conflating the git workspace with everything else in the product. There are system requirements that a customer would be expected to adhere to if they wanted a valid enterprise support contract with one of these vendors.
    - to11mtm 1y ago
      I think GP's point is that the filesystems used by someone self-hosting gitlab may not be the same as what gitlab themselves are using. File systems can be weird. Sometimes the OS can be weird and fsync type calls may not do what you expect. At least at one point MacOS fsync didn't behave the same way as Linux (i.e. Linux should ensure the write is truly done and not just in cache so long as the drive isn't lying). [0] > There are system requirements that a customer would be expected to adhere to if they wanted a valid enterprise support contract with one of these vendors. Gitlab has a community edition. Not handling data well would be bad for their public image. [0] - https://news.ycombinator.com/item?id=30372218 https://news.ycombinator.com/item?id=30372218
rubit_xxx21 1y ago
[flagged]
- herpderperator 1y ago
  If the requirement is to check uniqueness, what assumptions could possibly cause a bug? In this case, why does it matter if the uniqueness is tested with a nested for loop or with a map? There are many identical ways to check uniqueness, some being faster than others.
  - rubit_xxx22_ 1y ago
    [flagged]
    - nightpool 1y ago
      Why are you making a new account for each comment? You seem to be deliberately avoiding HN's moderation system
      - rubit_xxx22___ 1y ago
        [flagged]
        Dylan16807 1y ago
        > I don’t want something gathering all my thoughts historically together and tying it to something else; nothing good comes from that; I’m not writing a serial novel. Yeah but you should want your thoughts on a single post to tie together. > Many years ago I had a user with thousands of karma points. I used to get really annoyed with other users downvoting my valid and thoughtful comments because it affected my karma. Despite attempts to rally the community around getting rid of downvoting, that never happened. Sorry you had that reaction. While I get annoyed by downvotes sometimes, I've never cared about losing some points from the mostly useless pile.
deleted 1y ago
[deleted]
einpoklum 1y ago
I had a somewhat similar experience when writing a "remove duplicates" extension for Thunderbird: https://addons.thunderbird.net/en-US/thunderbird/addon/removedupes/ https://addons.thunderbird.net/en-US/thunderbird/addon/remov... I used a hash to begin with, using a simplistic digest function to the message headers I was comparing, getting me a 4-byte hash key. That worked, but was kind of slow. Finally, the idea came to me to not apply _any_ digesting, and use the combined concatenated headers of the messages as hash keys. About 2k bytes per hash key! The result: About 20x perf improvement if memory serves. How is that possible? The reason is that the code all runs in a Javascript machine; and applying the digest was not a built-in function, it was looping over the headers and doing the arithmetic. Thousands upon thousands of JS abstract machine steps. The use of the large hash key may be inefficient, but - it's just one JS object / dictionary operation, and one of the most heavily-optimized in any implementation.
sneak 1y ago
…and they say leetcode-style problems are out of date. While perhaps implementing low level sorts is silly, knowing which data structures to use and when, and what underlying big-o performance they have, is critical, as demonstrated here.
kristianp 1y ago
It would have been nice if the post included some details, such as before and after code.
niffydroid 1y ago
Why use this method over just having a script do a clone or pull elsewhere? Got is about distribution right?
deleted 1y ago
[deleted]
iamcreasy 1y ago
Cool! Please post another flame graph after applying the patch.
tcdent 1y ago
TLDR if you only add objects to an array that are already not contained in said array you won't have to iterate back through it to remove the duplicates you created. wild that this a pattern like this would be part of git-core, but I guess we all overlook stuff on a regular basis
katella 1y ago
I don't know much about git backups, but why would there be race conditions if you just create the backup off the local repo instead of remote?
KETpXDDzR 1y ago
With git it should be straightforward to implement an incremental, dedup backup solution since all objects are stored with their hashs in filename.
- mdaniel 1y ago
  Run `man git-repack` or its `man git-gc` friend and recall that most filesystems hate dealing with a bazillion small files I think there have been several attempts to use S3-ish blobstores as git backends but of the two major git hosters, only one of them is MIT licensed and they don't attempt that stunt, so safe to assume it's not a viable approach
KlausWinter 1y ago
[dead]
DeepYogurt 1y ago
I miss a good tech blog post. Cheers for this
ianks 1y ago
Reminds me of the timeless advice I got for acing leet code interviews: “remember to use a hash map.” Tends to work out pretty well.
SkiFire13 1y ago
> 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.
- globular-toast 1y ago
  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.
jas39 1y ago
What a poor write-up, neither defining the problem nor the solution with any clearity. Did anyone come away with any information that can be used for anything?
fHr 1y ago
absolute chads, nice!
hinkley 1y ago
This feels like some of the problems I’ve ended up tackling. The people too close to the problem don’t see it so someone has to reach across the aisle and make something happen in code they normally wouldn’t touch. Even with the quadratic complexity I suspect this problem has been brewing for a while. This commit has been biding its time for 16 years waiting to ruin someone’s day (let’s not confuse the utility of Make it Work early in a project with justifying retaining that code in perpetuity. Make it Right, Make it Fast.) Backups have probably been going over six hours for years and steadily climbing. “We” feels a lot like one or two people jumping on a grenade.
gbacon 1y ago
Algorithmic improvements beat micro-optimizations.
James_K 1y ago
Perhaps nested for loops should be some kind of compiler warning.
abhashanand1501 1y ago
Lot of comments complaining that going from O(n^2) to O(log n) is not an exponential improvement, but it is indeed an exponential improvement. In fact O(n) is exponentially more than O(log n).
SergeAx 1y ago
I can't shake off the feeling that the second half of the article is generated by a neural network.

593 points by nayak 1y ago

See also: https://www.tumblr.com/accidentallyquadratic 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.

vjerancrnjak 1y ago
This particular change was not accidental. It was announced as quadratic.
hinkley 1y ago
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.

jeffbee 1y ago

Are there any reimplementations of git, by professional programmers using real tools? The source in question — object.c — is "banging rocks together" material.

landr0id 1y ago
https://github.com/GitoxideLabs/gitoxide https://github.com/GitoxideLabs/gitoxide
School-Cotton 1y ago
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.
Vilian 1y ago
Git, but as it was intended to be used
kgeist 1y ago
We use go-git in one of our Go projects that relies on Git for version control of its data.
protonfckff 1y ago
[dead]
gonzus 1y ago
https://github.com/libgit2/libgit2 https://github.com/libgit2/libgit2
fHr 1y ago
lmao

hiddew 1y ago

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

School-Cotton 1y ago
This is not the precise mathematical definition of exponential, but rather the colloquial one, where it just means "a lot".
- cvoss 1y ago
  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.
  - blharr 1y ago
    I somewhat agree, but for lack of a better word, what would you use? Quadratically doesn't have the same punch
    - School-Cotton 1y ago
      “Dramatically” ?
      - deleted 1y ago
        [deleted]
    - remram 1y ago
      "a lot"
    - jjmarr 1y ago
      "by a factor of `n`" also sounds impressive.

gre 1y ago

looks like the commit is here: https://github.com/git/git/commit/a52d459e72b890c192485002ec518bb9e01c19a6 https://github.com/git/git/commit/a52d459e72b890c192485002ec...

throawayonthe 1y ago
> * Warning: this function uses an O(N^2) algorithm.
mortar 1y ago
Thanks, this helped me find the submission and related discussion thread - https://lore.kernel.org/git/20250401-488-generating-bundles-with-many-references-has-non-linear-performance-v1-2-6d23b2d96557@gmail.com/ https://lore.kernel.org/git/20250401-488-generating-bundles-...

SomaticPirate 1y ago

How was the flame graph created? (Not very familiar with C and the performance tools around it)

plorkyeran 1y ago
https://github.com/brendangregg/FlameGraph https://github.com/brendangregg/FlameGraph You record performance data with `perf`, then use the scripts there to turn it into a SVG.
- immortaljoe 1y ago
  OP here. In this particular case, I used https://github.com/flamegraph-rs/flamegraph https://github.com/flamegraph-rs/flamegraph
- IshKebab 1y ago
  I strongly recommend not using this. Instead use pprof - it has a MUCH better interactive flamegraph, plus other nice performance visualisations (e.g. a call graph): https://github.com/google/pprof https://github.com/google/pprof go install github.com/google/pprof@latest pprof -http=: prof.out I normally collect the profiles with gperftools (https://github.com/gperftools/gperftools https://github.com/gperftools/gperftools) and then just LD_PRELOAD=/usr/lib/libtcmalloc_and_profiler.so CPUPROFILE=prof.out <your command> I've been meaning to try Samply though. Not sure if it works with pprof.
landr0id 1y ago
You can also use https://github.com/mstange/samply https://github.com/mstange/samply to make recording and viewing in the Firefox profiler easier. It will spin up a localhost server after the trace ends, the profiler uses the localhost server and nothing is shared with Firefox servers unless you explicitly choose to upload the data and create a permalink.

edflsafoiewq 1y ago

So they replaced a nested for loop for checking for duplicates with a set data structure. Surprised such a common thing was in git.

tomxor 1y ago

One of the many reasons I moved to self hosting. I use ZFS to backup every 15 minutes, ... could do it even more frequently but that seems a little pointless. Also moved away from Gitlab because it's so damn slow.

glookler 1y ago
ZFS is great, getting off gitlab would also be great, what did you switch to?
- tomxor 1y ago
  Gitea, i can't recommend it enough. Lightening fast compared to the proprietary offerings, clean simple UI like an older Github, and super simple to self host.
  - mdaniel 1y ago
    So long as you have an existing CI/CD story, or are willing to invest in head-to-heading them, to find one that fits your needs. Because both it and Forgejo's "we're deploying act, what could go wrong" give me the heebie-jeebies. And, aside from that, there are so many FLOSS ones they could have chosen that legitimately work making that decision extra opaque to me
haroldp 1y ago
This was my thought too, but I figured I just didn't understand the problem. Why use git commands to backup when a file system copy seems like it would do? zfs snapshot takes less than a second on any size repo. zfs send transfers just the changes since the last backup, as fast as your network, more or less.
- tomxor 1y ago
  Yup, once you've used snapshots for backups once, doing any kind of filesystem level backup just seems absurd. I now use it as the basis for every piece of infrastructure I add that holds valuable data. The only place it doesn't really fit is distributed databases.

treesknees 1y ago

Duplicate of https://news.ycombinator.com/item?id=44197061 https://news.ycombinator.com/item?id=44197061

mdaniel 1y ago
Since that one only has one comment, I'm pretty sure that means the HN front-page is luck of the draw and I wouldn't have bothered even commenting about the other one

LgWoodenBadger 1y ago

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.

parthdesai 1y ago
My rule of thumb for 80%-90% of the problems is, if you need complicated algorithm, it means your data model isn't right. Sure, you do need complicated algorithms for compilers, db internals, route planning et all, but all things considered, those are minority of the use cases.
- anttihaapala 1y ago
  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.
  - throwaway2037 1y ago
    > 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.
    - saagarjha 1y ago
      Yes, the problem is getting them into your project.
      - account42 1y ago
        That's only a problem if you have never done any C development.
- 1y ago

Arcuru 1y ago

48 hours is a crazy amount of time to spend just to compress a git folder, it's only a couple GB. 41 minutes still seems like quite a long time. Why aren't they just snapshotting and archiving the full git repo? Does `git bundle` add something over frequent ZFS backups?

bombela 1y ago
> Be aware that even with these recommendations, syncing in this way has some risk since it bypasses Git’s normal integrity checking for repositories, so having backups is advised. You may also wish to do a git fsck to verify the integrity of your data on the destination system after syncing. https://git-scm.com/docs/gitfaq#_transfers https://git-scm.com/docs/gitfaq#_transfers It doesn't tell you how to make a backup safely though. On a personal scale, Syncthing and Btrfs snapshots work plenty good enough. It's as fast as the storage/network too.
- nightfly 1y ago
  Syncthing is the only way I've ever corrupted a git repo before
  - deleted 1y ago
    [deleted]
  - hobofan 1y ago
    I think that's why they specified the "BTRFS snapshots" part. Yes, directly syncing a .git directory seems like a recipe for disaster with how often I've seen individual files lagging to sync, but I guess with BTRFS snaphots one can ensure that only a consistent view of a git directory is being backed up and synced.
    - bombela 1y ago
      Nah I truly do it the wrong way around. Syncthing on the git repos. And one of my device in the Syncthing cluster does btrfs snapshots minutely for recovery and further backups. Because it's at a personal scale, the only time I can corrupt a git repo is if I work on the same repo (and it's workdir) from more than one device in the time it takes for Syncthing to replicate the changes. But even then it's not a big deal because git fsck is quick. And I have my snapshots, and the syncthing versioning, and git defaults to two weeks before pruning. And because of how git works, using hash to identify contents, files are not easily overwritten either. In 10y I only had one git corruption (I ran a command on the same repo on a different machine via ssh, yielding a synctning conflict). Syncthing kept copies of the conflict file. One commit disappeared from the history but not from the database. It was easy to rebase the changes. I think I used git fsck to deleted the syncthing versioned files.

DamonHD 1y ago

Here comes an unpopular nitpick: "... 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." Uh no you didn't. Not possible. At most a polynomial reduction is possible else complexity theory needs a re-write. (OK, yes, k could be doing some heavy lifting here, but I doubt it.) If you are going to quote a maths formula then please don't use "exponetially" to mean "lots". I stopped reading there: I don't want to have to read each word and wonder if they actually meant it, or it's just bad hype.

nayak 1y ago
OP here. Feedback is always welcome, I did mean exponentially in the colloquial sense. I do see how it is confusing here, will change it.
- DamonHD 1y ago
  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...)
  - ctxc 1y ago
    Art term?
    - wizzwizz4 1y ago
      https://en.wiktionary.org/wiki/term_of_art https://en.wiktionary.org/wiki/term_of_art
      - ctxc 1y ago
        Ah, thanks. I could only think of art as in literal, artistic art.

Lammy 1y ago

> What this means for GitLab customers — [a bunch of stuff about how customers can now back up more frequently and more robustly] Realtalk: They should rewrite this post's headline to be in a positive tense instead of leading with a negative word. I'm glad I read the post, because it is a cool and good fix, but I saw “Decreasing […] repo backup” and my first thought was that it was an announcement of some service downgrade like some sort of cost-cutting measure.

serial_dev 1y ago
I don’t think it’s unreasonable to expect interested people to read five words from the title. I know people don’t always do that, but complaining about it as if they did something wrong is ridiculous.
- robertlagrant 1y ago
  No one was complaining.

divbzero 1y ago

The performance improvement that GitLab contributed to Git is slated to be released with v2.50.0: https://github.com/git/git/commit/bb74c0abbc31da35be52999569ea481ebd149d1d https://github.com/git/git/commit/bb74c0abbc31da35be52999569...

Nemo_bis 1y ago
Nice that GitLab is active upstream! Do I see correctly that the most active contributors to git are currently GitLab employees?
- dfc 1y ago
  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%2F2023 https://github.com/git/git/graphs/contributors?from=6%2F3%2F...
  - Nemo_bis 1y ago
    I had looked at the monthly activity. Indeed on a longer timespan it looks different, thanks.
    - dfc 1y ago
      That's weird I looked at the monthly and did not see any Gitlab employees. Were you looking at a different repo?
      - nayak 1y ago
        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/infrastructure-platforms/data-access/git/ https://handbook.gitlab.com/handbook/engineering/infrastruct...

pjmlp 1y ago

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.

IshKebab 1y ago
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 about it.
- pjmlp 1y ago
  Yeah, not something that WG14 will ever care about.
- masklinn 1y ago
  > 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 about it. The original commit was made in January 2009 (https://github.com/git/git/commit/b2a6d1c6868b6d5e7d2b4fa9129341220a1e848a https://github.com/git/git/commit/b2a6d1c6868b6d5e7d2b4fa912...), strmap was added in November 2020 (https://github.com/git/git/commit/ae20bf1ad98bdc716879a8da99e7f329e3cc2730 https://github.com/git/git/commit/ae20bf1ad98bdc716879a8da99..., strset was added a few days later: https://github.com/git/git/commit/1201eb628ac753af5751258466df5f964bdc9f17 https://github.com/git/git/commit/1201eb628ac753af5751258466...). It was first proposed in 2018 (https://lore.kernel.org/git/20180906191203.GA26184@sigill.intra.peff.net/ https://lore.kernel.org/git/20180906191203.GA26184@sigill.in... the proposal specifically mentions it fixing possibly quadratic sites). As noted in the comment, git did have a sorted string list with bisection search, and that's from 2008 (and it actually dates back to 2006 as the "path list" API, before it was renamed following the realisation that it was a generalised string list). Though as the hashmap proposal notes, it's a bit tricky because there's a single type with functions for sorted and functions for unsorted operations, you need to know whether your list is sorted or not independent of its type.

ashishb 1y ago

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

hinkley 1y ago
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.

divbzero 1y ago

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.

Quekid5 1y ago
If a set-of-strings was trivially available in the source language (at time of implementation) the original programmer would probably have done this (relatively) trivial optimization... This is a symptom of anemic languages like C.

prymitive 1y ago

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

SoftTalker 1y ago

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

kokada 1y ago
Yes. I read the whole article thinking that this must have been generated by LLM, because at least the style remembers it.
- ruuda 1y ago
  That was also my thought.
- Scaevolus 1y ago
  Em dashes and bullet points!
- jaygreco 1y ago
  Glad I wasn’t the only one who thought this. The post is also missing one obvious thing that I expect in any technical post: code snippets. Let me see the code. ChatGPT has ruined bullet points for the rest of us… No offense but writing this blog post couldn’t take more than a few minutes, why spoil it with LLM? Shoot, use one to check grammar and recommend edits even.
- bearjaws 1y ago
  Don't take my bullet points away from me
  - jorvi 1y ago
    They came for the em dashes, and I did not speak up. Then they came for the bullet points, and I did not speak up..
- djdeutschebahn 1y ago
  Exactly thought the same. Reading experience of the post would have been definitely improved, with less text.

bob1029 1y ago

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

nonameiguess 1y ago
Gitlab isn't just a managed service. They release the software for self-hosted instances as well. There is no guarantee or requirement that users all run Gitlab on the same filesystem or even a filesystem that supports block level snapshots at all. Presumably, they want a universal backup system that works for all Gitlabs.
- bob1029 1y ago
  I've never heard of a .git folder that spanned multiple filesystems. It sounds like we are now conflating the git workspace with everything else in the product. There are system requirements that a customer would be expected to adhere to if they wanted a valid enterprise support contract with one of these vendors.
  - to11mtm 1y ago
    I think GP's point is that the filesystems used by someone self-hosting gitlab may not be the same as what gitlab themselves are using. File systems can be weird. Sometimes the OS can be weird and fsync type calls may not do what you expect. At least at one point MacOS fsync didn't behave the same way as Linux (i.e. Linux should ensure the write is truly done and not just in cache so long as the drive isn't lying). [0] > There are system requirements that a customer would be expected to adhere to if they wanted a valid enterprise support contract with one of these vendors. Gitlab has a community edition. Not handling data well would be bad for their public image. [0] - https://news.ycombinator.com/item?id=30372218 https://news.ycombinator.com/item?id=30372218

rubit_xxx21 1y ago

[flagged]

herpderperator 1y ago
If the requirement is to check uniqueness, what assumptions could possibly cause a bug? In this case, why does it matter if the uniqueness is tested with a nested for loop or with a map? There are many identical ways to check uniqueness, some being faster than others.
- rubit_xxx22_ 1y ago
  [flagged]
  - nightpool 1y ago
    Why are you making a new account for each comment? You seem to be deliberately avoiding HN's moderation system
    - rubit_xxx22___ 1y ago
      [flagged]
      - Dylan16807 1y ago
        > I don’t want something gathering all my thoughts historically together and tying it to something else; nothing good comes from that; I’m not writing a serial novel. Yeah but you should want your thoughts on a single post to tie together. > Many years ago I had a user with thousands of karma points. I used to get really annoyed with other users downvoting my valid and thoughtful comments because it affected my karma. Despite attempts to rally the community around getting rid of downvoting, that never happened. Sorry you had that reaction. While I get annoyed by downvotes sometimes, I've never cared about losing some points from the mostly useless pile.

deleted 1y ago

[deleted]

einpoklum 1y ago

I had a somewhat similar experience when writing a "remove duplicates" extension for Thunderbird: https://addons.thunderbird.net/en-US/thunderbird/addon/removedupes/ https://addons.thunderbird.net/en-US/thunderbird/addon/remov... I used a hash to begin with, using a simplistic digest function to the message headers I was comparing, getting me a 4-byte hash key. That worked, but was kind of slow. Finally, the idea came to me to not apply _any_ digesting, and use the combined concatenated headers of the messages as hash keys. About 2k bytes per hash key! The result: About 20x perf improvement if memory serves. How is that possible? The reason is that the code all runs in a Javascript machine; and applying the digest was not a built-in function, it was looping over the headers and doing the arithmetic. Thousands upon thousands of JS abstract machine steps. The use of the large hash key may be inefficient, but - it's just one JS object / dictionary operation, and one of the most heavily-optimized in any implementation.

sneak 1y ago

…and they say leetcode-style problems are out of date. While perhaps implementing low level sorts is silly, knowing which data structures to use and when, and what underlying big-o performance they have, is critical, as demonstrated here.

kristianp 1y ago

It would have been nice if the post included some details, such as before and after code.

niffydroid 1y ago

Why use this method over just having a script do a clone or pull elsewhere? Got is about distribution right?

deleted 1y ago

[deleted]

iamcreasy 1y ago

Cool! Please post another flame graph after applying the patch.

tcdent 1y ago

TLDR if you only add objects to an array that are already not contained in said array you won't have to iterate back through it to remove the duplicates you created. wild that this a pattern like this would be part of git-core, but I guess we all overlook stuff on a regular basis

katella 1y ago

I don't know much about git backups, but why would there be race conditions if you just create the backup off the local repo instead of remote?

KETpXDDzR 1y ago

With git it should be straightforward to implement an incremental, dedup backup solution since all objects are stored with their hashs in filename.

mdaniel 1y ago
Run `man git-repack` or its `man git-gc` friend and recall that most filesystems hate dealing with a bazillion small files I think there have been several attempts to use S3-ish blobstores as git backends but of the two major git hosters, only one of them is MIT licensed and they don't attempt that stunt, so safe to assume it's not a viable approach

KlausWinter 1y ago

[dead]

DeepYogurt 1y ago

I miss a good tech blog post. Cheers for this

ianks 1y ago

Reminds me of the timeless advice I got for acing leet code interviews: “remember to use a hash map.” Tends to work out pretty well.

SkiFire13 1y ago

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

globular-toast 1y ago
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.

jas39 1y ago

What a poor write-up, neither defining the problem nor the solution with any clearity. Did anyone come away with any information that can be used for anything?

fHr 1y ago

absolute chads, nice!

hinkley 1y ago

This feels like some of the problems I’ve ended up tackling. The people too close to the problem don’t see it so someone has to reach across the aisle and make something happen in code they normally wouldn’t touch. Even with the quadratic complexity I suspect this problem has been brewing for a while. This commit has been biding its time for 16 years waiting to ruin someone’s day (let’s not confuse the utility of Make it Work early in a project with justifying retaining that code in perpetuity. Make it Right, Make it Fast.) Backups have probably been going over six hours for years and steadily climbing. “We” feels a lot like one or two people jumping on a grenade.

gbacon 1y ago

Algorithmic improvements beat micro-optimizations.

James_K 1y ago

Perhaps nested for loops should be some kind of compiler warning.

abhashanand1501 1y ago

Lot of comments complaining that going from O(n^2) to O(log n) is not an exponential improvement, but it is indeed an exponential improvement. In fact O(n) is exponentially more than O(log n).

SergeAx 1y ago

I can't shake off the feeling that the second half of the article is generated by a neural network.