Mikhail, The deleted jsregexp-inl.h file is still referenced from tools/gyp/v8.gyp and tools/v8.xcodeproj/.
Cheers, Kasper On Wed, Jul 29, 2009 at 10:11 AM, <[email protected]> wrote: > > Revision: 2570 > Author: [email protected] > Date: Wed Jul 29 01:10:19 2009 > Log: Introduce first approximation of constructor heap profile for JS > objects. > > It is activated with '--log-gc' flag. > > JS object size is calculated as its size + size of 'properties' > and 'elements' arrays, if they are non-empty. This doesn't take maps, > strings, heap numbers, and other shared objects into account. > > As Soeren suggested, I've moved ZoneSplayTree from jsregexp to zone, and > removed now empty jsregexp-inl header file. > > Review URL: http://codereview.chromium.org/159504 > http://code.google.com/p/v8/source/detail?r=2570 > > Deleted: > /branches/bleeding_edge/src/jsregexp-inl.h > Modified: > /branches/bleeding_edge/src/heap.cc > /branches/bleeding_edge/src/jsregexp.cc > /branches/bleeding_edge/src/jsregexp.h > /branches/bleeding_edge/src/log.cc > /branches/bleeding_edge/src/log.h > /branches/bleeding_edge/src/spaces.h > /branches/bleeding_edge/src/zone-inl.h > /branches/bleeding_edge/src/zone.h > /branches/bleeding_edge/test/cctest/test-regexp.cc > /branches/bleeding_edge/tools/process-heap-prof.py > /branches/bleeding_edge/tools/visual_studio/v8_base.vcproj > /branches/bleeding_edge/tools/visual_studio/v8_base_arm.vcproj > > ======================================= > --- /branches/bleeding_edge/src/jsregexp-inl.h Mon May 25 03:05:56 2009 > +++ /dev/null > @@ -1,260 +0,0 @@ > -// Copyright 2008 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 > -// with the distribution. > -// * Neither the name of Google Inc. nor the names of its > -// contributors may be used to endorse or promote products derived > -// from this software without specific prior written permission. > -// > -// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS > -// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT > -// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR > -// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT > -// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, > -// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT > -// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, > -// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY > -// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT > -// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE > -// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. > - > -#ifndef V8_JSREGEXP_INL_H_ > -#define V8_JSREGEXP_INL_H_ > - > - > -#include "jsregexp.h" > -#include "regexp-macro-assembler.h" > - > - > -namespace v8 { > -namespace internal { > - > - > -template <typename C> > -bool ZoneSplayTree<C>::Insert(const Key& key, Locator* locator) { > - if (is_empty()) { > - // If the tree is empty, insert the new node. > - root_ = new Node(key, C::kNoValue); > - } else { > - // Splay on the key to move the last node on the search path > - // for the key to the root of the tree. > - Splay(key); > - // Ignore repeated insertions with the same key. > - int cmp = C::Compare(key, root_->key_); > - if (cmp == 0) { > - locator->bind(root_); > - return false; > - } > - // Insert the new node. > - Node* node = new Node(key, C::kNoValue); > - if (cmp > 0) { > - node->left_ = root_; > - node->right_ = root_->right_; > - root_->right_ = NULL; > - } else { > - node->right_ = root_; > - node->left_ = root_->left_; > - root_->left_ = NULL; > - } > - root_ = node; > - } > - locator->bind(root_); > - return true; > -} > - > - > -template <typename C> > -bool ZoneSplayTree<C>::Find(const Key& key, Locator* locator) { > - if (is_empty()) > - return false; > - Splay(key); > - if (C::Compare(key, root_->key_) == 0) { > - locator->bind(root_); > - return true; > - } else { > - return false; > - } > -} > - > - > -template <typename C> > -bool ZoneSplayTree<C>::FindGreatestLessThan(const Key& key, > - Locator* locator) { > - if (is_empty()) > - return false; > - // Splay on the key to move the node with the given key or the last > - // node on the search path to the top of the tree. > - Splay(key); > - // Now the result is either the root node or the greatest node in > - // the left subtree. > - int cmp = C::Compare(root_->key_, key); > - if (cmp <= 0) { > - locator->bind(root_); > - return true; > - } else { > - Node* temp = root_; > - root_ = root_->left_; > - bool result = FindGreatest(locator); > - root_ = temp; > - return result; > - } > -} > - > - > -template <typename C> > -bool ZoneSplayTree<C>::FindLeastGreaterThan(const Key& key, > - Locator* locator) { > - if (is_empty()) > - return false; > - // Splay on the key to move the node with the given key or the last > - // node on the search path to the top of the tree. > - Splay(key); > - // Now the result is either the root node or the least node in > - // the right subtree. > - int cmp = C::Compare(root_->key_, key); > - if (cmp >= 0) { > - locator->bind(root_); > - return true; > - } else { > - Node* temp = root_; > - root_ = root_->right_; > - bool result = FindLeast(locator); > - root_ = temp; > - return result; > - } > -} > - > - > -template <typename C> > -bool ZoneSplayTree<C>::FindGreatest(Locator* locator) { > - if (is_empty()) > - return false; > - Node* current = root_; > - while (current->right_ != NULL) > - current = current->right_; > - locator->bind(current); > - return true; > -} > - > - > -template <typename C> > -bool ZoneSplayTree<C>::FindLeast(Locator* locator) { > - if (is_empty()) > - return false; > - Node* current = root_; > - while (current->left_ != NULL) > - current = current->left_; > - locator->bind(current); > - return true; > -} > - > - > -template <typename C> > -bool ZoneSplayTree<C>::Remove(const Key& key) { > - // Bail if the tree is empty > - if (is_empty()) > - return false; > - // Splay on the key to move the node with the given key to the top. > - Splay(key); > - // Bail if the key is not in the tree > - if (C::Compare(key, root_->key_) != 0) > - return false; > - if (root_->left_ == NULL) { > - // No left child, so the new tree is just the right child. > - root_ = root_->right_; > - } else { > - // Left child exists. > - Node* right = root_->right_; > - // Make the original left child the new root. > - root_ = root_->left_; > - // Splay to make sure that the new root has an empty right child. > - Splay(key); > - // Insert the original right child as the right child of the new > - // root. > - root_->right_ = right; > - } > - return true; > -} > - > - > -template <typename C> > -void ZoneSplayTree<C>::Splay(const Key& key) { > - if (is_empty()) > - return; > - Node dummy_node(C::kNoKey, C::kNoValue); > - // Create a dummy node. The use of the dummy node is a bit > - // counter-intuitive: The right child of the dummy node will hold > - // the L tree of the algorithm. The left child of the dummy node > - // will hold the R tree of the algorithm. Using a dummy node, left > - // and right will always be nodes and we avoid special cases. > - Node* dummy = &dummy_node; > - Node* left = dummy; > - Node* right = dummy; > - Node* current = root_; > - while (true) { > - int cmp = C::Compare(key, current->key_); > - if (cmp < 0) { > - if (current->left_ == NULL) > - break; > - if (C::Compare(key, current->left_->key_) < 0) { > - // Rotate right. > - Node* temp = current->left_; > - current->left_ = temp->right_; > - temp->right_ = current; > - current = temp; > - if (current->left_ == NULL) > - break; > - } > - // Link right. > - right->left_ = current; > - right = current; > - current = current->left_; > - } else if (cmp > 0) { > - if (current->right_ == NULL) > - break; > - if (C::Compare(key, current->right_->key_) > 0) { > - // Rotate left. > - Node* temp = current->right_; > - current->right_ = temp->left_; > - temp->left_ = current; > - current = temp; > - if (current->right_ == NULL) > - break; > - } > - // Link left. > - left->right_ = current; > - left = current; > - current = current->right_; > - } else { > - break; > - } > - } > - // Assemble. > - left->right_ = current->left_; > - right->left_ = current->right_; > - current->left_ = dummy->right_; > - current->right_ = dummy->left_; > - root_ = current; > -} > - > - > -template <typename Node, class Callback> > -static void DoForEach(Node* node, Callback* callback) { > - if (node == NULL) return; > - DoForEach<Node, Callback>(node->left(), callback); > - callback->Call(node->key(), node->value()); > - DoForEach<Node, Callback>(node->right(), callback); > -} > - > - > -}} // namespace v8::internal > - > - > -#endif // V8_JSREGEXP_INL_H_ > ======================================= > --- /branches/bleeding_edge/src/heap.cc Tue Jul 28 01:43:51 2009 > +++ /branches/bleeding_edge/src/heap.cc Wed Jul 29 01:10:19 2009 > @@ -3409,6 +3409,100 @@ > Shutdown(); > Init(); > } > + > + > +#ifdef ENABLE_LOGGING_AND_PROFILING > +namespace { > + > +// JSConstructorProfile is responsible for gathering and logging > +// "constructor profile" of JS object allocated on heap. > +// It is run during garbage collection cycle, thus it doesn't need > +// to use handles. > +class JSConstructorProfile BASE_EMBEDDED { > + public: > + JSConstructorProfile() : zscope_(DELETE_ON_EXIT) {} > + void CollectStats(JSObject* obj); > + void PrintStats(); > + // Used by ZoneSplayTree::ForEach. > + void Call(String* name, const NumberAndSizeInfo& number_and_size); > + private: > + struct TreeConfig { > + typedef String* Key; > + typedef NumberAndSizeInfo Value; > + static const Key kNoKey; > + static const Value kNoValue; > + // Strings are unique, so it is sufficient to compare their pointers. > + static int Compare(const Key& a, const Key& b) { > + return a == b ? 0 : (a < b ? -1 : 1); > + } > + }; > + > + typedef ZoneSplayTree<TreeConfig> JSObjectsInfoTree; > + static int CalculateJSObjectNetworkSize(JSObject* obj); > + > + ZoneScope zscope_; > + JSObjectsInfoTree js_objects_info_tree_; > +}; > + > +const JSConstructorProfile::TreeConfig::Key > + JSConstructorProfile::TreeConfig::kNoKey = NULL; > +const JSConstructorProfile::TreeConfig::Value > + JSConstructorProfile::TreeConfig::kNoValue; > + > + > +int JSConstructorProfile::CalculateJSObjectNetworkSize(JSObject* obj) { > + int size = obj->Size(); > + // If 'properties' and 'elements' are non-empty (thus, non-shared), > + // take their size into account. > + if (FixedArray::cast(obj->properties())->length() != 0) { > + size += obj->properties()->Size(); > + } > + if (FixedArray::cast(obj->elements())->length() != 0) { > + size += obj->elements()->Size(); > + } > + return size; > +} > + > + > +void JSConstructorProfile::Call(String* name, > + const NumberAndSizeInfo& number_and_size) { > + SmartPointer<char> s_name; > + if (name != NULL) { > + s_name = name->ToCString(DISALLOW_NULLS, ROBUST_STRING_TRAVERSAL); > + } > + LOG(HeapSampleJSConstructorEvent(*s_name, > + number_and_size.number(), > + number_and_size.bytes())); > +} > + > + > +void JSConstructorProfile::CollectStats(JSObject* obj) { > + String* constructor_func = NULL; > + if (obj->map()->constructor()->IsJSFunction()) { > + JSFunction* constructor = JSFunction::cast(obj->map()->constructor()); > + SharedFunctionInfo* sfi = constructor->shared(); > + String* name = String::cast(sfi->name()); > + constructor_func = name->length() > 0 ? name : sfi->inferred_name(); > + } else if (obj->IsJSFunction()) { > + constructor_func = Heap::function_class_symbol(); > + } > + JSObjectsInfoTree::Locator loc; > + if (!js_objects_info_tree_.Find(constructor_func, &loc)) { > + js_objects_info_tree_.Insert(constructor_func, &loc); > + } > + NumberAndSizeInfo number_and_size = loc.value(); > + number_and_size.increment_number(1); > + number_and_size.increment_bytes(CalculateJSObjectNetworkSize(obj)); > + loc.set_value(number_and_size); > +} > + > + > +void JSConstructorProfile::PrintStats() { > + js_objects_info_tree_.ForEach(this); > +} > + > +} // namespace > +#endif > > > // > @@ -3435,9 +3529,14 @@ > INSTANCE_TYPE_LIST(DEF_TYPE_NAME) > #undef DEF_TYPE_NAME > > + JSConstructorProfile js_cons_profile; > HeapIterator iterator; > while (iterator.has_next()) { > - CollectStats(iterator.next(), info); > + HeapObject* obj = iterator.next(); > + CollectStats(obj, info); > + if (obj->IsJSObject()) { > + js_cons_profile.CollectStats(JSObject::cast(obj)); > + } > } > > // Lump all the string types together. > @@ -3458,6 +3557,8 @@ > info[i].bytes())); > } > } > + > + js_cons_profile.PrintStats(); > > LOG(HeapSampleEndEvent("Heap", "allocated")); > } > ======================================= > --- /branches/bleeding_edge/src/jsregexp.cc Tue Jul 28 01:43:51 2009 > +++ /branches/bleeding_edge/src/jsregexp.cc Wed Jul 29 01:10:19 2009 > @@ -31,7 +31,7 @@ > #include "compiler.h" > #include "execution.h" > #include "factory.h" > -#include "jsregexp-inl.h" > +#include "jsregexp.h" > #include "platform.h" > #include "runtime.h" > #include "top.h" > ======================================= > --- /branches/bleeding_edge/src/jsregexp.h Tue Jul 7 01:11:19 2009 > +++ /branches/bleeding_edge/src/jsregexp.h Wed Jul 29 01:10:19 2009 > @@ -214,108 +214,6 @@ > }; > > > -template <typename Node, class Callback> > -static void DoForEach(Node* node, Callback* callback); > - > - > -// A zone splay tree. The config type parameter encapsulates the > -// different configurations of a concrete splay tree: > -// > -// typedef Key: the key type > -// typedef Value: the value type > -// static const kNoKey: the dummy key used when no key is set > -// static const kNoValue: the dummy value used to initialize nodes > -// int (Compare)(Key& a, Key& b) -> {-1, 0, 1}: comparison function > -// > -template <typename Config> > -class ZoneSplayTree : public ZoneObject { > - public: > - typedef typename Config::Key Key; > - typedef typename Config::Value Value; > - > - class Locator; > - > - ZoneSplayTree() : root_(NULL) { } > - > - // Inserts the given key in this tree with the given value. Returns > - // true if a node was inserted, otherwise false. If found the locator > - // is enabled and provides access to the mapping for the key. > - bool Insert(const Key& key, Locator* locator); > - > - // Looks up the key in this tree and returns true if it was found, > - // otherwise false. If the node is found the locator is enabled and > - // provides access to the mapping for the key. > - bool Find(const Key& key, Locator* locator); > - > - // Finds the mapping with the greatest key less than or equal to the > - // given key. > - bool FindGreatestLessThan(const Key& key, Locator* locator); > - > - // Find the mapping with the greatest key in this tree. > - bool FindGreatest(Locator* locator); > - > - // Finds the mapping with the least key greater than or equal to the > - // given key. > - bool FindLeastGreaterThan(const Key& key, Locator* locator); > - > - // Find the mapping with the least key in this tree. > - bool FindLeast(Locator* locator); > - > - // Remove the node with the given key from the tree. > - bool Remove(const Key& key); > - > - bool is_empty() { return root_ == NULL; } > - > - // Perform the splay operation for the given key. Moves the node with > - // the given key to the top of the tree. If no node has the given > - // key, the last node on the search path is moved to the top of the > - // tree. > - void Splay(const Key& key); > - > - class Node : public ZoneObject { > - public: > - Node(const Key& key, const Value& value) > - : key_(key), > - value_(value), > - left_(NULL), > - right_(NULL) { } > - Key key() { return key_; } > - Value value() { return value_; } > - Node* left() { return left_; } > - Node* right() { return right_; } > - private: > - friend class ZoneSplayTree; > - friend class Locator; > - Key key_; > - Value value_; > - Node* left_; > - Node* right_; > - }; > - > - // A locator provides access to a node in the tree without actually > - // exposing the node. > - class Locator { > - public: > - explicit Locator(Node* node) : node_(node) { } > - Locator() : node_(NULL) { } > - const Key& key() { return node_->key_; } > - Value& value() { return node_->value_; } > - void set_value(const Value& value) { node_->value_ = value; } > - inline void bind(Node* node) { node_ = node; } > - private: > - Node* node_; > - }; > - > - template <class Callback> > - void ForEach(Callback* c) { > - DoForEach<typename ZoneSplayTree<Config>::Node, Callback>(root_, c); > - } > - > - private: > - Node* root_; > -}; > - > - > // A set of unsigned integers that behaves especially well on small > // integers (< 32). May do zone-allocation. > class OutSet: public ZoneObject { > ======================================= > --- /branches/bleeding_edge/src/log.cc Mon Jul 20 02:38:44 2009 > +++ /branches/bleeding_edge/src/log.cc Wed Jul 29 01:10:19 2009 > @@ -882,6 +882,21 @@ > msg.WriteToLogFile(); > #endif > } > + > + > +void Logger::HeapSampleJSConstructorEvent(const char* constructor, > + int number, int bytes) { > +#ifdef ENABLE_LOGGING_AND_PROFILING > + if (!Log::IsEnabled() || !FLAG_log_gc) return; > + LogMessageBuilder msg; > + msg.Append("heap-js-cons-item,%s,%d,%d\n", > + constructor != NULL ? > + (constructor[0] != '\0' ? constructor : "(anonymous)") : > + "(no_constructor)", > + number, bytes); > + msg.WriteToLogFile(); > +#endif > +} > > > void Logger::DebugTag(const char* call_site_tag) { > ======================================= > --- /branches/bleeding_edge/src/log.h Mon Jul 20 02:38:44 2009 > +++ /branches/bleeding_edge/src/log.h Wed Jul 29 01:10:19 2009 > @@ -219,6 +219,8 @@ > static void HeapSampleBeginEvent(const char* space, const char* kind); > static void HeapSampleEndEvent(const char* space, const char* kind); > static void HeapSampleItemEvent(const char* type, int number, int bytes); > + static void HeapSampleJSConstructorEvent(const char* constructor, > + int number, int bytes); > static void HeapSampleStats(const char* space, const char* kind, > int capacity, int used); > > ======================================= > --- /branches/bleeding_edge/src/spaces.h Tue Jul 14 15:38:06 2009 > +++ /branches/bleeding_edge/src/spaces.h Wed Jul 29 01:10:19 2009 > @@ -931,34 +931,41 @@ > > > #if defined(DEBUG) || defined(ENABLE_LOGGING_AND_PROFILING) > -// HistogramInfo class for recording a single "bar" of a histogram. This > -// class is used for collecting statistics to print to stdout (when > compiled > -// with DEBUG) or to the log file (when compiled with > -// ENABLE_LOGGING_AND_PROFILING). > -class HistogramInfo BASE_EMBEDDED { > +class NumberAndSizeInfo BASE_EMBEDDED { > public: > - HistogramInfo() : number_(0), bytes_(0) {} > - > - const char* name() { return name_; } > - void set_name(const char* name) { name_ = name; } > - > - int number() { return number_; } > + NumberAndSizeInfo() : number_(0), bytes_(0) {} > + > + int number() const { return number_; } > void increment_number(int num) { number_ += num; } > > - int bytes() { return bytes_; } > + int bytes() const { return bytes_; } > void increment_bytes(int size) { bytes_ += size; } > > - // Clear the number of objects and size fields, but not the name. > void clear() { > number_ = 0; > bytes_ = 0; > } > > private: > - const char* name_; > int number_; > int bytes_; > }; > + > + > +// HistogramInfo class for recording a single "bar" of a histogram. This > +// class is used for collecting statistics to print to stdout (when > compiled > +// with DEBUG) or to the log file (when compiled with > +// ENABLE_LOGGING_AND_PROFILING). > +class HistogramInfo: public NumberAndSizeInfo { > + public: > + HistogramInfo() : NumberAndSizeInfo() {} > + > + const char* name() { return name_; } > + void set_name(const char* name) { name_ = name; } > + > + private: > + const char* name_; > +}; > #endif > > > ======================================= > --- /branches/bleeding_edge/src/zone-inl.h Mon May 25 03:05:56 2009 > +++ /branches/bleeding_edge/src/zone-inl.h Wed Jul 29 01:10:19 2009 > @@ -66,6 +66,223 @@ > segment_bytes_allocated_ += delta; > Counters::zone_segment_bytes.Set(segment_bytes_allocated_); > } > + > + > +template <typename C> > +bool ZoneSplayTree<C>::Insert(const Key& key, Locator* locator) { > + if (is_empty()) { > + // If the tree is empty, insert the new node. > + root_ = new Node(key, C::kNoValue); > + } else { > + // Splay on the key to move the last node on the search path > + // for the key to the root of the tree. > + Splay(key); > + // Ignore repeated insertions with the same key. > + int cmp = C::Compare(key, root_->key_); > + if (cmp == 0) { > + locator->bind(root_); > + return false; > + } > + // Insert the new node. > + Node* node = new Node(key, C::kNoValue); > + if (cmp > 0) { > + node->left_ = root_; > + node->right_ = root_->right_; > + root_->right_ = NULL; > + } else { > + node->right_ = root_; > + node->left_ = root_->left_; > + root_->left_ = NULL; > + } > + root_ = node; > + } > + locator->bind(root_); > + return true; > +} > + > + > +template <typename C> > +bool ZoneSplayTree<C>::Find(const Key& key, Locator* locator) { > + if (is_empty()) > + return false; > + Splay(key); > + if (C::Compare(key, root_->key_) == 0) { > + locator->bind(root_); > + return true; > + } else { > + return false; > + } > +} > + > + > +template <typename C> > +bool ZoneSplayTree<C>::FindGreatestLessThan(const Key& key, > + Locator* locator) { > + if (is_empty()) > + return false; > + // Splay on the key to move the node with the given key or the last > + // node on the search path to the top of the tree. > + Splay(key); > + // Now the result is either the root node or the greatest node in > + // the left subtree. > + int cmp = C::Compare(root_->key_, key); > + if (cmp <= 0) { > + locator->bind(root_); > + return true; > + } else { > + Node* temp = root_; > + root_ = root_->left_; > + bool result = FindGreatest(locator); > + root_ = temp; > + return result; > + } > +} > + > + > +template <typename C> > +bool ZoneSplayTree<C>::FindLeastGreaterThan(const Key& key, > + Locator* locator) { > + if (is_empty()) > + return false; > + // Splay on the key to move the node with the given key or the last > + // node on the search path to the top of the tree. > + Splay(key); > + // Now the result is either the root node or the least node in > + // the right subtree. > + int cmp = C::Compare(root_->key_, key); > + if (cmp >= 0) { > + locator->bind(root_); > + return true; > + } else { > + Node* temp = root_; > + root_ = root_->right_; > + bool result = FindLeast(locator); > + root_ = temp; > + return result; > + } > +} > + > + > +template <typename C> > +bool ZoneSplayTree<C>::FindGreatest(Locator* locator) { > + if (is_empty()) > + return false; > + Node* current = root_; > + while (current->right_ != NULL) > + current = current->right_; > + locator->bind(current); > + return true; > +} > + > + > +template <typename C> > +bool ZoneSplayTree<C>::FindLeast(Locator* locator) { > + if (is_empty()) > + return false; > + Node* current = root_; > + while (current->left_ != NULL) > + current = current->left_; > + locator->bind(current); > + return true; > +} > + > + > +template <typename C> > +bool ZoneSplayTree<C>::Remove(const Key& key) { > + // Bail if the tree is empty > + if (is_empty()) > + return false; > + // Splay on the key to move the node with the given key to the top. > + Splay(key); > + // Bail if the key is not in the tree > + if (C::Compare(key, root_->key_) != 0) > + return false; > + if (root_->left_ == NULL) { > + // No left child, so the new tree is just the right child. > + root_ = root_->right_; > + } else { > + // Left child exists. > + Node* right = root_->right_; > + // Make the original left child the new root. > + root_ = root_->left_; > + // Splay to make sure that the new root has an empty right child. > + Splay(key); > + // Insert the original right child as the right child of the new > + // root. > + root_->right_ = right; > + } > + return true; > +} > + > + > +template <typename C> > +void ZoneSplayTree<C>::Splay(const Key& key) { > + if (is_empty()) > + return; > + Node dummy_node(C::kNoKey, C::kNoValue); > + // Create a dummy node. The use of the dummy node is a bit > + // counter-intuitive: The right child of the dummy node will hold > + // the L tree of the algorithm. The left child of the dummy node > + // will hold the R tree of the algorithm. Using a dummy node, left > + // and right will always be nodes and we avoid special cases. > + Node* dummy = &dummy_node; > + Node* left = dummy; > + Node* right = dummy; > + Node* current = root_; > + while (true) { > + int cmp = C::Compare(key, current->key_); > + if (cmp < 0) { > + if (current->left_ == NULL) > + break; > + if (C::Compare(key, current->left_->key_) < 0) { > + // Rotate right. > + Node* temp = current->left_; > + current->left_ = temp->right_; > + temp->right_ = current; > + current = temp; > + if (current->left_ == NULL) > + break; > + } > + // Link right. > + right->left_ = current; > + right = current; > + current = current->left_; > + } else if (cmp > 0) { > + if (current->right_ == NULL) > + break; > + if (C::Compare(key, current->right_->key_) > 0) { > + // Rotate left. > + Node* temp = current->right_; > + current->right_ = temp->left_; > + temp->left_ = current; > + current = temp; > + if (current->right_ == NULL) > + break; > + } > + // Link left. > + left->right_ = current; > + left = current; > + current = current->right_; > + } else { > + break; > + } > + } > + // Assemble. > + left->right_ = current->left_; > + right->left_ = current->right_; > + current->left_ = dummy->right_; > + current->right_ = dummy->left_; > + root_ = current; > +} > + > + > +template <typename Node, class Callback> > +static void DoForEach(Node* node, Callback* callback) { > + if (node == NULL) return; > + DoForEach<Node, Callback>(node->left(), callback); > + callback->Call(node->key(), node->value()); > + DoForEach<Node, Callback>(node->right(), callback); > +} > > > } } // namespace v8::internal > ======================================= > --- /branches/bleeding_edge/src/zone.h Mon May 25 03:05:56 2009 > +++ /branches/bleeding_edge/src/zone.h Wed Jul 29 01:10:19 2009 > @@ -204,6 +204,108 @@ > }; > > > +template <typename Node, class Callback> > +static void DoForEach(Node* node, Callback* callback); > + > + > +// A zone splay tree. The config type parameter encapsulates the > +// different configurations of a concrete splay tree: > +// > +// typedef Key: the key type > +// typedef Value: the value type > +// static const kNoKey: the dummy key used when no key is set > +// static const kNoValue: the dummy value used to initialize nodes > +// int (Compare)(Key& a, Key& b) -> {-1, 0, 1}: comparison function > +// > +template <typename Config> > +class ZoneSplayTree : public ZoneObject { > + public: > + typedef typename Config::Key Key; > + typedef typename Config::Value Value; > + > + class Locator; > + > + ZoneSplayTree() : root_(NULL) { } > + > + // Inserts the given key in this tree with the given value. Returns > + // true if a node was inserted, otherwise false. If found the locator > + // is enabled and provides access to the mapping for the key. > + bool Insert(const Key& key, Locator* locator); > + > + // Looks up the key in this tree and returns true if it was found, > + // otherwise false. If the node is found the locator is enabled and > + // provides access to the mapping for the key. > + bool Find(const Key& key, Locator* locator); > + > + // Finds the mapping with the greatest key less than or equal to the > + // given key. > + bool FindGreatestLessThan(const Key& key, Locator* locator); > + > + // Find the mapping with the greatest key in this tree. > + bool FindGreatest(Locator* locator); > + > + // Finds the mapping with the least key greater than or equal to the > + // given key. > + bool FindLeastGreaterThan(const Key& key, Locator* locator); > + > + // Find the mapping with the least key in this tree. > + bool FindLeast(Locator* locator); > + > + // Remove the node with the given key from the tree. > + bool Remove(const Key& key); > + > + bool is_empty() { return root_ == NULL; } > + > + // Perform the splay operation for the given key. Moves the node with > + // the given key to the top of the tree. If no node has the given > + // key, the last node on the search path is moved to the top of the > + // tree. > + void Splay(const Key& key); > + > + class Node : public ZoneObject { > + public: > + Node(const Key& key, const Value& value) > + : key_(key), > + value_(value), > + left_(NULL), > + right_(NULL) { } > + Key key() { return key_; } > + Value value() { return value_; } > + Node* left() { return left_; } > + Node* right() { return right_; } > + private: > + friend class ZoneSplayTree; > + friend class Locator; > + Key key_; > + Value value_; > + Node* left_; > + Node* right_; > + }; > + > + // A locator provides access to a node in the tree without actually > + // exposing the node. > + class Locator { > + public: > + explicit Locator(Node* node) : node_(node) { } > + Locator() : node_(NULL) { } > + const Key& key() { return node_->key_; } > + Value& value() { return node_->value_; } > + void set_value(const Value& value) { node_->value_ = value; } > + inline void bind(Node* node) { node_ = node; } > + private: > + Node* node_; > + }; > + > + template <class Callback> > + void ForEach(Callback* c) { > + DoForEach<typename ZoneSplayTree<Config>::Node, Callback>(root_, c); > + } > + > + private: > + Node* root_; > +}; > + > + > } } // namespace v8::internal > > #endif // V8_ZONE_H_ > ======================================= > --- /branches/bleeding_edge/test/cctest/test-regexp.cc Tue Jul 7 01:11:19 > 2009 > +++ /branches/bleeding_edge/test/cctest/test-regexp.cc Wed Jul 29 01:10:19 > 2009 > @@ -35,7 +35,7 @@ > #include "zone-inl.h" > #include "parser.h" > #include "ast.h" > -#include "jsregexp-inl.h" > +#include "jsregexp.h" > #include "regexp-macro-assembler.h" > #include "regexp-macro-assembler-irregexp.h" > #ifdef V8_TARGET_ARCH_ARM > ======================================= > --- /branches/bleeding_edge/tools/process-heap-prof.py Mon Jul 20 02:38:44 > 2009 > +++ /branches/bleeding_edge/tools/process-heap-prof.py Wed Jul 29 01:10:19 > 2009 > @@ -35,10 +35,14 @@ > # $ ./shell --log-gc script.js > # $ tools/process-heap-prof.py v8.log | hp2ps -c > script-heap-graph.ps > # ('-c' enables color, see hp2ps manual page for more options) > +# or > +# $ tools/process-heap-prof.py --js-cons-profile v8.log | hp2ps -c > > script-heap-graph.ps > +# to get JS constructor profile > + > > import csv, sys, time > > -def process_logfile(filename): > +def process_logfile(filename, itemname): > first_call_time = None > sample_time = 0.0 > sampling = False > @@ -63,11 +67,14 @@ > elif row[0] == 'heap-sample-end' and row[1] == 'Heap': > print('END_SAMPLE %.2f' % sample_time) > sampling = False > - elif row[0] == 'heap-sample-item' and sampling: > + elif row[0] == itemname and sampling: > print('%s %d' % (row[1], int(row[3]))) > finally: > logfile.close() > except: > sys.exit('can\'t open %s' % filename) > > -process_logfile(sys.argv[1]) > +if sys.argv[1] == '--js-cons-profile': > + process_logfile(sys.argv[2], 'heap-js-cons-item') > +else: > + process_logfile(sys.argv[1], 'heap-sample-item') > ======================================= > --- /branches/bleeding_edge/tools/visual_studio/v8_base.vcproj Thu Jul 16 > 22:37:09 2009 > +++ /branches/bleeding_edge/tools/visual_studio/v8_base.vcproj Wed Jul 29 > 01:10:19 2009 > @@ -519,10 +519,6 @@ > <File > > RelativePath="..\..\src\ia32\jump-target-ia32.cc" > > > - </File> > - <File > - RelativePath="..\..\src\jsregexp-inl.h" > - > > </File> > <File > RelativePath="..\..\src\jsregexp.cc" > ======================================= > --- /branches/bleeding_edge/tools/visual_studio/v8_base_arm.vcproj Thu > Jul > 16 22:37:09 2009 > +++ /branches/bleeding_edge/tools/visual_studio/v8_base_arm.vcproj Wed > Jul > 29 01:10:19 2009 > @@ -519,10 +519,6 @@ > <File > RelativePath="..\..\src\arm\jump-target-arm.cc" > > > - </File> > - <File > - RelativePath="..\..\src\jsregexp-inl.h" > - > > </File> > <File > RelativePath="..\..\src\jsregexp.cc" > > > > --~--~---------~--~----~------------~-------~--~----~ v8-dev mailing list [email protected] http://groups.google.com/group/v8-dev -~----------~----~----~----~------~----~------~--~---
