Earlier quoted context omitted.
Except I am too busy to read "You’re a busy person"
But not too busy to read the comments!
The comments have a higher density of opinions and experience.
Fastest branchless binary search
91–100 of 155 posts
Re: Fastest branchless binary search
#92Every time I see people trying to eliminate branches, I wonder, do we realize that having long pipelines where a branch misprediction stalls the pipeline is not actually a necessary part of architecture? The pipeline is long because we do lots of analysis and translation on the fly, just in time, which could easily be done in most cases ahead of time, as it's not a very stateful algorithm. This is how Transmeta Cruso…
> After all, if you think about it, all operations are branches Isn't this definition the crux of it? If you redefine everything as a Branch™, even things that are not branches, then you can definitely precompute some Branch™es. But the sort of non-Branch™ branch elimination is talking about actually branching computation routes in code due to an if/else statement or similar, is it not? That would still be useful to…
[deleted]
Re: Fastest branchless binary search
#93Every time I see people trying to eliminate branches, I wonder, do we realize that having long pipelines where a branch misprediction stalls the pipeline is not actually a necessary part of architecture? The pipeline is long because we do lots of analysis and translation on the fly, just in time, which could easily be done in most cases ahead of time, as it's not a very stateful algorithm. This is how Transmeta Cruso…
> The pipeline is long because we do lots of analysis and translation on the fly, just in time, which could easily be done in most cases ahead of time, as it's not a very stateful algorithm. You're going down the wrong path, again, as Intel did with Itanium. We have pipelines because CPUs are performing Tomasulo's algorithm at runtime, because there are 10 pipelines in practice (for Intel systems), and all can be run…
I have little experience in hardware related performance optimizations, so excuse me if some of the things you wrote went over my head. But this sentence:
> Everyone does this parallel computation now. If you go static / compiled ahead-of-time, you can't do this kind of thing anymore. So you lose out in speed compared to regular CPUs that have OoO analysis going on.
Are you implying that in JIT compiled languages I can care less about making my code branchless, since both CPU and JIT compiler will optimize to a branchless version on the fly whereever possible, whereas in AoT compiled languages such as C++ I loose this edge?
Are JIT compiled languages just better when it comes to utilizing the branch predictor?
Re: Fastest branchless binary search
#94>gcc has __builtin_expect_with_probability(cond, 0, 0.5) but it does nothing (tested v10). ↩ I wonder what could possibly be the use of this builtin. Branch prediction varies enough between different processors that it seems unlikely that anything useful could be done with a fine-grained probability estimate.
There are ARM processors where bits in the branch instructions encode whether they should be predicted as taken or not. So on such architectures such hints can be useful. On x86-64, however, they are afaik completely useless (from an optimization perspective).
Re: Fastest branchless binary search
#95Earlier quoted context omitted.
> The pipeline is long because we do lots of analysis and translation on the fly, just in time, which could easily be done in most cases ahead of time, as it's not a very stateful algorithm. You're going down the wrong path, again, as Intel did with Itanium. We have pipelines because CPUs are performing Tomasulo's algorithm at runtime, because there are 10 pipelines in practice (for Intel systems), and all can be run…
I have little experience in hardware related performance optimizations, so excuse me if some of the things you wrote went over my head. But this sentence: > Everyone does this parallel computation now. If you go static / compiled ahead-of-time, you can't do this kind of thing anymore. So you lose out in speed compared to regular CPUs that have OoO analysis going on. Are you implying that in JIT compiled languages I c…
JIT is completely separate issue entirely. I'm not talking about C++ vs Java here. I'm talking about the designs of different assembly languages.
I'm talking about Intel Itanium (ia64) vs AMD x86-64. Or VLIW (compiler-driven parallelism) vs Out-of-Order pipelined processors.
Intel Itanium had "premade bundles". Without getting into too far into the weeds, *the compiler* was responsible for discovering parallelism. The compiler then bundled instructions together
So think of this code:
theLoop:
mov ebx, eax[ecx] ; y = array[x]
add ebx, edx ; y += z
add ecx, 4
cmp ecx,
jnz theLoop
mov ebx, eax[ecx] ;
add ebx, edx : add ecx, 4; // This line executed in parallel
cmp ecx;
jnz theLoop
But look at how few optimizations are available to Itanium or its compiler!! The amount of parallelism in practice (for classic x86 code) was much bigger, especially when you consider Tomasulo's Algorithm.
Re: Fastest branchless binary search
#96Every time I see people trying to eliminate branches, I wonder, do we realize that having long pipelines where a branch misprediction stalls the pipeline is not actually a necessary part of architecture? The pipeline is long because we do lots of analysis and translation on the fly, just in time, which could easily be done in most cases ahead of time, as it's not a very stateful algorithm. This is how Transmeta Cruso…
Is that you Dave? :-) There was paper[1] comparing superscalar CISC approaches to uniscalar RISC in terms of work done over time versus instructions per clock. I recall telling srk at the time that it was a good treatise on how choosing the metric (IPC vs throughput) can influence ones thinking about what is "good" and what is "bad."
The IPC crowd reasons that if they can get a higher IPC value, then the process guys can crank the clock and everybody wins. The thoughput crowd takes the more pragmatic approach that Moore's law is dead and making silicon clock faster melts it so being clever in the ISA wins the day. Both camps have had successes and setbacks over the last 20 years.
I am really enjoying the RISC-V stuff which is getting back into this level of question with regard to CPU architectures. Also a good place to look if you want to catch up on what "modern" superscalar ideas are being added with support of instruction set flexibility. My guess is that wins the game in the long run.
[1] This was in the early oughts so could have been HotChips, Microprocessor Forum, or HPC workshops.
Re: Fastest branchless binary search
#97Every time I see people trying to eliminate branches, I wonder, do we realize that having long pipelines where a branch misprediction stalls the pipeline is not actually a necessary part of architecture? The pipeline is long because we do lots of analysis and translation on the fly, just in time, which could easily be done in most cases ahead of time, as it's not a very stateful algorithm. This is how Transmeta Cruso…
You could rephrase that the pipeline is long because there is a lot of independent work that you can do in a processor. Consider, for every independent operation that can be done, you can potentially do that much at the same time.
And I don't just mean decode, fetch, and execute. If your computer has independent ALU and Shifting units, you can potentially be shifting something as you are also adding. Have a dedicated Adder and a Multiplication unit? No reason you can't try and do both as the same time.
This directly leads to wanting multiple instructions in flight at the same time, which means you have to be able to fetch and decode instructions faster than you are processing them. Also naturally leads to situations where you want to reorder so that the N Add instructions don't keep you from seeing an independent Shift that you could do in the same time.
You can think that things are more complicated than they need to be. And, you may not even be wrong. But a ton of engineering is going into making what we have. If you think you can make something a ton faster by not doing it this way, probably a good thing to dig into how accurate that claim is.
Re: Fastest branchless binary search
#98Oh, C++, the language where templates are extremely powerful but their usability is so poor that code like this is kind of idiomatic and even compiles:
template This looks generic, it compiles by itself, it contains a fancy word “ForwardIt”, and it works if you try it with a vector or an array. But you can’t actually subtract forward iterators, and binary searching a range of forward iterators is quite silly.
Rust would have required using the correct trait. Maybe C++ will improve the situation in the long run.
Re: Fastest branchless binary search
#99>gcc has __builtin_expect_with_probability(cond, 0, 0.5) but it does nothing (tested v10). ↩ I wonder what could possibly be the use of this builtin. Branch prediction varies enough between different processors that it seems unlikely that anything useful could be done with a fine-grained probability estimate.
I think it is used for code layout: typically you want to make the most often taken branch as fallthrough as it can be slightly faster even when perfectly predicted. I also tried (and failed) to use expect with probability to generate a cmov, but in retrospect it is obvious: the parameter is not the prediction probability, but the taken/not-taken probability, and even a branch that goes either way with 50% probabilit…
>typically you want to make the most often taken branch as fallthrough as it can be slightly faster even when perfectly predicted.
Sure, but that application doesn't require a fine-grained probability estimate.
Re: Fastest branchless binary search
#100>gcc has __builtin_expect_with_probability(cond, 0, 0.5) but it does nothing (tested v10). ↩ I wonder what could possibly be the use of this builtin. Branch prediction varies enough between different processors that it seems unlikely that anything useful could be done with a fine-grained probability estimate.
Read https://en.algorithmica.org/hpc/pipelining/branching/ and the following chapter. TL;DR: you can generate different, and more efficient code if you know how much it is going to be mispredicted.
Nothing in that link shows how a compiler could make use of a fine-grained probability estimate in a practical way to guide optimizations. I'm perfectly aware of the general concept of branch prediction and the annotations that certain architectures have in their instruction sets.