Re: code optimization in embedded systems

On Nov 15, 4:30 pm, "Wilco Dijkstra" <Wilco_dot_Dijks...@xxxxxxxxxxxx>
wrote:
All of this can be done in a machine independent way. If you
have 20+ non-dense cases it is pretty obvious that linear search
is much worse than binary search. If you want to do better, then
the traditional way is to let the backend decide when the linear
search becomes better. This may depend not only on the target but
also on the actual case values or the optimization goal.


Indeed: The usual approach is to turn a sparse tree into a hard coded
binary search for the upper part of the tree, and then a linear search
for the lower part. The point where you switch depends on the cost of
mispredicted branches. In the binary tree part, about half the
branches will mispredict (not counting the branch-eq leg of the common
compare / branch-gt / branch-eq construction), in the sequential part,
only one (the one that's actually taken) will mispredict. Each extra
layer of the binary search adds a compare, and half each of a
predicted and mispredicted branch, but halves the number of compares
and correctly predicted branches in the sequential part.

And of course switches with both spares and dense sections often
generate code that does computed branches in the dense parts of the
tree.
.

Relevant Pages

  • Re: Linear search vs. Binary search (was: Assembler code)
    ... If usage of the function request codes were uniformly distributed, the average number of list item comparisons with five items for binary search would be 2.2 versus 3.0 for linear search, but each comparison in the binary search requires slightly more control instructions. ... You then did a branch to subroutine to register "n" to execute ...
    (bit.listserv.ibm-main)
  • Re: Binary Search
    ... it "totally defeats the purpose of binary search" and "your performance ... A hybrid approach is obviously better than just plain sequential ... search will go faster than a plain linear search. ... the first hit could take ...
    (comp.lang.pascal.delphi.misc)
  • Re: Search algorithm to use
    ... >binary search like the one I illustrated. ... and the simple linear search was only 25% slower than ... >less competent programmers, and because the myth of it being difficult ... >outperforms even the fully unrolled linear search. ...
    (comp.lang.c)
  • Re: Search algorithm to use
    ... > One comparison suffices if you use a sentinel. ... The linear search needs an increment. ... > binary search which is just about a wash. ... compare was "expensive" relative to other operations. ...
    (comp.lang.c)
  • binary search has a longer combinational delay than linear search
    ... I spent quite a lot of time building an HDL design that I thought ... elsif x<B1 then ... I assumed from my schooling that a binary search for the correct ... the linear search has a shorter combinational delay and therefore can ...
    (comp.lang.vhdl)