231–240 of 273 posts
The performance improvement that GitLab contributed to Git is slated to be released with v2.50.0: https://github.com/git/git/commit/bb74c0abbc31da35be52999569...
Earlier quoted context omitted.
I feel this is too hardline and e.g. eliminates the useful things people do with SAT solvers.
The first SAT solver case that comes to mind is circuit layout, and then you have a k vs n problem. Because you don’t SAT solve per chip, you SAT solve per model and then amortize that cost across the first couple years’ sales. And they’re also “cheating” by copy pasting cores, which means the SAT problem is growing much more slowly than the number of gates per chip. Probably more like n^1/2 these days. If SAT solver…
"Oh well my algorithm isn't really O(N^2) because I'm going to print N copies of the answer!"
Absurd!
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.
I have an n^3 operation that's currently a huge bottleneck at only 10k elements. Not sure how to fix it.
The performance improvement that GitLab contributed to Git is slated to be released with v2.50.0: https://github.com/git/git/commit/bb74c0abbc31da35be52999569...
Nice that GitLab is active upstream! Do I see correctly that the most active contributors to git are currently GitLab employees?
[1]: https://github.com/git/git/graphs/contributors?from=6%2F3%2F...
Earlier quoted context omitted.
> where linear search beats constant time maps Can you give an example? You said lots of good things in your post, but I struggling to believe this one. Also, it would help to see some wall clock times or real world impact.
You've got to keep in mind that computers aren't the 1-instruction-at-a-time purely sequential machines anymore. Let's say you've got a linear array of bytes, and you want to see if it contains a specific value. What would a modern CPU need to execute? Well, we can actually compare 64 values at a time with _mm512_mask_cmp_epu8_mask! You still need a little bit of setup and a final "did any of them match" check, of co…
A string search algorithm that uses SIMD to do quickly discard a majority of 16, 32 or 64 attempts in parallel, and then verify the surviving ones quadratically (again 16, 32 or 64 bytes at a time) can go a very long way against a sublinear algorithm that understands needle structure, but necessarily needs to process the haystack one byte at a time.
Earlier quoted context omitted.
[flagged]
This is why I said "We are discussing (mostly) tech here". I don't agree that creating a throwaway for every comment is "superior". It's basically spamming and it's even noted in the guidelines. Nazi Germany & Jews issue is different. There's an aspect of forcing, and this is unethical and wrong on so many levels, and I'll just leave the subject here. OTOH, from my perspective if you're afraid that you're writing a s…
Earlier quoted context omitted.
The second law is that O(n * log n) is for practical intents and purposes O(n).
Skiena has a great table in his algorithms book mapping time complexity to hypothetical times for different input sizes. For n of 10^9, where lg n takes 0.03 us and n takes 1 s, n lg n takes 29.9 s and n ^2 takes 31.7 years .
Earlier quoted context omitted.
The GEMM is O(n^3) actually. Transformers are quadratic in the size of their context window.
I read that as a typo given the next sentence. I’m on the fence about cubic time. I was mostly thinking of exponential and factorial problems. I think some very clever people can make cubic work despite my warnings. But most of us shouldn’t. General advice is to be ignored by masters when appropriate. That’s also the story arc of about half of kung fu movies. Did chess solvers really progress much before there was a…
Thank you for the courtesy.
> I think some very clever people can make cubic work despite my warnings.
I think you're selling yourself short. You don't need to be that clever to make these algorithms work, you have all the tools necessary. Asymptotic analysis is helpful not just because it tells us a growth, but also because it limits that growth to being in _n_. If you're doing matmul and n is proportional to the size of the input matrix, then you know that if your matrix is constant then the matmul will always take the same time. It does not matter to you what the asymptotic complexity is, because you have a fixed n. In your program, it's O(1). As long as the runtime is sufficient, you know it will never change for the lifetime of the program.
There's absolutely no reason to be scared of that kind of work, it's not hard.
Earlier quoted context omitted.
Nice that GitLab is active upstream! Do I see correctly that the most active contributors to git are currently GitLab employees?
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%2F...