Re: g_hash_table_resize (#59026)

[Owen Taylor <otaylor redhat com>]

Darin Adler <darin bentspoon com> writes:

> On Saturday, August 18, 2001, at 10:09  PM, Owen Taylor wrote:
> 
> > +#define G_HASH_TABLE_RESIZE(hash_table)				\
> > +   G_STMT_START {						\
> > +     if (hash_table->nnodes < hash_table->size)			\
> > +       {							\
> > +	 if (hash_table->size < 3 * hash_table->nnodes ||	\
> > +	     hash_table->size <= HASH_TABLE_MIN_SIZE)		\
> > +	   goto __ok;						\
> > +       }							\
> > +     else							\
> > +       {							\
> > +	 if (3 * hash_table->size > hash_table->nnodes ||	\
> > +	     hash_table->size >= HASH_TABLE_MAX_SIZE)		\
> > +	   goto __ok;						\
> > +       }							\
> > +     g_hash_table_resize (hash_table);				\
> > +     __ok:							\
> > +   } G_STMT_END
> 
> I think you should try putting in two calls to g_hash_table_resize
> instead of doing the goto. Many good compilers will still share the
> code for a single function invocation, so you probably won't sacrifice
> code size, and leaving out the gotos can give the optimizer a better
> chance to do a good job.

I've never seen gcc actually combine function calls in such 
circumstances; I don't believe its common-subexpression code
handles expressions/statement with possible side-effects.
It's possible other compilers do better.

Not combining the two function calls doesn't actually slow
the code down much but it does make things a bit bigger.  

Even within GCC, how the compiler treats different variant of
this code is pretty dependent on versions ... gcc
2.95 nails the code generation for:

====
#define G_HASH_TABLE_RESIZE(hash_table)                         \
   G_STMT_START {                                               \
     if ((hash_table->nnodes < hash_table->size &&              \
          hash_table->size >= 3 * hash_table->nnodes &&         \
          hash_table->size > HASH_TABLE_MIN_SIZE) ||            \
         (!(hash_table->nnodes < hash_table->size) &&           \
          3 * hash_table->size <= hash_table->nnodes &&         \
          hash_table->size < HASH_TABLE_MAX_SIZE))              \
           g_hash_table_resize (hash_table);                    \
   } G_STMT_END
====

But gcc-2.96, which generally has considerably better optimization
misses the fact that the two branches of the if are exclusive.

And its dependent on processor ... when I tried timing multiple
versions there was very little consistency in ordering between
a PIII and a celeron. (With total variation being small --
a few percent even in my artificial micro-benchmark)

But, in my tests, one thing I did discover is that the simple
version:

===
#define G_HASH_TABLE_RESIZE(hash_table)                         \
   G_STMT_START {                                               \
     if ((hash_table->size >= 3 * hash_table->nnodes &&         \
          hash_table->size > HASH_TABLE_MIN_SIZE) ||            \
         (3 * hash_table->size <= hash_table->nnodes &&         \
          hash_table->size < HASH_TABLE_MAX_SIZE))              \
           g_hash_table_resize (hash_table);                    \
   } G_STMT_END
===

Was fastest on the PIII, and only a few percent slower than
the best fastest version (my original with the goto) on the
Celeron. Since it is also smallest and clearest, this is most
likely the one to go with....

(Though if a compiler/processor didn't have a fast way of doing
multiplication by 3, it might be a a fair bit slower. GCC uses the
trick of:

        leal    (%ecx,%ecx,2), %eax

depending on the x86's overabundance of addressing modes...)

Regards,
                                        Owen

[ For those playing along at home, the final variant I
  tested, using Darin's idea, was:

#define G_HASH_TABLE_RESIZE(hash_table)                         \
   G_STMT_START {                                               \
     if (hash_table->nnodes < hash_table->size)                 \
       {                                                        \
         if (hash_table->size >= 3 * hash_table->nnodes &&      \
             hash_table->size > HASH_TABLE_MIN_SIZE)            \
           g_hash_table_resize (hash_table);                    \
       }                                                        \
     else                                                       \
       {                                                        \
         if (3 * hash_table->size <= hash_table->nnodes &&      \
             hash_table->size < HASH_TABLE_MAX_SIZE)            \
           g_hash_table_resize (hash_table);                    \
       }                                                        \
   } G_STMT_END
#endif

]