Re: [cxx-conversion] New Hash Table (issue6244048)

[Lawrence Crowl <crowl at google dot com>]

On 5/24/12, Jakub Jelinek <jakub@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