This is the mail archive of the
gcc@gcc.gnu.org
mailing list for the GCC project.
Re: GCC Optimisation, Part 0: Introduction
On Thu, Apr 28, 2011 at 9:13 PM, Robert Dewar <dewar@adacore.com> wrote:
> I think the hash table is a much better choice than the B+ tree. You
> really are much more interested in average case performance in a compiler
> than worst case, especially when the worst case will not
> happen in practice.
Basically, I agree with you. Hash table is better in most cases, but
is not always better, especially on ultra large key set.
O(1) is better than O(log(n)), but is not much better. If you have 1
million elements, at most, you only need 20 comparisons. Comparison
may be much cheaper than hashing. 20 comparisons may be faster than
1 hashing.
--
Chiheng Xu
Wuhan,China