[v8-dev] Make TemplateLiteral hashing algorithm more memory efficient (issue 765473006 by [email protected])

Wed, 26 Nov 2014 16:31:31 -0800 

Reviewers: Dmitry Lomov (chromium), arv, rossberg,

Message:
PTAL --- as suggested in crrev.com/745233002, it changes the hashing strategy to 
build rolling hashes from each string component.
Tests pass on debug, so I think this should be a pretty trivial refactoring (but 
it does mean adding 2 static helpers to StringHasher).

Description:
Make TemplateLiteral hashing algorithm more memory efficient
Previously, a separate string to be hashed (in order to help determine the need 
to
use a cached Template Call Site) was built up by joining UTF8 spans within a
template.
Now, the hash key is generated from the original strings, removing the allocate 
a new
buffer and copy strings into it.

BUG=

Please review this at https://codereview.chromium.org/765473006/

Base URL: https://chromium.googlesource.com/v8/v8.git@master

Affected files (+33, -17 lines):
  M src/objects.h
  M src/objects-inl.h
  M src/parser.cc


Index: src/objects-inl.h
diff --git a/src/objects-inl.h b/src/objects-inl.h
index 03aea64736d818f456c748f76a31d583593dc664..fa6d3beb254c2ba15b5d94ba6709ff71970c27a7 100644 
--- a/src/objects-inl.h
+++ b/src/objects-inl.h
@@ -6722,6 +6722,28 @@ uint32_t StringHasher::GetHashCore(uint32_t running_hash) { 
 }


+uint32_t StringHasher::ComputeRunningHash(uint32_t running_hash,
+                                          const uc16* chars, int length) {
+  DCHECK(chars && length > 0);
+  for (int i = 0; i < length; ++i) {
+    running_hash = AddCharacterCore(running_hash, *chars++);
+  }
+  return running_hash;
+}
+
+
+uint32_t StringHasher::ComputeRunningHashOneByte(uint32_t running_hash,
+                                                 const char* chars,
+                                                 int length) {
+  DCHECK(chars && length > 0);
+  for (int i = 0; i < length; ++i) {
+    uint16_t c = static_cast<uint16_t>(*chars++);
+    running_hash = AddCharacterCore(running_hash, c);
+  }
+  return running_hash;
+}
+
+
 void StringHasher::AddCharacter(uint16_t c) {
   // Use the Jenkins one-at-a-time hash function to update the hash
   // for the given character.
Index: src/objects.h
diff --git a/src/objects.h b/src/objects.h
index 746f88d1c4c0c10083e63263a005f79ec4378b9d..eaea38623fbc5fe58ee6cf9c4dbb08baa3fa834c 100644 
--- a/src/objects.h
+++ b/src/objects.h
@@ -8489,6 +8489,11 @@ class StringHasher {
   // Reusable parts of the hashing algorithm.
INLINE(static uint32_t AddCharacterCore(uint32_t running_hash, uint16_t c)); 
   INLINE(static uint32_t GetHashCore(uint32_t running_hash));
+  INLINE(static uint32_t ComputeRunningHash(uint32_t running_hash,
+ const uc16* chars, int length)); 
+  INLINE(static uint32_t ComputeRunningHashOneByte(uint32_t running_hash,
+                                                   const char* chars,
+                                                   int length));

  protected:
   // Returns the value to store in the hash field of a string with
Index: src/parser.cc
diff --git a/src/parser.cc b/src/parser.cc
index c2d6c5754849a1601b23569e6b1aef8f562a255b..819e5481a9c4de09a9d8d62f78478a1c3fee18c0 100644 
--- a/src/parser.cc
+++ b/src/parser.cc
@@ -5295,14 +5295,7 @@ ZoneList<Expression*>* Parser::TemplateRawStrings(const TemplateLiteral* lit, 

   raw_strings = new (zone()) ZoneList<Expression*>(total, zone());

-  int num_hash_chars = (total - 1) * 3;
-  for (int index = 0; index < total; ++index) {
-    // Allow about length * 4 to handle most UTF8 sequences.
-    num_hash_chars += lengths->at(index) * 4;
-  }
-
-  Vector<uint8_t> hash_string = Vector<uint8_t>::New(num_hash_chars);
-  num_hash_chars = 0;
+  uint32_t running_hash = 0;

   for (int index = 0; index < total; ++index) {
     int span_start = cooked_strings->at(index)->position() + 1;
@@ -5311,9 +5304,8 @@ ZoneList<Expression*>* Parser::TemplateRawStrings(const TemplateLiteral* lit, 
     int to_index = 0;

     if (index) {
-      hash_string[num_hash_chars++] = '$';
-      hash_string[num_hash_chars++] = '{';
-      hash_string[num_hash_chars++] = '}';
+      running_hash = StringHasher::ComputeRunningHashOneByte(
+          running_hash, "${}", 3);
     }

     SmartArrayPointer<char> raw_chars =
@@ -5330,7 +5322,6 @@ ZoneList<Expression*>* Parser::TemplateRawStrings(const TemplateLiteral* lit, 
           ++from_index;
         }
       }
-      hash_string[num_hash_chars++] = ch;
       raw_chars[to_index++] = ch;
     }
@@ -5342,6 +5333,8 @@ ZoneList<Expression*>* Parser::TemplateRawStrings(const TemplateLiteral* lit, 
     if (utf16_length > 0) {
       uc16* utf16_buffer = zone()->NewArray<uc16>(utf16_length);
       to_index = decoder->WriteUtf16(utf16_buffer, utf16_length);
+      running_hash = StringHasher::ComputeRunningHash(
+          running_hash, utf16_buffer, to_index);
const uint16_t* data = reinterpret_cast<const uint16_t*>(utf16_buffer); 
       const AstRawString* raw_str = ast_value_factory()->GetTwoByteString(
           Vector<const uint16_t>(data, to_index));
@@ -5354,11 +5347,7 @@ ZoneList<Expression*>* Parser::TemplateRawStrings(const TemplateLiteral* lit, 
     raw_strings->Add(raw_lit, zone());
   }

-  hash_string.Truncate(num_hash_chars);
-  int utf16_length;
- *hash = StringHasher::ComputeUtf8Hash(Vector<const char>::cast(hash_string), 
-      num_hash_chars, &utf16_length);
-  hash_string.Dispose();
+  *hash = running_hash;

   return raw_strings;
 }


--
--
v8-dev mailing list
[email protected]
http://groups.google.com/group/v8-dev
--- You received this message because you are subscribed to the Google Groups "v8-dev" group. 
To unsubscribe from this group and stop receiving emails from it, send an email 
to [email protected].
For more options, visit https://groups.google.com/d/optout.

Reply via email to