Re: Limiting the number of domains/signatures verifications

From: Alessandro Vesely <vesely_at_tana.it>
Date: Wed, 10 Oct 2012 10:10:00 +0200

On Tue 09/Oct/2012 21:15:41 +0200 Murray S. Kucherawy wrote:
> On Tue, 9 Oct 2012, SM wrote:
>>> However, my filter sorts signatures using an O(n^2) algorithm
>>> (gnome sort) which is good for a few signatures only.
>>
>> I don't have a plausible reason for using more than 100 DKIM
>> signatures in production. I'd say that you shouldn't encounter even
>> half that number.
>
> I agree.
>
> I also think you can use the prescreen callback to apply a more
> efficient sort.

You mean there's no point in using both callbacks? Good hint, I can
save some cycles that way. Thank you.

> Even quicksort would be better, and libc provides that on every
> system I've ever seen (see qsort(3))..

I don't think so. Although some libraries (e.g. Plauger's) implement
qsort() with better algorithms than quicksort, any of those would be
overkill for sorting the usual 2~4 items. What's nice of gnome sort
is its extreme simplicity.
Received on Wed Oct 10 2012 - 08:10:10 PST