News for hackers. Stuff that matters.
Re:Do Not Taunt Happy Fun Branch Predictor by londons_explore on Wednesday January 25, 2023 @01:36PM (#34522302)
Observation: Almost any code, when micro-optimized, can gain about 10x performance.

So, if we had the time and energy, we could probably make all of computing at least 10x faster.

But we don't have the time or energy to dedicate that much effort to every line of code... But perhaps AI does?

Re:Do Not Taunt Happy Fun Branch Predictor by celeritascelery on Wednesday January 25, 2023 @01:40PM (#34522355)
I don’t think that is generally true. He only got a large speedup because he used SIMD, which has nothing to do with micro optimization. I would say a better take away is that micro optimization is really hard and you will often make things worse if you don’t know what you are doing. Even if you do, you are only going to get a few percentage points.
Re:Do Not Taunt Happy Fun Branch Predictor by thethirdone on Wednesday January 25, 2023 @02:16PM (#34522836)
My experience micro optimizing things is that even without SIMD, most software can get at least a 5x in performance. With SIMD, you can often get 50x improvements.

The reason why people thing "Even if you do, you are only going to get a few percentage points." is because it generally takes 5-50x the developer time to optimize such code. If it takes half a day to write naive code to do something like validate utf8, it probably takes ~25 workdays to make a fast SIMD version. If you instead spend an extra half a day, there is a good chance you get a 10-50% speedup using normal code.

Re:Do Not Taunt Happy Fun Branch Predictor by mumumu on Wednesday January 25, 2023 @02:54PM (#34523273)
This is true on a few streaming application (such as parsing).

And most of the speedup is because of tricks to avoid doing beaches. There is a great blog post from one of the authors of JSON SIMD discussing this.

I'm on mobile, there is a link for the blog post on the simd JSON github repository.

Re:Do Not Taunt Happy Fun Branch Predictor by mumumu on Wednesday January 25, 2023 @10:12PM (#34527290)
*avoid branches

The blog post I mentioned:

Paper: Parsing Gigabytes of JSON per Second https://branchfree.org/2019/02/25/paper-parsing-gigabytes-of...

Another related post from Lemire:

Ridiculously fast unicode (UTF-8) validation https://lemire.me/blog/2020/10/20/ridiculously-fast-unicode-...

Those algorithms are fast. But to put them in perspective. A single x86 CPU can write 64B per cycle. At 5GHz, the theorical maximum bandwidth is 320 GBps. IIRC, the read bandwidth is twice that.

There are others botlenecks, and is very hard to write code that writes at every cycle.

A interesting consequence, is that the theorical maximum bandwidth is logarithmical to the number of cycles. Again, talking about branchless streaming application.

Re:Do Not Taunt Happy Fun Branch Predictor by bee_rider on Wednesday January 25, 2023 @04:50PM (#34524658)
It also can we weird and non-obvious. For example depending on the instruction mix and hardware it might not be worth getting dinged by AVX-512 clocks. And if you are, say, writing the UTF validation code as a library (more favorable to put effort into a library!) you might not know where the code is being used, so you might not even know the instruction mix…
Re:Do Not Taunt Happy Fun Branch Predictor by fluoridation on Wednesday January 25, 2023 @01:52PM (#34522518)
Not true by a long shot, unfortunately. Getting even a 100% performance gain out of manual optimization is unusual. Usually the only way to get significant gains is by either switching algorithms or by relaxing problem requirements.
Re:Do Not Taunt Happy Fun Branch Predictor by cozzyd on Wednesday January 25, 2023 @06:19PM (#34525578)
It... depends. Often things like changing memory layout, intelligent prefetching, etc. can make a pretty big difference.
Re:Do Not Taunt Happy Fun Branch Predictor by Pet_Ant on Wednesday January 25, 2023 @01:56PM (#34522584)
Whenever you read/hear/think "AI" replace it with "a probabilistic process". If you can validate the output then it's really a beam search ( https://en.wikipedia.org/wiki/Beam_search ) of the solution space, and not really "AI".

If you can't, then it's really a crap shoot as to whether the output is at all valid. If we want to use more opaque processes, I think we need more transparent outputs. If a neural net can produce a machine checkable proof or supply it with the optimisation that's great, but otherwise it's just hot air.

Re:Do Not Taunt Happy Fun Branch Predictor by david2ndaccount on Wednesday January 25, 2023 @02:10PM (#34522774)
He didn’t gain 10x from a micro optimization, he gained that much by converting it to use SIMD which is a macro optimization. You usually have to structure your program in such a way to be SIMD friendly. In this case it was already simd-friendly (adding a large number of floats).
Re:Do Not Taunt Happy Fun Branch Predictor by Jensson on Wednesday January 25, 2023 @03:38PM (#34523849)
> In this case it was already simd-friendly (adding a large number of floats).

So it was micro optimization afterall!

Re:Do Not Taunt Happy Fun Branch Predictor by lmm on Wednesday January 25, 2023 @05:25PM (#34525026)
It was a micro optimization because it was a toy example. Doing floating-point arithmetic (and not already using BLAS etc.) is very niche in real code.
Re:Do Not Taunt Happy Fun Branch Predictor by Jensson on Wednesday January 25, 2023 @05:28PM (#34525042)
It is still micro optimization to ensure that those instructions are used when the compiler is too dumb to use them. You can say that they are niche, but that is different from it being micro optimization.
Re:Do Not Taunt Happy Fun Branch Predictor by lmm on Wednesday January 25, 2023 @06:23PM (#34525615)
It's not the compiler being dumb, it won't use those extensions because they reassociate the arithmetic and change the result - and setting that compiler flag is very much a macro rather than micro change.
Re:Do Not Taunt Happy Fun Branch Predictor by Jensson on Wednesday January 25, 2023 @07:01PM (#34526000)
But he didn't set the compiler option, he rewrote it to explicitly use those instructions, that is micro optimization no matter how you look at it. The reason micro optimization is so easy to get better than compiler results is that you know things about the data the compiler doesn't, like in this case you know it is fine to reorder the result while the compiler is too dumb to know that. You need much smarter compilers than we have today in order for such micro optimizations to stop paying dividends.
Re:Do Not Taunt Happy Fun Branch Predictor by lmm on Wednesday January 25, 2023 @07:31PM (#34526252)
Making sure it will behave correctly with that change (which changes the result of the function!) is a macro change - you have to trace the implications all the way through the program.
Re:Do Not Taunt Happy Fun Branch Predictor by shoo on Wednesday January 25, 2023 @02:11PM (#34522787)
> Almost any code, when micro-optimized, can gain about 10x performance.

well, it depends on where you start from. the speedups can become arbitrarily impressive sounding when the starting point is arbitrarily inefficient.

e.g. if you're starting with a python script that wasn't written with performance in mind and has ended up being compute-bound in pure python number crunching code, if you rewrite the thing in C while thinking a little about appropriate data structures and memory allocation/access -- i.e. replacing a festival of python dict lookups and very frequent memory allocation for tiny intermediate results with indexing into preallocated arrays or so on -- it's quite common to see speedups of 500x - 1000x. this is before micro-optimisation, before introducing SIMD or multi-threading or setting the compiler to build for your exact CPU or so on.