On 10/17/2010 02:19 PM, Dean Rasheed wrote:
> That makes me think maybe the "fast" and "slow" comparisons should
> both be done the same way, having a cache so that we notice
> immediately if we get a new value.
>
> Obviously that's not going to be as fast as the current "fast" method,
> but the question is, can it be made sufficiently close? I think the
> current sort+bsearch method is always going to be significantly
> slower, but perhaps a dedicated hash table algorithm might work.
>
Making that as fast as "Is this sorted? If yes, compare the two oids" or
even acceptably slower seems likely to be a challenge. I thought about
the sort of approach you suggest initially and didn't come up with
anything that seemed likely to work well enough.
cheers
andrew