You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@lucene.apache.org by Marvin Humphrey <ma...@rectangular.com> on 2005/11/01 01:31:14 UTC

Re: bytecount as String and prefix length

I wrote...

> I think I'll take a crack at a custom charsToUTF8 converter algo.

Still no luck.  Still 20% slower than the current implementation.   
The algo is below, for reference.

It's entirely possible that my patches are doing something dumb  
that's causing this, given my limited experience with Java.  But if  
that's not the case, I can think of two other explanations.

One is that the passage of the text through an intermediate buffer  
before blasting it out is considerably more expensive than anticipated.

The other is that the pre-allocation of a char[] array based on the  
length VInt yields a significant benefit over the standard techniques  
for reading in UTF-8.  That wouldn't be hard to believe.  Without  
that number, there's a lot of guesswork involved.  English requires  
about 1.1 bytes per UTF-8 code point; Japanese, 3.  Multiple memory  
allocation ops may be required as bytes get read in, especially if  
the final String object kicked out HAS to use the bare minimum amount  
of memory.  I don't suppose there's any way for me to snoop just  
what's happening under the hood in these CharsetDecoder classes or  
String constructors, is there?

Scanning through a SegmentTermEnum with next() doesn't seem to be any  
slower with a byte-based TermBuffer, and my index-1000-wikipedia-docs  
benchmarker doesn't slow down that much when IndexInput is changed to  
use a String constructor that accepts UTF-8 bytes rather than chars.   
However, it's possible that the modified toTerm method of TermBuffer  
is a bottleneck, as it also uses the UTF-8 String constructor.  It  
doesn't get exercised under SegmentTermEnum.next(), but during  
merging of segments I believe it sees plenty of action -- maybe a lot  
more than IndexInput's readString.

So my next step is to write a utf8ToString method that's as efficient  
as I can make it.  After that... I dunno, I'm running out of ideas.

Marvin Humphrey
Rectangular Research
http://www.rectangular.com/


   public static final ByteBuffer stringToUTF8(
         String s, int start, int length, ByteBuffer byteBuf) {
     byteBuf.clear();
     int i = start;
     int j = 0;
     try {
       final int end = start + length;
       byte[] bytes = byteBuf.array();
       for ( ; i < end; i++) {
         final int code = (int)s.charAt(i);
         if (code < 0x80)
           bytes[j++] = (byte)code;
         else if (code < 0x800) {
           bytes[j++] = (byte)(0xC0 | (code >> 6));
           bytes[j++] = (byte)(0x80 | (code & 0x3F));
         } else if (code < 0xD800 || code > 0xDFFF) {
           bytes[j++] = (byte)(0xE0 | (code >>> 12));
           bytes[j++] = (byte)(0x80 | ((code >> 6) & 0x3F));
           bytes[j++] = (byte)(0x80 | (code & 0x3F));
         } else {
           // surrogate pair
           int utf32;
           // confirm valid high surrogate
           if (code < 0xDC00 && (i < end-1)) {
             utf32 = ((int)s.charAt(i+1));
             // confirm valid low surrogate and write pair
             if (utf32 >= 0xDC00 && utf32 <= 0xDFFF) {
               utf32 = ((code - 0xD7C0) << 10) + (utf32 & 0x3FF);
               i++;
               bytes[j++] = (byte)(0xF0 | (utf32 >>> 18));
               bytes[j++] = (byte)(0x80 | ((utf32 >> 12) & 0x3f));
               bytes[j++] = (byte)(0x80 | ((utf32 >> 6) & 0x3F));
               bytes[j++] = (byte)(0x80 | (utf32 & 0x3F));
               continue;
             }
           }
           // replace unpaired surrogate or out-of-order low surrogate
           // with substitution character
           bytes[j++] = (byte)0xEF;
           bytes[j++] = (byte)0xBF;
           bytes[j++] = (byte)0xBD;
         }
       }
     }
     catch (ArrayIndexOutOfBoundsException e) {
       // guess how many more bytes it will take, plus 10%
       float charsProcessed = (float)(i - start);
       float bytesPerChar = (j / charsProcessed) * 1.1f;

       float charsLeft = length - charsProcessed;
       float targetSize
         = (float)byteBuf.capacity() + bytesPerChar * charsLeft + 1.0f;

       return stringToUTF8(s, start, length, ByteBuffer.allocate((int) 
targetSize));
     }
     byteBuf.position(j);
     return byteBuf;
   }





---------------------------------------------------------------------
To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-dev-help@lucene.apache.org


Re: bytecount as String and prefix length

Posted by Doug Cutting <cu...@apache.org>.
Marvin Humphrey wrote:
> I think it's time to throw in the towel.

Please don't give up.  I think you're quite close.

I would be careful using CharBuffer instead of char[] unless you're sure 
all methods you call are very efficient.  You could try avoiding 
CharBuffer by adding something (ugly) like an int[]charLength parameter 
where the length is stored, then simply return the char[], in case you 
had to re-allocate.

Using an exception for control flow is not only considered bad style, 
but is also a performance pitfall.  A catch that is unused is free, but 
catching and throwing exceptions is expensive.

A complete diff would make it easier to see if there's something else 
which may be slowing things, e.g., inadvertantly allocating something 
for each call.  Also, someone else could try to tune it more.

Have you profiled this?  Sun's built-in profiler can be useful.  It can 
give you allocation counts, so you can see if you're allocating 
significantly more objects.  It also gives call counts (in the old 'java 
-prof' mode) which are useful.  It slows things so much that I find 
relative performance of methods to be nearly worthless, but call and 
allocation counts can point out problems.

Cheers,

Doug

---------------------------------------------------------------------
To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-dev-help@lucene.apache.org


Re: bytecount as String and prefix length

Posted by Marvin Humphrey <ma...@rectangular.com>.
On Nov 1, 2005, at 9:51 AM, Doug Cutting wrote:

> Another approach might be to, instead of converting to UTF-8 to  
> strings right away, change things to convert lazily, if at all.
> During index merging such conversion should never be needed.

!!

There ought to be some gains possible there, then.  No predictions as  
to how much, though.

> You needn't do this systematically throughout Lucene, but only  
> where it makes a big difference.  For example, if you could avoid  
> strings in SegmentMerger.mergeTermInfos() it might make a huge  
> difference.  This might be as simple as changing SegmentMergeInfo  
> to use a TermBuffer instead of a Term.  Does that make sense?

Abundant sense.  I'm not as familiar with SegmentMerger as I am with  
other parts of the org.apache.lucene.index package, because I haven't  
ported it yet.  But conceptually I understand exactly why this should  
require fewer resources.

I'll take a swing at SegmentMerger and submit a comprehensive diff.

Thanks for the suggestions,

Marvin Humphrey
Rectangular Research
http://www.rectangular.com/


---------------------------------------------------------------------
To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-dev-help@lucene.apache.org


Re: bytecount as String and prefix length

Posted by Doug Cutting <cu...@apache.org>.
Another approach might be to, instead of converting to UTF-8 to strings 
right away, change things to convert lazily, if at all.  During index 
merging such conversion should never be needed.  You needn't do this 
systematically throughout Lucene, but only where it makes a big 
difference.  For example, if you could avoid strings in 
SegmentMerger.mergeTermInfos() it might make a huge difference.  This 
might be as simple as changing SegmentMergeInfo to use a TermBuffer 
instead of a Term.  Does that make sense?

Doug

---------------------------------------------------------------------
To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-dev-help@lucene.apache.org


Re: bytecount as String and prefix length

Posted by Yonik Seeley <ys...@gmail.com>.
Thanks for looking into this Marvin... very interesting stuff!
I haven't had a chance to review it in detail, but my gut tells me
that it should be able to be faster.

-Yonik
Now hiring -- http://forms.cnet.com/slink?231706

---------------------------------------------------------------------
To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-dev-help@lucene.apache.org


Re: bytecount as String and prefix length

Posted by Marvin Humphrey <ma...@rectangular.com>.
I wrote:

> I've got one more idea... time to try overriding readString and  
> writeString in BufferedIndexInput and BufferedIndexOutput, to take  
> advantage of buffers that are already there.

Too complicated to be worthwhile, it turns out.  I think it's time to  
throw in the towel.  Frustrating, because I was shooting for a win- 
win solution (bytecounts and valid UTF-8 both make things a lot  
easier on the Perl side).  My valid-UTF-8 patches from a month ago  
perform better than the current Java implementation, but bytecounts  
make for slower indexing.  Time to re-rethink the goal of index- 
compatibility.  How about, compatible for ascii-only indexes?  :|

Marvin Humphrey
Rectangular Research
http://www.rectangular.com/


---------------------------------------------------------------------
To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-dev-help@lucene.apache.org


Re: bytecount as String and prefix length

Posted by Marvin Humphrey <ma...@rectangular.com>.
On Oct 31, 2005, at 5:15 PM, Robert Engels wrote:

> All of the JDK source is available via download from Sun.

Thanks.  I believe the UTF-8 coding algos can be found in...

j2se > src > share > classes > sun > nio > cs > UTF_8.java

It looks like the translator methods have fairly high loop overheads,  
since they have to keep track of the member variables of ByteBuffer  
and CharBuffer objects and prepare to return result objects on each  
loop iter.  Also, they have robust error-checking for malformed  
source data, which Lucene traditionally has not.  The algo below my  
sig should be faster.

I wrote...

> So my next step is to write a utf8ToString method that's as efficient
> as I can make it.

Ok, this time we made a little headway.  We're down from 20% slower  
to around 10% slower indexing than current implementation.  But I  
don't see how I'm going to get it any faster.  There's maybe one  
conditional in FieldsReader that can be simplified.

There's another downside to the way I'm implementing this right now.   
The byteBuf and charBuf have to be kept somewhere.  Currently, I'm  
allocating a ByteBuffer for each TermInfosWriter and a charBuf for  
each TermBuffer.  That's something of a memory hit, though it's hard  
to say exactly how much.  IndexInput and IndexOutput are still using  
the Sun methods -- when I gave them Buffers, they slowed down.

I've got one more idea... time to try overriding readString and  
writeString in BufferedIndexInput and BufferedIndexOutput, to take  
advantage of buffers that are already there.

Marvin Humphrey
Rectangular Research
http://www.rectangular.com/

//----------------------------------------------------------------

   public static final CharBuffer utf8ToChars (
         byte[] bytes, int start, int length, CharBuffer charBuf) {
     int i = start;
     int j = 0;
     final int end = start + length;
     char[] chars = charBuf.array();
     try {
       while (i < end) {
         byte b = bytes[i++];
         switch (TRAILING_BYTES_FOR_UTF8[b & 0xFF]) {
           case 0:
             chars[j++] = (char)(b & 0x7F);
             break;
           case 1:
             chars[j++] = (char)(((b & 0x1F) << 6)
               | (bytes[i++] & 0x3F));
             break;
           case 2:
             chars[j++] = (char)(((b & 0x0F) << 12)
               | ((bytes[i++] & 0x3F) << 6)
               |  (bytes[i++] & 0x3F));
             break;
           case 3:
             int utf32 = (((b & 0x0F) << 18)
               | ((bytes[i++] & 0x3F) << 12)
               | ((bytes[i++] & 0x3F) << 6)
               |  (bytes[i++] & 0x3F));
             chars[j++] = (char)((utf32 >> 10) + 0xD7C0);
             i++;
             chars[j++] = (char)((utf32 & 0x03FF) + 0xDC00);
             break;
         }
       }
     }
     catch (ArrayIndexOutOfBoundsException e) {
       float bytesProcessed = (float)(i - start);
       float bytesPerChar = (j / bytesProcessed) * 1.1f;

       float bytesLeft = length - bytesProcessed;
       float targetSize = (float)chars.length + bytesPerChar *  
bytesLeft + 1.0f;
       return utf8ToChars(bytes, start, length, CharBuffer.allocate 
((int)targetSize));
     }
     charBuf.position(j);
     return charBuf;
   }



---------------------------------------------------------------------
To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-dev-help@lucene.apache.org


RE: bytecount as String and prefix length

Posted by Robert Engels <re...@ix.netcom.com>.
All of the JDK source is available via download from Sun.

-----Original Message-----
From: Marvin Humphrey [mailto:marvin@rectangular.com]
Sent: Monday, October 31, 2005 6:31 PM
To: java-dev@lucene.apache.org
Subject: Re: bytecount as String and prefix length


I wrote...

> I think I'll take a crack at a custom charsToUTF8 converter algo.

Still no luck.  Still 20% slower than the current implementation.   
The algo is below, for reference.

It's entirely possible that my patches are doing something dumb  
that's causing this, given my limited experience with Java.  But if  
that's not the case, I can think of two other explanations.

One is that the passage of the text through an intermediate buffer  
before blasting it out is considerably more expensive than anticipated.

The other is that the pre-allocation of a char[] array based on the  
length VInt yields a significant benefit over the standard techniques  
for reading in UTF-8.  That wouldn't be hard to believe.  Without  
that number, there's a lot of guesswork involved.  English requires  
about 1.1 bytes per UTF-8 code point; Japanese, 3.  Multiple memory  
allocation ops may be required as bytes get read in, especially if  
the final String object kicked out HAS to use the bare minimum amount  
of memory.  I don't suppose there's any way for me to snoop just  
what's happening under the hood in these CharsetDecoder classes or  
String constructors, is there?

Scanning through a SegmentTermEnum with next() doesn't seem to be any  
slower with a byte-based TermBuffer, and my index-1000-wikipedia-docs  
benchmarker doesn't slow down that much when IndexInput is changed to  
use a String constructor that accepts UTF-8 bytes rather than chars.   
However, it's possible that the modified toTerm method of TermBuffer  
is a bottleneck, as it also uses the UTF-8 String constructor.  It  
doesn't get exercised under SegmentTermEnum.next(), but during  
merging of segments I believe it sees plenty of action -- maybe a lot  
more than IndexInput's readString.

So my next step is to write a utf8ToString method that's as efficient  
as I can make it.  After that... I dunno, I'm running out of ideas.

Marvin Humphrey
Rectangular Research
http://www.rectangular.com/


   public static final ByteBuffer stringToUTF8(
         String s, int start, int length, ByteBuffer byteBuf) {
     byteBuf.clear();
     int i = start;
     int j = 0;
     try {
       final int end = start + length;
       byte[] bytes = byteBuf.array();
       for ( ; i < end; i++) {
         final int code = (int)s.charAt(i);
         if (code < 0x80)
           bytes[j++] = (byte)code;
         else if (code < 0x800) {
           bytes[j++] = (byte)(0xC0 | (code >> 6));
           bytes[j++] = (byte)(0x80 | (code & 0x3F));
         } else if (code < 0xD800 || code > 0xDFFF) {
           bytes[j++] = (byte)(0xE0 | (code >>> 12));
           bytes[j++] = (byte)(0x80 | ((code >> 6) & 0x3F));
           bytes[j++] = (byte)(0x80 | (code & 0x3F));
         } else {
           // surrogate pair
           int utf32;
           // confirm valid high surrogate
           if (code < 0xDC00 && (i < end-1)) {
             utf32 = ((int)s.charAt(i+1));
             // confirm valid low surrogate and write pair
             if (utf32 >= 0xDC00 && utf32 <= 0xDFFF) {
               utf32 = ((code - 0xD7C0) << 10) + (utf32 & 0x3FF);
               i++;
               bytes[j++] = (byte)(0xF0 | (utf32 >>> 18));
               bytes[j++] = (byte)(0x80 | ((utf32 >> 12) & 0x3f));
               bytes[j++] = (byte)(0x80 | ((utf32 >> 6) & 0x3F));
               bytes[j++] = (byte)(0x80 | (utf32 & 0x3F));
               continue;
             }
           }
           // replace unpaired surrogate or out-of-order low surrogate
           // with substitution character
           bytes[j++] = (byte)0xEF;
           bytes[j++] = (byte)0xBF;
           bytes[j++] = (byte)0xBD;
         }
       }
     }
     catch (ArrayIndexOutOfBoundsException e) {
       // guess how many more bytes it will take, plus 10%
       float charsProcessed = (float)(i - start);
       float bytesPerChar = (j / charsProcessed) * 1.1f;

       float charsLeft = length - charsProcessed;
       float targetSize
         = (float)byteBuf.capacity() + bytesPerChar * charsLeft + 1.0f;

       return stringToUTF8(s, start, length, ByteBuffer.allocate((int) 
targetSize));
     }
     byteBuf.position(j);
     return byteBuf;
   }





---------------------------------------------------------------------
To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-dev-help@lucene.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: java-dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: java-dev-help@lucene.apache.org