i#1114 JIT optimization: resizable trace head counter hashtable

Commit log for first patchset:
---------------
i#1114 JIT optimization: resizable trace head counter hashtable

Make the trace head counter hashtable resizable, since it can
become a bottleneck in the larger Octane benchmarks. This
custom bucket hashtable in monitor.c is better suited for JIT
code than the generic open-address table in hashtable.h,
which developed hotspots from clumping during some benchmarks.
---------------

[bruening, 2015-12-01 01:31:24]

> This custom bucket hashtable in monitor.c is better suited for JIT
> code than the generic open-address table in hashtable.h,
> which developed hotspots from clumping during some benchmarks.

I would like to see this evaluated more thoroughly: is the load factor simply
too small?  Is a different hash function needed?  What about these keys causes
this behavior?  Does this have ramifications for the other hashtables in DR?

But, it seems fine to file an issue on this (please file one) and use this CL
for now, so LGTM w/ comments

https://codereview.appspot.com/271630043/diff/1/core/monitor.c
File core/monitor.c (right):

https://codereview.appspot.com/271630043/diff/1/core/monitor.c#newcode1
core/monitor.c:1: /* **********************************************************
Please update these monitor.h comments:

    /* FIXME: use open-address to save memory, and share code
     * w/ fragment.c?
     */

    /* FIXME: use new generic_table_t and generic_hash_* routines */

https://codereview.appspot.com/271630043/diff/1/core/monitor.c#newcode284
core/monitor.c:284: thcounter_init(dcontext_t *dcontext)
IMHO this should take in a trace_head_table_t*, not a dcontext

https://codereview.appspot.com/271630043/diff/1/core/monitor.c#newcode457
core/monitor.c:457: trace_head_counter_t *e, *prev_e, *next_e;
prev_e is unused

[Byron, 2015-12-02 20:20:21]

On 2015/12/01 01:31:24, bruening wrote:
> > This custom bucket hashtable in monitor.c is better suited for JIT
> > code than the generic open-address table in hashtable.h,
> > which developed hotspots from clumping during some benchmarks.
> 
> I would like to see this evaluated more thoroughly: is the load factor simply
> too small?  Is a different hash function needed?  What about these keys causes
> this behavior?  Does this have ramifications for the other hashtables in DR?
> 
> But, it seems fine to file an issue on this (please file one) and use this CL
> for now, so LGTM w/ comments
> 
> https://codereview.appspot.com/271630043/diff/1/core/monitor.c
> File core/monitor.c (right):
I'm going to try the generic_table_t one more time to see exactly what the issue
is. It seems like there must be a special reason for chains to form, if the
table is sparse enough and the hash function is *phi.

> 
> https://codereview.appspot.com/271630043/diff/1/core/monitor.c#newcode1
> core/monitor.c:1: /*
**********************************************************
> Please update these monitor.h comments:
> 
>     /* FIXME: use open-address to save memory, and share code
>      * w/ fragment.c?
>      */
> 
>     /* FIXME: use new generic_table_t and generic_hash_* routines */
> 
> https://codereview.appspot.com/271630043/diff/1/core/monitor.c#newcode284
> core/monitor.c:284: thcounter_init(dcontext_t *dcontext)
> IMHO this should take in a trace_head_table_t*, not a dcontext
> 
> https://codereview.appspot.com/271630043/diff/1/core/monitor.c#newcode457
> core/monitor.c:457: trace_head_counter_t *e, *prev_e, *next_e;
> prev_e is unused

[Byron, 2015-12-03 09:45:47]

When I try the generic table now, there are no long collisions, so that is
probably the better choice. One issue is the "free entry" function--it does not
provide the dcontext, but the counter tables are thread-local and would benefit
from using the thread-local alloc/free routines. There are several ways to
resolve this:

1. Add the dcontext to the free() callback. 
   - This affects 8 existing instances of the generic table.
2. Add an out-arg for the payload to generic_hash_iterate_remove() (since this
table only uses range-remove). 
   - This would affect only 3 of the existing generic tables (one in
core/unix/os.c and two in core/unix/native_elf.c). 
3. Store the dcontext in each counter. 
   - This is not space efficient.

[bruening, 2015-12-03 15:55:30]

On 2015/12/03 09:45:47, Byron wrote:
> When I try the generic table now, there are no long collisions, so that is
> probably the better choice. One issue is the "free entry" function--it does
not
> provide the dcontext, but the counter tables are thread-local and would
benefit
> from using the thread-local alloc/free routines. There are several ways to
> resolve this:
> 
> 1. Add the dcontext to the free() callback. 
>    - This affects 8 existing instances of the generic table.
> 2. Add an out-arg for the payload to generic_hash_iterate_remove() (since this
> table only uses range-remove). 
>    - This would affect only 3 of the existing generic tables (one in
> core/unix/os.c and two in core/unix/native_elf.c). 
> 3. Store the dcontext in each counter. 
>    - This is not space efficient.

I would vote for #1.