From: Philippe Elie <phil.el@wa...>  20030928 04:40:17

I rewrite counter allocation. It's not obvious if the worst case is better or not than the currently used algorithm but 1) allocation remains optimal 2) only possible solution are scanned 3) speed depend on number of events allocated 2) means than if counter class are sparse it'll performs vell 3) imply than worst seems N counter Ci allowing M events for each Ci allowed events are X(0), X(1), ... X(i1), X(i+1) ... X(M) but in this case a lot of different solution exists. complexity w/o prunning is (pow(N, min(nr events selected, average allowed events by counter)) / nr solution for this set of event selected) Algorithm is a simple backtrack tree search with pruning when impossible solution are reach, test for impossible solution is O(1). Depth of tree is equal to nr events selected. A few test with P4 events show it performs better by twice. I expect much better win on worst case. For Falk problem (one event slected over 19 counters) algo will succeed immediatly. I suspect we can do a better pruning by partionning counter in class, each class contain all counter allowing events which are not allowed by other class so counter in each class will be interchangeable and we can reduce the number of try but for now I think this will be sufficient (This trick does not change the worst case I describe above, in this case each counter go in its own class) patch #if 0 #else the current implementation to shrink patch (all code in op_alloc_counter.c is replaced) any questions, comments ? regards, Phil 