[cups.development] why not hash?

[Michael Sweet]

Hidetomo Katsura wrote:
> thanks for the quick response, Michael.
> 
> i guess i wasn't clear what i meant by "hash". i meant to use the hash table
> lookup which is O(1) assuming the collision is minimum, not the binary search
> or linear search of hash values.
> 
> http://en.wikipedia.org/wiki/Hash_table
> 
> anyways, i'll post the changes when i have something.

Thanks.  FWIW, I coded up something simple for the array API that
you can play with, along with a benchmark program to test the
performance of ppdConflicts().  The code is available at:

     http://svn.easysw.com/public/cups/branches/hasharray

When I run the benchmark (which calls ppdConflicts 1000 times) against
a rather large Canon PPD file that has an enormous number of
UIConstraint lines (2056), I get the following results:

     CUPS 1.1.23: 2.346 seconds
     CUPS 1.2.10: 2.659 seconds
     CUPS hasharray: 2.168 seconds

So, at least for this particular PPD the old O(n) lookup code was
slightly faster than the current code, with the new hashed code
being just slightly faster than the 1.1.x code.

I'm guessing that another optimization such as a caching the lookups
in a shadow constraints array may yield the best results - that way
we only have the overhead of one set of lookups (1/1000th of the times
above) followed by quick loops through the cached constraints.

-- 
______________________________________________________________________
Michael Sweet, Easy Software Products           mike at easysw dot com
Internet Printing and Publishing Software        http://www.easysw.com