I wrote:
> I looked this over a bit and was immediately confused by one thing:
> the introductory comment says that the skip table size ought to be based
> on the length of the haystack, which makes sense to me, but the code is
> actually initializing it on the basis of len2, ie, the length of the
> needle. Isn't that a bug? Was the same bug present in the tests you
> made to determine the best table sizes?
BTW, to the extent that you feel like testing a different idea,
I would suggest:
* don't bother initializing the skiptable when len1 < len2
* otherwise, choose its size based on len1 - len2, not just len1 or
len2. This is (one less than) the maximum number of search loop
consultations of the skip table that can happen, so it seems like a
plausible number, and better than either length alone.
regards, tom lane