On 5/24/12, Jakub Jelinek <ja...@redhat.com> wrote: > On Thu, May 24, 2012 at 09:43:42AM -0700, Lawrence Crowl wrote: > > Add a type-safe hash table, typed_htab. Uses of this table > > replace uses of libiberty's htab_t. The benefits include less > > boiler-plate code, full type safety, and improved performance. > > You haven't looked at the most important problem of that approach > - code bloat.
Are you claiming that the size of the binary is more important than run-time performance, type safety, and source code size? > hashtab.o .text is currently ~ 4KB on x86_64, in your version > only very small part out of it is shared. In a cc1plus binary > I count roughly 179 htab_create{,_ggc} calls, ignoring the first > parameter (initial size) that is roughly 139 unique hash/eq/del > fn combinations, thus you'll end up with over hundred copies of > most of the hashtab code, First, the new hash table code is smaller because it avoid supporting special cases that we are not using in practice. What was formerly conditional is now unconditional, leading to tighter binaries for a given function. As you say, there will be more functions in the source, leading to an increased executable size. Setting aside run-time performance, why is that size important? > in many of the cases performance critical and thus its I-cache > friendliness is quite important. It is precisely the performance critical code that needs the template approach. The approach avoids two indirect calls, which go across translation units. The optimizer has no ability to inline the often trivial actions within those indirect calls. This problem is most severe in the traverse functions, because the optimize cannot see enough to do anything useful with the loop. The inliner also has no ability to elide comparisons for null function pointers. In short, with the libiberty code, the operations must span a large number of completely useless operations. Those operations disappear with the template approach. The result is that the working set in the cache is much smaller. That said, if you think code size is important for tables that are not performance critical, I can provide a version of the code that simply reuses libiberty and gets the type safety without the performance. I don't have a good intuition for which of those tables are performance-critical, so please give me an idea of which they are. -- Lawrence Crowl