Lucene, mail # user - Re: SorterTemplate.quickSort causes StackOverflowError

SorterTemplate.quickSort causes StackOverflowError

Otis Gospodnetic 2011-04-28, 21:17

Hi,

I'm looking at some code that uses MemoryIndex (Lucene 3.1) and that's
exhibiting a strange behaviour - it slows down over time.
The MemoryIndex contains 1 doc, of course, and executes a set of a few thousand
queries against it. The set of queries does not change - the same set of
queries gets executed on all incoming documents.
This code runs very quickly..... in the beginning. But with time is gets
slower and slower.... and slower..... and then I get this:

4/28/11 10:32:52 PM (S) SolrException.log : java.lang.StackOverflowError
   at org.apache.lucene.util.SorterTemplate.quickSort(SorterTemplate.java:104)
   at org.apache.lucene.util.SorterTemplate.quickSort(SorterTemplate.java:104)
   at org.apache.lucene.util.SorterTemplate.quickSort(SorterTemplate.java:104)

I haven't profiled this code yet (remote server, firewall in between, can't use
YourKit...), but does the above look familiar to anyone?
I've looked at the code and obviously there is the recursive call that's
problematic here - it looks like the recursion just gets deeper and deeper and
"gets stuck", eventually getting too deep for the JVM's taste.

Thanks,
Otis
----
Sematext :: http://sematext.com/ :: Solr - Lucene - Nutch
Lucene ecosystem search :: http://search-lucene.com/
---------------------------------------------------------------------

Re: SorterTemplate.quickSort causes StackOverflowError

jm 2011-04-28, 21:29

Hi Otis,

I have exactly the same scenario, also on 3.1, the only difference is I have
less queries, like 20 or 30.

Yesterday this code processed over 1 million incoming docs (in
a synthetic test), and did not get any error...

Not very helpful maybe but just so you get some other feedback.

javier
On Thu, Apr 28, 2011 at 11:17 PM, Otis Gospodnetic <
[EMAIL PROTECTED]> wrote:

> Hi,
>
> I'm looking at some code that uses MemoryIndex (Lucene 3.1) and that's
> exhibiting a strange behaviour - it slows down over time.
> The MemoryIndex contains 1 doc, of course, and executes a set of a few
> thousand
> queries against it. The set of queries does not change - the same set of
> queries gets executed on all incoming documents.
> This code runs very quickly..... in the beginning. But with time is gets
> slower and slower.... and slower..... and then I get this:
>
> 4/28/11 10:32:52 PM (S) SolrException.log : java.lang.StackOverflowError
> at
> org.apache.lucene.util.SorterTemplate.quickSort(SorterTemplate.java:104)
> at
> org.apache.lucene.util.SorterTemplate.quickSort(SorterTemplate.java:104)
> at
> org.apache.lucene.util.SorterTemplate.quickSort(SorterTemplate.java:104)
>
> I haven't profiled this code yet (remote server, firewall in between, can't
> use
> YourKit...), but does the above look familiar to anyone?
> I've looked at the code and obviously there is the recursive call that's
> problematic here - it looks like the recursion just gets deeper and deeper
> and
> "gets stuck", eventually getting too deep for the JVM's taste.
>
> Thanks,
> Otis
> ----
> Sematext :: http://sematext.com/ :: Solr - Lucene - Nutch
> Lucene ecosystem search :: http://search-lucene.com/
>
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: [EMAIL PROTECTED]
> For additional commands, e-mail: [EMAIL PROTECTED]
>
>

RE: SorterTemplate.quickSort causes StackOverflowError

Uwe Schindler 2011-04-28, 21:36

Hi Otis,

Can you reproduce this somehow and send test code? I could look into it. I
don't expect the error in the quicksort algorithm itself as this one is used
e.g. BytesRefHash / TermsHash, if there is a bug we would have seen it long
time ago.

I have not seen this before, but I suspect a problem in this very strange
comparator in MemoryIndex (which is very broken, if you look at its code -
it can compare Strings with Map.Entry and so on, brrrr), maybe the
comparator is not stable? In this case, quicksort can easily loop endless
and stack overflow. In Lucene 3.0 this used stock java sort (which is
mergesort), maybe replace the ArrayUtils.quickSort my ArrayUtils.mergeSort()
and see if problem is still there?

Uwe

-----
Uwe Schindler
H.-H.-Meier-Allee 63, D-28213 Bremen
http://www.thetaphi.de
eMail: [EMAIL PROTECTED]
> -----Original Message-----
> From: Otis Gospodnetic [mailto:[EMAIL PROTECTED]]
> Sent: Thursday, April 28, 2011 11:17 PM
> To: [EMAIL PROTECTED]
> Subject: SorterTemplate.quickSort causes StackOverflowError
>
> Hi,
>
> I'm looking at some code that uses MemoryIndex (Lucene 3.1) and that's
> exhibiting a strange behaviour - it slows down over time.
> The MemoryIndex contains 1 doc, of course, and executes a set of a few
> thousand queries against it. The set of queries does not change - the
same
> set of queries gets executed on all incoming documents.
> This code runs very quickly..... in the beginning. But with time is gets
> slower and slower.... and slower..... and then I get this:
>
> 4/28/11 10:32:52 PM (S) SolrException.log : java.lang.StackOverflowError
> at
> org.apache.lucene.util.SorterTemplate.quickSort(SorterTemplate.java:104)
> at
> org.apache.lucene.util.SorterTemplate.quickSort(SorterTemplate.java:104)
> at
> org.apache.lucene.util.SorterTemplate.quickSort(SorterTemplate.java:104)
>
> I haven't profiled this code yet (remote server, firewall in between,
can't use
> YourKit...), but does the above look familiar to anyone?
> I've looked at the code and obviously there is the recursive call that's
> problematic here - it looks like the recursion just gets deeper and deeper
and
> "gets stuck", eventually getting too deep for the JVM's taste.
>
> Thanks,
> Otis
> ----
> Sematext :: http://sematext.com/ :: Solr - Lucene - Nutch Lucene ecosystem
> search :: http://search-lucene.com/
>
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: [EMAIL PROTECTED]
> For additional commands, e-mail: [EMAIL PROTECTED]

---------------------------------------------------------------------

Re: SorterTemplate.quickSort causes StackOverflowError

Otis Gospodnetic 2011-04-28, 21:48

Thanks for confirming, Javier! :)

Uwe, I assume you are referring to this line 528 in MemoryIndex?

   528 if (size > 1) ArrayUtil.quickSort(entries, termComparator);

And this funky Comparator from MemoryIndex:

   208 private static final Comparator<Object> termComparator = new
Comparator<Object>() {
   209 @SuppressWarnings("unchecked")
   210 public int compare(Object o1, Object o2) {
   211 if (o1 instanceof Map.Entry<?,?>) o1 = ((Map.Entry<?,?>)
o1).getKey();
   212 if (o2 instanceof Map.Entry<?,?>) o2 = ((Map.Entry<?,?>)
o2).getKey();
   213 if (o1 == o2) return 0;
   214 return ((Comparable) o1).compareTo((Comparable) o2);
   215 }
   216 };

Will try, thanks!

Otis
----
Sematext :: http://sematext.com/ :: Solr - Lucene - Nutch
Lucene ecosystem search :: http://search-lucene.com/

----- Original Message ----
> From: Uwe Schindler <[EMAIL PROTECTED]>
> To: [EMAIL PROTECTED]
> Sent: Thu, April 28, 2011 5:36:13 PM
> Subject: RE: SorterTemplate.quickSort causes StackOverflowError
>
> Hi Otis,
>
> Can you reproduce this somehow and send test code? I could look into it. I
> don't expect the error in the quicksort algorithm itself as this one is used
> e.g. BytesRefHash / TermsHash, if there is a bug we would have seen it long
> time ago.
>
> I have not seen this before, but I suspect a problem in this very strange
> comparator in MemoryIndex (which is very broken, if you look at its code -
> it can compare Strings with Map.Entry and so on, brrrr), maybe the
> comparator is not stable? In this case, quicksort can easily loop endless
> and stack overflow. In Lucene 3.0 this used stock java sort (which is
> mergesort), maybe replace the ArrayUtils.quickSort my ArrayUtils.mergeSort()
> and see if problem is still there?
>
> Uwe
>
> -----
> Uwe Schindler
> H.-H.-Meier-Allee 63, D-28213 Bremen
> http://www.thetaphi.de
> eMail: [EMAIL PROTECTED]
>
>
> > -----Original Message-----
> > From: Otis Gospodnetic [mailto:[EMAIL PROTECTED]]
> > Sent: Thursday, April 28, 2011 11:17 PM
> > To: [EMAIL PROTECTED]
> > Subject: SorterTemplate.quickSort causes StackOverflowError
> >
> > Hi,
> >
> > I'm looking at some code that uses MemoryIndex (Lucene 3.1) and that's
> > exhibiting a strange behaviour - it slows down over time.
> > The MemoryIndex contains 1 doc, of course, and executes a set of a few
> > thousand queries against it. The set of queries does not change - the
> same
> > set of queries gets executed on all incoming documents.
> > This code runs very quickly..... in the beginning. But with time is gets
> > slower and slower.... and slower..... and then I get this:
> >
> > 4/28/11 10:32:52 PM (S) SolrException.log : java.lang.StackOverflowError
> > at
> > org.apache.lucene.util.SorterTemplate.quickSort(SorterTemplate.java:104)
> > at
> > org.apache.lucene.util.SorterTemplate.quickSort(SorterTemplate.java:104)
> > at
> > org.apache.lucene.util.SorterTemplate.quickSort(SorterTemplate.java:104)
> >
> > I haven't profiled this code yet (remote server, firewall in between,
> can't use
> > YourKit...), but does the above look familiar to anyone?
> > I've looked at the code and obviously there is the recursive call that's
> > problematic here - it looks like the recursion just gets deeper and deeper
> and
> > "gets stuck", eventually getting too deep for the JVM's taste.
> >
> > Thanks,
> > Otis
> > ----
> > Sematext :: http://sematext.com/ :: Solr - Lucene - Nutch Lucene ecosystem
> > search :: http://search-lucene.com/
> >
> >
> > ---------------------------------------------------------------------
> > 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]

RE: SorterTemplate.quickSort causes StackOverflowError

Uwe Schindler 2011-04-28, 21:54

> Thanks for confirming, Javier! :)
>
> Uwe, I assume you are referring to this line 528 in MemoryIndex?
>
> 528 if (size > 1) ArrayUtil.quickSort(entries, termComparator);
>
> And this funky Comparator from MemoryIndex:
>
> 208 private static final Comparator<Object> termComparator = new
> Comparator<Object>() {
> 209 @SuppressWarnings("unchecked")
> 210 public int compare(Object o1, Object o2) {
> 211 if (o1 instanceof Map.Entry<?,?>) o1 = ((Map.Entry<?,?>)
> o1).getKey();
> 212 if (o2 instanceof Map.Entry<?,?>) o2 = ((Map.Entry<?,?>)
> o2).getKey();
> 213 if (o1 == o2) return 0;
> 214 return ((Comparable) o1).compareTo((Comparable) o2);
> 215 }
> 216 };
>
> Will try, thanks!

Yeah, simply try with mergeSort in line 528. If that helps, this comparator
is buggy.

Uwe
> ----- Original Message ----
> > From: Uwe Schindler <[EMAIL PROTECTED]>
> > To: [EMAIL PROTECTED]
> > Sent: Thu, April 28, 2011 5:36:13 PM
> > Subject: RE: SorterTemplate.quickSort causes StackOverflowError
> >
> > Hi Otis,
> >
> > Can you reproduce this somehow and send test code? I could look into
> > it. I don't expect the error in the quicksort algorithm itself as this
> > one is used e.g. BytesRefHash / TermsHash, if there is a bug we would
> > have seen it long time ago.
> >
> > I have not seen this before, but I suspect a problem in this very
> > strange comparator in MemoryIndex (which is very broken, if you look
> > at its code - it can compare Strings with Map.Entry and so on,
> > brrrr), maybe the comparator is not stable? In this case, quicksort
> > can easily loop endless and stack overflow. In Lucene 3.0 this used
> > stock java sort (which is mergesort), maybe replace the
> > ArrayUtils.quickSort my ArrayUtils.mergeSort() and see if problem is
still
> there?
> >
> > Uwe
> >
> > -----
> > Uwe Schindler
> > H.-H.-Meier-Allee 63, D-28213 Bremen
> > http://www.thetaphi.de
> > eMail: [EMAIL PROTECTED]
> >
> >
> > > -----Original Message-----
> > > From: Otis Gospodnetic [mailto:[EMAIL PROTECTED]]
> > > Sent: Thursday, April 28, 2011 11:17 PM
> > > To: [EMAIL PROTECTED]
> > > Subject: SorterTemplate.quickSort causes StackOverflowError
> > >
> > > Hi,
> > >
> > > I'm looking at some code that uses MemoryIndex (Lucene 3.1) and
> > > that's exhibiting a strange behaviour - it slows down over time.
> > > The MemoryIndex contains 1 doc, of course, and executes a set of a
> > > few thousand queries against it. The set of queries does not
> > > change - the
> > same
> > > set of queries gets executed on all incoming documents.
> > > This code runs very quickly..... in the beginning. But with time is
gets
> > > slower and slower.... and slower..... and then I get this:
> > >
> > > 4/28/11 10:32:52 PM (S) SolrException.log :
java.lang.StackOverflowError
> > > at
> > >
> org.apache.lucene.util.SorterTemplate.quickSort(SorterTemplate.java:104)
> > > at
> > >
> org.apache.lucene.util.SorterTemplate.quickSort(SorterTemplate.java:104)
> > > at
> > >
> > > org.apache.lucene.util.SorterTemplate.quickSort(SorterTemplate.java:
> > > 104)
> > >
> > > I haven't profiled this code yet (remote server, firewall in
> > > between,
> > can't use
> > > YourKit...), but does the above look familiar to anyone?
> > > I've looked at the code and obviously there is the recursive call
> > > that's problematic here - it looks like the recursion just gets
> > > deeper and deeper
> > and
> > > "gets stuck", eventually getting too deep for the JVM's taste.
> > >
> > > Thanks,
> > > Otis
> > > ----
> > > Sematext :: http://sematext.com/ :: Solr - Lucene - Nutch Lucene
> > > ecosystem search :: http://search-lucene.com/
> > >
> > >
> > >
> > > --------------------------------------------------------------------
> > > - To unsubscribe, e-mail: [EMAIL PROTECTED]
> > > For additional commands, e-mail: [EMAIL PROTECTED]

Re: SorterTemplate.quickSort causes StackOverflowError

Otis Gospodnetic 2011-04-29, 11:40

Hi,

OK, so it looks like it's not MemoryIndex and its Comparator that are funky.
After switching from quickSort call in MemoryIndex to mergeSort, the problem
persists:

'1205215856@qtp-684754483-7' Id=18, RUNNABLE on lock=, total cpu
time=497060.0000ms user time=495210.0000msat
org.apache.lucene.util.SorterTemplate.quickSort(SorterTemplate.java:105)

at org.apache.lucene.util.SorterTemplate.quickSort(SorterTemplate.java:104)
at org.apache.lucene.util.SorterTemplate.quickSort(SorterTemplate.java:104)
at org.apache.lucene.util.SorterTemplate.quickSort(SorterTemplate.java:104)
So something else is calling quickSort when it gets stuck. Weirdly, when I get
a thread dump and get the above, I don't see the original caller. Maybe because
the stack is already too deep and the printout is limited to N lines per call
stack?

Otis
----
Sematext :: http://sematext.com/ :: Solr - Lucene - Nutch
Lucene ecosystem search :: http://search-lucene.com/

----- Original Message ----
> From: Uwe Schindler <[EMAIL PROTECTED]>
> To: [EMAIL PROTECTED]
> Sent: Thu, April 28, 2011 5:54:44 PM
> Subject: RE: SorterTemplate.quickSort causes StackOverflowError
>
> > Thanks for confirming, Javier! :)
> >
> > Uwe, I assume you are referring to this line 528 in MemoryIndex?
> >
> > 528 if (size > 1) ArrayUtil.quickSort(entries, termComparator);
> >
> > And this funky Comparator from MemoryIndex:
> >
> > 208 private static final Comparator<Object> termComparator = new
> > Comparator<Object>() {
> > 209 @SuppressWarnings("unchecked")
> > 210 public int compare(Object o1, Object o2) {
> > 211 if (o1 instanceof Map.Entry<?,?>) o1 = ((Map.Entry<?,?>)
> > o1).getKey();
> > 212 if (o2 instanceof Map.Entry<?,?>) o2 = ((Map.Entry<?,?>)
> > o2).getKey();
> > 213 if (o1 == o2) return 0;
> > 214 return ((Comparable) o1).compareTo((Comparable) o2);
> > 215 }
> > 216 };
> >
> > Will try, thanks!
>
> Yeah, simply try with mergeSort in line 528. If that helps, this comparator
> is buggy.
>
> Uwe
>
>
> > ----- Original Message ----
> > > From: Uwe Schindler <[EMAIL PROTECTED]>
> > > To: [EMAIL PROTECTED]
> > > Sent: Thu, April 28, 2011 5:36:13 PM
> > > Subject: RE: SorterTemplate.quickSort causes StackOverflowError
> > >
> > > Hi Otis,
> > >
> > > Can you reproduce this somehow and send test code? I could look into
> > > it. I don't expect the error in the quicksort algorithm itself as this
> > > one is used e.g. BytesRefHash / TermsHash, if there is a bug we would
> > > have seen it long time ago.
> > >
> > > I have not seen this before, but I suspect a problem in this very
> > > strange comparator in MemoryIndex (which is very broken, if you look
> > > at its code - it can compare Strings with Map.Entry and so on,
> > > brrrr), maybe the comparator is not stable? In this case, quicksort
> > > can easily loop endless and stack overflow. In Lucene 3.0 this used
> > > stock java sort (which is mergesort), maybe replace the
> > > ArrayUtils.quickSort my ArrayUtils.mergeSort() and see if problem is
> still
> > there?
> > >
> > > Uwe
> > >
> > > -----
> > > Uwe Schindler
> > > H.-H.-Meier-Allee 63, D-28213 Bremen
> > > http://www.thetaphi.de
> > > eMail: [EMAIL PROTECTED]
> > >
> > >
> > > > -----Original Message-----
> > > > From: Otis Gospodnetic [mailto:[EMAIL PROTECTED]]
> > > > Sent: Thursday, April 28, 2011 11:17 PM
> > > > To: [EMAIL PROTECTED]
> > > > Subject: SorterTemplate.quickSort causes StackOverflowError
> > > >
> > > > Hi,
> > > >
> > > > I'm looking at some code that uses MemoryIndex (Lucene 3.1) and
> > > > that's exhibiting a strange behaviour - it slows down over time.
> > > > The MemoryIndex contains 1 doc, of course, and executes a set of a
> > > > few thousand queries against it. The set of queries does not
> > > > change - the
> > > same
> > > > set of queries gets executed on all incoming documents.

Re: SorterTemplate.quickSort causes StackOverflowError

jm 2011-04-29, 11:50

maybe http://youdebug.kenai.com/ could be useful. If you are lucky you could
get it to set a breakpoint when the recursive call has reached depth X.

On Fri, Apr 29, 2011 at 1:40 PM, Otis Gospodnetic <
[EMAIL PROTECTED]> wrote:

> Hi,
>
> OK, so it looks like it's not MemoryIndex and its Comparator that are
> funky.
> After switching from quickSort call in MemoryIndex to mergeSort, the
> problem
> persists:
>
> '1205215856@qtp-684754483-7' Id=18, RUNNABLE on lock=, total cpu
> time=497060.0000ms user time=495210.0000msat
> org.apache.lucene.util.SorterTemplate.quickSort(SorterTemplate.java:105)
>
> at org.apache.lucene.util.SorterTemplate.quickSort(SorterTemplate.java:104)
> at org.apache.lucene.util.SorterTemplate.quickSort(SorterTemplate.java:104)
> at org.apache.lucene.util.SorterTemplate.quickSort(SorterTemplate.java:104)
> So something else is calling quickSort when it gets stuck. Weirdly, when I
> get
> a thread dump and get the above, I don't see the original caller. Maybe
> because
> the stack is already too deep and the printout is limited to N lines per
> call
> stack?
>
> Otis
> ----
> Sematext :: http://sematext.com/ :: Solr - Lucene - Nutch
> Lucene ecosystem search :: http://search-lucene.com/
>
>
>
> ----- Original Message ----
> > From: Uwe Schindler <[EMAIL PROTECTED]>
> > To: [EMAIL PROTECTED]
> > Sent: Thu, April 28, 2011 5:54:44 PM
> > Subject: RE: SorterTemplate.quickSort causes StackOverflowError
> >
> > > Thanks for confirming, Javier! :)
> > >
> > > Uwe, I assume you are referring to this line 528 in MemoryIndex?
> > >
> > > 528 if (size > 1) ArrayUtil.quickSort(entries,
> termComparator);
> > >
> > > And this funky Comparator from MemoryIndex:
> > >
> > > 208 private static final Comparator<Object> termComparator = new
> > > Comparator<Object>() {
> > > 209 @SuppressWarnings("unchecked")
> > > 210 public int compare(Object o1, Object o2) {
> > > 211 if (o1 instanceof Map.Entry<?,?>) o1 > ((Map.Entry<?,?>)
> > > o1).getKey();
> > > 212 if (o2 instanceof Map.Entry<?,?>) o2 > ((Map.Entry<?,?>)
> > > o2).getKey();
> > > 213 if (o1 == o2) return 0;
> > > 214 return ((Comparable) o1).compareTo((Comparable) o2);
> > > 215 }
> > > 216 };
> > >
> > > Will try, thanks!
> >
> > Yeah, simply try with mergeSort in line 528. If that helps, this
> comparator
> > is buggy.
> >
> > Uwe
> >
> >
> > > ----- Original Message ----
> > > > From: Uwe Schindler <[EMAIL PROTECTED]>
> > > > To: [EMAIL PROTECTED]
> > > > Sent: Thu, April 28, 2011 5:36:13 PM
> > > > Subject: RE: SorterTemplate.quickSort causes StackOverflowError
> > > >
> > > > Hi Otis,
> > > >
> > > > Can you reproduce this somehow and send test code? I could look
> into
> > > > it. I don't expect the error in the quicksort algorithm itself as
> this
> > > > one is used e.g. BytesRefHash / TermsHash, if there is a bug we
> would
> > > > have seen it long time ago.
> > > >
> > > > I have not seen this before, but I suspect a problem in this very
> > > > strange comparator in MemoryIndex (which is very broken, if you
> look
> > > > at its code - it can compare Strings with Map.Entry and so on,
> > > > brrrr), maybe the comparator is not stable? In this case, quicksort
> > > > can easily loop endless and stack overflow. In Lucene 3.0 this used
> > > > stock java sort (which is mergesort), maybe replace the
> > > > ArrayUtils.quickSort my ArrayUtils.mergeSort() and see if problem
> is
> > still
> > > there?
> > > >
> > > > Uwe
> > > >
> > > > -----
> > > > Uwe Schindler
> > > > H.-H.-Meier-Allee 63, D-28213 Bremen
> > > > http://www.thetaphi.de
> > > > eMail: [EMAIL PROTECTED]
> > > >
> > > >
> > > > > -----Original Message-----
> > > > > From: Otis Gospodnetic [mailto:[EMAIL PROTECTED]]
> > > > > Sent: Thursday, April 28, 2011 11:17 PM
> > > > > To: [EMAIL PROTECTED]
> > > > > Subject: SorterTemplate.quickSort causes StackOverflowError

Re: SorterTemplate.quickSort causes StackOverflowError

Dawid Weiss 2011-04-29, 11:51

Don't know if this helps, but debugging stuff like this I simply add a
(manually inserted or aspectj-injected) recursion count, add a breakpoint
inside an if checking for recursion count >> X and run the vm with an
attached socket debugger. This lets you run at (nearly) full speed and once
you hit the breakpoint, inspect the stack, variables, etc...

Dawid

On Fri, Apr 29, 2011 at 1:40 PM, Otis Gospodnetic <
[EMAIL PROTECTED]> wrote:

> Hi,
>
> OK, so it looks like it's not MemoryIndex and its Comparator that are
> funky.
> After switching from quickSort call in MemoryIndex to mergeSort, the
> problem
> persists:
>
> '1205215856@qtp-684754483-7' Id=18, RUNNABLE on lock=, total cpu
> time=497060.0000ms user time=495210.0000msat
> org.apache.lucene.util.SorterTemplate.quickSort(SorterTemplate.java:105)
>
> at org.apache.lucene.util.SorterTemplate.quickSort(SorterTemplate.java:104)
> at org.apache.lucene.util.SorterTemplate.quickSort(SorterTemplate.java:104)
> at org.apache.lucene.util.SorterTemplate.quickSort(SorterTemplate.java:104)
> So something else is calling quickSort when it gets stuck. Weirdly, when I
> get
> a thread dump and get the above, I don't see the original caller. Maybe
> because
> the stack is already too deep and the printout is limited to N lines per
> call
> stack?
>
> Otis
> ----
> Sematext :: http://sematext.com/ :: Solr - Lucene - Nutch
> Lucene ecosystem search :: http://search-lucene.com/
>
>
>
> ----- Original Message ----
> > From: Uwe Schindler <[EMAIL PROTECTED]>
> > To: [EMAIL PROTECTED]
> > Sent: Thu, April 28, 2011 5:54:44 PM
> > Subject: RE: SorterTemplate.quickSort causes StackOverflowError
> >
> > > Thanks for confirming, Javier! :)
> > >
> > > Uwe, I assume you are referring to this line 528 in MemoryIndex?
> > >
> > > 528 if (size > 1) ArrayUtil.quickSort(entries,
> termComparator);
> > >
> > > And this funky Comparator from MemoryIndex:
> > >
> > > 208 private static final Comparator<Object> termComparator = new
> > > Comparator<Object>() {
> > > 209 @SuppressWarnings("unchecked")
> > > 210 public int compare(Object o1, Object o2) {
> > > 211 if (o1 instanceof Map.Entry<?,?>) o1 > ((Map.Entry<?,?>)
> > > o1).getKey();
> > > 212 if (o2 instanceof Map.Entry<?,?>) o2 > ((Map.Entry<?,?>)
> > > o2).getKey();
> > > 213 if (o1 == o2) return 0;
> > > 214 return ((Comparable) o1).compareTo((Comparable) o2);
> > > 215 }
> > > 216 };
> > >
> > > Will try, thanks!
> >
> > Yeah, simply try with mergeSort in line 528. If that helps, this
> comparator
> > is buggy.
> >
> > Uwe
> >
> >
> > > ----- Original Message ----
> > > > From: Uwe Schindler <[EMAIL PROTECTED]>
> > > > To: [EMAIL PROTECTED]
> > > > Sent: Thu, April 28, 2011 5:36:13 PM
> > > > Subject: RE: SorterTemplate.quickSort causes StackOverflowError
> > > >
> > > > Hi Otis,
> > > >
> > > > Can you reproduce this somehow and send test code? I could look
> into
> > > > it. I don't expect the error in the quicksort algorithm itself as
> this
> > > > one is used e.g. BytesRefHash / TermsHash, if there is a bug we
> would
> > > > have seen it long time ago.
> > > >
> > > > I have not seen this before, but I suspect a problem in this very
> > > > strange comparator in MemoryIndex (which is very broken, if you
> look
> > > > at its code - it can compare Strings with Map.Entry and so on,
> > > > brrrr), maybe the comparator is not stable? In this case, quicksort
> > > > can easily loop endless and stack overflow. In Lucene 3.0 this used
> > > > stock java sort (which is mergesort), maybe replace the
> > > > ArrayUtils.quickSort my ArrayUtils.mergeSort() and see if problem
> is
> > still
> > > there?
> > > >
> > > > Uwe
> > > >
> > > > -----
> > > > Uwe Schindler
> > > > H.-H.-Meier-Allee 63, D-28213 Bremen
> > > > http://www.thetaphi.de
> > > > eMail: [EMAIL PROTECTED]
> > > >
> > > >
> > > > > -----Original Message-----

Re: SorterTemplate.quickSort causes StackOverflowError

Otis Gospodnetic 2011-04-29, 17:12

Hi,

Yeah, that's what we were going to do, but instead we did:
* changed MemoryIndex to use ArrayUtil.mergeSort
* ran the up and did a thread dump that shows that SorterTemplate.quickSort in
deep recursion again!
* looked for other places where this call is made - found it in
MultiPhraseQuery$MultiPhraseWeight and changed that call from
ArrayUtil.quickSort to ArrayUtil.mergeSort
* now we no longer see SorterTemplate.quickSort in deep recursion when we do a
thread dump
* we now occasionally catch SorterTemplate.mergeSort in our thread dumps, but
only a few levels deep, which looks healthy

I don't think we'll be able to reproduce this easily - this happens with
MemoryIndex and a few thousand stored queries that are confidential customer
data :(

I'll be back if after a while mergeSort starts behaving the same as quickSort.

Thanks!
Otis
----
Sematext :: http://sematext.com/ :: Solr - Lucene - Nutch
Lucene ecosystem search :: http://search-lucene.com/

----- Original Message ----
> From: Dawid Weiss <[EMAIL PROTECTED]>
> To: [EMAIL PROTECTED]
> Sent: Fri, April 29, 2011 7:51:39 AM
> Subject: Re: SorterTemplate.quickSort causes StackOverflowError
>
> Don't know if this helps, but debugging stuff like this I simply add a
> (manually inserted or aspectj-injected) recursion count, add a breakpoint
> inside an if checking for recursion count >> X and run the vm with an
> attached socket debugger. This lets you run at (nearly) full speed and once
> you hit the breakpoint, inspect the stack, variables, etc...
>
> Dawid
>
> On Fri, Apr 29, 2011 at 1:40 PM, Otis Gospodnetic <
> [EMAIL PROTECTED]> wrote:
>
> > Hi,
> >
> > OK, so it looks like it's not MemoryIndex and its Comparator that are
> > funky.
> > After switching from quickSort call in MemoryIndex to mergeSort, the
> > problem
> > persists:
> >
> > '1205215856@qtp-684754483-7' Id=18, RUNNABLE on lock=, total cpu
> > time=497060.0000ms user time=495210.0000msat
> > org.apache.lucene.util.SorterTemplate.quickSort(SorterTemplate.java:105)
> >
> > at
org.apache.lucene.util.SorterTemplate.quickSort(SorterTemplate.java:104)
> > at
org.apache.lucene.util.SorterTemplate.quickSort(SorterTemplate.java:104)
> > at
org.apache.lucene.util.SorterTemplate.quickSort(SorterTemplate.java:104)
> > So something else is calling quickSort when it gets stuck. Weirdly, when
I
> > get
> > a thread dump and get the above, I don't see the original caller. Maybe
> > because
> > the stack is already too deep and the printout is limited to N lines per
> > call
> > stack?
> >
> > Otis
> > ----
> > Sematext :: http://sematext.com/ :: Solr - Lucene - Nutch
> > Lucene ecosystem search :: http://search-lucene.com/
> >
> >
> >
> > ----- Original Message ----
> > > From: Uwe Schindler <[EMAIL PROTECTED]>
> > > To: [EMAIL PROTECTED]
> > > Sent: Thu, April 28, 2011 5:54:44 PM
> > > Subject: RE: SorterTemplate.quickSort causes StackOverflowError
> > >
> > > > Thanks for confirming, Javier! :)
> > > >
> > > > Uwe, I assume you are referring to this line 528 in MemoryIndex?
> > > >
> > > > 528 if (size > 1) ArrayUtil.quickSort(entries,
> > termComparator);
> > > >
> > > > And this funky Comparator from MemoryIndex:
> > > >
> > > > 208 private static final Comparator<Object> termComparator = new
> > > > Comparator<Object>() {
> > > > 209 @SuppressWarnings("unchecked")
> > > > 210 public int compare(Object o1, Object o2) {
> > > > 211 if (o1 instanceof Map.Entry<?,?>) o1 > > ((Map.Entry<?,?>)
> > > > o1).getKey();
> > > > 212 if (o2 instanceof Map.Entry<?,?>) o2 > > ((Map.Entry<?,?>)
> > > > o2).getKey();
> > > > 213 if (o1 == o2) return 0;
> > > > 214 return ((Comparable) o1).compareTo((Comparable) o2);
> > > > 215 }
> > > > 216 };
> > > >
> > > > Will try, thanks!
> > >
> > > Yeah, simply try with mergeSort in line 528. If that helps, this

RE: SorterTemplate.quickSort causes StackOverflowError

Uwe Schindler 2011-04-29, 19:54

Hi Otis,

Thanks for trying out. From what I see, the problem is at all not in
MemoryIndex, so I suggest that you replace the mergeSort by quicksort again
(for MemoryIndex, see below). The problem seem to be the comparators that's
are in those Queries, which have no tie-breaker. MergeSort can handle them
better, because mergeSort is stable in comparison to quicksort.

I did some testing with random data and did not get a stack overflow at all
(with standard terms / integers). A integer sort showed that even 200
million integers sorted a) much faster with quickSort and did not stack
overflow (in reality, for good comparators, integers should at most do 31
recursions, but only with 2^31 integers in an array!!!), so quickSort is
fine for strings and integers.

Mike McCandless did some tests in TermsHash/BytesRefHash (Lucene Core), that
showed that quicksort is 20% faster than mergeSort. The code is similar to
MemoryIndex, so this is why I suggest to not change MemoryIndex at all. From
your description of the issue its also unlikely that MemoryIndex is causing
this, because sorting is only done on building the index, not when queries
are running! So the bad guys are the PhraseQueries. We should fix them ASAP,
as this may affect other users, too.

More on https://issues.apache.org/jira/browse/LUCENE-3054,
Thanks Robert!

I will review later, I am heavy busy at the moment.
Uwe

-----
Uwe Schindler
H.-H.-Meier-Allee 63, D-28213 Bremen
http://www.thetaphi.de
eMail: [EMAIL PROTECTED]
> -----Original Message-----
> From: Otis Gospodnetic [mailto:[EMAIL PROTECTED]]
> Sent: Friday, April 29, 2011 7:13 PM
> To: [EMAIL PROTECTED]
> Subject: Re: SorterTemplate.quickSort causes StackOverflowError
>
> Hi,
>
> Yeah, that's what we were going to do, but instead we did:
> * changed MemoryIndex to use ArrayUtil.mergeSort
> * ran the up and did a thread dump that shows that
> SorterTemplate.quickSort in deep recursion again!
> * looked for other places where this call is made - found it in
> MultiPhraseQuery$MultiPhraseWeight and changed that call from
> ArrayUtil.quickSort to ArrayUtil.mergeSort
> * now we no longer see SorterTemplate.quickSort in deep recursion when
> we do a thread dump
> * we now occasionally catch SorterTemplate.mergeSort in our thread dumps,
> but only a few levels deep, which looks healthy
>
> I don't think we'll be able to reproduce this easily - this happens with
> MemoryIndex and a few thousand stored queries that are confidential
> customer data :(
>
> I'll be back if after a while mergeSort starts behaving the same as
quickSort.
>
> Thanks!
> Otis
> ----
> Sematext :: http://sematext.com/ :: Solr - Lucene - Nutch Lucene ecosystem
> search :: http://search-lucene.com/
>
>
>
> ----- Original Message ----
> > From: Dawid Weiss <[EMAIL PROTECTED]>
> > To: [EMAIL PROTECTED]
> > Sent: Fri, April 29, 2011 7:51:39 AM
> > Subject: Re: SorterTemplate.quickSort causes StackOverflowError
> >
> > Don't know if this helps, but debugging stuff like this I simply add
> > a (manually inserted or aspectj-injected) recursion count, add a
> > breakpoint inside an if checking for recursion count >> X and run the
> > vm with an attached socket debugger. This lets you run at (nearly)
> > full speed and once you hit the breakpoint, inspect the stack,
variables,
> etc...
> >
> > Dawid
> >
> > On Fri, Apr 29, 2011 at 1:40 PM, Otis Gospodnetic <
> > [EMAIL PROTECTED]> wrote:
> >
> > > Hi,
> > >
> > > OK, so it looks like it's not MemoryIndex and its Comparator that
> > > are funky.
> > > After switching from quickSort call in MemoryIndex to mergeSort,
> > > the problem
> > > persists:
> > >
> > > '1205215856@qtp-684754483-7' Id=18, RUNNABLE on lock=, total cpu
> > > time=497060.0000ms user time=495210.0000msat
> > >
> > > org.apache.lucene.util.SorterTemplate.quickSort(SorterTemplate.java:
> > > 105)
> > >
> > > at
> org.apache.lucene.util.SorterTemplate.quickSort(SorterTemplate.java:104)
o2);
we
In
StackOverflowError
time.
set
with
taste.