lucene-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From robert engels <>
Subject Re: [jira] Resolved: (LUCENE-693) ConjunctionScorer - more tuneup
Date Fri, 23 Nov 2007 18:01:59 GMT
The Java classes use a merge sort, but will use an insertion sort if  
the array is smaller enough.

It might be that array clone avoidance is worths the O(n*d) versus O 
(n log n) performance difference.

Seems like a bug in the JDK - its should test the array size before  
the clone operation, as it is not needed in the insertion sort case.

BUT, more importantly and an FYI, the statement that "it is a  
bottleneck because of the 'size of norms array contained in it'" is  
not correct.  Cloning an array is a 'shallow copy', it only makes an  
array of the correct size, and copies the element references, it does  
not clone the elements themselves, so what each element references is  

On Nov 23, 2007, at 11:22 AM, Yonik Seeley wrote:

> On Nov 23, 2007 12:09 PM, robert engels <> wrote:
>> I don't understand this.
>> If the problem is the "clone", just remove the clone and call
>> Arrays.sort() using the bounded version (from,to indices)
> ???
> They both do a mergeSort and hence both require additional space.
> Regardless, the patch I created removes the sort-per-skipTo  
> altogether.
> -Yonik
> ---------------------------------------------------------------------
> To unsubscribe, e-mail:
> For additional commands, e-mail:

To unsubscribe, e-mail:
For additional commands, e-mail:

View raw message