Fast case conversion for ascii strings.

src/runtime.cc

 // Copyright 2006-2009 the V8 project authors. All rights reserved.
 // Redistribution and use in source and binary forms, with or without
 // modification, are permitted provided that the following conditions are
 // met:
 //
 //     * Redistributions of source code must retain the above copyright
 //       notice, this list of conditions and the following disclaimer.
 //     * Redistributions in binary form must reproduce the above
 //       copyright notice, this list of conditions and the following
 //       disclaimer in the documentation and/or other materials provided
@@ skipping 4066 matching lines @@
   } else {
     // If we didn't actually change anything in doing the conversion
     // we simple return the result and let the converted string
     // become garbage; there is no reason to keep two identical strings
     // alive.
     return s;
   }
 }
 
 
-template <class Converter>
-static Object* ConvertCase(Arguments args,
-                           unibrow::Mapping<Converter, 128>* mapping) {
+static inline SeqAsciiString* TryGetSeqAsciiString(String* s) {
+  if (!s->IsFlat() || !s->IsAsciiRepresentation()) return NULL;
+  if (s->IsConsString()) {
+    ASSERT(ConsString::cast(s)->second()->length() == 0);
+    return SeqAsciiString::cast(ConsString::cast(s)->first());
+  }
+  return SeqAsciiString::cast(s);
+}
+
+
+namespace {
+
+struct ToLowerTraits {
+  typedef unibrow::ToLowercase UnibrowConverter;
+
+  static bool ConvertAscii(char* dst, char* src, int length) {

[antonm, 2010/03/03 16:20:11]

just curious if this and below loops could be sped up with unfolding.

[Vitaly Repeshko, 2010/03/03 16:40:46]

Performance tuning is poisonous :)

GCC 4.2.4 with -O3 produces
  c0:   0f b6 54 29 0b          movzbl 0xb(%ecx,%ebp,1),%edx
  c5:   8d 42 bf                lea    -0x41(%edx),%eax
  c8:   3c 19                   cmp    $0x19,%al
  ca:   77 08                   ja     d4
  cc:   83 c2 20                add    $0x20,%edx
  cf:   c6 44 24 17 01          movb   $0x1,0x17(%esp)
  d4:   88 54 39 0b             mov    %dl,0xb(%ecx,%edi,1)
  d8:   83 c1 01                add    $0x1,%ecx
  db:   39 f1                   cmp    %esi,%ecx
  dd:   75 e1                   jne    c0
so, yeah, it can benefit from manual unrolling. My plan is to do a pass with
lower-level optimizations like this later.

+    bool changed = false;
+    for (int i = 0; i < length; ++i) {
+      char c = src[i];
+      if ('A' <= c && c <= 'Z') {
+        c += ('a' - 'A');
+        changed = true;
+      }
+      dst[i] = c;
+    }
+    return changed;
+  }
+};
+
+
+struct ToUpperTraits {
+  typedef unibrow::ToUppercase UnibrowConverter;
+
+  static bool ConvertAscii(char* dst, char* src, int length) {
+    bool changed = false;
+    for (int i = 0; i < length; ++i) {
+      char c = src[i];
+      if ('a' <= c && c <= 'z') {
+        c -= ('a' - 'A');
+        changed = true;
+      }
+      dst[i] = c;
+    }
+    return changed;
+  }
+};
+
+}  // namespace
+
+
+template <typename ConvertTraits>
+static Object* ConvertCase(
+    Arguments args,
+    unibrow::Mapping<typename ConvertTraits::UnibrowConverter, 128>* mapping) {
   NoHandleAllocation ha;
-
   CONVERT_CHECKED(String, s, args[0]);
   s->TryFlatten();
 
-  int input_string_length = s->length();
+  const int length = s->length();
   // Assume that the string is not empty; we need this assumption later
-  if (input_string_length == 0) return s;
-  int length = input_string_length;
+  if (length == 0) return s;
+
+  // Simpler handling of ascii strings.
+  //
+  // NOTE: This assumes that the upper/lower case of an ascii
+  // character is also ascii.  This is currently the case, but it
+  // might break in the future if we implement more context and locale
+  // dependent upper/lower conversions.
+  SeqAsciiString* seq_ascii = TryGetSeqAsciiString(s);
+  if (seq_ascii != NULL) {
+    Object* o = Heap::AllocateRawAsciiString(length);
+    if (o->IsFailure()) return o;
+    SeqAsciiString* result = SeqAsciiString::cast(o);
+    bool has_changed_character = ConvertTraits::ConvertAscii(
+        result->GetChars(), seq_ascii->GetChars(), length);
+    return has_changed_character ? result : s;
+  }
 
   Object* answer = ConvertCaseHelper(s, length, length, mapping);
   if (answer->IsSmi()) {
     // Retry with correct length.
     answer = ConvertCaseHelper(s, Smi::cast(answer)->value(), length, mapping);
   }
   return answer;  // This may be a failure.
 }
 
 
 static Object* Runtime_StringToLowerCase(Arguments args) {
-  return ConvertCase<unibrow::ToLowercase>(args, &to_lower_mapping);
+  return ConvertCase<ToLowerTraits>(args, &to_lower_mapping);
 }
 
 
 static Object* Runtime_StringToUpperCase(Arguments args) {
-  return ConvertCase<unibrow::ToUppercase>(args, &to_upper_mapping);
+  return ConvertCase<ToUpperTraits>(args, &to_upper_mapping);
 }
 
+
 static inline bool IsTrimWhiteSpace(unibrow::uchar c) {
   return unibrow::WhiteSpace::Is(c) || c == 0x200b;
 }
 
+
 static Object* Runtime_StringTrim(Arguments args) {
   NoHandleAllocation ha;
   ASSERT(args.length() == 3);
 
   CONVERT_CHECKED(String, s, args[0]);
   CONVERT_BOOLEAN_CHECKED(trimLeft, args[1]);
   CONVERT_BOOLEAN_CHECKED(trimRight, args[2]);
 
   s->TryFlatten();
   int length = s->length();
@@ skipping 4283 matching lines @@
   } else {
     // Handle last resort GC and make sure to allow future allocations
     // to grow the heap without causing GCs (if possible).
     Counters::gc_last_resort_from_js.Increment();
     Heap::CollectAllGarbage(false);
   }
 }
 
 
 } }  // namespace v8::internal