I agree that even though we don't see gains on the queries tested,
there are in theory cases where there could be a great many
allocations that would be saved.
I think we should do Shai's suggested option 1 (add the method and
change TDC to call it), change heap to be protected not private, plus
the 2 tiny performance gains Nadav suggests below? Shai can you open
a Jira issue & attach a patch for these changes? Thanks!
Mike
Nadav Har'El wrote:
On Mon, Dec 10, 2007, Shai Erera wrote about "Performance
Improvement for Search using PriorityQueue":
Hi
Lucene's PQ implements two methods: put (assumes the PQ has room
for the
object) and insert (checks whether the object can be inserted
etc.). The
implementation of insert() requires the application that uses it
to allocate
a new object every time it calls insert. Specifically, it cannot
reuse the
objects that were removed from the PQ.
I've read this entire thread, and would like to add my comments
about three
independent issues, which I think that can and perhaps should be
considered
separately:
1. When Shai wanted to add the insertWithOverflow() method to
PriorityQueue
he couldn't just subclass PriorityQueue in his application, but
rather
was forced to modify PriorityQueue itself. Why? just because one
field
of that classi - "heap" - was defined "private" instead of
"protected".
Is there a special reason for that? If not, can we make the
trivial change
to make PriorityQueue's fields protected, to allow Shai and
others (see the
next point) to add functionality on top of PriorityQueue?
2. PriorityQueue, in addition to being used in about a dozen places
inside
Lucene, is also a public class that advanced users often find
useful when
implementing features like new collectors, new queries, and so on.
Unfortunately, my experience exactly matches Shai's: In the two
occasions
where I used a PriorityQueue, I found that I needed such a
insertWithOverflow() method. If this feature is so useful (I
can't believe
that Shai and me are the only ones who found it useful), I think
it would
be nice to add it to Lucene's PriorityQueue, even if it isn't
(yet) used
inside Lucene.
Just to make it sound more interesting, let me give you an
example where
I needed (and implemented) an "insertWithOverflow()": I was
implementing a
faceted search capability over Lucene. It calculated a count for
each
facet value, and then I used a PriorityQueue to find the 10 best
values.
The problem is that I also needed an "other" aggregator, which
was supposed
to aggregate (in various ways) all the facets except the 10 best
ones. For
that, I needed to know which facets dropped off the priorityqueue.
3. Finally, Shai asked for this new PriorityQueue.insertWithOverflow()
to be used in TopDocCollector. I have to admit I don't know how
much
of a benefit this will be in the "typical" case. But I do know that
there's no such thing as a "typical" case...
I can easily think of a quite typical "worst case" though:
Consider a
collection indexed in order of document age (a pretty typical
scenario
for a long-running index), and then you do a sorting query
(TopFieldDocCollector), asking it to bring the 10 newest documents.
In that case, each and every document will have a new DocScore
created -
which is the worst-case that Shai feared.
It would be nice if Shai or someone else could provide a
measurement in
that case.
P.S. When looking now at PriorityQueue's code, I found two tiny
performance improvements that could be easily made to it - I wonder if
there's any reason not to do them:
1. Insert can use heap[1] directly instead of calling top(). After
all,
this is done in an if() that already ensures that size>0.
2. Regardless, top() could return heap[1] always, without any if
(). After
all, the heap array is initialized to all nulls, so when
size==0, heap[1]
is null anyway.
PriorityQueue change (added insertWithOverflow method)
---------------------------------------------------------------------
--------------
/**
* insertWithOverflow() is similar to insert(), except its
return value:
it
* returns the object (if any) that was dropped off the heap
because it
was
* full. This can be the given parameter (in case it is
smaller than the
* full heap's minimum, and couldn't be added) or another
object that
was
* previously the smallest value in the heap and now has been
replaced
by a
* larger one.
*/
public Object insertWithOverflow(Object element) {
if (size < maxSize) {
put(element);
return null;
} else if (size > 0 && !lessThan(element, top())) {
Object ret = heap[1];
heap[1] = element;
adjustTop();
return ret;
} else {
return element;
}
}
[Very similar to insert(), only it returns the object that was
kicked out of
the Queue, or null]
--
Nadav Har'El | Tuesday, Dec 11 2007, 3
Tevet 5768
IBM Haifa Research Lab
|-----------------------------------------
|A professor is one who talks
in someone
http://nadav.harel.org.il |else's sleep.
---------------------------------------------------------------------
To unsubscribe, e-mail: [EMAIL PROTECTED]
For additional commands, e-mail: [EMAIL PROTECTED]
---------------------------------------------------------------------
To unsubscribe, e-mail: [EMAIL PROTECTED]
For additional commands, e-mail: [EMAIL PROTECTED]
