On Mon, May 2, 2011 at 4:16 PM, Jan Hubicka <hubi...@ucw.cz> wrote:
> Hi,
> according to oprofile, libiberty hashing takes about 30% of streaming in time
> and according to callgrind, the most busy cache is node_map cache in the
> streamer.
>
> This patch turns it into pointer-map that also saves about 400MB of memory
> and is bit prettier. I get about 8-10% speedup on Mozilla streaming.
> There are other uses of tree_int map, I could probably convert them, too.
>
> Bootstrapped/regtested x86_64-linux, OK?
>
> Honza
>
> * lto-streamer.c (lto_streamer_cache_insert_1,
> lto_streamer_cache_lookup, lto_streamer_cache_create,
> lto_streamer_cache_delete): Use pointer map instead of hashtable.
> * lto-streamer.h (lto_streamer_cache_d): Turn node_map into
> pointer_map.
> Index: lto-streamer.c
> ===================================================================
> *** lto-streamer.c (revision 173251)
> --- lto-streamer.c (working copy)
> *************** lto_streamer_cache_insert_1 (struct lto_
> *** 348,373 ****
> bool insert_at_next_slot_p)
> {
> void **slot;
> - struct tree_int_map d_entry, *entry;
> unsigned ix;
> bool existed_p;
>
> gcc_assert (t);
>
> ! d_entry.base.from = t;
> ! slot = htab_find_slot (cache->node_map, &d_entry, INSERT);
> ! if (*slot == NULL)
> {
> /* Determine the next slot to use in the cache. */
> if (insert_at_next_slot_p)
> ix = VEC_length (tree, cache->nodes);
> else
> ix = *ix_p;
> !
> ! entry = (struct tree_int_map *)pool_alloc (cache->node_map_entries);
> ! entry->base.from = t;
> ! entry->to = ix;
> ! *slot = entry;
>
> lto_streamer_cache_add_to_node_array (cache, ix, t);
>
> --- 348,367 ----
> bool insert_at_next_slot_p)
> {
> void **slot;
> unsigned ix;
> bool existed_p;
>
> gcc_assert (t);
>
> ! slot = pointer_map_insert (cache->node_map, t);
> ! if (!*slot)
> {
> /* Determine the next slot to use in the cache. */
> if (insert_at_next_slot_p)
> ix = VEC_length (tree, cache->nodes);
> else
> ix = *ix_p;
> ! *slot = (void *)(size_t) (ix);
>
> lto_streamer_cache_add_to_node_array (cache, ix, t);
>
> *************** lto_streamer_cache_insert_1 (struct lto_
> *** 376,383 ****
> }
> else
> {
> ! entry = (struct tree_int_map *) *slot;
> ! ix = entry->to;
>
> if (!insert_at_next_slot_p && ix != *ix_p)
> {
> --- 370,376 ----
> }
> else
> {
> ! ix = (size_t) *slot;
>
> if (!insert_at_next_slot_p && ix != *ix_p)
> {
> *************** lto_streamer_cache_lookup (struct lto_st
> *** 442,455 ****
> unsigned *ix_p)
> {
> void **slot;
> - struct tree_int_map d_slot;
> bool retval;
> unsigned ix;
>
> gcc_assert (t);
>
> ! d_slot.base.from = t;
> ! slot = htab_find_slot (cache->node_map, &d_slot, NO_INSERT);
> if (slot == NULL)
> {
> retval = false;
> --- 435,446 ----
> unsigned *ix_p)
> {
> void **slot;
> bool retval;
> unsigned ix;
>
> gcc_assert (t);
>
> ! slot = pointer_map_contains (cache->node_map, t);
> if (slot == NULL)
> {
> retval = false;
> *************** lto_streamer_cache_lookup (struct lto_st
> *** 458,464 ****
> else
> {
> retval = true;
> ! ix = ((struct tree_int_map *) *slot)->to;
> }
>
> if (ix_p)
> --- 449,455 ----
> else
> {
> retval = true;
> ! ix = (size_t) *slot;
> }
>
> if (ix_p)
> *************** lto_streamer_cache_create (void)
> *** 608,618 ****
>
> cache = XCNEW (struct lto_streamer_cache_d);
>
> ! cache->node_map = htab_create (101, tree_int_map_hash, tree_int_map_eq,
> NULL);
> !
> ! cache->node_map_entries = create_alloc_pool ("node map",
> ! sizeof (struct tree_int_map),
> ! 100);
>
> /* Load all the well-known tree nodes that are always created by
> the compiler on startup. This prevents writing them out
> --- 599,605 ----
>
> cache = XCNEW (struct lto_streamer_cache_d);
>
> ! cache->node_map = pointer_map_create ();
>
> /* Load all the well-known tree nodes that are always created by
> the compiler on startup. This prevents writing them out
> *************** lto_streamer_cache_delete (struct lto_st
> *** 636,643 ****
> if (c == NULL)
> return;
>
> ! htab_delete (c->node_map);
> ! free_alloc_pool (c->node_map_entries);
> VEC_free (tree, heap, c->nodes);
> free (c);
> }
> --- 623,629 ----
> if (c == NULL)
> return;
>
> ! pointer_map_destroy (c->node_map);
> VEC_free (tree, heap, c->nodes);
> free (c);
> }
> Index: lto-streamer.h
> ===================================================================
> *** lto-streamer.h (revision 173251)
> --- lto-streamer.h (working copy)
> *************** typedef void (lto_free_section_data_f) (
> *** 346,355 ****
> struct lto_streamer_cache_d
> {
> /* The mapping between tree nodes and slots into the nodes array. */
> ! htab_t node_map;
> !
> ! /* Node map to store entries into. */
> ! alloc_pool node_map_entries;
>
> /* The nodes pickled so far. */
> VEC(tree,heap) *nodes;
> --- 346,352 ----
> struct lto_streamer_cache_d
> {
> /* The mapping between tree nodes and slots into the nodes array. */
> ! struct pointer_map_t GTY((skip)) *node_map;
If you skip node_map you can end up with false entries for re-used
trees. So I don't think that's a good idea.
Richard.
>
> /* The nodes pickled so far. */
> VEC(tree,heap) *nodes;
>
