MBOX-Line: From mrc at CAC.Washington.EDU  Wed Dec 20 12:50:16 2006
To: imap-protocol@u.washington.edu
From: Mark Crispin <mrc@CAC.Washington.EDU>
Date: Fri Jun  8 12:34:38 2018
Subject: [Imap-protocol] Searching
In-Reply-To: <rBtlBkn+facAYdHBwRiNTg.md5@libertango.oryx.com>
References: <1166603479.22214.298.camel@hurina> 
	<alpine.OSX.0.81.0612201018450.10225@pangtzu.panda.com>
	<rBtlBkn+facAYdHBwRiNTg.md5@libertango.oryx.com>
Message-ID: <alpine.OSX.0.81.0612201155450.414@pangtzu.panda.com>

On Wed, 20 Dec 2006, Arnt Gulbrandsen wrote:
> Boyer-Moore is k*O(n) with an impressive k. People want k*O(log n) these 
> days, if possible with an impressive k.

I question that assumption for IMAP searches.  Even with large mailboxes, 
Boyer-Moore causes no user-visible delay in search time.

What causes search time delays is I/O time; and that is the attraction 
behind such things as indexed searching.  However, indexing can have its 
own costs (I turned off Spotlight on my Mac due to its indexing consuming 
most of the CPU for hours on end!), and it doesn't do any good if it 
violates the specification and leads to the failure of a client that 
relies upon the specification.

-- Mark --

http://panda.com/mrc
Democracy is two wolves and a sheep deciding what to eat for lunch.
Liberty is a well-armed sheep contesting the vote.

