Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(275)

Side by Side Diff: src/objects.cc

Issue 3020003: StringDictionary::FindEntry optimized for symbol strings. (Closed) Base URL: http://v8.googlecode.com/svn/branches/bleeding_edge/
Patch Set: '' Created 10 years, 5 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch | Annotate | Revision Log
« no previous file with comments | « src/objects.h ('k') | no next file » | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
1 // Copyright 2006-2009 the V8 project authors. All rights reserved. 1 // Copyright 2006-2009 the V8 project authors. All rights reserved.
2 // Redistribution and use in source and binary forms, with or without 2 // Redistribution and use in source and binary forms, with or without
3 // modification, are permitted provided that the following conditions are 3 // modification, are permitted provided that the following conditions are
4 // met: 4 // met:
5 // 5 //
6 // * Redistributions of source code must retain the above copyright 6 // * Redistributions of source code must retain the above copyright
7 // notice, this list of conditions and the following disclaimer. 7 // notice, this list of conditions and the following disclaimer.
8 // * Redistributions in binary form must reproduce the above 8 // * Redistributions in binary form must reproduce the above
9 // copyright notice, this list of conditions and the following 9 // copyright notice, this list of conditions and the following
10 // disclaimer in the documentation and/or other materials provided 10 // disclaimer in the documentation and/or other materials provided
(...skipping 7320 matching lines...) Expand 10 before | Expand all | Expand 10 after
7331 while (true) { 7331 while (true) {
7332 Object* element = KeyAt(entry); 7332 Object* element = KeyAt(entry);
7333 if (element->IsUndefined()) break; // Empty entry. 7333 if (element->IsUndefined()) break; // Empty entry.
7334 if (!element->IsNull() && Shape::IsMatch(key, element)) return entry; 7334 if (!element->IsNull() && Shape::IsMatch(key, element)) return entry;
7335 entry = NextProbe(entry, count++, capacity); 7335 entry = NextProbe(entry, count++, capacity);
7336 } 7336 }
7337 return kNotFound; 7337 return kNotFound;
7338 } 7338 }
7339 7339
7340 7340
7341 // Find entry for key otherwise return kNotFound.
7342 int StringDictionary::FindEntry(String* key) {
7343 if (!key->IsSymbol()) {
7344 return HashTable<StringDictionaryShape, String*>::FindEntry(key);
7345 }
7346
7347 // Optimized for symbol key. Knowledge of the key type allows:
7348 // 1. Move the check if the key is a symbol out of the loop.
7349 // 2. Avoid comparing hash codes in symbol to symbol comparision.
7350 // 3. Detect a case when a dictionary key is not a symbol but the key is.
7351 // In case of positive result the dictionary key may be replaced by
7352 // the symbol with minimal performance penalty. It gives a chance to
7353 // perform further lookups in code stubs (and significant performance boost
7354 // a certain style of code).
7355
7356 // EnsureCapacity will guarantee the hash table is never full.
7357 uint32_t capacity = Capacity();
7358 uint32_t entry = FirstProbe(key->Hash(), capacity);
7359 uint32_t count = 1;
7360
7361 while (true) {
7362 int index = EntryToIndex(entry);
7363 Object* element = get(index);
7364 if (element->IsUndefined()) break; // Empty entry.
7365 if (key == element) return entry;
7366 if (!element->IsSymbol() &&
7367 !element->IsNull() &&
7368 String::cast(element)->Equals(key)) {
7369 // Replace a non-symbol key by the equivalent symbol for faster further
7370 // lookups.
7371 set(index, key);
7372 return entry;
7373 }
7374 ASSERT(element->IsNull() || !String::cast(element)->Equals(key));
7375 entry = NextProbe(entry, count++, capacity);
7376 }
7377 return kNotFound;
7378 }
7379
7380
7341 template<typename Shape, typename Key> 7381 template<typename Shape, typename Key>
7342 Object* HashTable<Shape, Key>::EnsureCapacity(int n, Key key) { 7382 Object* HashTable<Shape, Key>::EnsureCapacity(int n, Key key) {
7343 int capacity = Capacity(); 7383 int capacity = Capacity();
7344 int nof = NumberOfElements() + n; 7384 int nof = NumberOfElements() + n;
7345 int nod = NumberOfDeletedElements(); 7385 int nod = NumberOfDeletedElements();
7346 // Return if: 7386 // Return if:
7347 // 50% is still free after adding n elements and 7387 // 50% is still free after adding n elements and
7348 // at most 50% of the free elements are deleted elements. 7388 // at most 50% of the free elements are deleted elements.
7349 if (nod <= (capacity - nof) >> 1) { 7389 if (nod <= (capacity - nof) >> 1) {
7350 int needed_free = nof >> 1; 7390 int needed_free = nof >> 1;
(...skipping 1418 matching lines...) Expand 10 before | Expand all | Expand 10 after
8769 if (break_point_objects()->IsUndefined()) return 0; 8809 if (break_point_objects()->IsUndefined()) return 0;
8770 // Single beak point. 8810 // Single beak point.
8771 if (!break_point_objects()->IsFixedArray()) return 1; 8811 if (!break_point_objects()->IsFixedArray()) return 1;
8772 // Multiple break points. 8812 // Multiple break points.
8773 return FixedArray::cast(break_point_objects())->length(); 8813 return FixedArray::cast(break_point_objects())->length();
8774 } 8814 }
8775 #endif 8815 #endif
8776 8816
8777 8817
8778 } } // namespace v8::internal 8818 } } // namespace v8::internal
OLDNEW
« no previous file with comments | « src/objects.h ('k') | no next file » | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698