[flagged]
This is a valid concern, but checking for uniqueness with a hash is fairly straightforward and the new implementation reuses a strset struct that has been in use since 2020:
How we decreased GitLab repo backup times from 48 hours to 41 minutes
81–90 of 273 posts
Re: How we decreased GitLab repo backup times from 48 hours to 41 minutes
#82Earlier quoted context omitted.
I'd say the exception is when `n` is under about 10, and is counting some sort of hardware constrained thing (e.g. some operation over all CAN interfaces pesent on an OBDII connector can be O(n^(2)) since n will always be between 1 and 4). If you wouldn't have to physically replace hardware for `n` to increase, you really need to avoid n^2 operations. And even then consider them carefully, perhaps explicitly failing…
> perhaps explicitly failing if `n` gets too big That's the problem. A lot of these quadratic time algorithms don't set limits. Even 'n!' is fine for small 'n'. Real production use cases don't have small 'n'.
> Real production use cases don't have small 'n'.
Real production use cases absolutely have small n. You don't hear about them, because it's very hard for them to cause issues. Unless the use case changes and now the n is not small anymore and nobody noticed the trap.
Re: How we decreased GitLab repo backup times from 48 hours to 41 minutes
#83A 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…
> 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/b2a6d1c6868b6d5e7d2b4fa912...), strmap was added in November 2020 (https://github.com/git/git/commit/ae20bf1ad98bdc716879a8da99..., strset was added a few days later: https://github.com/git/git/commit/1201eb628ac753af5751258466...). It was first proposed in 2018 (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.
Re: How we decreased GitLab repo backup times from 48 hours to 41 minutes
#84[flagged]
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.
[flagged]
Re: How we decreased GitLab repo backup times from 48 hours to 41 minutes
#85IME, 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.
Bruce Dawson says: I like to call this Dawson’s first law of computing: O(n^2) is the sweet spot of badly scaling algorithms: fast enough to make it into production, but slow enough to make things fall down once it gets there. https://bsky.app/profile/randomascii.bsky.social/post/3lk4c6...
The second law is that O(n * log n) is for practical intents and purposes O(n).
Re: How we decreased GitLab repo backup times from 48 hours to 41 minutes
#86IME, 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.
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.
This isn't knapsack. This is a dict lookup.
Re: How we decreased GitLab repo backup times from 48 hours to 41 minutes
#87Earlier quoted context omitted.
Bruce Dawson says: I like to call this Dawson’s first law of computing: O(n^2) is the sweet spot of badly scaling algorithms: fast enough to make it into production, but slow enough to make things fall down once it gets there. https://bsky.app/profile/randomascii.bsky.social/post/3lk4c6...
The second law is that O(n * log n) is for practical intents and purposes O(n).
To be clear though, that isn't his second law, at least as of two months ago, according to https://bsky.app/profile/randomascii.bsky.social/post/3lk4c6...
Re: How we decreased GitLab repo backup times from 48 hours to 41 minutes
#88Earlier quoted context omitted.
> perhaps explicitly failing if `n` gets too big That's the problem. A lot of these quadratic time algorithms don't set limits. Even 'n!' is fine for small 'n'. Real production use cases don't have small 'n'.
Or, phrased differently, if n has an upper limit, the algorithm is O(1).
As long as you have tests that regularly exercise your algorithm at n=max where you would notice if they were exceptionally slow
Re: How we decreased GitLab repo backup times from 48 hours to 41 minutes
#8948 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?
zfs snapshots are difficult to offsite in non-zfs replicas, say like an S3 bucket. That said, there's another less known feature that bundles help out with when used with `git clone --bundle-uri` The client can specify a location to a bundle, or the server can send the client the bundle location in the clone results and the client can fetch the bundle, unpack it, and then update the delta via the git server, so it's…
I think if you want consistent snapshot backups on non-zfs destinations the safest thing is to clone the snapshot and rsync from the clone. Not a single-step operation but preserves the atomicity of the snapshot.
EDIT: you could also rsync from a .zfs snapshot directory if you have them enabled.
Re: How we decreased GitLab repo backup times from 48 hours to 41 minutes
#90There 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.
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.