[PATCH] Speedup IVOPTs

Richard Biener rguenther@suse.de
Tue Feb 19 15:09:00 GMT 2013


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 <rguenther@suse.de>
SUSE / SUSE Labs
SUSE LINUX Products GmbH - Nuernberg - AG Nuernberg - HRB 16746
GF: Jeff Hawn, Jennifer Guild, Felix Imend



More information about the Gcc-patches mailing list