[cups.development] why not hash?

[Hidetomo Katsura]

fyi, as long as the hash table doesn't noticeably slow down common cases,
even 1.2x or 1.3x is extremely important to us, efi, with huge PPD files.

yes, i agree that our next step is to improve ppdConflicts() itself. i'll
look into it, too. one step at a time.

and i appreciate it if you consider taking the hash table improvement.
thanks.

katsura

-----Original Message-----
From: cups-dev-bounces at easysw.com on behalf of Michael Sweet
Sent: Tue 4/24/2007 11:55 AM
To: cups-dev at easysw.com
Subject: Re: [cups.development] why not hash?
 
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
_______________________________________________
cups-dev mailing list
cups-dev at easysw.com
http://lists.easysw.com/mailman/listinfo/cups-dev