On Tue, 19 Feb 2013, Jakub Jelinek wrote: > 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?
Well, I used the lame variant to avoid a zero argument to ceil_log2 ... I'll use yours instead. Ok? Thanks, Richard. > > --- 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 > > -- Richard Biener <rguent...@suse.de> SUSE / SUSE Labs SUSE LINUX Products GmbH - Nuernberg - AG Nuernberg - HRB 16746 GF: Jeff Hawn, Jennifer Guild, Felix Imend
