Earlier quoted context omitted.
I somewhat agree, but for lack of a better word, what would you use? Quadratically doesn't have the same punch
"by a factor of `n`" also sounds impressive.
[deleted]
How we decreased GitLab repo backup times from 48 hours to 41 minutes
121–130 of 273 posts
Re: How we decreased GitLab repo backup times from 48 hours to 41 minutes
#122Cool 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.
Yes. I read the whole article thinking that this must have been generated by LLM, because at least the style remembers it.
That was also my thought.
Re: How we decreased GitLab repo backup times from 48 hours to 41 minutes
#123Earlier 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
If you just mean "a lot" in a non-technical sense, there are plenty of words available. enormously. immensely. tremendously. remarkably. incredibly. vastly.
Re: How we decreased GitLab repo backup times from 48 hours to 41 minutes
#124"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.
If you replace an n^2 algorithm with a log(n) lookup you get an exponential speed up. Although a hashmap lookup is usually O(1), which is even faster.
That is not true unless n^C / e^n = log(n) where C is some constant, which it is not. The difference between log(n) and some polynomial is logarithmic, not exponential.
Re: How we decreased GitLab repo backup times from 48 hours to 41 minutes
#125Earlier 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'.
I have an app that's been running an O n^2 algorithm in "production" (free open source app used by various communities) for about half a year now.
It's been fine because "n" is "number of aircraft flying in this flight simulator" - and the simulator's engine starts to fail above around 2000 anyway. So even in the worst case it's still going to run within milliseconds.
Re: How we decreased GitLab repo backup times from 48 hours to 41 minutes
#126Earlier quoted context omitted.
> 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…
[flagged]
You don't have to enter any e-mail address to get an HN account. You login from a (Firefox) incognito window and get your cookies deleted the moment the window is closed.
Why you're so afraid to let your ideas and views collect under a single account? Are they that controversial or are you weary of your own thoughts and don't want to see them again, or are you afraid to own your views as yours?
We're talking (mostly) tech here, and nobody is forced to comment.
Re: How we decreased GitLab repo backup times from 48 hours to 41 minutes
#127IME, 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.
I have an n^3 operation that's currently a huge bottleneck at only 10k elements. Not sure how to fix it.
Re: How we decreased GitLab repo backup times from 48 hours to 41 minutes
#128Cool! Please post another flame graph after applying the patch.
Re: How we decreased GitLab repo backup times from 48 hours to 41 minutes
#129Earlier quoted context omitted.
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...
Yes, that isn't actually Dawson's second law.
Re: How we decreased GitLab repo backup times from 48 hours to 41 minutes
#130Earlier quoted context omitted.
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...
Fair, but `n log n` definitely is the historical "good enough to actually sleep at night" in my head, every time I see it I think of the prof who taught my first CSC course and our data structures course due to how often it came up. Also, the wise statement that 'memory is fairly cheap compared to CPU for scaling'. It's insane to see how often folks would rather manually open and scan a 'static-on-deploy' 20-100MB Js…
[deleted]