i#1114 JIT optimization: replace trace head hashtable

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

Replaces the custom trace head hashtable with the generic
open-address table, eliminating hotspots in runs of Octane
that need the hashtable to expand. Also reduces memory
usage and improves code sharing.
---------------

[Byron, 2015-12-03 23:02:50]

https://codereview.appspot.com/279260043/diff/1/core/monitor.c
File core/monitor.c (left):

https://codereview.appspot.com/279260043/diff/1/core/monitor.c#oldcode456
core/monitor.c:456: #if 0 /* not used */
I'm removing this because it's not used, and it becomes a one-line call to the
generic table.

[bruening, 2015-12-04 21:18:49]

Re: persistent trace head counters: see my thesis Section 2.3.2 page 49 where it
was found to be best to keep the counter values across capacity eviction of
trace head blocks.

[bruening, 2015-12-04 21:24:49]

Are you waiting on anything else from me?  I assume you'll upload a new patchset
here?

[Byron, 2015-12-04 21:32:53]

On 2015/12/04 21:24:49, bruening wrote:
> Are you waiting on anything else from me?  I assume you'll upload a new
patchset
> here?

This is the new version, with the generic hashtable (I abandoned the other one
because the code changes are 100% different). I just need to add the comment
about the trace head persistence.

[bruening, 2015-12-05 02:52:47]

LGTM

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

https://codereview.appspot.com/279260043/diff/1/core/monitor.c#newcode352
core/monitor.c:352: md = heap_alloc(dcontext, sizeof(monitor_data_t)
HEAPACCT(ACCT_TRACE));
I think you will get warnings with clang here, best to leave the cast

https://codereview.appspot.com/279260043/diff/1/core/monitor.c#newcode445
core/monitor.c:445: } while (true);
optional: we could add a generic_hash_range_remove()

[Byron, 2015-12-05 08:51:00]

Commit log for latest patchset:
---------------
i#1114 JIT optimization: replace trace head hashtable

Replaces the custom trace head hashtable with the generic
open-address table, eliminating hotspots in runs of Octane
that need the hashtable to expand. Also reduces memory
usage and improves code sharing.

Review-URL: https://codereview.appspot.com/279260043
---------------

[Byron, 2015-12-05 08:53:26]

Please check the API of the new generic_hash_range_remove(). I tried to match
the template's range remove.

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

https://codereview.appspot.com/279260043/diff/1/core/monitor.c#newcode352
core/monitor.c:352: md = heap_alloc(dcontext, sizeof(monitor_data_t)
HEAPACCT(ACCT_TRACE));
On 2015/12/05 02:52:47, bruening wrote:
> I think you will get warnings with clang here, best to leave the cast

Done.

https://codereview.appspot.com/279260043/diff/1/core/monitor.c#newcode445
core/monitor.c:445: } while (true);
On 2015/12/05 02:52:47, bruening wrote:
> optional: we could add a generic_hash_range_remove()

Done.

[bruening, 2015-12-07 04:35:25]

https://codereview.appspot.com/279260043/diff/20001/core/hashtable.c
File core/hashtable.c (right):

https://codereview.appspot.com/279260043/diff/20001/core/hashtable.c#newcode196
core/hashtable.c:196: int iter = 0;
I thought this could just use hashtable_generic_range_remove() from
hashtablex.h?

[Byron, 2015-12-07 07:01:40]

Commit log for latest patchset:
---------------
i#1114 JIT optimization: replace trace head hashtable

Replaces the custom trace head hashtable with the generic
open-address table, eliminating hotspots in runs of Octane
that need the hashtable to expand. Also reduces memory
usage and improves code sharing.

Review-URL: https://codereview.appspot.com/279260043
---------------

[Byron, 2015-12-07 07:03:34]

https://codereview.appspot.com/279260043/diff/20001/core/hashtable.c
File core/hashtable.c (right):

https://codereview.appspot.com/279260043/diff/20001/core/hashtable.c#newcode196
core/hashtable.c:196: int iter = 0;
On 2015/12/07 04:35:24, bruening wrote:
> I thought this could just use hashtable_generic_range_remove() from
> hashtablex.h?

Added a comment that the payload needs to be freed for each removed entry
(similar to generic_hash_remove() above).

[bruening, 2015-12-07 15:53:31]

https://codereview.appspot.com/279260043/diff/20001/core/hashtable.c
File core/hashtable.c (right):

https://codereview.appspot.com/279260043/diff/20001/core/hashtable.c#newcode196
core/hashtable.c:196: int iter = 0;
On 2015/12/07 07:03:34, Byron wrote:
> On 2015/12/07 04:35:24, bruening wrote:
> > I thought this could just use hashtable_generic_range_remove() from
> > hashtablex.h?
> 
> Added a comment that the payload needs to be freed for each removed entry
> (similar to generic_hash_remove() above).

I don't understand: hashtable_generic_range_remove() does call
hashtable_generic_free_entry(), at line 1541 of hashtablex.h.

[Byron, 2015-12-07 19:03:40]

On 2015/12/07 15:53:31, bruening wrote:
> https://codereview.appspot.com/279260043/diff/20001/core/hashtable.c
> File core/hashtable.c (right):
> 
>
https://codereview.appspot.com/279260043/diff/20001/core/hashtable.c#newcode196
> core/hashtable.c:196: int iter = 0;
> On 2015/12/07 07:03:34, Byron wrote:
> > On 2015/12/07 04:35:24, bruening wrote:
> > > I thought this could just use hashtable_generic_range_remove() from
> > > hashtablex.h?
> > 
> > Added a comment that the payload needs to be freed for each removed entry
> > (similar to generic_hash_remove() above).
> 
> I don't understand: hashtable_generic_range_remove() does call
> hashtable_generic_free_entry(), at line 1541 of hashtablex.h.

That will only free the user's payload. But the generic hashtable wraps the
user's payload in a generic_entry_t, which would not be freed in this case. In
hashtable.c, this line assigns the user's free func to the internal callback:

129     table->free_payload_func = free_payload_func;

But the generic_entry_t is freed only by hashtable_generic_free_entry(), which
must be called separately from somewhere in hashtable.c because it is not
assigned to the internal callback. This is why the existing
generic_hash_remove() function explicitly calls hashtable_generic_free_entry()
in addition to calling hashtable_generic_remove(). 

To improve things, we could revise hashtable.c to wrap the user's free func with
its own free func (hashtable_generic_free_entry). That would avoid all of these
extra calls to free the payload wrapper (the generic_entry_t).

[Byron, 2015-12-07 23:48:23]

On 2015/12/07 19:03:40, Byron wrote:
> On 2015/12/07 15:53:31, bruening wrote:
> > https://codereview.appspot.com/279260043/diff/20001/core/hashtable.c
> > File core/hashtable.c (right):
> > 
> >
>
https://codereview.appspot.com/279260043/diff/20001/core/hashtable.c#newcode196
> > core/hashtable.c:196: int iter = 0;
> > On 2015/12/07 07:03:34, Byron wrote:
> > > On 2015/12/07 04:35:24, bruening wrote:
> > > > I thought this could just use hashtable_generic_range_remove() from
> > > > hashtablex.h?
> > > 
> > > Added a comment that the payload needs to be freed for each removed entry
> > > (similar to generic_hash_remove() above).
> > 
> > I don't understand: hashtable_generic_range_remove() does call
> > hashtable_generic_free_entry(), at line 1541 of hashtablex.h.
> 
> That will only free the user's payload. But the generic hashtable wraps the
> user's payload in a generic_entry_t, which would not be freed in this case. In
> hashtable.c, this line assigns the user's free func to the internal callback:
> 
> 129     table->free_payload_func = free_payload_func;
> 
> But the generic_entry_t is freed only by hashtable_generic_free_entry(), which
> must be called separately from somewhere in hashtable.c because it is not
> assigned to the internal callback. This is why the existing
> generic_hash_remove() function explicitly calls hashtable_generic_free_entry()
> in addition to calling hashtable_generic_remove(). 
> 
> To improve things, we could revise hashtable.c to wrap the user's free func
with
> its own free func (hashtable_generic_free_entry). That would avoid all of
these
> extra calls to free the payload wrapper (the generic_entry_t).

Another way to simplify memory management in hashtable.c is to change the entry
type from "generic_entry_t *" to just "generic_entry_t" (i.e., make it an inline
entry). This doubles the size of the table data at first, but once the table
reaches 33% capacity, it starts to reduce memory usage (vs. the pointer
version). It also omits a pointer indirection step, and avoids a ton of
alloc/free calls with the associated code maintenance. 

In my research build, I only use inline entries for the template data structures
and it works great--both faster and smaller, with simpler code.

[bruening, 2015-12-08 06:22:03]

On 2015/12/07 19:03:40, Byron wrote:
> On 2015/12/07 15:53:31, bruening wrote:
> > https://codereview.appspot.com/279260043/diff/20001/core/hashtable.c
> > File core/hashtable.c (right):
> > 
> >
>
https://codereview.appspot.com/279260043/diff/20001/core/hashtable.c#newcode196
> > core/hashtable.c:196: int iter = 0;
> > On 2015/12/07 07:03:34, Byron wrote:
> > > On 2015/12/07 04:35:24, bruening wrote:
> > > > I thought this could just use hashtable_generic_range_remove() from
> > > > hashtablex.h?
> > > 
> > > Added a comment that the payload needs to be freed for each removed entry
> > > (similar to generic_hash_remove() above).
> > 
> > I don't understand: hashtable_generic_range_remove() does call
> > hashtable_generic_free_entry(), at line 1541 of hashtablex.h.
> 
> That will only free the user's payload. But the generic hashtable wraps the
> user's payload in a generic_entry_t, which would not be freed in this case.

No, hashtable_generic_range_remove() calls hashtable_generic_free_entry() which
frees both the user's payload and the generic_entry_t wrapper.  

> In hashtable.c, this line assigns the user's free func to the internal
callback:
> 
> 129     table->free_payload_func = free_payload_func;

That free_payload_func field is specific to generic hashtables.  I'm not sure
what problem you think this line is causing?

> But the generic_entry_t is freed only by hashtable_generic_free_entry(),

That's the routine I'm talking about, which does indeed free the wrapper -- but
you are contradicting your earlier claim here.  Did you mean to point at a
different routine??

> which
> must be called separately from somewhere in hashtable.c because it is not
> assigned to the internal callback. This is why the existing
> generic_hash_remove() function explicitly calls hashtable_generic_free_entry()
> in addition to calling hashtable_generic_remove(). 

No, the reason for that is because the hashtablex.h-provided remove() routine
does not free the payload at all.

[Byron, 2015-12-08 07:26:13]

Commit log for latest patchset:
---------------
i#1114 JIT optimization: replace trace head hashtable

Replaces the custom trace head hashtable with the generic
open-address table, eliminating hotspots in runs of Octane
that need the hashtable to expand. Also reduces memory
usage and improves code sharing.

Review-URL: https://codereview.appspot.com/279260043
---------------

[Byron, 2015-12-08 07:30:35]

> 
> No, hashtable_generic_range_remove() calls hashtable_generic_free_entry()
which
> frees both the user's payload and the generic_entry_t wrapper.  
> 

Ok, now I see what you're saying. It never occurred to me that the template
would declare HTNAME(hashtable_,NAME_KEY,_free_entry) and expect the
instantiation to define it.

So why define this new function generic_hash_range_remove(), when it just
redirects to an existing function hashtable_generic_range_remove()? Just for
naming consistency?

BTW, the FIXME on hashtable.c:142 added to my confusion--it sounds as if the
free func is not really working. Is there really something to fix, or could that
be deleted at this point?

[bruening, 2015-12-08 16:40:09]

On 2015/12/08 07:30:35, Byron wrote:
> So why define this new function generic_hash_range_remove(), when it just
> redirects to an existing function hashtable_generic_range_remove()? Just for
> naming consistency?

Yes, just like generic_hash_clear().
 
> BTW, the FIXME on hashtable.c:142 added to my confusion--it sounds as if the
> free func is not really working. Is there really something to fix, or could
that
> be deleted at this point?

That's talking about HTNAME(hashtable_,NAME_KEY,_free), not
HTNAME(hashtable_,NAME_KEY,_free_entry), as well as complaining about the
remove() issue discussed earlier.

[Byron, 2015-12-08 20:34:11]

Committed as
https://github.com/DynamoRIO/dynamorio/commit/343b99a0000660836eca400f7ad4975...

Final commit log: 
---------------
i#1114 JIT optimization: replace trace head hashtable

Replaces the custom trace head hashtable with the generic
open-address table, eliminating hotspots in runs of Octane
that need the hashtable to expand. Also reduces memory
usage and improves code sharing.

Review-URL: https://codereview.appspot.com/279260043
---------------