On Thu, Apr 28, 2011 at 2:52 PM, Chiheng Xu <chiheng...@gmail.com> wrote: > On Wed, Apr 27, 2011 at 10:29 PM, Basile Starynkevitch > <bas...@starynkevitch.net> wrote: >> >>> Here are some areas I'll look closer to, as shown by some early profiling >>> I performed: >>> * hash tables (both htab and symtab) >> >> There is probably a lot of tuning possible around GCC hash tables. However, >> I would imagine that tuned performance might depend on the particular >> hardware running the so modified GCC. And C++ is becoming an acceptable >> programming language inside GCC. So replacing current C hashtables by some >> fancier C++ collections might be considered (but I have no idea if this will >> be a performance win, perhaps no!; it could be a readability win.). >> >> Perhaps some hashtables are used to associate data to important structures >> (like gimple) which are difficult to change. Perhaps if you have strong >> measurements that adding information inside gimple instead of keeping an >> hashtable for it you might be able to remove some hashtables, but this is >> difficult, since GCC essential data types have been very hand-optimized. >> > > It seems to me that hash table in GCC is more like mapping(or > dictionary, or associated array, or function(Key->Value)), instead of > containter. > > I think the main problem of hash table is that conflict rate is > unpredictable, so the lookup time is unpredictable. At it's worst > condition, you will run equal method on all the elements to find a > slot. > > Perhaps using B+ tree to implement mapping may be an alternative. > Using hash table , you should implement hash and equal methods. Using > B+ tree, you should only implement compare method. Using B+ tree, the > time complexity of lookup is O(log(n)), which is much better.
Well, with a good hash-function your average lookup complexity is O(1) which is much better. Richard.
