On Tue, Feb 19, 2013 at 02:59:46PM +0100, Richard Biener wrote:
> This speeds up IVOPTs by optimizing its hottest function when compiling
> polyhedron linpk. The datastructure used for recording use, candidate
> costs (a hashtable) should make O(1) queries on average - but it turns
> out that for use, candidate queries that have no entry recorded in
> it it is O(n) currently. That's because the collision handling does
> not abort when coming across an empty hashtable entry (oops).
>
> Overall compile-time effect is noise (linpk compiles in less than
> a second for me ...), but callgrind tells me it results in a 3%
> compile-time improvement.
>
> There is still the degenerate cases when the hashtable is (almost)
> full (doesn't happen for this testcase), but that's an unrelated issue.
>
> Bootstrap and regtest running on x86_64-unknown-linux-gnu.
>
> Jakub, does this look ok for trunk now or shall I wait for stage1?
>
This:
> /* Round up to the power of two, so that moduling by it is fast. */
> ! for (size = 1; size < s; size <<= 1)
> ! continue;
> }
>
> use->n_map_members = size;
isn't equivalent to:
> /* Round up to the power of two, so that moduling by it is fast. */
> ! size = 1 << ceil_log2 (s + 1);
> }
size = s ? (1 << ceil_log2 (s)) : 1;
would be I think. Is it intentional that for power of 2 you set now size
to double that value?
> --- 2725,2737 ----
> for (i = s; i < use->n_map_members; i++)
> if (use->cost_map[i].cand == cand)
> return use->cost_map + i;
> ! else if (use->cost_map[i].cand == NULL)
> ! return NULL;
> for (i = 0; i < s; i++)
> if (use->cost_map[i].cand == cand)
> return use->cost_map + i;
> + else if (use->cost_map[i].cand == NULL)
> + return NULL;
>
> return NULL;
> }
This looks good to me, even at this point.
Jakub
