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 -~----------~----~----~----~------~----~------~--~---
