Revision: 12598
Author: [email protected]
Date: Mon Sep 24 07:23:46 2012
Log: Fast path for symbol lookup in JSON.parse.
[email protected]
BUG=
Review URL: https://chromiumcodereview.appspot.com/10969069
http://code.google.com/p/v8/source/detail?r=12598
Modified:
/branches/bleeding_edge/src/json-parser.h
/branches/bleeding_edge/src/objects-inl.h
/branches/bleeding_edge/src/objects.cc
/branches/bleeding_edge/src/objects.h
=======================================
--- /branches/bleeding_edge/src/json-parser.h Fri Aug 17 02:03:08 2012
+++ /branches/bleeding_edge/src/json-parser.h Mon Sep 24 07:23:46 2012
@@ -71,11 +71,11 @@
inline void AdvanceSkipWhitespace() {
do {
Advance();
- } while (c0_ == '\t' || c0_ == '\r' || c0_ == '\n' || c0_ == ' ');
+ } while (c0_ == ' ' || c0_ == '\t' || c0_ == '\n' || c0_ == '\r');
}
inline void SkipWhitespace() {
- while (c0_ == '\t' || c0_ == '\r' || c0_ == '\n' || c0_ == ' ') {
+ while (c0_ == ' ' || c0_ == '\t' || c0_ == '\n' || c0_ == '\r') {
Advance();
}
}
@@ -563,6 +563,52 @@
AdvanceSkipWhitespace();
return Handle<String>(isolate()->heap()->empty_string());
}
+
+ if (seq_ascii && is_symbol) {
+ // Fast path for existing symbols. If the the string being parsed is
not
+ // a known symbol, contains backslashes or unexpectedly reaches the
end of
+ // string, return with an empty handle.
+ uint32_t running_hash = isolate()->heap()->HashSeed();
+ int position = position_;
+ uc32 c0 = c0_;
+ do {
+ if (c0 == '\\') {
+ return SlowScanJsonString<SeqAsciiString, char>(source_,
+ position_,
+ position);
+ }
+ running_hash = StringHasher::AddCharacterCore(running_hash, c0);
+ position++;
+ if (position > source_length_) return Handle<String>::null();
+ c0 = seq_source_->SeqAsciiStringGet(position);
+ } while (c0 != '"');
+ int length = position - position_;
+ uint32_t hash = (length <= String::kMaxHashCalcLength)
+ ? StringHasher::GetHashCore(running_hash) : length;
+ Vector<const char> string_vector(
+ seq_source_->GetChars() + position_, length);
+ SymbolTable* symbol_table = isolate()->heap()->symbol_table();
+ uint32_t capacity = symbol_table->Capacity();
+ uint32_t index = SymbolTable::FirstProbe(hash, capacity);
+ uint32_t count = 1;
+ while (true) {
+ Object* element = symbol_table->KeyAt(index);
+ if (element == isolate()->heap()->raw_unchecked_undefined_value()) {
+ // Lookup failure.
+ break;
+ }
+ if (element != isolate()->heap()->raw_unchecked_the_hole_value() &&
+ String::cast(element)->IsAsciiEqualTo(string_vector)) {
+ // Lookup success, update the current position.
+ position_ = position;
+ // Advance past the last '"'.
+ AdvanceSkipWhitespace();
+ return Handle<String>(String::cast(element));
+ }
+ index = SymbolTable::NextProbe(hash, count++, capacity);
+ }
+ }
+
int beg_pos = position_;
// Fast case for ASCII only without escape characters.
do {
=======================================
--- /branches/bleeding_edge/src/objects-inl.h Wed Sep 19 02:54:10 2012
+++ /branches/bleeding_edge/src/objects-inl.h Mon Sep 24 07:23:46 2012
@@ -4949,8 +4949,7 @@
raw_running_hash_(seed),
array_index_(0),
is_array_index_(0 < length_ && length_ <= String::kMaxArrayIndexSize),
- is_first_char_(true),
- is_valid_(true) {
+ is_first_char_(true) {
ASSERT(FLAG_randomize_hashes || raw_running_hash_ == 0);
}
@@ -4958,6 +4957,25 @@
bool StringHasher::has_trivial_hash() {
return length_ > String::kMaxHashCalcLength;
}
+
+
+uint32_t StringHasher::AddCharacterCore(uint32_t running_hash, uint32_t c)
{
+ running_hash += c;
+ running_hash += (running_hash << 10);
+ running_hash ^= (running_hash >> 6);
+ return running_hash;
+}
+
+
+uint32_t StringHasher::GetHashCore(uint32_t running_hash) {
+ running_hash += (running_hash << 3);
+ running_hash ^= (running_hash >> 11);
+ running_hash += (running_hash << 15);
+ if ((running_hash & String::kHashBitMask) == 0) {
+ return 27;
+ }
+ return running_hash;
+}
void StringHasher::AddCharacter(uint32_t c) {
@@ -4967,9 +4985,7 @@
}
// Use the Jenkins one-at-a-time hash function to update the hash
// for the given character.
- raw_running_hash_ += c;
- raw_running_hash_ += (raw_running_hash_ << 10);
- raw_running_hash_ ^= (raw_running_hash_ >> 6);
+ raw_running_hash_ = AddCharacterCore(raw_running_hash_, c);
// Incremental array index computation.
if (is_array_index_) {
if (c < '0' || c > '9') {
@@ -4999,23 +5015,14 @@
AddSurrogatePairNoIndex(c); // Not inlined.
return;
}
- raw_running_hash_ += c;
- raw_running_hash_ += (raw_running_hash_ << 10);
- raw_running_hash_ ^= (raw_running_hash_ >> 6);
+ raw_running_hash_ = AddCharacterCore(raw_running_hash_, c);
}
uint32_t StringHasher::GetHash() {
// Get the calculated raw hash value and do some more bit ops to
distribute
// the hash further. Ensure that we never return zero as the hash value.
- uint32_t result = raw_running_hash_;
- result += (result << 3);
- result ^= (result >> 11);
- result += (result << 15);
- if ((result & String::kHashBitMask) == 0) {
- result = 27;
- }
- return result;
+ return GetHashCore(raw_running_hash_);
}
=======================================
--- /branches/bleeding_edge/src/objects.cc Wed Sep 19 04:09:07 2012
+++ /branches/bleeding_edge/src/objects.cc Mon Sep 24 07:23:46 2012
@@ -7385,7 +7385,6 @@
uint32_t StringHasher::GetHashField() {
- ASSERT(is_valid());
if (length_ <= String::kMaxHashCalcLength) {
if (is_array_index()) {
return MakeArrayIndexHash(array_index(), length_);
=======================================
--- /branches/bleeding_edge/src/objects.h Thu Sep 20 08:18:00 2012
+++ /branches/bleeding_edge/src/objects.h Mon Sep 24 07:23:46 2012
@@ -2913,11 +2913,12 @@
return (hash + GetProbeOffset(number)) & (size - 1);
}
- static uint32_t FirstProbe(uint32_t hash, uint32_t size) {
+ inline static uint32_t FirstProbe(uint32_t hash, uint32_t size) {
return hash & (size - 1);
}
- static uint32_t NextProbe(uint32_t last, uint32_t number, uint32_t size)
{
+ inline static uint32_t NextProbe(
+ uint32_t last, uint32_t number, uint32_t size) {
return (last + number) & (size - 1);
}
@@ -3004,6 +3005,8 @@
private:
MUST_USE_RESULT MaybeObject* LookupKey(HashTableKey* key, Object** s);
+ template <bool seq_ascii> friend class JsonParser;
+
DISALLOW_IMPLICIT_CONSTRUCTORS(SymbolTable);
};
@@ -7053,10 +7056,6 @@
// Returns true if the characters seen so far make up a legal array
// index.
bool is_array_index() { return is_array_index_; }
-
- bool is_valid() { return is_valid_; }
-
- void invalidate() { is_valid_ = false; }
// Calculated hash value for a string consisting of 1 to
// String::kMaxArrayIndexSize digits with no leading zeros (except "0").
@@ -7076,13 +7075,33 @@
inline uint32_t GetHash();
+ // Reusable parts of the hashing algorithm.
+ INLINE(static uint32_t AddCharacterCore(uint32_t running_hash, uint32_t
c));
+ INLINE(static uint32_t GetHashCore(uint32_t running_hash));
+
int length_;
uint32_t raw_running_hash_;
uint32_t array_index_;
bool is_array_index_;
bool is_first_char_;
- bool is_valid_;
friend class TwoCharHashTableKey;
+
+ template <bool seq_ascii> friend class JsonParser;
+};
+
+
+class IncrementalAsciiStringHasher {
+ public:
+ explicit inline IncrementalAsciiStringHasher(uint32_t seed, char
first_char);
+ inline void AddCharacter(uc32 c);
+ inline uint32_t GetHash();
+
+ private:
+ int length_;
+ uint32_t raw_running_hash_;
+ uint32_t array_index_;
+ bool is_array_index_;
+ char first_char_;
};
--
v8-dev mailing list
[email protected]
http://groups.google.com/group/v8-dev
