[cups.development] why not hash?

[Michael Sweet]

Hidetomo Katsura wrote:
> thanks for the actual numbers. i just implemented my own hash table lookup
> code (instead of using CFDictionary/CFString) and got the actual numbers of
> 1000 ppdConflicts() calls + 1 ppdOpenFile() call.
> 
> k: keywords, c: constraints, bs: binary search (cups 1.3r6458), ht: hash
> table
> 
> k: 67, c: 1076
>   bs: 1.337919, ht: 1.021581 (1.31x)
> 
> k: 19, c: 0
>   bs: 0.002012, ht: 0.002060 (0.94x)
> 
> k: 30, c: 26
>   bs: 0.030796, ht: 0.024412 (1.26x)
> 
> the improvement is intended for the keyword (option->keyword) lookup, so we
> don't get much benefit when the number of keywords is small.
> 
> what do you think?

I'm thinking that the performance improvement offered by hashing is
not worth the extra code.  Instead, I'd like to look at optimizing
the conflicts algorithm - if we can reduce the number of lookups
(== 4x the number of constraints) or optimize the order of the
lookups (e.g. sort the constraints), we'll likely get a bigger
improvement than hashing can provide.

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