Chromium Code Reviews
|
|
Chromium Code Reviews
Issue
9634005:
Implement a hash based look-up to speed up containing address check in large (Closed)
|
Created:
8 years, 9 months ago by kewpie.w.zp Modified:
8 years, 9 months ago Reviewers:
Vyacheslav Egorov (Chromium) CC:
v8-dev Base URL:
http://v8.googlecode.com/svn/trunk/ Visibility:
Public. |
DescriptionImplement a hash based look-up to speed up containing address check in large
object space. Before, it was a link-list based look-up, and make this function
a little bit 'hot' from profile point.
BUG=v8:853
TEST=
Committed: https://code.google.com/p/v8/source/detail?r=11084
Patch Set 1 #
Total comments: 20
Patch Set 2 : #
Total comments: 13
Patch Set 3 : #
Messages
Total messages: 9 (0 generated)
http://codereview.chromium.org/9634005/diff/1/src/spaces.cc File src/spaces.cc (left): http://codereview.chromium.org/9634005/diff/1/src/spaces.cc#oldcode2625 src/spaces.cc:2625: accidental edit? please revert. http://codereview.chromium.org/9634005/diff/1/src/spaces.cc File src/spaces.cc (right): http://codereview.chromium.org/9634005/diff/1/src/spaces.cc#newcode2523 src/spaces.cc:2523: static bool match(void* key1, void* key2) { Please give this function a more meaningful name, e.g. ComparePointers/SamePointers/etc http://codereview.chromium.org/9634005/diff/1/src/spaces.cc#newcode2526 src/spaces.cc:2526: one additional empty line http://codereview.chromium.org/9634005/diff/1/src/spaces.cc#newcode2588 src/spaces.cc:2588: // map following entries to this page object, in which keys are comments should start with a capital letter and end with a dot. http://codereview.chromium.org/9634005/diff/1/src/spaces.cc#newcode2588 src/spaces.cc:2588: // map following entries to this page object, in which keys are I would rephrase this comment, for example: // Register all MemoryChunk::kAlignment-aligned chunks covered by this large page in the chunk map. http://codereview.chromium.org/9634005/diff/1/src/spaces.cc#newcode2595 src/spaces.cc:2595: key += MemoryChunk::kAlignment, hash++) { I think you can just unify hash and key (make key == hash) because key is aligned and it's 20 less significant bits are always zeros. This will make this loop cleaner. http://codereview.chromium.org/9634005/diff/1/src/spaces.cc#newcode2596 src/spaces.cc:2596: (map_.Lookup(reinterpret_cast<void*>(key), hash, true))->value = page; I would prefer this is done in two lines instead of a single line. http://codereview.chromium.org/9634005/diff/1/src/spaces.cc#newcode2624 src/spaces.cc:2624: if ( page_address <= a && a < page_address + page->size() ) { accidental edit? please revert. http://codereview.chromium.org/9634005/diff/1/src/spaces.cc#newcode2642 src/spaces.cc:2642: return page; This code is duplicated in two places. Please move everything to a single helper function. http://codereview.chromium.org/9634005/diff/1/src/spaces.cc#newcode2679 src/spaces.cc:2679: // remove entries belonging to this page comments should start with a capital letter and end with a dot. http://codereview.chromium.org/9634005/diff/1/src/spaces.h File src/spaces.h (right): http://codereview.chromium.org/9634005/diff/1/src/spaces.h#newcode2540 src/spaces.h:2540: HashMap map_; // speed up containing pointer check Consider more meaningful name and comment. For example: // Map MemoryChunk::kAlignment-aligned chunks to large pages covering them. chunk_map_;
almost there. please fix last comments. http://codereview.chromium.org/9634005/diff/7002/src/spaces.cc File src/spaces.cc (right): http://codereview.chromium.org/9634005/diff/7002/src/spaces.cc#newcode2591 src/spaces.cc:2591: uint32_t base = reinterpret_cast<uint32_t>(page)/MemoryChunk::kAlignment; casting page to uint32_t is not suitable for 64-bit arch. consider using uintptr_t instead. http://codereview.chromium.org/9634005/diff/7002/src/spaces.cc#newcode2616 src/spaces.cc:2616: LargePage* page = FindPageContainingPc(a); I would suggest retaining FindPageContainingPc because you are calling it from the function that is used for arbitrary addresses. http://codereview.chromium.org/9634005/diff/7002/src/spaces.cc#newcode2633 src/spaces.cc:2633: if (page_address <= pc && pc < page_address + page->size()) { Consider using page->Contains(pc) here. http://codereview.chromium.org/9634005/diff/7002/src/spaces.cc#newcode2673 src/spaces.cc:2673: uint32_t base = reinterpret_cast<uint32_t>(page)/MemoryChunk::kAlignment; casting page to uint32_t is not suitable for 64-bit arch. consider using uintptr_t instead.
http://codereview.chromium.org/9634005/diff/1/src/spaces.cc File src/spaces.cc (left): http://codereview.chromium.org/9634005/diff/1/src/spaces.cc#oldcode2625 src/spaces.cc:2625: On 2012/03/08 11:41:23, Vyacheslav Egorov wrote: > accidental edit? please revert. Done. http://codereview.chromium.org/9634005/diff/1/src/spaces.cc File src/spaces.cc (right): http://codereview.chromium.org/9634005/diff/1/src/spaces.cc#newcode2523 src/spaces.cc:2523: static bool match(void* key1, void* key2) { On 2012/03/08 11:41:23, Vyacheslav Egorov wrote: > Please give this function a more meaningful name, e.g. > ComparePointers/SamePointers/etc Done. http://codereview.chromium.org/9634005/diff/1/src/spaces.cc#newcode2526 src/spaces.cc:2526: On 2012/03/08 11:41:23, Vyacheslav Egorov wrote: > one additional empty line Done. http://codereview.chromium.org/9634005/diff/1/src/spaces.cc#newcode2588 src/spaces.cc:2588: // map following entries to this page object, in which keys are On 2012/03/08 11:41:23, Vyacheslav Egorov wrote: > comments should start with a capital letter and end with a dot. Done. http://codereview.chromium.org/9634005/diff/1/src/spaces.cc#newcode2595 src/spaces.cc:2595: key += MemoryChunk::kAlignment, hash++) { On 2012/03/08 11:41:23, Vyacheslav Egorov wrote: > I think you can just unify hash and key (make key == hash) because key is > aligned and it's 20 less significant bits are always zeros. This will make this > loop cleaner. Done. http://codereview.chromium.org/9634005/diff/1/src/spaces.cc#newcode2596 src/spaces.cc:2596: (map_.Lookup(reinterpret_cast<void*>(key), hash, true))->value = page; On 2012/03/08 11:41:23, Vyacheslav Egorov wrote: > I would prefer this is done in two lines instead of a single line. Done. http://codereview.chromium.org/9634005/diff/1/src/spaces.cc#newcode2624 src/spaces.cc:2624: if ( page_address <= a && a < page_address + page->size() ) { On 2012/03/08 11:41:23, Vyacheslav Egorov wrote: > accidental edit? please revert. Done. http://codereview.chromium.org/9634005/diff/1/src/spaces.cc#newcode2642 src/spaces.cc:2642: return page; On 2012/03/08 11:41:23, Vyacheslav Egorov wrote: > This code is duplicated in two places. Please move everything to a single helper > function. Accepted, will reduce FindObject(a) size by calling this function instead to remove duplicated code http://codereview.chromium.org/9634005/diff/1/src/spaces.cc#newcode2679 src/spaces.cc:2679: // remove entries belonging to this page On 2012/03/08 11:41:23, Vyacheslav Egorov wrote: > comments should start with a capital letter and end with a dot. Done. http://codereview.chromium.org/9634005/diff/7002/src/spaces.cc File src/spaces.cc (right): http://codereview.chromium.org/9634005/diff/7002/src/spaces.cc#newcode2591 src/spaces.cc:2591: uint32_t base = reinterpret_cast<uint32_t>(page)/MemoryChunk::kAlignment; On 2012/03/09 12:15:37, Vyacheslav Egorov wrote: > casting page to uint32_t is not suitable for 64-bit arch. > > consider using uintptr_t instead. Done. http://codereview.chromium.org/9634005/diff/7002/src/spaces.cc#newcode2616 src/spaces.cc:2616: LargePage* page = FindPageContainingPc(a); On 2012/03/09 12:15:37, Vyacheslav Egorov wrote: > I would suggest retaining FindPageContainingPc because you are calling it from > the function that is used for arbitrary addresses. Not very sure if I catch your point. Please allow me to confirm. Do you suggest retaining the linear search of FindPageContainingPc() and just change FindObject() to hash lookup, or reversed, or something else ? Thanks a lot for your answering http://codereview.chromium.org/9634005/diff/7002/src/spaces.cc#newcode2633 src/spaces.cc:2633: if (page_address <= pc && pc < page_address + page->size()) { On 2012/03/09 12:15:37, Vyacheslav Egorov wrote: > Consider using page->Contains(pc) here. The check range of page->Contains(pc) falls into (base+Page::kObjectStartOffset, base+chunk_size), so if pc falls into page's header range (base, base+Page::kObjectStartOffset) will be failed, which would succeed otherwise. Should we allow this difference and replace it with Contains() anyway ? http://codereview.chromium.org/9634005/diff/7002/src/spaces.cc#newcode2673 src/spaces.cc:2673: uint32_t base = reinterpret_cast<uint32_t>(page)/MemoryChunk::kAlignment; On 2012/03/09 12:15:37, Vyacheslav Egorov wrote: > casting page to uint32_t is not suitable for 64-bit arch. > > consider using uintptr_t instead. Done.
http://codereview.chromium.org/9634005/diff/7002/src/spaces.cc File src/spaces.cc (right): http://codereview.chromium.org/9634005/diff/7002/src/spaces.cc#newcode2616 src/spaces.cc:2616: LargePage* page = FindPageContainingPc(a); On 2012/03/12 02:00:40, kewpie.w.zp wrote: > On 2012/03/09 12:15:37, Vyacheslav Egorov wrote: > > I would suggest retaining FindPageContainingPc because you are calling it from > > the function that is used for arbitrary addresses. > > Not very sure if I catch your point. Please allow me to confirm. Do you suggest > retaining the linear search of FindPageContainingPc() and just change > FindObject() to hash lookup, or reversed, or something else ? Thanks a lot for > your answering My original comment should read: "I would suggest _renaming_...". Sorry for the confusion, there was a typo. My point was that there is nothing PC or code object specific in the code. http://codereview.chromium.org/9634005/diff/7002/src/spaces.cc#newcode2633 src/spaces.cc:2633: if (page_address <= pc && pc < page_address + page->size()) { On 2012/03/12 02:00:40, kewpie.w.zp wrote: > On 2012/03/09 12:15:37, Vyacheslav Egorov wrote: > > Consider using page->Contains(pc) here. > > The check range of page->Contains(pc) falls into (base+Page::kObjectStartOffset, > base+chunk_size), so if pc falls into page's header range (base, > base+Page::kObjectStartOffset) will be failed, which would succeed otherwise. > Should we allow this difference and replace it with Contains() anyway ? I don't think anybody should pass addresses that fall outside of inner object area to this function. If anybody does --- that is clearly a bug.
Thanks really for your time and comments. Seems we're getting closer to final draft. :) http://codereview.chromium.org/9634005/diff/7002/src/spaces.cc File src/spaces.cc (right): http://codereview.chromium.org/9634005/diff/7002/src/spaces.cc#newcode2616 src/spaces.cc:2616: LargePage* page = FindPageContainingPc(a); On 2012/03/12 12:04:12, Vyacheslav Egorov wrote: > On 2012/03/12 02:00:40, kewpie.w.zp wrote: > > On 2012/03/09 12:15:37, Vyacheslav Egorov wrote: > > > I would suggest retaining FindPageContainingPc because you are calling it > from > > > the function that is used for arbitrary addresses. > > > > Not very sure if I catch your point. Please allow me to confirm. Do you > suggest > > retaining the linear search of FindPageContainingPc() and just change > > FindObject() to hash lookup, or reversed, or something else ? Thanks a lot for > > your answering > > My original comment should read: "I would suggest _renaming_...". Sorry for the > confusion, there was a typo. > > My point was that there is nothing PC or code object specific in the code. I see. Maybe it's named so because called by InnerPointerToCodeCache::GcSafeFindCodeForInnerPointer(). How about change to "FindPage(Address a)", or something else you'd like to recommend ? http://codereview.chromium.org/9634005/diff/7002/src/spaces.cc#newcode2633 src/spaces.cc:2633: if (page_address <= pc && pc < page_address + page->size()) { On 2012/03/12 12:04:12, Vyacheslav Egorov wrote: > On 2012/03/12 02:00:40, kewpie.w.zp wrote: > > On 2012/03/09 12:15:37, Vyacheslav Egorov wrote: > > > Consider using page->Contains(pc) here. > > > > The check range of page->Contains(pc) falls into > (base+Page::kObjectStartOffset, > > base+chunk_size), so if pc falls into page's header range (base, > > base+Page::kObjectStartOffset) will be failed, which would succeed otherwise. > > Should we allow this difference and replace it with Contains() anyway ? > > I don't think anybody should pass addresses that fall outside of inner object > area to this function. If anybody does --- that is clearly a bug. Done.
We are almost there I think. http://codereview.chromium.org/9634005/diff/7002/src/spaces.cc File src/spaces.cc (right): http://codereview.chromium.org/9634005/diff/7002/src/spaces.cc#newcode2616 src/spaces.cc:2616: LargePage* page = FindPageContainingPc(a); On 2012/03/13 01:44:35, kewpie.w.zp wrote: > On 2012/03/12 12:04:12, Vyacheslav Egorov wrote: > > On 2012/03/12 02:00:40, kewpie.w.zp wrote: > > > On 2012/03/09 12:15:37, Vyacheslav Egorov wrote: > > > > I would suggest retaining FindPageContainingPc because you are calling it > > > from > > > > the function that is used for arbitrary addresses. > > > > > > Not very sure if I catch your point. Please allow me to confirm. Do you > > suggest > > > retaining the linear search of FindPageContainingPc() and just change > > > FindObject() to hash lookup, or reversed, or something else ? Thanks a lot > for > > > your answering > > > > My original comment should read: "I would suggest _renaming_...". Sorry for > the > > confusion, there was a typo. > > > > My point was that there is nothing PC or code object specific in the code. > > I see. Maybe it's named so because called by > InnerPointerToCodeCache::GcSafeFindCodeForInnerPointer(). How about change to > "FindPage(Address a)", or something else you'd like to recommend ? > FindPage sounds good to me
On 2012/03/13 11:39:11, Vyacheslav Egorov wrote: > We are almost there I think. > > http://codereview.chromium.org/9634005/diff/7002/src/spaces.cc > File src/spaces.cc (right): > > http://codereview.chromium.org/9634005/diff/7002/src/spaces.cc#newcode2616 > src/spaces.cc:2616: LargePage* page = FindPageContainingPc(a); > On 2012/03/13 01:44:35, kewpie.w.zp wrote: > > On 2012/03/12 12:04:12, Vyacheslav Egorov wrote: > > > On 2012/03/12 02:00:40, kewpie.w.zp wrote: > > > > On 2012/03/09 12:15:37, Vyacheslav Egorov wrote: > > > > > I would suggest retaining FindPageContainingPc because you are calling > it > > > > > from > > > > > the function that is used for arbitrary addresses. > > > > > > > > Not very sure if I catch your point. Please allow me to confirm. Do you > > > suggest > > > > retaining the linear search of FindPageContainingPc() and just change > > > > FindObject() to hash lookup, or reversed, or something else ? Thanks a lot > > for > > > > your answering > > > > > > My original comment should read: "I would suggest _renaming_...". Sorry for > > the > > > confusion, there was a typo. > > > > > > My point was that there is nothing PC or code object specific in the code. > > > > I see. Maybe it's named so because called by > > InnerPointerToCodeCache::GcSafeFindCodeForInnerPointer(). How about change to > > "FindPage(Address a)", or something else you'd like to recommend ? > > > > FindPage sounds good to me Thanks a lot for your review. I'm not a committer, so could you kindly help commit it for me ? Really appreciate.
LGTM I'll benchmark and land.
landed! thank you for the contribution |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
