utf8 PR

[leerho]

@leventov

I made some style and cosmetic changes to your PR which I pulled into the utf8 branch here.
I had to add finals, make some methods static that could have been, etc. tools/SketchesCheckstyle should have caught those.

Question 1: You did not create a parallel get/put utf8 for buffer. Why?

Question 2: Have you done any testing that shows that adding this utf8 capability into Memory improves performance over what could have been done external to Memory?

[leerho]

@leventov

Also, if we were to add this to Buffer, we would need to put the DecodeUtil class in Util as package private.

BTW: This is beautiful work!

[leventov]

1. Because I don't need it yet.

I want to rewrite Druid's GenericIndexed and ObjectStrategy interface to use Memory instead of ByteBuffers. Currently I think the interface should look like this:

interface ObjectStrategy<ObjectType, ReusableStateType>
{
  ...
  ReusableStateType makeReusableState();
  ObjectType read(Memory mem, long offset, int numBytes, ReusableStateType reusableState);
  ObjectType readNewObject(
      Memory mem,
      long offset,
      int numBytes,
      ReusableStateType reusableState
  );
}

And STRING_STRATEGY could look like this:

class StringStrategy implements ObjectStrategy<String, StringBuilder>
{
  ...
  StringBuilder makeReusableState() { return new StringBuilder(); }
  String read(Memory mem, long offset, int numBytes, StringBuilder reusableStringBuilder)
  {
    reusableStringBuilder.setLength(0);
    mem.getUtf8(offset, reusableStringBuilder, numBytes);
    return reusableStringBuilder.toString();
  }
}

It's not Region-based, because Regions are mutable, so we couldn't pass the same Region when deserializing all objects. On the other hand, we don't want to create a new Region for each new object deserialized.

2. I didn't compare. I wouldn't be surprised if JDK's UTF-8 encoding/decoding is faster than this, because it's heavily optimized, probably even intrinsified. But the primary goal is to avoid creating garbage. The new interface of ObjectStrategy, which has getUtf8/putUtf8, allows to generate absolute minimum garbage possible, as long as Druid's code centers around Strings. And could be made garbage-free, if Druid uses CharSequences instead of Strings.

And for complex object columns, it would allow garbage free ser/de already, that I need for apache/druid#4622. See also apache/druid#5172

FYI @cheddar @gianm

[leventov]

P. S. it's not my work, I just copied some code from https://github.com/google/protobuf repo.

[leventov]

@leerho FYI I pushed another small commit to this branch: ca731bf

[leerho]

@leventov

The method region() is immutable, writableRegion() is mutable.

Nonetheless, I get your point about not wanting to create another object.

I would like to do some characterization tests just to see how severe a hit we do get with this compared to native java, which I think would require an extra copy that would only be in Eden.

I think we may be OK, but I want to check with some folks to make sure we don't have a licensing issue.

[leventov]

Licensing issue with protobuf, you mean? There shouldn't be, because protobuf code is BSD-licensed, that is compatible with Apache.

[leerho]

@leventov

Yes, although it doesn't specifically name the license, I did confirm that it is exactly the "3 clause, BSD License 2.0".

BTW you might be interested in this thread.
It is a little old now, but it discusses several performance factors such as typical string length and whether the strings are typically mostly ASCII. These factors appear to affect whether the simpler String.getBytes() performs better or the direct encoding/decoding in protobuf performs better.

Most of the Java String.getBytes() implementation issues they mention are still in the Java 8 code (e.g., the 4x oversize allocation of the byte[] on encode).

I also had the thought (like David Dabbs) of directly accessing the String value array via reflection for read-only. It would reduce a copy for encode. Kenton Varda does not like the idea, but we are already down that path with ByteBuffer and Unsafe. Protobuf already uses Unsafe, so not sure Kenton's objection is still valid.

I would suggest we implement some temporary methods getUtf8Alt() and putUtf8Alt() which would use the much simpler String.getBytes() and String constructors and then run it on some actual Druid data and measure the encode / decode times and GC times; then run the same tests with the methods you have proposed. Is this something you could do?

[leventov]

I don't see the point of doing this. There are already methods to get and put byte array from/to Memory, it could be the intermediate step for JDK-based encoding, if somebody wants to do this. There is no need for implementing special methods in the Memory library.

Methods that I added are garbage-free, this is the reason for their existence. If somebody values speed above producing more garbage, he could use JDK as described above. BTW there is no guarantee that JDK is faster, we just assumed that. But is doesn't matter.

[leventov]

@leerho what is the point of disagreement here?

[leerho]

Not a major disagreement, but we are missing two things:

Because this Library is used for applications beyond what you and I might envision, we need to be as clear as possible to users why we are adding these Utf8 methods into the library and when these methods should be used.

• So far, there has been little discussion in the Javadocs that would give users guidance as to when they would choose these methods versus the String methods and what users should expect in terms of performance (both local throughput as well as GC performance). (I have added some comments, put they are still pretty vague)

• We have no characterization data to back up whatever we say in our verbal guidance. So I have built a characterization suite (now moved to the characterization repository) whereby we can publicly share the characterization tests that we use to measure accuracy and performance of all of our sketches. This will enable users to duplicate our tests if they should choose to do that.
  Characterizing performance of the Memory package is an important part of that.

Part of the delay has been my working on getting this characterization framework put together to run our characterization tests (some of which can run for many hours!). Now that that is pretty much done, I have started working on designing some characterization tests for the Udf8 encode speed and decode speed and compare that with the String methods. I also want to instrument it so we can demonstrate differences in GC performance as well.

Once we have adequate user guidance and the data to back it up. I will feel comfortable to merge.

[leventov]

Thanks for this work.

Actually there is a way to achieve low garbage rate with JDK as well - but it requires to first copy bytes from Memory to ByteBuffer, then invoke some CharsetDecoder with cached CharBuffer, and then create String from the CharBuffer. But since this path is not as optimized as new String(byte[], "UTF-8"), I expect that specialized reading method in memory should be faster.

[leerho]

@leventov

The first data is in, and it is quite a surprise!

These plots are normalized as nanoseconds per CodePoint. The X-axis is # of CP per Trial. The number of trials at each plot point is 2^16 (LgT=16), and there are 4 plot Points-Per-Octave (PPO).

The CP are randomly selected from the entire valid CP range, thus nearly all of the CP will be from the supplementary planes (planes 1 to 16), not the BMP and require two surrogate characters in the String form and 2 or 3 bytes in UTF8. I might try another test just using CP from the BMP as the encoding and decoding should be faster.

Nonetheless, I was really surprised to see the Memory Encoding to be faster than the Java Encoding, by 25%! The Memory Decoding is slower than the Java Decoding, but only by about 15%. Not bad!!

The next test will be to measure GC. I did have to insert System.gc() prior to each Trial Set to eliminate GC spikes in 3 of the plots (JavaEnc, JavaDec, and MemDec). The MemEnc did not have GC spikes!

This means that there still is some GC activity in the MemDec test, but this may be something I am doing in the test instead of the MemDec function itself.

All this code will be checked in shortly. Please take a look and run it if you are curious.

[leerho]

@leventov

To run this test: Run com.yahoo.sketches.characterization.Job and provide it a single string argument of "src/main/resources/memory/HeapUtf8SpeedJob.txt". The dependencies are sketches-core-0.10.3.jar, testng (which requires commander), and the current memory Utf8 branch.

[leerho]

@leventov

The current test setup is not free of garbage generation during the trial iterations and I could make it a lot cleaner. I cannot conclude that the MemDec test is garbage free, it may have been a coincidence.

[leerho]

@leventov

I want to discuss a different topic and that is the design of the method APIs:

GET:
void getUtf8(long offsetBytes, Appendable dst, int utf8Length)

• The problem I am having with the method name is that it is not analogous with getLongArray(). One is not getting Utf8 as a result. We could name it getCharArrayFromUtf8() or getCharsFromUtf8() or decodeUtf8Bytes().
• How do we expect the user to know what the utf8Length is? Suppose the Memory has a set of strings stored in Utf8. How does one know the length of each group of bytes? If the internal structure of the Memory was {int, byte[], int, byte[], ...} then it would be possible. This, in effect, would make a specialized positional interface, which might make more sense as part of Buffer.
• I am also thinking about providing more flexibility similar to getPrimitiveArray() where we allow specification of a destination offset and length. But the relationship between Utf8 bytes and chars is complex. Not sure how this would be used for characters outside the BMP.

PUT
long putUtf8(long offsetBytes, CharSequence src)

• I have similar suggestion about the putUtf8() method name: long putCharsToUtf8(), etc.
• The way this method is specified it assumes that the entire CharSequence is to be encoded. Would additional parameters to allow an offset and length makes sense? The complications of planes outside the BMP remaining.

Please give me a code snippets of how you would use these in practice, especially in the case where you are storing multiple strings in a single Memory.