Speed up repeating the separator between elements in sparse array .join

src/runtime/runtime-strings.cc

 // Copyright 2014 the V8 project authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "src/runtime/runtime-utils.h"
 
 #include "src/arguments.h"
 #include "src/conversions-inl.h"
 #include "src/isolate-inl.h"
 #include "src/regexp/jsregexp-inl.h"
@@ skipping 539 matching lines @@
   DisallowHeapAllocation no_gc;
 
   uc16* sink = answer->GetChars();
 #ifdef DEBUG
   uc16* end = sink + length;
 #endif
 
   RUNTIME_ASSERT(fixed_array->get(0)->IsString());
   String* first = String::cast(fixed_array->get(0));
   String* separator_raw = *separator;
+
   int first_length = first->length();
   String::WriteToFlat(first, sink, 0, first_length);
   sink += first_length;
 
   for (int i = 1; i < array_length; i++) {
     DCHECK(sink + separator_length <= end);
     String::WriteToFlat(separator_raw, sink, 0, separator_length);
     sink += separator_length;
 
     RUNTIME_ASSERT(fixed_array->get(i)->IsString());
     String* element = String::cast(fixed_array->get(i));
     int element_length = element->length();
     DCHECK(sink + element_length <= end);
     String::WriteToFlat(element, sink, 0, element_length);
     sink += element_length;
   }
   DCHECK(sink == end);
 
   // Use %_FastOneByteArrayJoin instead.
   DCHECK(!answer->IsOneByteRepresentation());
   return *answer;
 }
 
+template <typename sinkchar>
+static void WriteRepeatToFlat(String* src, Vector<sinkchar> buffer, int cursor,
+                              int repeat, int length) {
+  if (repeat == 0) return;
+
+  sinkchar* start = &buffer[cursor];
+  String::WriteToFlat<sinkchar>(src, start, 0, length);
+
+  int done = 1;
+  sinkchar* next = start + length;
+
+  while (done < repeat) {
+    int block = Min(done, repeat - done);
+    int block_chars = block * length;
+    CopyChars(next, start, block_chars);
+    next += block_chars;
+    done += block;
+  }
+}
+
 template <typename Char>
 static void JoinSparseArrayWithSeparator(FixedArray* elements,
                                          int elements_length,
                                          uint32_t array_length,
                                          String* separator,
                                          Vector<Char> buffer) {
   DisallowHeapAllocation no_gc;
   int previous_separator_position = 0;
   int separator_length = separator->length();
+  DCHECK_LT(0, separator_length);
   int cursor = 0;
   for (int i = 0; i < elements_length; i += 2) {
     int position = NumberToInt32(elements->get(i));
     String* string = String::cast(elements->get(i + 1));
     int string_length = string->length();
     if (string->length() > 0) {
-      while (previous_separator_position < position) {
-        String::WriteToFlat<Char>(separator, &buffer[cursor], 0,
-                                  separator_length);
-        cursor += separator_length;
-        previous_separator_position++;
-      }
+      int repeat = position - previous_separator_position;
+      WriteRepeatToFlat<Char>(separator, buffer, cursor, repeat,
+                              separator_length);
+      cursor += repeat * separator_length;
+      previous_separator_position = position;
       String::WriteToFlat<Char>(string, &buffer[cursor], 0, string_length);
       cursor += string->length();
     }
   }
-  if (separator_length > 0) {
-    // Array length must be representable as a signed 32-bit number,
-    // otherwise the total string length would have been too large.
-    DCHECK(array_length <= 0x7fffffff);  // Is int32_t.
-    int last_array_index = static_cast<int>(array_length - 1);
-    while (previous_separator_position < last_array_index) {
-      String::WriteToFlat<Char>(separator, &buffer[cursor], 0,
-                                separator_length);
-      cursor += separator_length;
-      previous_separator_position++;
-    }
-  }
+
+  int last_array_index = static_cast<int>(array_length - 1);
+  // Array length must be representable as a signed 32-bit number,
+  // otherwise the total string length would have been too large.
+  DCHECK(array_length <= 0x7fffffff);  // Is int32_t.
+  int repeat = last_array_index - previous_separator_position;
+  WriteRepeatToFlat<Char>(separator, buffer, cursor, repeat, separator_length);
+  cursor += repeat * separator_length;
   DCHECK(cursor <= buffer.length());
 }
 
 
 RUNTIME_FUNCTION(Runtime_SparseJoinWithSeparator) {
   HandleScope scope(isolate);
   DCHECK(args.length() == 3);
   CONVERT_ARG_HANDLE_CHECKED(JSArray, elements_array, 0);
   CONVERT_NUMBER_CHECKED(uint32_t, array_length, Uint32, args[1]);
   CONVERT_ARG_HANDLE_CHECKED(String, separator, 2);
@@ skipping 672 matching lines @@
   SealHandleScope shs(isolate);
   DCHECK(args.length() == 2);
   if (!args[0]->IsString()) return isolate->heap()->undefined_value();
   if (!args[1]->IsNumber()) return isolate->heap()->undefined_value();
   if (std::isinf(args.number_at(1))) return isolate->heap()->nan_value();
   return __RT_impl_Runtime_StringCharCodeAtRT(args, isolate);
 }
 
 }  // namespace internal
 }  // namespace v8