Buffer.byteLength

[ronag]

Does simdutf + V8 fast calls do anything for Buffer.byteLength which currently can be a bottleneck for e.g. http servers which are writing string to the response object.

[ronag]

This greatly affects performance of e.g. ServerResponse.write(string)

[lemire]

So we have that Buffer.byteLength(string, 'utf8')---which is what Buffer.byteLength(string) defaults to---seeks to return the number of bytes that the string would use, if it were serialized as UTF-8.

• If the string is stored in UTF-16, then it is just simdutf::utf8_length_from_utf16.
• If the string is stored in some European ISO format, then this can be optimized to be very fast too.

This ends up calling String::Utf8Length in v8 (api.cc), credit to @anonrig for the analysis:

int String::Utf8Length(Isolate* v8_isolate) const {
  i::Handle<i::String> str = Utils::OpenHandle(this);
  str = i::String::Flatten(reinterpret_cast<i::Isolate*>(v8_isolate), str);
  int length = str->length();
  if (length == 0) return 0;
  i::DisallowGarbageCollection no_gc;
  i::String::FlatContent flat = str->GetFlatContent(no_gc);
  DCHECK(flat.IsFlat());
  int utf8_length = 0;
  if (flat.IsOneByte()) {
    for (uint8_t c : flat.ToOneByteVector()) {
      utf8_length += c >> 7;
    }
    utf8_length += length;
  } else {
    int last_character = unibrow::Utf16::kNoPreviousCharacter;
    for (uint16_t c : flat.ToUC16Vector()) {
      utf8_length += unibrow::Utf8::Length(c, last_character);
      last_character = c;
    }
  }
  return utf8_length;
}

Let us focus on...

 int last_character = unibrow::Utf16::kNoPreviousCharacter;
 for (uint16_t c : flat.ToUC16Vector()) {
      utf8_length += unibrow::Utf8::Length(c, last_character);
      last_character = c;
 }

The ToUC16Vector() call returns a view of the whole of the data into a vector... and then it goes through it, character by character, with a tiny state machine, to compute the size... I think GetFlatContent does not do further copies or allocations, and is just a safety routine.

So you should be able to replace...

 int last_character = unibrow::Utf16::kNoPreviousCharacter;
 for (uint16_t c : flat.ToUC16Vector()) {
      utf8_length += unibrow::Utf8::Length(c, last_character);
      last_character = c;
 }

with the accelerated version...

auto v = flat.ToUC16Vector();
utf8_length = simdutf::utf8_length_from_utf16(v.start(), v.length())

In a future release of simdutf, we could just do...

int String::Utf8Length(Isolate* v8_isolate) const {
  i::Handle<i::String> str = Utils::OpenHandle(this);
  str = i::String::Flatten(reinterpret_cast<i::Isolate*>(v8_isolate), str);
  int length = str->length();
  if (length == 0) return 0;
  i::DisallowGarbageCollection no_gc;
  i::String::FlatContent flat = str->GetFlatContent(no_gc);
  DCHECK(flat.IsFlat());
  int utf8_length = 0;
  if (flat.IsOneByte()) {
    auto v = flat.ToOneByteVector();
    return  simdutf::utf8_length_from_latin(v.start(), v.length());
  }
  auto v = flat.ToUC16Vector();
  return  simdutf::utf8_length_from_utf16(v.start(), v.length());
}

It looks easy enough but this code I am modifying is in v8, not in Node.

If you don't want to modify v8, and I trust that you do not, then you need to intercept all of the str->Utf8Length(args.GetIsolate()) calls...

You have some fun code in Node, like this...

    const int32_t length = str->Utf8Length(args.GetIsolate()) + 1;
    char* buf = new char[length];
    str->WriteUtf8(args.GetIsolate(), buf, length);
    delete[] buf;

Of course, simdutf can do the WriteUtf8 faster too!!! Again, it is the same story, this calls into v8... and if you don't want to modify v8... well...

The question is therefore entirely a software engineering question. We know how to write the code, the simdutf library is already in node. So how does one do it?

[TimothyGu]

Has anyone explored integrating simdutf (or some equivalent library) into V8?

Also, you can effectively emulate Utf8Length through the V8 API by using some combination of v8::String::IsOneByte, v8::String::Write, and v8::String::WriteOneByte. However, Write/WriteOneByte does an extra memcpy whereas i::String::FlatContent is just a view, so I suppose the question is whether the benefit from simdutf will outweigh the memcpy.

[ronag]

I think doing anything in v8 will be difficult.

[BridgeAR]

We had a very productive collaboration with the @nodejs/v8 team before. It is of course a bit different to code there but I would favor to first try that.

As such, let's discuss the possibility of integrating simdutf as everyone would profit by that and it makes it easier for users such as Node.js.

[ronag]

@BridgeAR Sure! Who can champion that?

[lemire]

so I suppose the question is whether the benefit from simdutf will outweigh the memcpy.

A memcpy is cheap, but if you need to do extra memory allocations just to scan the data, it is a non-starter.

[joyeecheung]

I think the problem is that flattening the strings (notice the String::Flatten() call before DisallowGarbageCollection in String::Utf8Length()) can and is very likely to incur heap allocation on the V8 side - a very common case is Buffer.byteLength('hello' + 'world', 'utf8') and in this case V8 needs to flatten the result of 'hello' + 'world', and that results in allocation of a new string. If the string is not flattened, then the C++ side just cannot read it. To get around the problem we could try to copy all the code points to an array buffer in JS and pass that into the fast call but I am not sure if that would already kill any performance gain.

[joyeecheung]

Another way to solve it could be to add a new V8 API that returns whether the string is already flatten, and the fast API call gives up if it gets a false. Then in JS land we can do use some heuristics (like indexing into the strings) to flatten it before invoking the fast call. If that heuristics fails, we'd still go back to the slow branch.

[lemire]

If the string is not flattened

Right. So the function above, already in v8, Utf8Length, can cause a call to SlowGetFlatContent. But that can be remedied by writing the code differently in JavaScript land. If you can accelerate the flat case, then you can later explain to your users how to benefit. It will always be the case that you can write your JavaScript to get suboptimal performance... the engine can only do so much for you.

To get around the problem we could try to copy all the code points to an array

Isn't it what SlowGetFlatContent does already (conceptually)?

[ronag]

Maybe stupid question... but why flatten it at all? Why not just walk the string rope and get the size of each part?

[joyeecheung]

Sorry, I should've been clearer, #52 (comment) was about using V8 fast API calls for the method, not about switching from Utf8Length to simdutf (and that's why heap allocation matter).

[joyeecheung]

Maybe stupid question... but why flatten it at all? Why not just walk the string rope and get the size of each part?

This is more of an V8 question, and my guess is when someone calls Utf8Length() it's very likely that they are going to actually read the content of that string later (which means V8 would need to flatten them to write into a contiguous block of memory anyway), so might as well just flatten it now. Also concatenated strings aren't the only case where the string needs flattening (for now there are also repeated strings and sliced strings that would strictly need some processing to turn into a flat string, but it's not certain that the list would not grow in the future) EDIT: not true, only cons strings strictly need flattening now, though that might still change in the future.

[joyeecheung]

And regarding replacing unibrow with simdutf, there is also a (pretty old) plan to switch unibrow to ICU altogether: https://bugs.chromium.org/p/v8/issues/detail?id=5500

For non-Chromium embedders like Node.js though the easier upstream request might be to just extend the String API a bit so that whatever used to calculate the size of the result or do the actual conversion is a parameter to a new API that we can customize. So for example, this is more likely to be accepted:

enum class ContentType {
  kLatin1,
  kUTF16LE,
};
using ByteLengthCalculator = int (*)(ContentType, const void* start, size_t size);

int String::Utf8Length(Isolate* v8_isolate, ByteLengthCalculator calculator) const {
  i::Handle<i::String> str = Utils::OpenHandle(this);
  str = i::String::Flatten(reinterpret_cast<i::Isolate*>(v8_isolate), str);
  int length = str->length();
  if (length == 0) return 0;
  i::DisallowGarbageCollection no_gc;
  i::String::FlatContent flat = str->GetFlatContent(no_gc);
  DCHECK(flat.IsFlat());
  int utf8_length = 0;
  if (flat.IsOneByte()) {
    auto one_byte_vector = flat.ToOneByteVector();
    return calculator(ContentType::kLatin1,
                      one_byte_vector.begin(), one_byte_vector.size());
  }
  auto two_byte_vector = flat.ToUC16Vector();
  return calculator(ContentType::kUTF16LE,
                    two_byte_vector.begin(), two_byte_vector.size());
}

String::WriteUtf8 can be done in a similar fasion. That avoids the problem of changing a dependency of V8, which can be more difficult (convincing V8 to add a new dependency that is only going to be used in a handful of embedder APIs is going to be a tough sell, while updating all the unibrow usage in V8 internals would also need more buy-in).