You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@lucene.apache.org by Shai Erera <se...@gmail.com> on 2009/04/24 21:26:21 UTC
Another possible optimization - now in DocIdSetIterator
Hi
I think we can make some optimization to DocIdSetIterator. Today, it defines
next() and skipTo(int) which return a boolean. I've checked the code and it
looks like almost always when these two are called, they are followed by a
call to doc().
I was thinking that if those two returned the doc Id they are at, instead of
boolean, that will save the call to doc(). Those that use these can:
* Compare doc to a NO_MORE_DOCS constant (set to -1), to understand there
are no more docs in this iterator.
* If skipTo() is called, compare the 'target' to the returned Id, and if
they are not the same, save it so that the next skipTo is requested, they
don't perform it if the returned Id is greater than the target. If it's not
possible to save it, they can call doc() to get that information.
The way I see it, the impls that will still need to call doc() will lose
nothing. All we'll do is change the 'if' from comparing a boolean to
comparing ints (even though that's a bit less efficient than comparing
booleans). The impls that call doc() just because all they have in hand is a
boolean, will gain.
Obviously we can't change those methods' signature, so we can deprecate them
and intorudce nextDoc() and skipToDoc(int target). We should still keep
doc() around though.
What do you think? If you agree to this change, I can add them to 1593, or
create a new issue (I prefer the latter so that 1593 will be focused on the
changes to Collectors).
Shai
Re: Another possible optimization - now in DocIdSetIterator
Posted by Michael McCandless <lu...@mikemccandless.com>.
It's a nice approach, but I think it relies on C interpreting integer
0 as false, which we can't do in Java. (And, we lack "unsigned int"
in java so we have immense freedom to pick any negative number as our
sentinel ;) ).
Not to mention it'd be a scary change to make at this point! So I
think we should just stick with -1 as our sentinel.
Mike
On Fri, Apr 24, 2009 at 5:33 PM, Marvin Humphrey <ma...@rectangular.com> wrote:
> On Fri, Apr 24, 2009 at 05:18:30PM -0400, Michael McCandless wrote:
>
>> > One additional wrinkle, though: doc nums start at 1 rather than 0, so the
>> > return values for Next() and Advance() can double as a booleans.
>>
>> Meaning they return 0 to indicate "no more docs"?
>
> Yes. 0 is our sentinel.
>
> Marvin Humphrey
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
> For additional commands, e-mail: java-dev-help@lucene.apache.org
>
>
---------------------------------------------------------------------
To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-dev-help@lucene.apache.org
Re: Another possible optimization - now in DocIdSetIterator
Posted by Marvin Humphrey <ma...@rectangular.com>.
On Fri, Apr 24, 2009 at 05:18:30PM -0400, Michael McCandless wrote:
> > One additional wrinkle, though: doc nums start at 1 rather than 0, so the
> > return values for Next() and Advance() can double as a booleans.
>
> Meaning they return 0 to indicate "no more docs"?
Yes. 0 is our sentinel.
Marvin Humphrey
---------------------------------------------------------------------
To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-dev-help@lucene.apache.org
Re: Another possible optimization - now in DocIdSetIterator
Posted by Marvin Humphrey <ma...@rectangular.com>.
On Sat, Apr 25, 2009 at 12:24:59AM +0300, Shai Erera wrote:
> But I thought doc Ids start with 0? That's why I wrote 'set to -1' ...
This was in the context of KinoSearch. In KS, doc numbers start at 1.
Marvin Humphrey
---------------------------------------------------------------------
To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-dev-help@lucene.apache.org
Re: Another possible optimization - now in DocIdSetIterator
Posted by Shai Erera <se...@gmail.com>.
But I thought doc Ids start with 0? That's why I wrote 'set to -1' ...
On Sat, Apr 25, 2009 at 12:18 AM, Michael McCandless <
lucene@mikemccandless.com> wrote:
> On Fri, Apr 24, 2009 at 4:20 PM, Marvin Humphrey <ma...@rectangular.com>
> wrote:
>
> > One additional wrinkle, though: doc nums start at 1 rather than 0, so the
> > return values for Next() and Advance() can double as a booleans.
>
> Meaning they return 0 to indicate "no more docs"?
>
> Mike
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
> For additional commands, e-mail: java-dev-help@lucene.apache.org
>
>
Re: Another possible optimization - now in DocIdSetIterator
Posted by Michael McCandless <lu...@mikemccandless.com>.
On Fri, Apr 24, 2009 at 4:20 PM, Marvin Humphrey <ma...@rectangular.com> wrote:
> One additional wrinkle, though: doc nums start at 1 rather than 0, so the
> return values for Next() and Advance() can double as a booleans.
Meaning they return 0 to indicate "no more docs"?
Mike
---------------------------------------------------------------------
To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-dev-help@lucene.apache.org
Re: Another possible optimization - now in DocIdSetIterator
Posted by Marvin Humphrey <ma...@rectangular.com>.
On Fri, Apr 24, 2009 at 10:26:21PM +0300, Shai Erera wrote:
> I think we can make some optimization to DocIdSetIterator. Today, it defines
> next() and skipTo(int) which return a boolean. I've checked the code and it
> looks like almost always when these two are called, they are followed by a
> call to doc().
>
> I was thinking that if those two returned the doc Id they are at, instead of
> boolean, that will save the call to doc().
> What do you think?
It'll work.
Nathan Kurz proposed exactly this change for KinoSearch last July.
<http://rectangular.com/pipermail/kinosearch/2007-July/004149.html>
I think there is a small gain by having Scorer_Advance return a doc number
directly rather than a boolean, obviating the need for a follow-up call to
Scorer_Doc.
I finished the implementation last October.
One additional wrinkle, though: doc nums start at 1 rather than 0, so the
return values for Next() and Advance() can double as a booleans.
Marvin Humphrey
---------------------------------------------------------------------
To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-dev-help@lucene.apache.org
Re: Another possible optimization - now in DocIdSetIterator
Posted by Mark Miller <ma...@gmail.com>.
Mark Miller wrote:
> Shai Erera wrote:
>> Hi
>>
>> I think we can make some optimization to DocIdSetIterator. Today, it
>> defines next() and skipTo(int) which return a boolean. I've checked
>> the code and it looks like almost always when these two are called,
>> they are followed by a call to doc().
>>
>> I was thinking that if those two returned the doc Id they are at,
>> instead of boolean, that will save the call to doc(). Those that use
>> these can:
>> * Compare doc to a NO_MORE_DOCS constant (set to -1), to understand
>> there are no more docs in this iterator.
>> * If skipTo() is called, compare the 'target' to the returned Id, and
>> if they are not the same, save it so that the next skipTo is
>> requested, they don't perform it if the returned Id is greater than
>> the target. If it's not possible to save it, they can call doc() to
>> get that information.
>>
>> The way I see it, the impls that will still need to call doc() will
>> lose nothing. All we'll do is change the 'if' from comparing a
>> boolean to comparing ints (even though that's a bit less efficient
>> than comparing booleans). The impls that call doc() just because all
>> they have in hand is a boolean, will gain.
>>
>> Obviously we can't change those methods' signature, so we can
>> deprecate them and intorudce nextDoc() and skipToDoc(int target). We
>> should still keep doc() around though.
>>
>> What do you think? If you agree to this change, I can add them to
>> 1593, or create a new issue (I prefer the latter so that 1593 will be
>> focused on the changes to Collectors).
>>
>> Shai
> any micro benchmarks or anything? If its a net real world win, +1.
>
P.S. I'd make a new issue myself.
--
- Mark
http://www.lucidimagination.com
---------------------------------------------------------------------
To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-dev-help@lucene.apache.org
Re: Another possible optimization - now in DocIdSetIterator
Posted by Mark Miller <ma...@gmail.com>.
Shai Erera wrote:
> Hi
>
> I think we can make some optimization to DocIdSetIterator. Today, it
> defines next() and skipTo(int) which return a boolean. I've checked
> the code and it looks like almost always when these two are called,
> they are followed by a call to doc().
>
> I was thinking that if those two returned the doc Id they are at,
> instead of boolean, that will save the call to doc(). Those that use
> these can:
> * Compare doc to a NO_MORE_DOCS constant (set to -1), to understand
> there are no more docs in this iterator.
> * If skipTo() is called, compare the 'target' to the returned Id, and
> if they are not the same, save it so that the next skipTo is
> requested, they don't perform it if the returned Id is greater than
> the target. If it's not possible to save it, they can call doc() to
> get that information.
>
> The way I see it, the impls that will still need to call doc() will
> lose nothing. All we'll do is change the 'if' from comparing a boolean
> to comparing ints (even though that's a bit less efficient than
> comparing booleans). The impls that call doc() just because all they
> have in hand is a boolean, will gain.
>
> Obviously we can't change those methods' signature, so we can
> deprecate them and intorudce nextDoc() and skipToDoc(int target). We
> should still keep doc() around though.
>
> What do you think? If you agree to this change, I can add them to
> 1593, or create a new issue (I prefer the latter so that 1593 will be
> focused on the changes to Collectors).
>
> Shai
any micro benchmarks or anything? If its a net real world win, +1.
--
- Mark
http://www.lucidimagination.com
---------------------------------------------------------------------
To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-dev-help@lucene.apache.org
Re: Another possible optimization - now in DocIdSetIterator
Posted by Yonik Seeley <yo...@lucidimagination.com>.
On Fri, Apr 24, 2009 at 6:20 PM, eks dev <ek...@yahoo.co.uk> wrote:
> just do not forget to use -1 < doc instead of -1 != doc
Perhaps doc >=0 instead of doc != -1?
The crux of it is that status flags (result positive, negative, or
zero) are set by many operations - hence a compare/test operation can
often be eliminated. For this same reason, counting down to zero in a
loop instead of counting up to a limit can be slightly faster. It's a
single cycle though.... normally not much to worry about :-)
Of course, now we have processors like the i7 with macro-ops fusion
that can take a TEST/CMP followed by a branch and fuse it into a
single operation.... may level the field again.
-Yonik
http://www.lucidimagination.com
---------------------------------------------------------------------
To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-dev-help@lucene.apache.org
Re: Another possible optimization - now in DocIdSetIterator
Posted by eks dev <ek...@yahoo.co.uk>.
Hi Shai,
absolutely!
we have been there, and there are already some micro benchmarks done in LUCENE-1345
just do not forget to use -1 < doc instead of -1 != doc, trust me, Yonik convinced me :)
as a side effect, this change would have some positive effects on iterator semantics, prevents, very hard to find, "one off" bugs " caused by calling doc() before calling next()". we had quite a few of those.
-1 is good, as it supports "move to the first" in next() without if(initialized), just incrementing
.
cheers,
eks
From: Shai Erera <se...@gmail.com>
To: java-dev@lucene.apache.org
Sent: Friday, 24 April, 2009 21:26:21
Subject: Another possible optimization - now in DocIdSetIterator
Hi
I think we can make some optimization to DocIdSetIterator. Today, it defines next() and skipTo(int) which return a boolean. I've checked the code and it looks like almost always when these two are called, they are followed by a call to doc().
I was thinking that if those two returned the doc Id they are at, instead of boolean, that will save the call to doc(). Those that use these can:
* Compare doc to a NO_MORE_DOCS constant (set to -1), to understand there are no more docs in this iterator.
* If skipTo() is called, compare the 'target' to the returned Id, and if they are not the same, save it so that the next skipTo is requested, they don't perform it if the returned Id is greater than the target. If it's not possible to save it, they can call doc() to get that information.
The way I see it, the impls that will still need to call doc() will lose nothing. All we'll do is change the 'if' from comparing a boolean to comparing ints (even though that's a bit less efficient than comparing booleans). The impls that call doc() just because all they have in hand is a boolean, will gain.
Obviously we can't change those methods' signature, so we can deprecate them and intorudce nextDoc() and skipToDoc(int target). We should still keep doc() around though.
What do you think? If you agree to this change, I can add them to 1593, or create a new issue (I prefer the latter so that 1593 will be focused on the changes to Collectors).
Shai
Re: Another possible optimization - now in DocIdSetIterator
Posted by Michael McCandless <lu...@mikemccandless.com>.
On the "it touches the same code" criteria, I would agree.
On the "it's the same core problem" criteria, I would disagree.
Also I would think this change is simpler than the "isRandomAccess"
addition and so probably would land before isRandomAccess... so I
think I'd lean towards keeping them as separate issues.
Mike
On Fri, Apr 24, 2009 at 4:06 PM, Uwe Schindler <uw...@thetaphi.de> wrote:
> Maybe combine this with the isRandomAccess change it DocIdSet?
>
> -----
> Uwe Schindler
> H.-H.-Meier-Allee 63, D-28213 Bremen
> http://www.thetaphi.de
> eMail: uwe@thetaphi.de
>
>> -----Original Message-----
>> From: Michael McCandless [mailto:lucene@mikemccandless.com]
>> Sent: Friday, April 24, 2009 9:46 PM
>> To: java-dev@lucene.apache.org
>> Subject: Re: Another possible optimization - now in DocIdSetIterator
>>
>> I think this is a good idea! I think a new issue is best.
>>
>> Mike
>>
>> On Fri, Apr 24, 2009 at 3:26 PM, Shai Erera <se...@gmail.com> wrote:
>> > Hi
>> >
>> > I think we can make some optimization to DocIdSetIterator. Today, it
>> defines
>> > next() and skipTo(int) which return a boolean. I've checked the code and
>> it
>> > looks like almost always when these two are called, they are followed by
>> a
>> > call to doc().
>> >
>> > I was thinking that if those two returned the doc Id they are at,
>> instead of
>> > boolean, that will save the call to doc(). Those that use these can:
>> > * Compare doc to a NO_MORE_DOCS constant (set to -1), to understand
>> there
>> > are no more docs in this iterator.
>> > * If skipTo() is called, compare the 'target' to the returned Id, and if
>> > they are not the same, save it so that the next skipTo is requested,
>> they
>> > don't perform it if the returned Id is greater than the target. If it's
>> not
>> > possible to save it, they can call doc() to get that information.
>> >
>> > The way I see it, the impls that will still need to call doc() will lose
>> > nothing. All we'll do is change the 'if' from comparing a boolean to
>> > comparing ints (even though that's a bit less efficient than comparing
>> > booleans). The impls that call doc() just because all they have in hand
>> is a
>> > boolean, will gain.
>> >
>> > Obviously we can't change those methods' signature, so we can deprecate
>> them
>> > and intorudce nextDoc() and skipToDoc(int target). We should still keep
>> > doc() around though.
>> >
>> > What do you think? If you agree to this change, I can add them to 1593,
>> or
>> > create a new issue (I prefer the latter so that 1593 will be focused on
>> the
>> > changes to Collectors).
>> >
>> > Shai
>> >
>>
>> ---------------------------------------------------------------------
>> To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
>> For additional commands, e-mail: java-dev-help@lucene.apache.org
>
>
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
> For additional commands, e-mail: java-dev-help@lucene.apache.org
>
>
---------------------------------------------------------------------
To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-dev-help@lucene.apache.org
RE: Another possible optimization - now in DocIdSetIterator
Posted by Uwe Schindler <uw...@thetaphi.de>.
Maybe combine this with the isRandomAccess change it DocIdSet?
-----
Uwe Schindler
H.-H.-Meier-Allee 63, D-28213 Bremen
http://www.thetaphi.de
eMail: uwe@thetaphi.de
> -----Original Message-----
> From: Michael McCandless [mailto:lucene@mikemccandless.com]
> Sent: Friday, April 24, 2009 9:46 PM
> To: java-dev@lucene.apache.org
> Subject: Re: Another possible optimization - now in DocIdSetIterator
>
> I think this is a good idea! I think a new issue is best.
>
> Mike
>
> On Fri, Apr 24, 2009 at 3:26 PM, Shai Erera <se...@gmail.com> wrote:
> > Hi
> >
> > I think we can make some optimization to DocIdSetIterator. Today, it
> defines
> > next() and skipTo(int) which return a boolean. I've checked the code and
> it
> > looks like almost always when these two are called, they are followed by
> a
> > call to doc().
> >
> > I was thinking that if those two returned the doc Id they are at,
> instead of
> > boolean, that will save the call to doc(). Those that use these can:
> > * Compare doc to a NO_MORE_DOCS constant (set to -1), to understand
> there
> > are no more docs in this iterator.
> > * If skipTo() is called, compare the 'target' to the returned Id, and if
> > they are not the same, save it so that the next skipTo is requested,
> they
> > don't perform it if the returned Id is greater than the target. If it's
> not
> > possible to save it, they can call doc() to get that information.
> >
> > The way I see it, the impls that will still need to call doc() will lose
> > nothing. All we'll do is change the 'if' from comparing a boolean to
> > comparing ints (even though that's a bit less efficient than comparing
> > booleans). The impls that call doc() just because all they have in hand
> is a
> > boolean, will gain.
> >
> > Obviously we can't change those methods' signature, so we can deprecate
> them
> > and intorudce nextDoc() and skipToDoc(int target). We should still keep
> > doc() around though.
> >
> > What do you think? If you agree to this change, I can add them to 1593,
> or
> > create a new issue (I prefer the latter so that 1593 will be focused on
> the
> > changes to Collectors).
> >
> > Shai
> >
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
> For additional commands, e-mail: java-dev-help@lucene.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-dev-help@lucene.apache.org
Re: Another possible optimization - now in DocIdSetIterator
Posted by Michael McCandless <lu...@mikemccandless.com>.
I think this is a good idea! I think a new issue is best.
Mike
On Fri, Apr 24, 2009 at 3:26 PM, Shai Erera <se...@gmail.com> wrote:
> Hi
>
> I think we can make some optimization to DocIdSetIterator. Today, it defines
> next() and skipTo(int) which return a boolean. I've checked the code and it
> looks like almost always when these two are called, they are followed by a
> call to doc().
>
> I was thinking that if those two returned the doc Id they are at, instead of
> boolean, that will save the call to doc(). Those that use these can:
> * Compare doc to a NO_MORE_DOCS constant (set to -1), to understand there
> are no more docs in this iterator.
> * If skipTo() is called, compare the 'target' to the returned Id, and if
> they are not the same, save it so that the next skipTo is requested, they
> don't perform it if the returned Id is greater than the target. If it's not
> possible to save it, they can call doc() to get that information.
>
> The way I see it, the impls that will still need to call doc() will lose
> nothing. All we'll do is change the 'if' from comparing a boolean to
> comparing ints (even though that's a bit less efficient than comparing
> booleans). The impls that call doc() just because all they have in hand is a
> boolean, will gain.
>
> Obviously we can't change those methods' signature, so we can deprecate them
> and intorudce nextDoc() and skipToDoc(int target). We should still keep
> doc() around though.
>
> What do you think? If you agree to this change, I can add them to 1593, or
> create a new issue (I prefer the latter so that 1593 will be focused on the
> changes to Collectors).
>
> Shai
>
---------------------------------------------------------------------
To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-dev-help@lucene.apache.org