261–270 of 273 posts
Earlier quoted context omitted.
But why couldn't they just dedupe the refs from the command line before starting the actual bundling - surely there are never more than a couple of hundred of those (one per branch)?
The point is the performance hit had nothing to do with dupe count (which could be zero), and everything to do with ref count.
Earlier quoted context omitted.
I've seen this exact problem in C code many times in my life, especially in kernel space where data structures and memory allocations are fun. Ironically, this is much _faster_ for small sets. Sometimes the error is intentional, because the programmer believes that all inputs will be small. IME, those programmers were wrong, but that's the inverse of survival bias.
And in fairness I can understand not considering someone might eventually be bundling a repository with tens of thousands of refs back in early 2009.
Earlier quoted context omitted.
Which term is appropriate here? What would you suggest? (honest question)
"hugely" or "a lot" or "to O(XXX)" whatever the new XXX complexity is.
Earlier quoted context omitted.
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 ca…
Earlier quoted context omitted.
The algorithm complexity went down in the function they patched (6x improvement in their benchmark), but in the context of how they benefited with how they were using the algorithm the impact was much larger (improved to taking 1% of the time), which is plausibly exponential (and figuring out the actual complexity is neither relevant nor an economic use of time).
> figuring out the actual complexity is neither relevant nor an economic use of time The fix was replacing a nested loop with a map. Figuring out that this goes from O(n^2) to O(n) (modulo details like bucket count) is immediate if you know what the words mean and understand enough to identify the problem and make the fix in the first place.
Earlier quoted context omitted.
They’re too ridiculous… unless a more optimal solution does not exist
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…
Earlier quoted context omitted.
> 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.
Yes, the problem is getting them into your project.
Earlier quoted context omitted.
Meaningless and non-constructive pedantry.
>pedantry I wasted 2 minutes of my life looking for the exponential reduction. So did many others. Now I'm wasting more of my life shit posting about it, but at least that's a conscious choice.
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.
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…
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.