[PEAK] Major update to generic functions in CVS

[Phillip J. Eby]

I just checked in a major overhaul of index handling in generic functions 
to eliminate unnecessary O(n^2) algorithms, with a resulting major speed 
increase for large generic functions (i.e. 100 methods and up) that use 
only standard comparison operators and non-negated class-based 
(isinstance/issubclass) criteria.  Comparisons involving negated tests 
(i.e. not isinstance, not issubclass, etc.), however, are still O(n^2) in 
the number of negated tests for a given expression.  Generating dispatch 
nodes for <,<=,>,>=, and != comparisons may still involve an O(n^2) 
complexity as well.

To be clear, these performance issues are in the *definition* of generic 
functions, not their invocation.  I'm measuring the complexity of adding N 
methods to a generic function, assuming that there is only one expression 
being checked by the method.

I think I've now reached close to the theoretical limits of algorithmic 
performance for these operations, as the reason that negated criteria and 
large range criteria are so expensive is because they have lots of cases 
where they apply.  So, the indexes get filled with lots of entries for 
"method X applies to this and this and this and this and this...", and as 
far as I can tell there's no way around that without paying for it at 
function invocation time.  For the moment, I'm preferring to burn more time 
for setup in order to have invocation be as fast as possible.

Anyway, because this was such a big set of changes to the core indexing 
procedures, it's possible that stability may be disrupted.  If you have 
software that's been working well with generic functions to date, please 
try it with the latest CVS and report any bugs to me as soon as 
practical.  I'd like to get this thing stable enough to be able to declare 
a 1.0a0 release for David Mertz' forthcoming article on generic 
functions.  (With the "0" in this case meaning zero documentation.  ;) )