On Tue, Aug 09, 2005 at 04:59:28PM +0200, Sebastian Pop wrote: > Joe Buck wrote: > > Algorithms that are sometimes exponential can still be used if there is > > a cutoff mechanism, to abort the algorithm if it exceeds a budget. This > > assumes that we can then fall back to an algorithm that might produce > > inferior results, but will produce something usable in reasonable time. > > > > Okay, I stand corrected. As a practical implementation we can have a > mechanism as push/pop timevar, that would monitor the time and space > of an algorithm and that can cancel the computation for failing on a > safe approximation. As a first concretization, I was thinking to use > threads, but I'm not sure whether this is suitable for GCC.
The problem with using time as a cutoff is that you then get results that can't be reproduced reliably. Better to count something that is a feature of the algorithm, e.g. number of executions of some inner loop, number of nodes visited, or the like, so that all users get the same results.
