This is the mail archive of the gcc@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: numerical instability and estimate-probability


> In article <20011116173148.B26573@atrey.karlin.mff.cuni.cz> you write:
> >
> >Actualy in this case we are speaking about frequencies (for probabilities
> >it is just OK to use 0 ... 10000 integers).
> >
> >The frequencies can get very huge, so only sane workaround wihtout FP
> >is IMO only inventing the mantisa/exponent at my own :(
> 
> Ehh.. Why do you need a mantissa at all?
> 
> You're kidding yourself if you think the frequencies are exact, so why
> not just do frequencies with logarithmic operations, and always
> represent them as powers-of-two - as a simple integer.
> 
> I assume that you never do addition of frequencies anyway (what would
> that mean?), so you really only ever multiply frequencies with each
> other, no?

I was also thinkingg about logaritmic sollution. But actually I do add
frequencies (to compute frequency of basic block, you need to sub frequencies
of all it's predecesor, thats the rule).
Unfortunately predecesors can be numberous and making error in such case
is relativly important.

Imagine switch statement followed by code.  If the switch do have 200
possibilities I sum together 200 values and I need to get 1, not 0 in case the
switch is executed.

I will try to re-think this, but when I was oriignally thinking about this
solution (1 year ago roughly), it didn't fit...

For those who are curious, the algorithm basically estimates probabilities
for branches. Based on that it attempt to compute how often given basic block
compute.  In the acyclic tree you can simply propagate frequencies - once
all predecesors are known, you simply sum them.

In the cyclic code the algorithm ignore everything except natural loop
(loop with single entry point and single backward edge).  Then it goes
over loop nest and always compute "cyclic probability" that is probability
that loopback edge is reached when the loop is entered.

The expected amount of iteration is then 1/cyclic_probability *
frequency_of_header.

So I need to sum, compute reciprocals and multiply.

Honza


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]