151–160 of 273 posts
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.
For those that haven't read the article yet, scroll down to the flame graph and start reading unit it starts talking about back porting the fix. Then stop.
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.
Modern computers are pretty great at scanning small blocks of memory repeatedly, so n^2 can be faster than the alternative using a map in cases for small N. I spent a lot of time fixing n^2 in blink, but there were some fun surprises: https://source.chromium.org/chromium/chromium/src/+/main:thi... For large N without a cache :nth-child matching would be very slow doing n^2 scans of the siblings to compute the index.…
> where linear search beats constant time maps
Earlier quoted context omitted.
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 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.
> That is not the case in C though, as it is much easier to use arrays and nested loops instead of hash maps.
Earlier 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
Earlier 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
Earlier quoted context omitted.
The second law is that O(n * log n) is for practical intents and purposes O(n).
But sometimes a big enough C can flip which solution helps you hit your margins.
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.
it could have been longer. I still don't know why they were doing backup bundles with two refs :)
1.https://github.com/git/git/commit/bb74c0abbc31da35be52999569...
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.
Yes. I read the whole article thinking that this must have been generated by LLM, because at least the style remembers it.
Earlier quoted context omitted.
Good call. O(N^2) is the worst time complexity because it's fast enough to be instantaneous in all your testing, but slow enough to explode in prod. I've seen it several times before, and it's exactly what happened here.
We just had this exact problem. Tests ran great, production slowed to a crawl.
Earlier quoted context omitted.
Modern computers are pretty great at scanning small blocks of memory repeatedly, so n^2 can be faster than the alternative using a map in cases for small N. I spent a lot of time fixing n^2 in blink, but there were some fun surprises: https://source.chromium.org/chromium/chromium/src/+/main:thi... For large N without a cache :nth-child matching would be very slow doing n^2 scans of the siblings to compute the index.…
> 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.
1. Tokenization (checking if a word is a keyword)
2. Interpretation (mapping an instruction name to its action)
3. ML (encoding low-cardinality string features in something like catboost)
4. JSON parsers (usually key count is low, so parse into a linear-scan hashmap rather than a general-purpose hashmap)
Details vary in the exact workload, the hardware you're using, what other instructions you're mixing in, etc. It's a well-known phenomenon though, and when you're doing a microoptimization pass it's definitely something to consider. 2x speedups are common. 10x or more happen from time to time.
It's similar to (but not _quite_ the same as) the reason real-world binary search uses linear scans for small element counts.
When you go to really optimize the system, you'll also find that the linear scan solution is often more amenable to performance improvements from batching.
As to how much it matters for your composite program? Even at a microoptimization level I think it's much more important to pay attention to memory access patterns. When we wrote our protobuf parser that's all we really had to care about to improve performance (33% less execution time for the entire workload, proto parsing being much better than that). You're much more likely to be able to write sane code that way (contrasted with focusing on instructions and whatnot first), and it's easier to layer CPU improvements on top of a good memory access pattern than to go the other way around.