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. I don't think C++ STL map is necessarily better than hash table or B+ tree. For every (Key, Value) pair, it will instantiate a new class, rendering the resulting code size unnecessarily big. >> * ggc_internal_alloc_stat() or maybe implementing proper memory >> management instead of garbage collection, for hottest callers > > My opinion is that a garbage collector is (or can become) a proper memory > manager. > If you really want to switch back to manual memory management, please be > sure to make changes which will be easy to revert. > I believe that the current GCC garbage collector could be improved (but that > is very hard work!) > Agree. -- Chiheng Xu Wuhan,China
