4 ms·

> as it's not a very stateful algorithm It might be stateless, but it depends on many things unknown at compile time. One of them is the input data being proc

> as it's not a very stateful algorithm 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.

scottlamb 3y ago
> > > as it's not a very stateful algorithm > 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. Are you and 3cats-in-a-coat are talking about the same "it"? I think they're talking about the work that requires such a long pipeline [1], as they've stated that doing more ahead of time would reduce the length of the pipeline and thus importance of accurate branch prediction. You are talking about...the branch predictor? the application's algorithm being executed (binary search in this case)? [1] my CPU microarchitectural knowledge isn't that good; I have only the vaguest idea of what that is. Register renaming / data dependency analysis / instruction scheduling, maybe? translation to micro-ops? other things? don't know!

scottlamb 3y ago

> > > as it's not a very stateful algorithm > 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. Are you and 3cats-in-a-coat are talking about the same "it"? I think they're talking about the work that requires such a long pipeline [1], as they've stated that doing more ahead of time would reduce the length of the pipeline and thus importance of accurate branch prediction. You are talking about...the branch predictor? the application's algorithm being executed (binary search in this case)? [1] my CPU microarchitectural knowledge isn't that good; I have only the vaguest idea of what that is. Register renaming / data dependency analysis / instruction scheduling, maybe? translation to micro-ops? other things? don't know!