Native (C++) implementation of "pure OR" BooleanQuery [LUCENE-5049]

[asfimport]

I've been playing with a C++ implementation of BooleanQuery containing
only OR'd (SHOULD) TermQuery clauses, collecting top N hits by score.

The results are impressive: ~3X speedup for BQ OR over two terms, and
also good speedups (~38-78%) for Fuzzy1/2 as well since they rewrite
to BQ OR over N terms:

                    Task    QPS base      StdDev    QPS comp      StdDev                Pct diff
                 MedTerm       69.47     (15.8%)       68.61     (13.4%)   -1.2% ( -26% -   33%)
                HighTerm       55.25     (16.2%)       54.63     (13.9%)   -1.1% ( -26% -   34%)
                 LowTerm      333.10      (9.6%)      329.43      (8.0%)   -1.1% ( -17% -   18%)
                  IntNRQ        3.37      (2.6%)        3.36      (4.6%)   -0.2% (  -7% -    7%)
                 Prefix3       18.91      (2.0%)       19.04      (3.5%)    0.7% (  -4% -    6%)
                Wildcard       29.40      (1.7%)       29.70      (2.8%)    1.0% (  -3% -    5%)
               MedPhrase      132.69      (6.2%)      134.66      (7.0%)    1.5% ( -11% -   15%)
        HighSloppyPhrase        0.82      (3.6%)        0.83      (3.5%)    1.9% (  -5% -    9%)
             AndHighHigh       19.65      (0.6%)       20.02      (0.8%)    1.9% (   0% -    3%)
              HighPhrase       11.74      (6.6%)       11.96      (7.1%)    1.9% ( -11% -   16%)
         MedSloppyPhrase       29.09      (1.2%)       29.76      (1.9%)    2.3% (   0% -    5%)
         LowSloppyPhrase       25.71      (1.4%)       26.98      (1.7%)    4.9% (   1% -    8%)
                 Respell      173.78      (3.0%)      182.41      (3.7%)    5.0% (  -1% -   12%)
             MedSpanNear       27.67      (2.5%)       29.07      (2.4%)    5.1% (   0% -   10%)
            HighSpanNear        2.95      (2.4%)        3.10      (2.8%)    5.4% (   0% -   10%)
             LowSpanNear        8.29      (3.4%)        8.82      (3.3%)    6.4% (   0% -   13%)
              AndHighMed       79.32      (1.6%)       84.44      (1.0%)    6.5% (   3% -    9%)
               LowPhrase       23.20      (2.0%)       25.14      (1.6%)    8.4% (   4% -   12%)
              AndHighLow      594.17      (3.4%)      660.32      (1.9%)   11.1% (   5% -   16%)
                  Fuzzy2       88.32      (6.4%)      121.44      (1.7%)   37.5% (  27% -   48%)
                  Fuzzy1       86.34      (6.0%)      153.49      (1.7%)   77.8% (  66% -   90%)
              OrHighHigh       16.29      (2.5%)       48.29      (1.3%)  196.5% ( 188% -  205%)
               OrHighMed       28.98      (2.7%)       87.81      (0.9%)  203.0% ( 194% -  212%)
               OrHighLow       27.38      (2.6%)       84.94      (1.1%)  210.3% ( 201% -  219%)

This is essentially a scaled back attempt at #2668 in that it's
"hardwired" to "just" the "OR of TermQuery" case.

---

Migrated from LUCENE-5049 by Michael McCandless (@mikemccand), 1 vote, updated Jun 22 2013
Attachments: LUCENE-5049.patch

[asfimport]

Michael McCandless (@mikemccand) (migrated from JIRA)

Patch.

I use NativeMMapDir (borrowed from LUCENE-3178) to be able to map a
single file without chunking.

No core changes were needed (it uses reflection to grab all the stuff
it needs).

This works with the current default 4.x codec, but it's somewhat
sub-optimal on x86 since Lucene stores longs big-endian but x86 is
little-endian: I do a long byte-swap for every long at read time
(though this is a single instruction on x86...). Also, the longs are
not "aligned" in memory, but x86 seems not to have much penalty for
this (I tried a modified PF that inserts spacer bytes to align each
block, but net/net it was slower).

It's simple to use: there is a single static NativeSearch.search
method, that will use the native code if it can apply to the current
"context", and otherwise falls back to normal IndexSearcher method.
So an app can just route all searches through this API, and those that
can be optimized, will be.

There are definite limitations:

• You must use NativeMMapDir, default codec and sim, all terms must
  be in one field, and you must sort by score.

• It's C code ... so when there are bugs, when you close the
  IndexSearcher while threads are still searching, etc., you'll get
  SEGV and the OS will kill the JVM!

• Only works on Linux (Unix) little-endian CPUs (only tested on
  Linux/Intel...) since I always byte swap ...

[asfimport]

Jack Krupansky (migrated from JIRA)

Okay, I'll be the first to ask it: C++? Really? Is this the beginning of the end for Java for the world of high-performance search?

Seriously, a second question: What about alternative JVM-based languages? I mean, maybe Java does have excess baggage related to its quirky semantics, but could the raw JVM support a lower-level implementation of BQ, without leaving the JVM... "bubble"? OTOH, maybe different JVM's could have different performance characteristics.

Oh, and what compiler/machine architecture was this for?

Another question: might there be alternative representations of BQ based on what exactly the clauses are?

OTOH, for us Solr guys, there is somewhat the impression that raw Lucene search is blazing fast already and not the bottleneck for Solr where other things, like caches and facets and highlighting are the concern.

Finally, some of these gains seem... marginal if not outright disappointing considering the raw expectation that bare C++ should be a LOT faster. So, is this maybe more of a "See, C++ doesn't have THAT big an advantage over Java even for core search operations?

[asfimport]

Robert Muir (@rmuir) (migrated from JIRA)

This is an apples vs oranges comparison.

If you write one huge hairy java method with hardcoded query (OR) + hardcoded Postingsformat (Lucene42) + hardcoded Directory (Mmap) + Hardcoded Similarity (Default) that only works if all terms are against a single field, it would be much faster there too...

[asfimport]

Michael McCandless (@mikemccand) (migrated from JIRA)

This is an apples vs oranges comparison.

I agree: all we can conclude from the benchmark is that this hardwired
C++ impl is ~3X faster (on OR-of-TermQuery) than what we have today in
Java.

We can't tell exactly where the gains come from, i.e. how much is due
to 1) Java vs C and how much from 2) specializing everything to single
dedicated code.

If we could build the same specialized code in Java then we could
separately test these contributions. Maybe we could also test which
components (decoding postings, matching, scoring, collecting) gave
which part of the gains.

[asfimport]

Michael McCandless (@mikemccand) (migrated from JIRA)

Okay, I'll be the first to ask it: C++? Really? Is this the beginning of the end for Java for the world of high-performance search?

I don't think so. This is just an option and it only matches users
doing OR BQ over TQ against one field, with default codec/sim, etc.
I certainly don't think we should switch Lucene to C++.

Seriously, a second question: What about alternative JVM-based languages? I mean, maybe Java does have excess baggage related to its quirky semantics, but could the raw JVM support a lower-level implementation of BQ, without leaving the JVM... "bubble"? OTOH, maybe different JVM's could have different performance characteristics.

We should explore that! I have no idea.

Oh, and what compiler/machine architecture was this for?

Linux / x86 is what I tested on, but I think the code would work fine on other OS's / CPUs.

Another question: might there be alternative representations of BQ based on what exactly the clauses are?

?

OTOH, for us Solr guys, there is somewhat the impression that raw Lucene search is blazing fast already and not the bottleneck for Solr where other things, like caches and facets and highlighting are the concern.

Faceting/highlighting are definitely costly...

Finally, some of these gains seem... marginal if not outright disappointing considering the raw expectation that bare C++ should be a LOT faster. So, is this maybe more of a "See, C++ doesn't have THAT big an advantage over Java even for core search operations?

Actually I think ~300% gains are unexpectedly high: they were more
than I expected.

It would be nice if most of those gains were from code spec and not
from Java/C++ ... then we could say "C++ doesn't have that big an
advantage over Java", but it's not clear now where the gains come
from.

[asfimport]

Uwe Schindler (@uschindler) (migrated from JIRA)

Hi Mike,

I agree with Robert and Jack - this is like comparing apples and pies. We are back at the same place like 4 ⚠ years ago when everybody added bulk APIs and you posted a highly optimized special case with all l☃☃ps-unr☃lled™ (#2668). This is comparing apples with pies: You use the specialized MMapDirectory which is really a lot faster, so a lot of the improvements also come from there. From most customers I have seen, the "OR" case with pure term queries is not the most common one (although it should in reality, but users want "and" - maybe because our default scoring is bad - other story?).

I am completely against the idea to have this anywhere in Lucene, same for NativeMMapDirectory (and I am not happy with NativeLinux/WindowsDirectory, too - although they are so special that they have some reason to exist). I would never suggest anybody to actually use this in production, it is too risky. If you want to release this code, its easy: Create a Google Code project and do it outside of Lucene. All interconnection points here are through reflection, so it can be completely separate. I definitely will not post you results anywhere in twitter, because doing this would create another shitstorm against Lucene, Java, Hotspot, and C++ - especially because the results here have nothing to do with Java vs. C++ - its just specialization, nothing more. As Robert said, you can do the same with pure Java (see LUCENE-1594).

The only possible way to bring C code back into the game is to bring CLucene back to live!

Seriously, a second question: What about alternative JVM-based languages? I mean, maybe Java does have excess baggage related to its quirky semantics, but could the raw JVM support a lower-level implementation of BQ, without leaving the JVM... "bubble"? OTOH, maybe different JVM's could have different performance characteristics.

I don't see any change in performance here, as other JVM-based languages produce the same bytecode like javac, just from another source code. Java bytecode is flexible but not too flexible. The optimizations are done by hotspot and those bytecode has not much room for optimization, thats up to the runtime engine.

The only thing I see is: We use ASM or Javassist to create specialized methods on-the-fly (like a just-in-time compiler). Instead of static Python generated code that is residing in the JAR file, we use a bytecode-generator that creates the packed int classes on the fly and loads them into the JVM using a private child classloader. This can do other code, too.

[asfimport]

Michael McCandless (@mikemccand) (migrated from JIRA)

OK, fair enough Uwe ... I've continued this effort at https://github.com/mikemccand/lucene-c-boost and wrote a blog post about it at http://blog.mikemccandless.com/2013/06/screaming-fast-lucene-searches-using-c.html