On 1/8/20 3:05 PM, Jan Hubicka wrote:
I would still preffer invalidation before streaming (which is fully
deterministic) and possibly have option
Do you mean __gcov_merge_topn?
I suggest we do the following:
- have non-deterministic and deterministic version of TOPN counter
and a flag chosing between deterministic and non-deterministic
instrumentation.
- in non-deterministic version do merging dropping least frequent
values as done with your patch.
Good.
- in deterministic version do the following
in __gcov-merge_topn
1) prune out all values in measured counts with associated counter
less than total_count/N (where N is number of values we track)
Can you please explain me how precisely is this prune useful?
2) prune out all values in read counter same way
3) merge the values ignoring any with resulting counter being
less than merged_total_count/N and invalidating whole counter if
there are too many suriving ones
4) before using profiles in GCC prune out all vlaues with associated
counter less than total_count/N (they are not useful anyway).
Here total_count can be simply sum of all N counters, it would be
better if it was total number of runs, but that is not available at
gcov_merge time unless we introduce extra counter for misses.
Observation is that since we never kick out value because counter is
full (but still rather invalidate whole counter) this remains
deterministics. Hopefully prunning out useless small values will
prevent the Firefox-like examples from triggering too often.
Definitly this is stronger than simply invalidating all counters
where number of runs != sum of all counts which is other
deterministics variant.
2) and 4) is only needed since we currently have no convenient place
to prune counters prior streaming if merging is not done at all.
If we invent one we could skip that step.
Does it make sense to you?
I was also wondering: with TOPN it would be nice to have the property
that target with at greater 1/(TOPN+1) probability gets into the counter,
but this guaranteed only for N=1.
For N>1 one can populate N-1 counters with not too important values
and only then start putting in frequent values be sure that they fight
and be sure that the frequent target is always fight between themself
for the last slot (exploiting the "lets decrease the least counter
heuristics")
Like for N=3
X X Y Y Z W Z W Z W Z W ......
here first two counters will get occupied by X and Y with counts 2 and
the third counter will end up with W. Z will be missed even if it has
limit 0.5 and both X and Y probability 0 in the limit.
What about increasing value of every couner by N on hit and decreasing
all by 1 on miss? It will make sure that counts having frequency less
than 1/N will be dropped making space for those with higher frequencies.
I like this approach. It looks smart. So then we'll divide all counter values
by N, right?
Note that we used to have the Google's profiling code for TOP N:
https://github.com/gcc-mirror/gcc/blob/gcc-7-branch/libgcc/libgcov-profiler.c#L179
It's somehow counting number of evictions and if it reaches a threshold, then
low
counter values are evicted.
Martin
This should also improve behaviour WRT the problem above.
-fno-deterministic-profile-merging (or something similar) for users who
do not care and for threaded programs where this is impossible
(which needs to trigger different merging in libgcov).
Fine, let's postpone that for GCC 11.
It is a regression, so I think we have right to solve it for GCC 10.
Honza
Martin
Honza
