I'm really sorry. It's because 'betterthangrep' ack tool skipped those files when searching for 'jsregexp-inl'. Good old grep found them.
On Fri, Jul 31, 2009 at 09:05, Kasper Lund<[email protected]> wrote: > 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 -~----------~----~----~----~------~----~------~--~---
