Live data from Hacker News

Your code is fast if you're lucky

tiki.li

11–20 of 90 posts

Re: Your code is fast if you're lucky

#11
post #2

I really envy programmers who are so skilled at this kind of low-level optimization. The same meaning, but different performance based on notation—it's ultimately about entering LLVM's optimization pass, which likely comes down to differences in the internal IR pattern. It almost feels like a difference in innate talent... I feel like I can build CRUD applications well enough, but I still seem to be weak at low-level…

Expose yourself to lower level technologies (compilers and optimization techniques, hardware history and design) and let curiosity guide you. Learn how to profile and analyze program performance.

Re: Your code is fast if you're lucky

#12
post #2

I really envy programmers who are so skilled at this kind of low-level optimization. The same meaning, but different performance based on notation—it's ultimately about entering LLVM's optimization pass, which likely comes down to differences in the internal IR pattern. It almost feels like a difference in innate talent... I feel like I can build CRUD applications well enough, but I still seem to be weak at low-level…

Got to my first job out of college and they gave me core dumps and had me debug the kernel for a year. Not my kind of fun, but definitely got me skilled in the art of low level.

Re: Your code is fast if you're lucky

#13
post #2

I really envy programmers who are so skilled at this kind of low-level optimization. The same meaning, but different performance based on notation—it's ultimately about entering LLVM's optimization pass, which likely comes down to differences in the internal IR pattern. It almost feels like a difference in innate talent... I feel like I can build CRUD applications well enough, but I still seem to be weak at low-level…

You could read compiler books, but I would actually recommend reading about CPUs and computer architecture directly. If you understand how the hardware works, then the optimizations are all very natural and fit into the picture perfectly, instead of being some arcane compiler magic that you have to take as a disconnected fact.

Personally I actually haven't read too many books on optimizations, I just absorbed information over years one thing at a time, but something like Computer Organization and Design is a pretty good intro to the low-level picture. If you want to drown in extremely dense technical topics that will give you a lot of jumping off points to search, read Agner Fog's microarchicture optimization guide (https://www.agner.org/optimize/). It won't tell you what LLVM is doing, but it'll tell you why it's doing it. Fair warning, it's dense and pretty dry.

Then it depends how interested you are in doing low-level nonsense. If you spend a lot of time writing performance oriented systems code, you'll come to use profiling tools that show you the assembly. If you stare at it long enough, you sometimes start to question why the compiler wrote it this way. And you're naturally led as you try to optimize your code to wonder how LLVM is coming up with this ASM that it spits out and why it sometimes gets it wrong.

There's nothing magical or that requires innate talent. You can learn all of this very naturally if you work close to the metal and take the time to question how the abstraction layer below you actually works. If you keep doing this, you eventually find out it's not that deep, it's just a lot of stuff accumulated over time, but none of it particularly difficult or inaccessible.

Re: Your code is fast if you're lucky

#14
Is it only me..?

Quicksort is supposed to be an algorithm that has O(n) to O(n²) performance and O(n log n) being only an average performance case. Test was made on random data coming from different archs (so I doubt it's characteristic would be remotely identical).

Given input size of 50M it means that performance could be between 50M (5e7) up to 2.5e15. That's like performance instability of 8 orders of magnitude.

I'm not sure here if we can't write instead that "Your code is fast if you picked fast case for it" especially since fix of 6 OOM is smaller than algorithm's performance range.

Re: Your code is fast if you're lucky

#15
post #2

I really envy programmers who are so skilled at this kind of low-level optimization. The same meaning, but different performance based on notation—it's ultimately about entering LLVM's optimization pass, which likely comes down to differences in the internal IR pattern. It almost feels like a difference in innate talent... I feel like I can build CRUD applications well enough, but I still seem to be weak at low-level…

I did Nand2Tetris and then I understod why I need to vectorize. You get a view from nand-gate to software and get to see all the interfaces. Its a wonderful course.

Re: Your code is fast if you're lucky

#16
post #13
post #2

I really envy programmers who are so skilled at this kind of low-level optimization. The same meaning, but different performance based on notation—it's ultimately about entering LLVM's optimization pass, which likely comes down to differences in the internal IR pattern. It almost feels like a difference in innate talent... I feel like I can build CRUD applications well enough, but I still seem to be weak at low-level…

You could read compiler books, but I would actually recommend reading about CPUs and computer architecture directly. If you understand how the hardware works, then the optimizations are all very natural and fit into the picture perfectly, instead of being some arcane compiler magic that you have to take as a disconnected fact. Personally I actually haven't read too many books on optimizations, I just absorbed informa…

I also agree that computer architecture is more important - it grounds your understanding of how to write efficient code regardless of platform since most machines today share very similar ideas (OOO execution, caches, NUMA etc).

How ever, I will disagree slightly that all the optimizations compilers do are about optimizing for a given architecture; some transformations are just weird algorithmic black magic about optimizing the underlying code itself. Knowing how to make sure the compiler sees through a given construct to give you the low level expression you want is too much art and randomness; we need better ways to express optimization expectations so that if the compiler fails to match expectations it becomes a loud compiler error.

Re: Your code is fast if you're lucky

#17
post #14

Is it only me..? Quicksort is supposed to be an algorithm that has O(n) to O(n²) performance and O(n log n) being only an average performance case. Test was made on random data coming from different archs (so I doubt it's characteristic would be remotely identical). Given input size of 50M it means that performance could be between 50M (5e7) up to 2.5e15. That's like performance instability of 8 orders of magnitude.…

I’m assuming he measured time by averaging on 100s of instances, or he maintained the exact same input for both versions of code. Would be a big oversight if not!

Re: Your code is fast if you're lucky

#18
post #14

Is it only me..? Quicksort is supposed to be an algorithm that has O(n) to O(n²) performance and O(n log n) being only an average performance case. Test was made on random data coming from different archs (so I doubt it's characteristic would be remotely identical). Given input size of 50M it means that performance could be between 50M (5e7) up to 2.5e15. That's like performance instability of 8 orders of magnitude.…

I hope the test data is the same when comparing the different runs. So the big o notation should be the same across different runs.

Re: Your code is fast if you're lucky

#19
post #14

Is it only me..? Quicksort is supposed to be an algorithm that has O(n) to O(n²) performance and O(n log n) being only an average performance case. Test was made on random data coming from different archs (so I doubt it's characteristic would be remotely identical). Given input size of 50M it means that performance could be between 50M (5e7) up to 2.5e15. That's like performance instability of 8 orders of magnitude.…

if you have decent (randomized) pivoting, you never hit the worst case or anything like it

Re: Your code is fast if you're lucky

#20
post #14

Is it only me..? Quicksort is supposed to be an algorithm that has O(n) to O(n²) performance and O(n log n) being only an average performance case. Test was made on random data coming from different archs (so I doubt it's characteristic would be remotely identical). Given input size of 50M it means that performance could be between 50M (5e7) up to 2.5e15. That's like performance instability of 8 orders of magnitude.…

Looking at big-O isn't very informative. We have plenty of statistical tools for telling whether there is an effect even with noisy data.
Post reply on HN