No - I didn't try to populate an index with real data and run real queries (what is "real" after all?). I know from my experience of indexes with several millions of documents where there are queries with several hundred thousands results (one query even hit 2.5 M documents). This is typical in search: users type on average 2.3 terms in a query. The chances you'd hit a query with huge result set are not that small in such cases (I'm not saying this is the most common case though, I agree that most of the searches don't process that many documents). However, this change will improve performance from the algorithm point of view - you allocate as many as numRequestedHits+1 no matter how many documents your query processes.
On Dec 10, 2007 10:59 AM, Michael McCandless <[EMAIL PROTECTED]> wrote: > > Have you done any tests on real queries to see what impact this > improvement has in practice? Or, to measure how many ScoreDocs are > "typically" allocated? > > Mike > > Shai Erera wrote: > > > I agree w.r.t the current implementation, however in the worse case > > (as we > > tend to consider when talking about computer algorithms), it will > > allocate a > > ScoreDoc per result. With the overflow reuse, it will not allocate > > those > > objects, no matter what's the input it gets. > > Also, notice that there is a performance hit with the current > > implementation > > of TopDocCollector: it first checks that the document should be > > inserted and > > if so, PQ does the same check again. > > So, if you change the current implementation to always attempt an > > insert, > > you'd gain some performance improvements as well. > > > > On Dec 10, 2007 10:15 AM, Paul Elschot <[EMAIL PROTECTED]> wrote: > > > >> The current TopDocCollector only allocates a ScoreDoc when the given > >> score causes a new ScoreDoc to be added into the queue, but it does > >> not reuse anything that overflows out of the queue. > >> So, reusing the overflow out of the queue should reduce object > >> allocations. especially for indexes that tend to have better scoring > >> docs at the end. I wouldn't expect a 30% improvement out of that, > >> but it would help, if only to reduce occasional performance > >> deteriorations. > >> > >> Regards, > >> Paul Elschot > >> > >> > >> On Monday 10 December 2007 08:11:50 Shai Erera wrote: > >>> 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 done some measurements on the performance that search would > >>> gain by > >>> using that method, through the change of TopDocCollector. > >>> > >>> 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] > >>> > >>> TopDocCollector's current implementation of collect() > >>> > >> --------------------------------------------------------------------- > >> ------- > >>> public void collect(int doc, float score) { > >>> if (score > 0.0f) { > >>> totalHits++; > >>> if (hq.size() < numHits || score >= minScore) { > >>> hq.insert(new ScoreDoc(doc, score)); > >>> minScore = ((ScoreDoc)hq.top()).score; // maintain minScore > >>> } > >>> } > >>> } > >>> [See how it allocates a new ScoreDoc every time this method is > >>> called] > >>> > >>> TopDocCollector's new implementation of collect() > >>> > >> --------------------------------------------------------------------- > >> -------- > >>> public void collect(int doc, float score) { > >>> if (score == 0.0f) { > >>> return; > >>> } > >>> totalHits++; > >>> if (hq.size() < numHits || score >= minScore) { > >>> if (sd == null) { > >>> sd = new ScoreDoc(doc, score); > >>> } else { > >>> sd.doc = doc; > >>> sd.score = score; > >>> } > >>> sd = (ScoreDoc) hq.insertWithOverflow(sd); > >>> minScore = ((ScoreDoc)hq.top()).score; // maintain > >>> minScore > >>> } > >>> } > >>> [sd is a class memeber of the collector, of type ScoreDoc] > >>> > >>> Now for the performance tests. I've done two tests: > >>> 1. Calling TopDocCollector.collect 1,000,000, 10,000,000 and > >>> 100,000,000 > >>> times using both implementations. Here are the results: > >>> 1M 10M 100M > >>> Current Collector 218 ms 1,907ms 20,000ms > >>> Modified Collector 141 ms 1,297ms 12,672ms > >>> As you can see, the new implementation 30-40% faster. > >>> > >>> 2. Wrote some tasks in the benchmark package that makes use of > >>> the new > >> PQ > >>> while executing a real search over an index with 1M documents, of > >>> small > >> size > >>> (10 characters). Here are the results: > >>> Current TopDocCollector > >>> > >> --------------------------------------------------------------------- > >> --------------------------------------------------------------------- > >> ----- > >>> ------------> Report Sum By (any) Name (5 about 6 out of 6) > >>> Operation round runCnt recsPerRun rec/s elapsedSec > >>> avgUsedMem avgTotalMem > >>> CreateIndex 0 1 1 10.6 0.09 > >>> 2,219,112 4,389,376 > >>> AddDocs_1000000 - 0 - - 1 - - 1000000 - 52,075.2 - - > >>> 19.20 - > >>> 34,497,176 - 52,689,408 > >>> CloseIndex 0 2 1 0.1 16.62 > >>> 26,178,972 51,378,688 > >>> OpenIndex - - - 0 - - 1 - - - - 1 - - 1,000.0 - - > >>> 0.00 - > >>> 48,771,304 - 50,067,968 > >>> --> MySearch 0 1 1 > >>> 5.3 0.19 > >>> 48,771,304 50,067,968 > >>> > >>> > >>> Modified TopDocCollector > >>> > >> --------------------------------------------------------------------- > >> --------------------------------------------------------------------- > >> ----- > >>> ------------> Report Sum By (any) Name (5 about 6 out of 6) > >>> Operation round runCnt recsPerRun rec/s elapsedSec > >>> avgUsedMem avgTotalMem > >>> CreateIndex 0 1 1 10.6 0.09 > >>> 2,207,008 4,389,376 > >>> AddDocs_1000000 - 0 - - 1 - - 1000000 - 50,955.4 - - > >>> 19.62 - > >>> 32,531,992 - 44,825,088 > >>> CloseIndex 0 2 1 0.1 16.84 > >>> 57,853,148 61,929,984 > >>> OpenIndex - - - 0 - - 1 - - - - 1 - - 1,000.0 - - > >>> 0.00 - > >>> 57,792,136 - 61,929,984 > >>> --> MySearch 0 1 1 > >>> 7.1 0.14 > >>> 57,939,856 61,929,984 > >>> Notice the time difference in search (0.14 modified vs. 0.19 > >>> current). > >> Here > >>> too, a 30% improvement. > >>> > >>> One thing that I wasn't able to show, but I think it's pretty > >>> much clear > >> --> > >>> the new implementation causes a lot less object allocations. > >>> Consider > >> the > >>> typical search for 10 results over an index with 1M documents. The > >> current > >>> implementation will allocate 1M (!) ScoreDoc instances, while the > >>> new > >> one > >>> will allocate 11 (10 for the PQ and 1 for reusing). On heavily > >>> loaded > >>> systems, this will result in far less work for the GC. > >>> > >>> I would like to suggest to reflect this new implementation in > >> PriorityQueue > >>> and also modify TopDocCollector to make use of this new method. > >>> Several > >> ways > >>> to do it: > >>> 1. Add insertWithOverflow to PQ (I hate the name and I'm willing to > >> accept > >>> better ones), make insert() deprecated (let's say in 2.3) and > >>> release > >> after > >>> that (2.4?) rename insertWithOverflow to insert(). A complex > >>> process, > >> but it > >>> won't break existing applications' code. > >>> 2. Change insert's signature and state that applications that > >>> move to > >>> 2.3(for example), need to change their code as well (actually it > >>> won't > >>> compile). > >>> 3. Any other alternatives? > >>> > >>> And .. of course, review the classes in the Lucene code that use > >>> PQ and > >>> modify them as necessary. > >>> > >>> A very long email for a very simple (but important) performance > >> improvement. > >>> > >>> Shai > >>> > >> > >> > >> > >> --------------------------------------------------------------------- > >> To unsubscribe, e-mail: [EMAIL PROTECTED] > >> For additional commands, e-mail: [EMAIL PROTECTED] > >> > >> > > > > > > -- > > Regards, > > > > Shai Erera > > > --------------------------------------------------------------------- > To unsubscribe, e-mail: [EMAIL PROTECTED] > For additional commands, e-mail: [EMAIL PROTECTED] > > -- Regards, Shai Erera