Michael loves building software; he's been building search engines for more than a decade, and has been working on Lucene as a committer, PMC member and Apache member, for the past few years. He's co-author of the recently published Lucene in Action, 2nd edition. In his spare time Michael enjoys building his own computers, writing software to control his house (mostly in Python), encoding videos and tinkering with all sorts of other things. Michael is a DZone MVB and is not an employee of DZone and has posted 47 posts at DZone. You can read more from them at their website. View Full User Profile

Moving readVInt to C

06.29.2011
| 7419 views |
  • submit to reddit
By far the hottest spot in Lucene during searching is the method (DataInput.readVInt) that decodes Lucene's variable-length integer representation (vInt). This method is called an insane number of times, while iterating the postings lists (docs, freqs, positions), during query execution.

This representation is not CPU friendly: for every single byte read, the CPU hits a hard-to-predict if statement (testing the high bit). Alternative block-based formats do a good job reducing branches while decoding, such as these encodings (PFOR-DELTA is currently an experimental codec attached as a patch on LUCENE-1410) or Google's Group Varint.

Anyway, I decided to test whether porting readVInt to C would gives us a performance boost. I had known the overhead of JNI was highish in the past, but I was hoping in modern JREs this had been improved.

Unfortunately, it wasn't: I see a ~10%-~40% slowdown, depending on the query. Likely hotspot's inability to inline native methods is also a factor here. Perhaps, if/when we switch to a block-based codec, we'll see a gain with a native implementation, since the amortized overhead of invoking JNI will be lower.
References
Published at DZone with permission of Michael Mccandless, author and DZone MVB. (source)

(Note: Opinions expressed in this article and its replies are the opinions of their respective authors and not those of DZone, Inc.)

Comments

Clemens Eisserer replied on Thu, 2011/06/30 - 4:48am

For flow-intensive code going to C is almost never a win compared to hotspot-server. Only when using native libraries (like the parallel computation libs from AMD/Intel) orSIMD can be used, gains are woth the trouble.

 Some time ago I ported a PC1 stream cipher from Java to C, and hotspot-server was exectly as fast as gcc -O3 -march=native, Intel's C compiler wasn't faster either.

 - Clemens

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.