VM: Speed up output of UTF8 for 1-byte strings.

runtime/vm/unicode.cc

Index: runtime/vm/unicode.cc
diff --git a/runtime/vm/unicode.cc b/runtime/vm/unicode.cc
index f2715747a0d882bcae39fbcfd56d59e17ff20107..6027f91892f4c63a8a8fd81e1c8d084cf993abcd 100644
--- a/runtime/vm/unicode.cc
+++ b/runtime/vm/unicode.cc
@@ -112,7 +112,55 @@ intptr_t Utf8::Length(int32_t ch) {
 }
 
 
+// A constant mask that can be 'and'ed with a word of data to determine if it
+// is all ASCII (with no Latin1 characters).
+#if defined(ARCH_IS_64_BIT)
+static const uintptr_t kAsciiWordMask = DART_UINT64_C(0x8080808080808080);
+#else
+static const uintptr_t kAsciiWordMask = 0x80808080u;
+#endif
+
+
 intptr_t Utf8::Length(const String& str) {
+  NoSafepointScope no_safepoint;
+  if (str.IsOneByteString() || str.IsExternalOneByteString()) {
+    // For 1-byte strings, all code points < 0x80 have single-byte UTF-8
+    // encodings and all >= 0x80 have two-byte encodings.  To get the length,
+    // start with the number of code points and add the number of high bits in
+    // the bytes.
+    uintptr_t char_length = str.Length();
+    uintptr_t length = char_length;
+    const uintptr_t* data;
+    if (str.IsOneByteString()) {

[Vyacheslav Egorov (Google), 2017/07/03 15:49:05]

I think NoSafepointScope should go here, right before the if()

[erikcorry, 2017/09/25 15:21:52]

Done.

+      data =
+          reinterpret_cast<const uintptr_t*>(OneByteString::CharAddr(str, 0));

[Vyacheslav Egorov (Google), 2017/07/03 15:49:05]

maybe it's better to have a helper here

OneByteString::DataStart(str)

instead of passing 0?

[erikcorry, 2017/09/25 15:21:52]

Done.

+    } else {
+      data = reinterpret_cast<const uintptr_t*>(
+          ExternalOneByteString::CharAddr(str, 0));
+    }
+    uintptr_t i;
+    for (i = 0; i + sizeof(uintptr_t) < char_length; i += sizeof(uintptr_t)) {
+      uintptr_t chunk = *data++;
+      chunk &= kAsciiWordMask;
+#if defined(ARCH_IS_64_BIT)
+      chunk += chunk >> 32;

[Vyacheslav Egorov (Google), 2017/07/03 15:49:05]

any reason for this shift-add to be before comparison with 0 unlike all others?

[erikcorry, 2017/09/25 15:21:51]

Done.

+#endif
+      if (chunk != 0) {
+        // Shuffle the bits until we have a count of bits in the low nibble.
+        chunk += chunk >> 16;
+        chunk += chunk >> 8;
+        length += (chunk >> 7) & 0xf;
+      }
+    }
+    // Take care of the tail of the string, the last length % wordsize chars.
+    for (; i < char_length; i++) {
+      if (str.CharAt(i) > kMaxOneByteChar) length++;

[Vyacheslav Egorov (Google), 2017/07/03 15:49:05]

maybe *OneByteString::CharAddr(str, i) here to avoid virtual dispatch?

[erikcorry, 2017/09/25 15:21:51]

I think that would not work with external strings.

+    }
+    return length;
+  }
+
+  // Slow case for 2-byte strings that handles surrogate pairs and longer UTF-8
+  // encodings.
   intptr_t length = 0;
   String::CodePointIterator it(str);
   while (it.Next()) {
@@ -150,16 +198,61 @@ intptr_t Utf8::Encode(int32_t ch, char* dst) {
 
 
 intptr_t Utf8::Encode(const String& src, char* dst, intptr_t len) {
+  NoSafepointScope scope;
+  uintptr_t array_len = len;
   intptr_t pos = 0;
-  String::CodePointIterator it(src);
-  while (it.Next()) {
-    int32_t ch = it.Current();
-    intptr_t num_bytes = Utf8::Length(ch);
-    if (pos + num_bytes > len) {
-      break;
+  ASSERT(static_cast<intptr_t>(array_len) >= Length(src));
+  if (src.IsOneByteString() || src.IsExternalOneByteString()) {
+    // For 1-byte strings, all code points < 0x80 have single-byte UTF-8
+    // encodings and all >= 0x80 have two-byte encodings.
+    const uintptr_t* data;
+    if (src.IsOneByteString()) {

[Vyacheslav Egorov (Google), 2017/07/03 15:49:05]

I think NoSafepointScope should go here, right before the if()

[erikcorry, 2017/09/25 15:21:52]

Done.

+      data =
+          reinterpret_cast<const uintptr_t*>(OneByteString::CharAddr(src, 0));
+    } else {
+      data = reinterpret_cast<const uintptr_t*>(
+          ExternalOneByteString::CharAddr(src, 0));
+    }
+    uintptr_t char_length = Length(src);

[Vyacheslav Egorov (Google), 2017/07/03 15:49:05]

why is this called char_length? should not this be byte_length?

[erikcorry, 2017/07/03 19:40:56]

No, it's the character length.  Byte length can be more.  The passed buffer
length (argument 3) should be enough for the byte length, but we are defensive
if it is too small for the output.  In that case we stop writing before the end
of the string.

[erikcorry, 2017/07/03 20:12:15]

Ah, I'm calling the wrong Length() method.  The good news is it will get faster
when I fix this.  Also: Need better tests.

+    uintptr_t pos = 0;
+    ASSERT(kMaxOneByteChar + 1 == 0x80);
+    for (uintptr_t i = 0; i < char_length; i += sizeof(uintptr_t)) {

[Vyacheslav Egorov (Google), 2017/07/03 15:49:04]

I don't get how this works. char_length can be up to 2x bigger than actual
length of the input data[] (str.Length()). I think this loop can easily go out
of bounds and start reading garbage.

[erikcorry, 2017/07/03 19:40:56]

No, see above.

[erikcorry, 2017/09/25 15:21:51]

Now fixed, good catch.

+      // Read the input one word at a time and just write it verbatim if it is
+      // plain ASCII, as determined by the mask.
+      if (i + sizeof(uintptr_t) <= char_length &&
+          (*data & kAsciiWordMask) == 0 &&
+          pos + sizeof(uintptr_t) <= array_len) {
+        *reinterpret_cast<uintptr_t*>(dst + pos) = *data;

[Vyacheslav Egorov (Google), 2017/07/03 15:49:05]

I wonder if this should use StoreUnaligned()? Also the comment might need some
moving. 

(The comment is unaligned)

[erikcorry, 2017/09/25 15:21:52]

Done.

+        // This can be an unaligned write.
+        pos += sizeof(uintptr_t);
+      } else {
+        const uint8_t* p = reinterpret_cast<const uint8_t*>(data);

[Vyacheslav Egorov (Google), 2017/07/03 15:49:05]

this needs a comment that else branch processes up to 1 word at a time.

[erikcorry, 2017/09/25 15:21:52]

Done.

+        const uint8_t* limit = p + sizeof(uintptr_t);
+        for (uintptr_t j = i; j < char_length && p < limit; p++, j++) {

[Vyacheslav Egorov (Google), 2017/07/03 15:49:05]

can't this loop have a single condition? e.g. p < limit, where limit is computed
to be p + min(sizeof(uintptr_t), char_length - i)?

[erikcorry, 2017/09/25 15:21:51]

Done.

+          uint8_t c = *p;
+          // These calls to Length and Encode get inlined and the cases for 3
+          // and 4 byte sequences are removed.
+          intptr_t bytes = Length(c);
+          if (pos + bytes > array_len) {
+            return pos;
+          }
+          Encode(c, reinterpret_cast<char*>(dst) + pos);
+          pos += bytes;
+        }
+      }
+      data++;
+    }
+  } else {
+    String::CodePointIterator it(src);
+    while (it.Next()) {
+      int32_t ch = it.Current();
+      intptr_t num_bytes = Utf8::Length(ch);
+      if (pos + num_bytes > len) {
+        break;
+      }
+      Utf8::Encode(ch, &dst[pos]);
+      pos += num_bytes;
     }
-    Utf8::Encode(ch, &dst[pos]);
-    pos += num_bytes;
   }
   return pos;
 }