You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@lucene.apache.org by Toke Eskildsen <te...@statsbiblioteket.dk> on 2015/08/01 23:44:14 UTC
Better DocSetCollector
Before I open a JIRA, I would like to run a sanity check here.
My understanding:
The DocSetCollector is used e.g. when the ResponseBuilder.isNeedDocSet is true. This is the case for e.g. field faceting. The DocSetCollector is optimistic and works from the assumption that the result set will be less than 1/64th of maxDoc. It does this by allocating an int[maxDoc/64], which takes up maxDoc/16 bytes. docIDs are collected in this array and when the DocSet is to be returned, the array is wrapped in a SortedIntDocSet, which reduces it to int[hits].
If the result set exceeds maxDoc/64, a FixedBitSet, which takes up maxDoc/8 bytes, is created and all the values are copied from the int-array. The int-array is not freed, so temporary overhead during collection is now maxDoc/16 + maxDoc/8 bytes. Then the collection has finished, a BitDocSet (maxDoc/8 bytes) is created from the FixedBitSet.
The JavaDoc indicates that the reason for this solution is to avoid very sparse bitmaps from small result sets with a FixedBitSet-only strategy. As the memory overhead for the current solution varies from 1/2 to 3/2 of the pure FixedBitSet-only solution, I assume that the problem with sparse bitmaps is not memory but processing time?
An idea:
The primary performance problem with BitDocSet (FixedBitSet really) is that all the empty areas (i.e. longs) of the bitmap must still be read for most operations. But we can avoid that.
Tracking non-empty areas can be done fairly simple by having a bitmap of length maxDoc/64: One bit for every long != 0 in the internal array in FixedBitSet. The memory overhead of the tracker is thus maxDoc/64/8 bytes and the performance penalty for updates will be the addition of
tracker[index >>> 12] |= 1L << ((index >>> 6) & 63)
to all FixedBitSet.set-calls.
Using the tracker would make operations such as iteration and intersection on sparse result sets cheap. For non-sparse results (we can define the cut-off point of sparseness where we want), the tracker could be discarded and the collected bits used with a standard FixedBitSet.
Does this sound reasonable? Should I open a JIRA? Attempt a patch?
- Toke Eskildsen
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: dev-help@lucene.apache.org
Re: Better DocSetCollector
Posted by Toke Eskildsen <te...@statsbiblioteket.dk>.
On Tue, 2015-08-11 at 11:57 +0200, Adrien Grand wrote:
> The go-to class for building a DocIdSet from a sorted iterator in
> Lucene would rather be RoaringDocIdSet. BitDocIdSet works too, but it
> has to trade quite some iteration/build speed and memory efficiency in
> order to provide random write and read access.
I guess one of the reasons for this mess of id set implementations is
the different needs: sparse vs. dense (memory and performance),
iteration vs. random access (performance), and/or/andNot operations
across different implementations.
I have looked at RoaringDocIdSet and agree that it looks very promising.
- Toke Eskildsen, State and University Library, Denmark
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: dev-help@lucene.apache.org
Re: Better DocSetCollector
Posted by Adrien Grand <jp...@gmail.com>.
The go-to class for building a DocIdSet from a sorted iterator in
Lucene would rather be RoaringDocIdSet. BitDocIdSet works too, but it
has to trade quite some iteration/build speed and memory efficiency in
order to provide random write and read access. It also looks to me
that roaring bitmaps would be a good compromise for the ideas that
Toke and Yonik are having, as it allocates chunks of memory and
happily deals with holes in the doc ID space?
On Tue, Aug 11, 2015 at 11:25 AM, Ramkumar R. Aiyengar
<an...@gmail.com> wrote:
> I wonder if there might be value in BitDocIdSet.Builder which Lucene uses.
> It had perf issues of its soon, but LUCENE-6645 seems to have fixed them,
> and it does a similar approach as above (int array and then fixedbitset).
>
> On 3 Aug 2015 12:35, "Toke Eskildsen" <te...@statsbiblioteket.dk> wrote:
>>
>> On Sat, 2015-08-01 at 15:09 -0700, Yonik Seeley wrote:
>> > I also investigated going the other way and tracking a List<int[]> and
>> > allocating in smaller chunks (and even having a memory pool to pull
>> > the fixed size chunks from) but it was slower on my first attempt and
>> > I haven't returned to try more variants yet. It *feels* like we
>> > should be able to get overall speedups by allocating in 8K chunks or
>> > so when the effects of memory bandwidth (the cost of zeroing) and GC
>> > are considered.
>>
>> Chunked allocations of int[] would still have the problem of having the
>> copy-to-bitmap step if the result set gets too big.
>>
>> Chunks might work better with the garbage collector, compared to the
>> current solution, but I greatly prefer the idea of re-using structures.
>>
>> That being said, I realize that it is not simple to choose the proper
>> strategy:
>>
>> http://stackoverflow.com/questions/1955322/at-what-point-is-it-worth-reusing-arrays-in-java
>>
>> In the case of an update-tracked structure, the cost of zeroing is
>> linear to the amount of changed values. This makes it even harder to
>> determine the best strategy as it will be tied to concrete index size
>> and query pattern.
>>
>> - Toke Eskildsen, State and University Library, Denmark
>>
>>
>> ---------------------------------------------------------------------
>> To unsubscribe, e-mail: dev-unsubscribe@lucene.apache.org
>> For additional commands, e-mail: dev-help@lucene.apache.org
>>
>
--
Adrien
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: dev-help@lucene.apache.org
Re: Better DocSetCollector
Posted by "Ramkumar R. Aiyengar" <an...@gmail.com>.
I wonder if there might be value in BitDocIdSet.Builder which Lucene uses.
It had perf issues of its soon, but LUCENE-6645 seems to have fixed them,
and it does a similar approach as above (int array and then fixedbitset).
On 3 Aug 2015 12:35, "Toke Eskildsen" <te...@statsbiblioteket.dk> wrote:
> On Sat, 2015-08-01 at 15:09 -0700, Yonik Seeley wrote:
> > I also investigated going the other way and tracking a List<int[]> and
> > allocating in smaller chunks (and even having a memory pool to pull
> > the fixed size chunks from) but it was slower on my first attempt and
> > I haven't returned to try more variants yet. It *feels* like we
> > should be able to get overall speedups by allocating in 8K chunks or
> > so when the effects of memory bandwidth (the cost of zeroing) and GC
> > are considered.
>
> Chunked allocations of int[] would still have the problem of having the
> copy-to-bitmap step if the result set gets too big.
>
> Chunks might work better with the garbage collector, compared to the
> current solution, but I greatly prefer the idea of re-using structures.
>
> That being said, I realize that it is not simple to choose the proper
> strategy:
>
> http://stackoverflow.com/questions/1955322/at-what-point-is-it-worth-reusing-arrays-in-java
>
> In the case of an update-tracked structure, the cost of zeroing is
> linear to the amount of changed values. This makes it even harder to
> determine the best strategy as it will be tied to concrete index size
> and query pattern.
>
> - Toke Eskildsen, State and University Library, Denmark
>
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: dev-unsubscribe@lucene.apache.org
> For additional commands, e-mail: dev-help@lucene.apache.org
>
>
Re: Better DocSetCollector
Posted by Toke Eskildsen <te...@statsbiblioteket.dk>.
On Sat, 2015-08-01 at 15:09 -0700, Yonik Seeley wrote:
> I also investigated going the other way and tracking a List<int[]> and
> allocating in smaller chunks (and even having a memory pool to pull
> the fixed size chunks from) but it was slower on my first attempt and
> I haven't returned to try more variants yet. It *feels* like we
> should be able to get overall speedups by allocating in 8K chunks or
> so when the effects of memory bandwidth (the cost of zeroing) and GC
> are considered.
Chunked allocations of int[] would still have the problem of having the
copy-to-bitmap step if the result set gets too big.
Chunks might work better with the garbage collector, compared to the
current solution, but I greatly prefer the idea of re-using structures.
That being said, I realize that it is not simple to choose the proper
strategy:
http://stackoverflow.com/questions/1955322/at-what-point-is-it-worth-reusing-arrays-in-java
In the case of an update-tracked structure, the cost of zeroing is
linear to the amount of changed values. This makes it even harder to
determine the best strategy as it will be tied to concrete index size
and query pattern.
- Toke Eskildsen, State and University Library, Denmark
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: dev-help@lucene.apache.org
Re: Better DocSetCollector
Posted by Yonik Seeley <ys...@gmail.com>.
On Sat, Aug 1, 2015 at 2:44 PM, Toke Eskildsen <te...@statsbiblioteket.dk> wrote:
> Before I open a JIRA, I would like to run a sanity check here.
>
> My understanding:
>
> The DocSetCollector is used e.g. when the ResponseBuilder.isNeedDocSet is true. This is the case for e.g. field faceting. The DocSetCollector is optimistic and works from the assumption that the result set will be less than 1/64th of maxDoc. It does this by allocating an int[maxDoc/64], which takes up maxDoc/16 bytes. docIDs are collected in this array and when the DocSet is to be returned, the array is wrapped in a SortedIntDocSet, which reduces it to int[hits].
>
> If the result set exceeds maxDoc/64, a FixedBitSet, which takes up maxDoc/8 bytes, is created and all the values are copied from the int-array. The int-array is not freed, so temporary overhead during collection is now maxDoc/16 + maxDoc/8 bytes. Then the collection has finished, a BitDocSet (maxDoc/8 bytes) is created from the FixedBitSet.
>
> The JavaDoc indicates that the reason for this solution is to avoid very sparse bitmaps from small result sets with a FixedBitSet-only strategy. As the memory overhead for the current solution varies from 1/2 to 3/2 of the pure FixedBitSet-only solution, I assume that the problem with sparse bitmaps is not memory but processing time?
You make a good point on the relative sizes of the sets.
We could free the int[] at the same time as the FixedBitSet is allocated.
I also investigated going the other way and tracking a List<int[]> and
allocating in smaller chunks (and even having a memory pool to pull
the fixed size chunks from) but it was slower on my first attempt and
I haven't returned to try more variants yet. It *feels* like we
should be able to get overall speedups by allocating in 8K chunks or
so when the effects of memory bandwidth (the cost of zeroing) and GC
are considered.
-Yonik
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: dev-help@lucene.apache.org