Products > Programming

Benchmark: C/C++ Efficient Searching

<< < (3/3)

udok:
I have made an update to the benchmarks.
Pictures are attached.

The first picture shows the search results for random integer keys.

Now I tested some "branchless" search methods.

With the branchless versions, an "if-else" is replaced by a
a "conditional-move".

"AVL-tree" and "bsearch-inline" are partially branchless.
"bsearch-branchless" is completely branchless,
which means that the search is always terminated after log2(N) comparisons.

Binary search methods jump through the array quite random,
and the CPU branchpredictor does not work well with random jumps.
The conditional move instructions does not have this problem, because
the same code path is always executed, and thus the CPU pipeline stays full.

This brings a considerable speed advantage, provided that
the data fits into the L2 cache.

The second picture shows the search results for random zero terminated strings.

Here you can see, that in practice the differences between the
search methods are much smaller, because the relatively slow strcmp()
function dominates the time.

Only the hash search methods stand out positively, because the strcmp()
function is executed only once.

Navigation

[0] Message Index

[*] Previous page

There was an error while thanking
Thanking...
Go to full version