lucene-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Uwe Schindler" <...@thetaphi.de>
Subject RE: [VOTE] release 3.3
Date Fri, 24 Jun 2011 17:35:41 GMT
Hi Yonik, I wrote atestcase that checks how prevSetBit behaves, if I add you
patch with optimization. It still had a bug, if the index is beyond last
word but not at a multiple of bitsPerWord. The following code is correct:

  public int prevSetBit(int index) {
    int i = index >> 6;
    final int subIndex;
    if (i >= wlen) {
      i = wlen - 1;
      if (i < 0) return -1;
      subIndex = 0x3f; // last possible bit
    } else {
      if (i < 0) return -1;
      subIndex = index & 0x3f;      // index within the word
    }
    long word = (bits[i] << (63-subIndex));  // skip all the bits to the
left of index

    if (word != 0) {
      return (i << 6) + subIndex - Long.numberOfLeadingZeros(word); // See
LUCENE-3197
    }

    while (--i >= 0) {
      word = bits[i];
      if (word !=0 ) {
        return (i << 6) + 63 - Long.numberOfLeadingZeros(word);
      }
    }

    return -1;
  }

Your additional optimization with negative indexes is invalid, because on
negative indexes prevSetBit() must be negative. If we don’t do this, a
typical loop like would AIOOBE:

for (int i = bs.prevSetBit(0); i >= 0; i = bs.prevSetBit(i-1)) {
     // operate on index i here
 }

Uwe

-----
Uwe Schindler
H.-H.-Meier-Allee 63, D-28213 Bremen
http://www.thetaphi.de
eMail: uwe@thetaphi.de


> -----Original Message-----
> From: yseeley@gmail.com [mailto:yseeley@gmail.com] On Behalf Of Yonik
> Seeley
> Sent: Friday, June 24, 2011 6:29 PM
> To: dev@lucene.apache.org
> Subject: Re: [VOTE] release 3.3
> 
> On Fri, Jun 24, 2011 at 12:14 PM, Yonik Seeley
<yonik@lucidimagination.com>
> wrote:
> > All that needs to be done is to move the negative index check to the
> > bottom (the first index<0 is not needed since we do a signed shift).
> >
> >  public int prevSetBit(int index) {
> >    int i = index>>6;
> >    if (i >= wlen) {
> >      i = wlen - 1;
> >    }
> >    if (i < 0) return -1;
> >    final int subIndex = index & 0x3f;      // index within the word
> >    long word = (bits[i] << (63-subIndex));  // skip all the bits to
> > the left of index
> 
> And a further minor optimization, if we assume that negative indexes are
not
> legal, is to move the (i<0) check inside the if (i>=wlen) block (and just
let a
> negative index passed by the user to cause a natural AIOOB).
> 
> -Yonik
> http://www.lucidimagination.com
> 
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: dev-unsubscribe@lucene.apache.org For additional
> commands, e-mail: dev-help@lucene.apache.org



---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: dev-help@lucene.apache.org


Mime
View raw message