[prev in list] [next in list] [prev in thread] [next in thread]
List: lucene-user
Subject: RE: SorterTemplate.quickSort causes StackOverflowError
From: "Uwe Schindler" <uwe () thetaphi ! de>
Date: 2011-04-29 19:54:07
Message-ID: 006c01cc06a7$33c7f7f0$9b57e7d0$ () thetaphi ! de
[Download RAW message or body]
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: uwe@thetaphi.de
> -----Original Message-----
> From: Otis Gospodnetic [mailto:otis_gospodnetic@yahoo.com]
> Sent: Friday, April 29, 2011 7:13 PM
> To: java-user@lucene.apache.org
> 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 <dawid.weiss@gmail.com>
> > To: java-user@lucene.apache.org
> > 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 <
> > otis_gospodnetic@yahoo.com> 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 <uwe@thetaphi.de>
> > > > To: java-user@lucene.apache.org
> > > > 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 <uwe@thetaphi.de>
> > > > > > To: java-user@lucene.apache.org
> > > > > > 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: uwe@thetaphi.de
> > > > > >
> > > > > >
> > > > > > > -----Original Message-----
> > > > > > > From: Otis Gospodnetic [mailto:otis_gospodnetic@yahoo.com]
> > > > > > > Sent: Thursday, April 28, 2011 11:17 PM > > > > To:
> > > java-user@lucene.apache.org
> > > > > > > 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:
> > > java-user-unsubscribe@lucene.apache.org
> > > > > > > For additional commands, e-mail:
> > > java-user-help@lucene.apache.org
> > > > > >
> > > > > >
> > > > > >
> > > > > >
> > >
> > > --------------------------------------------------------------------
> > > - > > > To unsubscribe, e-mail:
> > > java-user-unsubscribe@lucene.apache.org
> > > > > > For additional commands, e-mail:
> > > java-user-help@lucene.apache.org > > >
> > > > > >
> > > > >
> > > > >
---------------------------------------------------------------------
> > > > > To unsubscribe, e-mail:
> > > java-user-unsubscribe@lucene.apache.org
> > > > > For additional commands, e-mail:
> > > java-user-help@lucene.apache.org >
> > > >
> > > >
> > > >
> > > > ------------------------------------------------------------------
> > > > ---
> > > > To unsubscribe, e-mail: java-user-unsubscribe@lucene.apache.org
> > > > For additional commands, e-mail:
> > > java-user-help@lucene.apache.org >
> > > >
> > >
> > >
> > > --------------------------------------------------------------------
> > > - To unsubscribe, e-mail: java-user-unsubscribe@lucene.apache.org
> > > For additional commands, e-mail: java-user-help@lucene.apache.org
> > >
> > >
> >
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: java-user-unsubscribe@lucene.apache.org
> For additional commands, e-mail: java-user-help@lucene.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: java-user-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-user-help@lucene.apache.org
[prev in list] [next in list] [prev in thread] [next in thread]
Configure |
About |
News |
Add a list |
Sponsored by KoreLogic