Optimize VM's String.== implementation

[mkustermann]

Currently the Dart VM's String equality implementation is based on assembly intrinsics which load & compare each single byte (see asm_intrinsifier_x64.cc):

 
  // Check contents, no fall-through possible.
  // TODO(srdjan): write a faster check.
  __ SmiUntag(RDI);
  __ Bind(&loop);
  __ decq(RDI);
  __ cmpq(RDI, Immediate(0));
  __ j(LESS, &is_true, Assembler::kNearJump);
  if (string_cid == kOneByteStringCid) {
    __ movzxb(RBX, FieldAddress(RAX, RDI, TIMES_1,
                                target::OneByteString::data_offset()));
    __ movzxb(RDX, FieldAddress(RCX, RDI, TIMES_1,
                                target::OneByteString::data_offset()));
  } else if (string_cid == kTwoByteStringCid) {
    __ movzxw(RBX, FieldAddress(RAX, RDI, TIMES_2,
                                target::TwoByteString::data_offset()));
    __ movzxw(RDX, FieldAddress(RCX, RDI, TIMES_2,
                                target::TwoByteString::data_offset()));
  } else {
    UNIMPLEMENTED();
  }
  __ cmpq(RBX, RDX);
  __ j(NOT_EQUAL, &is_false, Assembler::kNearJump);
  __ jmp(&loop, Assembler::kNearJump);

We should consider optimizing this to use word-based loads & compares followed by remainder byte based loads & compares.

We may also consider introducing a MemoryCompareInstr (similar to our existing MemoryCopyInstr).

/cc @aam Maybe interested in picking this up?

[mkustermann]

/cc @rakudrama this shows up in dart2js profile (it may indicate some strings would benefit from canonicalization - to more often hit the fast if (identical(this, other)) return true path)

[rakudrama]

A string fits in a number of words. What is stored in the bytes of the last word beyond the length (or two words with heap alignment)? If it is deterministic and consistent (e.g. zero-fill or part of the bit-pattern for null), the words can be compared for the last word too, leaving no per-character loop.

Increasingly esoteric optimizations:

If the length is stored immediately before the characters, the block comparison can start with the length word, since if the lengths are different, the block comparison will fail before accessing beyond the length of the shorter string. If the 'internal fragmentation' dead bytes are nondeterministic, it might still be better to do an unaligned load of the last characters rather than loop. In a short string, the word load at mem[string+characters_offset+length-8] might underflow the characters, but this would be ok provided the length is stored at the underflow. An alternative to per-character testing or unaligned load is to shift out the uninitialized bytes of the last word, the shift count being a function of the low bits of the byte-length. Maybe there is a SIMD idiom for this.

Strings also have a cached hash-code. If the hash-codes are different it may be because the strings are different, providing an early exit for long strings with a common prefix (e.g. Uri strings), or one of the hash-codes has not been computed. If two strings with different hash-codes are equal it means that one is computed and the other can have the hash-code set by copying from the string with the initialized hash-code.

@mkustermann If it is easy, can you add the call stack where you saw this in the dart2js profile?

[aam]

thanks @mkustermann , sounds good

[mkustermann]

@mkustermann If it is easy, can you add the call stack where you saw this in the dart2js profile?

From profile of dart2js's global analysis phase:

- 1.61%  DartWorker       [.] String.== (#4)                                                                                                                                                                                       ▒
   - 1.39% String.== (#4)                                                                                                                                                                                                             ▒
      - 0.91% PrivateName.matches                                                                                                                                                                                                     ▒
         - Selector.appliesUnnamed                                                                                                                                                                                                    ▒
            - 0.90% FunctionSetNode.query                                                                                                                                                                                             ▒
                 FunctionSet.query                                                                                                                                                                                                    ▒
                 FunctionSet.filter                                                                                                                                                                                                   ▒
                 JsClosedWorld.locateMembersInDomain                                                                                                                                                                                  ▒
               + JsClosedWorld.locateMembers                                                                                                                                                                                          ▒
      - 0.24% _Uri.port                                                                                                                                                                                                               ▒
         - _Uri.==                                                                                                                                                                                                                    ▒
            - 0.23% PrivateName.matches                                                                                                                                                                                               ▒
               - Selector.appliesUnnamed                                                                                                                                                                                              ▒
                  + 0.23% FunctionSetNode.query    

(Not sure why it shows _Uri.port - may be misattributed somwhow)