71–80 of 155 posts
Is that still lower_bound? Maybe I am misreading the code but it looks like this returns any match, not the earliest match (when there are dupes). It’s common to have multiple matches even in a unique list if the comparison function is say looking for a certain string prefix to do autocomplete, but we want the earliest in the list.
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 Crusoe CPUs worked. Imagine NOT caring that you have a branch.
After all, if you think about it, all operations are branches. Down to bitwise operations and summing two numbers. It's branching in the ALU, carry bits and what not. You can't compute absolutely anything without looking at the state of one or more bits, and making a decision that changes the outcome. But the reason those branches don't hurt performance is that they're not branches on the main pipeline. These local branches have a very short (or non-existent) "pipeline". And the main pipeline is therefore not affected, despite the actual state of the system is.
lower_bound and upper_bound are typically implemented in terms of partition_point, which is much more general than this version of lower_bound taking an element.
Even more reason to use this if you don't need the more general case and its associated performance cost
> if you don't need the more general case and its associated performance cost
In C++ the "more general case" typically doesn't have a performance cost.
Every 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…
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 do in your world of Branch™es, just only the Branch™es that try and compute the results of more than one future at the same time (i.e. branches).
Every 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'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 in parallel. Multiply can be issued on pipeline0, pipeline1, or pipeline5.
If there are 3 multiply instructions, all three pipelines (p0, p1, and p5) all get issued a multiply on _THIS_ clock tick.
----------
The analysis must be dynamic because instructions such as "mov" can take a variable amount of time: loading data from L1 cache is 4-clock ticks, L2 cache is 40 clock ticks, L3 cache is ~150 clock ticks, and RAM is 400+ clock ticks.
That means a "lazy" strategy, where you analyze the state of the pipeline "as late as possible" before making a decision wins out. If you do pre-analysis (ie: what Intel's compiler was supposed to do with Itanium), you pretty much lose out on all variable-time instructions (ex: cache vs RAM).
If you know for certain that you have no memory-operations, then you probably should use a GPU instead of a CPU.
---------
theLoop:
mov ebx, eax[ecx] ; y = array[x]
add ebx, edx ; y += z
add ecx, 4
cmp ecx,
jnz theLoop
"add ecx, 4" can actually be done right now in parallel. You split ecx into two registers (ecx-old and ecx-new). You issue "mov ebx, eax[ecx-old]", and then you can execute future instructions with ecx-new. If the next loop is branch predicted (as would be the case in binary search, since you almost always loop), the pipeline/branch prediction stuff works together and you can execute mov ebx, eax[ecx0], mov ebx, eax[ecx1], mov ebx, eax[ecx2], mov ebx, eax[ecx3]... all in parallel (!!!!), as ecx3 gets branch predicted and multiple loops start running in parallel..
Its not hard, its not very difficult analysis, its low power. 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.
----------
Furthermore, most code with branches can seemingly be replaced with branchless code (ex: cmov instructions, min instruction, max instruction, etc. etc.)
So instead of magic compilers trying to solve an unsolvable problem (how do you schedule memory load/stores to keep the processor busy even though you don't know how long any memory operation takes...)... you write a magic compiler that solves a very easy to solve problem. (IE: convert the branchy-if statement into a branchless max or branchless cmov instruction instead).
--------
EDIT: I added "theLoop:" to the assembly above, because I realized that "branches" can be beneficial in the face of OoO / Tomasulo's algorithm. "Executing future loops" before the 1st loop is done is very beneficial.
Earlier quoted context omitted.
I don't know much about Rust data types or Rust in general but does it not have any integer overflow? I see (left+right)/2. Is it like python with unbounded precision?
It’s bounded precision, but Rust limits the max size of an object/array to isize’s max[1], not usize’s max. So adding two isize::MAX values using usize will never overflow. [1]: https://doc.rust-lang.org/stable/reference/types/numeric.htm...
Every 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…
It might be stateless, but it depends on many things unknown at compile time.
One of them is the input data being processed. Binary search is exactly that, compiler don’t know at which position the result will be found.
Another one is micro-architecture, most notably cache hierarchy, and composition of EUs inside codes. If you switch to ISA with instructions resembling the micro-ops of the current CPUs, you’ll have to re-compile for every micro-architecture. However, this one is technically solvable with JIT compiler in OSes, like current GPUs where programs ship in byte code formats (DXBC, SPIR-V, NVPTX) then user-mode half of GPU driver recompiles into actual hardware instructions.
Another huge one, other CPU threads are running unknow code. Even if you drop hyper-threading making cores independent, there’re still resources shared across the complete chip: L3 cache, off-chip memory, I/O bandwidth, and electricity i.e. thermals.
Earlier quoted context omitted.
> Also, what's wrong with C? Oodles and oodles of undefined behaviour, for example. C ain't clean.
Nah, thanks to CompCert[1] C actually has one of the highest quality and most predictable compilers. [1] https://compcert.org/
How can you call it branchless if it has "while (length > 0) {"
https://github.com/ehrmann/branchless-binary-search/blob/mas...