Major update to generic functions in CVS: Well, I finally did it. I finally nailed that O(n^2) inequality algorithm, and now only a handful of less-frequently-used criteria types show nonlinear behavior. Before the change, it took almost 2 seconds to register 500 distinct integer equality rules with a generic function on my PC. After the change, 5000 can be registered in roughly the same 2 seconds. And, the rate remains at a nice linear 2500 criteria definitions per second no matter how many rules you add, where the old algorithm became even slower with each added rule. (Note: this measurement actually includes the time needed to parse the string to define each criterion!)
Just to be even clearer, this is rule definition speed we’re talking about, not execution. Equality lookups at rule execution time are still safely O(1) no matter how many rules you’ve defined, and they’re measured in microseconds or fractions thereof. Fast enough, in other words, that I have felt safe turning some attention to the rule definition side of things. 2500 rule criteria per second is still a little slow for some applications, even as the one-time setup cost that it is, but at this point I haven’t actually brought any C code to bear on that side of things, and I’m also using Python 2.3 sets at the moment and hope to get a little boost out of 2.4’s C sets.
Anyway, I’d like to be able to put this puppy out as a 1.0a0 “technology preview” release to go with David Mertz’ upcoming article on generic functions, so I’d appreciate everyone’s kind help in verifying that I didn’t break anything with my refactoring. There’s a pretty extensive test suite, but I’m not 100% positive that the tests don’t have gaps in the area of things that the old algorithms didn’t do, but the new algorithms might. I think I’ve done too many refactorings without writing new tests to cover the new functionality, instead relying on old tests to verify that new stuff works. In the process, I’ve effectively converted some of the unit tests into integration tests, leaving new stuff uncovered by unit tests. I’ll fix that with doctests as I write documentation, but in the meantime I’d like to release the technology preview.
So, if you have software you’ve written using previous CVS versions of the dispatch package, please update soon, and tell me what breaks! With your help, I can then ensure that the preview release is right, as well as fast. Thanks.
