This is the mail archive of the
libstdc++@gcc.gnu.org
mailing list for the libstdc++ project.
[profile-stdlib] PATCH: Add three diagnostics and implement cost factor parameterization
- From: Changhee Jung <haemil99 at gmail dot com>
- To: libstdc++ at gcc dot gnu dot org
- Cc: Silvius Rus <rus at google dot com>, Nate Clark <ntclark at cc dot gatech dot edu>
- Date: Sun, 6 Dec 2009 22:38:29 -0500
- Subject: [profile-stdlib] PATCH: Add three diagnostics and implement cost factor parameterization
Hello libstdc++ maintainers,
The attached patch implements the following in the profile-stdlib branch:
1) New diagnostics
- list-to-vector; if data is inserted at the end of the list and
iteration operation is common, vector is better.
- list-to-slist; slist is more likely to fit in a cache line due to
less memory usage.
- list-to-set; if a find operation, 'std::find', is frequently used
in the list, set is better.
2) Cost factor parameterization; constant factors of the cost models
for diagnostics can be read from a file, "libstdcxx-profile.conf" or
environment variables.
There is an issue related to thel instrumentation of 'std::find'.
It seems that 'bits/stl_algo.h' was modified for the parallel mode so
that its functions declared in the namespace of '_GLIBCXX_STD_P' can
be used instead of original functions in the release mode.
Currently, I did the same thing, conditional compilation stuff, to
hide the original 'find' function under its wrapper function.
This inevitably causes a modification to the original 'bits/stl_algo.h'.
Alternatively, it is possible to duplicate the 'bits/stl_algo.h' in
'profile/stl_algo.h' and modify the copy to avoid any intrusion from
the profile mode to the release mode.
It would be appreciated if you come up with a better idea to deal with this.
Thank you,
Changhee
Index: libstdc++-v3/include/Makefile.in
===================================================================
--- libstdc++-v3/include/Makefile.in (revision 155023)
+++ libstdc++-v3/include/Makefile.in (working copy)
@@ -1014,6 +1014,9 @@
profile_srcdir = ${glibcxx_srcdir}/include/profile
profile_builddir = ./profile
profile_headers = \
+ ${profile_srcdir}/algo.h \
+ ${profile_srcdir}/algorithm \
+ ${profile_srcdir}/iterator_tracker.h \
${profile_srcdir}/base.h \
${profile_srcdir}/unordered_map \
${profile_srcdir}/unordered_set \
@@ -1041,7 +1044,10 @@
${profile_impl_srcdir}/profiler_state.h \
${profile_impl_srcdir}/profiler_trace.h \
${profile_impl_srcdir}/profiler_vector_size.h \
- ${profile_impl_srcdir}/profiler_vector_to_list.h
+ ${profile_impl_srcdir}/profiler_vector_to_list.h \
+ ${profile_impl_srcdir}/profiler_list_to_slist.h \
+ ${profile_impl_srcdir}/profiler_list_to_vector.h \
+ ${profile_impl_srcdir}/profiler_list_to_set.h
@GLIBCXX_C_HEADERS_EXTRA_FALSE@c_base_headers_extra =
Index: libstdc++-v3/include/std/algorithm
===================================================================
--- libstdc++-v3/include/std/algorithm (revision 155023)
+++ libstdc++-v3/include/std/algorithm (working copy)
@@ -65,4 +65,8 @@
# include <parallel/algorithm>
#endif
+#ifdef _GLIBCXX_PROFILE
+# include <profile/algorithm>
+#endif
+
#endif /* _GLIBCXX_ALGORITHM */
Index: libstdc++-v3/include/profile/algorithm
===================================================================
--- libstdc++-v3/include/profile/algorithm (revision 0)
+++ libstdc++-v3/include/profile/algorithm (revision 0)
@@ -0,0 +1,38 @@
+// Algorithm extensions -*- C++ -*-
+
+// Copyright (C) 2009
+// Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library. This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+// GNU General Public License for more details.
+
+// Under Section 7 of GPL version 3, you are granted additional
+// permissions described in the GCC Runtime Library Exception, version
+// 3.1, as published by the Free Software Foundation.
+
+// You should have received a copy of the GNU General Public License and
+// a copy of the GCC Runtime Library Exception along with this program;
+// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
+// <http://www.gnu.org/licenses/>.
+
+/** @file parallel/algorithm
+ * This file is a GNU extension to the Standard C++ Library.
+ */
+
+#ifndef _PROFILE_ALGORITHM
+#define _PROFILE_ALGORITHM 1
+
+#pragma GCC system_header
+
+#include <algorithm>
+#include <profile/algo.h>
+
+#endif
Index: libstdc++-v3/include/profile/iterator_tracker.h
===================================================================
--- libstdc++-v3/include/profile/iterator_tracker.h (revision 0)
+++ libstdc++-v3/include/profile/iterator_tracker.h (revision 0)
@@ -0,0 +1,271 @@
+#ifndef _GLIBCXX_ITERATOR_TRACKER
+#define _GLIBCXX_ITERATOR_TRACKER 1
+
+namespace std
+{
+namespace __profile
+{
+
+template<typename _Iterator, typename _Sequence>
+class __iterator_tracker
+{
+ typedef __iterator_tracker _Self;
+ // The underlying iterator
+ _Iterator _M_current;
+ // The underlying data structure
+ const _Sequence* _M_ds;
+ typedef std::iterator_traits<_Iterator> _Traits;
+
+ public:
+ typedef _Iterator _Base_iterator;
+ typedef typename _Traits::iterator_category iterator_category;
+ typedef typename _Traits::value_type value_type;
+ typedef typename _Traits::difference_type difference_type;
+ typedef typename _Traits::reference reference;
+ typedef typename _Traits::pointer pointer;
+
+ __iterator_tracker() : _M_current(), _M_ds(0) { }
+ __iterator_tracker(const _Iterator& __i, const _Sequence* seq)
+ : _M_current(__i), _M_ds(seq) { }
+ __iterator_tracker(const __iterator_tracker& __x)
+ : _M_current(__x._M_current), _M_ds(__x._M_ds) { }
+ template<typename _MutableIterator>
+ __iterator_tracker(const __iterator_tracker<_MutableIterator, typename __gnu_cxx::__enable_if<(std::__are_same<_MutableIterator, typename _Sequence::iterator::_Base_iterator>::__value), _Sequence>::__type>& __x)
+ : _M_current(__x.base()), _M_ds(__x._M_get_sequence()) { }
+
+ _Iterator
+ base() const { return _M_current; }
+ /**
+ * @brief Conversion to underlying non-debug iterator to allow
+ * better interaction with non-profile containers.
+ */
+ operator _Iterator() const { return _M_current; }
+
+ pointer
+ operator->() const { return &*_M_current; }
+
+ __iterator_tracker&
+ operator++()
+ {
+ _M_ds->_M_profile_iterate();
+ ++_M_current;
+ return *this;
+ }
+
+ __iterator_tracker&
+ operator++(int)
+ {
+ _M_ds->_M_profile_iterate();
+ __iterator_tracker __tmp(*this);
+ ++_M_current;
+ return __tmp;
+ }
+
+ __iterator_tracker&
+ operator--()
+ {
+ _M_ds->_M_profile_iterate(1);
+ --_M_current;
+ return *this;
+ }
+
+ __iterator_tracker&
+ operator--(int)
+ {
+ _M_ds->_M_profile_iterate(1);
+ __iterator_tracker __tmp(*this);
+ --_M_current;
+ return __tmp;
+ }
+
+ __iterator_tracker&
+ operator=(const __iterator_tracker& __x)
+ {
+ _M_current = __x._M_current;
+ return *this;
+ }
+
+ reference
+ operator*() const
+ {
+ return *_M_current;
+ }
+
+ // ------ Random access iterator requirements ------
+ reference
+ operator[](const difference_type& __n) const
+ {
+ return _M_current[__n];
+ }
+
+ __iterator_tracker&
+ operator+=(const difference_type& __n)
+ {
+ _M_current += __n;
+ return *this;
+ }
+
+ __iterator_tracker
+ operator+(const difference_type& __n) const
+ {
+ __iterator_tracker __tmp(*this);
+ __tmp += __n;
+ return __tmp;
+ }
+
+ __iterator_tracker&
+ operator-=(const difference_type& __n)
+ {
+ _M_current += -__n;
+ return *this;
+ }
+
+ __iterator_tracker
+ operator-(const difference_type& __n) const
+ {
+ __iterator_tracker __tmp(*this);
+ __tmp -= __n;
+ return __tmp;
+ }
+
+ void
+ _M_find()
+ {
+ _M_ds->_M_profile_find();
+ }
+
+ const _Sequence*
+ _M_get_sequence() const
+ {
+ return static_cast<const _Sequence*>(_M_ds);
+ }
+};
+
+template<typename _IteratorL, typename _IteratorR, typename _Sequence>
+inline bool
+operator==(const __iterator_tracker<_IteratorL, _Sequence>& __lhs,
+ const __iterator_tracker<_IteratorR, _Sequence>& __rhs)
+{
+ return __lhs.base() == __rhs.base();
+}
+
+template<typename _Iterator, typename _Sequence>
+inline bool
+operator==(const __iterator_tracker<_Iterator, _Sequence>& __lhs,
+ const __iterator_tracker<_Iterator, _Sequence>& __rhs)
+{
+ return __lhs.base() == __rhs.base();
+}
+
+template<typename _IteratorL, typename _IteratorR, typename _Sequence>
+inline bool
+operator!=(const __iterator_tracker<_IteratorL, _Sequence>& __lhs,
+ const __iterator_tracker<_IteratorR, _Sequence>& __rhs)
+{
+ return __lhs.base() != __rhs.base();
+}
+
+template<typename _Iterator, typename _Sequence>
+inline bool
+operator!=(const __iterator_tracker<_Iterator, _Sequence>& __lhs,
+ const __iterator_tracker<_Iterator, _Sequence>& __rhs)
+{
+ return __lhs.base() != __rhs.base();
+}
+
+template<typename _IteratorL, typename _IteratorR, typename _Sequence>
+inline bool
+operator<(const __iterator_tracker<_IteratorL, _Sequence>& __lhs,
+ const __iterator_tracker<_IteratorR, _Sequence>& __rhs)
+{
+ return __lhs.base() < __rhs.base();
+}
+
+template<typename _Iterator, typename _Sequence>
+inline bool
+operator<(const __iterator_tracker<_Iterator, _Sequence>& __lhs,
+ const __iterator_tracker<_Iterator, _Sequence>& __rhs)
+{
+ return __lhs.base() < __rhs.base();
+}
+
+template<typename _IteratorL, typename _IteratorR, typename _Sequence>
+inline bool
+operator<=(const __iterator_tracker<_IteratorL, _Sequence>& __lhs,
+ const __iterator_tracker<_IteratorR, _Sequence>& __rhs)
+{
+ return __lhs.base() <= __rhs.base();
+}
+
+template<typename _Iterator, typename _Sequence>
+inline bool
+operator<=(const __iterator_tracker<_Iterator, _Sequence>& __lhs,
+ const __iterator_tracker<_Iterator, _Sequence>& __rhs)
+{
+ return __lhs.base() <= __rhs.base();
+}
+
+template<typename _IteratorL, typename _IteratorR, typename _Sequence>
+inline bool
+operator>(const __iterator_tracker<_IteratorL, _Sequence>& __lhs,
+ const __iterator_tracker<_IteratorR, _Sequence>& __rhs)
+{
+ return __lhs.base() > __rhs.base();
+}
+
+template<typename _Iterator, typename _Sequence>
+inline bool
+operator>(const __iterator_tracker<_Iterator, _Sequence>& __lhs,
+ const __iterator_tracker<_Iterator, _Sequence>& __rhs)
+{
+ return __lhs.base() > __rhs.base();
+}
+
+template<typename _IteratorL, typename _IteratorR, typename _Sequence>
+inline bool
+operator>=(const __iterator_tracker<_IteratorL, _Sequence>& __lhs,
+ const __iterator_tracker<_IteratorR, _Sequence>& __rhs)
+{
+ return __lhs.base() >= __rhs.base();
+}
+
+template<typename _Iterator, typename _Sequence>
+inline bool
+operator>=(const __iterator_tracker<_Iterator, _Sequence>& __lhs,
+ const __iterator_tracker<_Iterator, _Sequence>& __rhs)
+{
+ return __lhs.base() >= __rhs.base();
+}
+
+// _GLIBCXX_RESOLVE_LIB_DEFECTS
+// According to the resolution of DR179 not only the various comparison
+// operators but also operator- must accept mixed iterator/const_iterator
+// parameters.
+ template<typename _IteratorL, typename _IteratorR, typename _Sequence>
+ inline typename __iterator_tracker<_IteratorL, _Sequence>::difference_type
+ operator-(const __iterator_tracker<_IteratorL, _Sequence>& __lhs,
+ const __iterator_tracker<_IteratorR, _Sequence>& __rhs)
+{
+ return __lhs.base() - __rhs.base();
+}
+
+template<typename _Iterator, typename _Sequence>
+inline typename __iterator_tracker<_Iterator, _Sequence>::difference_type
+operator-(const __iterator_tracker<_Iterator, _Sequence>& __lhs,
+ const __iterator_tracker<_Iterator, _Sequence>& __rhs)
+{
+ return __lhs.base() - __rhs.base();
+}
+
+template<typename _Iterator, typename _Sequence>
+inline __iterator_tracker<_Iterator, _Sequence>
+operator+(typename __iterator_tracker<_Iterator,_Sequence>::difference_type
+ __n,
+ const __iterator_tracker<_Iterator, _Sequence>& __i)
+{
+ return __i + __n;
+}
+
+} // namespace __profile
+} // namespace std
+#endif
Index: libstdc++-v3/include/profile/impl/profiler_list_to_set.h
===================================================================
--- libstdc++-v3/include/profile/impl/profiler_list_to_set.h (revision 0)
+++ libstdc++-v3/include/profile/impl/profiler_list_to_set.h (revision 0)
@@ -0,0 +1,283 @@
+// -*- C++ -*-
+//
+// Copyright (C) 2008 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library. This library is free
+// software; you can redistribute it and/or modify it under the terms
+// of the GNU General Public License as published by the Free Software
+// Foundation; either version 2, or (at your option) any later
+// version.
+
+// This library is distributed in the hope that it will be useful, but
+// WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+// General Public License for more details.
+
+// You should have received a copy of the GNU General Public License
+// along with this library; see the file COPYING. If not, write to
+// the Free Software Foundation, 59 Temple Place - Suite 330, Boston,
+// MA 02111-1307, USA.
+
+// As a special exception, you may use this file as part of a free
+// software library without restriction. Specifically, if other files
+// instantiate templates or use macros or inline functions from this
+// file, or you compile this file and link it with other files to
+// produce an executable, this file does not by itself cause the
+// resulting executable to be covered by the GNU General Public
+// License. This exception does not however invalidate any other
+// reasons why the executable file might be covered by the GNU General
+// Public License.
+
+/** @file profile/impl/profiler_list_to_set.h
+ * @brief diagnostics for list to set.
+ */
+
+// Written by Changhee Jung.
+
+#ifndef PROFCXX_PROFILER_LIST_TO_SET_H__
+#define PROFCXX_PROFILER_LIST_TO_SET_H__ 1
+
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+#include <cstdio>
+#include <cstdlib>
+#include <cstring>
+#else
+#include <stdio.h>
+#include <stdint.h>
+#include <string.h>
+#endif
+#include <string>
+#include <sstream>
+#include <math.h>
+#include "profile/impl/profiler.h"
+#include "profile/impl/profiler_node.h"
+#include "profile/impl/profiler_trace.h"
+
+static inline int __log2(size_t __size)
+{
+ for (int __bit_count = sizeof(size_t) - 1; __bit_count >= 0; --__bit_count) {
+ if ((2 << __bit_count) & __size) {
+ return __bit_count;
+ }
+ }
+ return 0;
+}
+
+namespace __cxxprof_impl
+{
+
+inline float __set_insert_cost(size_t __size)
+{
+ return __tables<0>::__set_insert_cost_factor * static_cast<float>(
+ __log2(__size));
+}
+
+inline float __set_find_cost(size_t __size)
+{
+ return __tables<0>::__set_find_cost_factor * static_cast<float>(
+ __log2(__size));
+}
+
+
+/** @brief A list-to-set instrumentation line in the object table. */
+class __list2set_info: public __object_info_base
+{
+ public:
+ __list2set_info()
+ : _M_insert(0), _M_find(0), _M_list_cost(0.0),
+ _M_set_cost(0.0), _M_valid(true) {}
+ __list2set_info(__stack_t __stack)
+ : __object_info_base(__stack), _M_insert(0), _M_find(0),
+ _M_list_cost(0.0), _M_set_cost(0.0), _M_valid(true) {}
+ virtual ~__list2set_info() {}
+ __list2set_info(const __list2set_info& __o);
+ void __merge(const __list2set_info& __o);
+ void __write(FILE* __f) const;
+ float __magnitude() const { return _M_list_cost - _M_set_cost; }
+ const char* __advice() const { return "change std::list to std::set"; }
+ float __list_cost() { return _M_list_cost; }
+ void __set_list_cost(float __lc) { _M_list_cost = __lc; }
+ void __set_set_cost(float __vc) { _M_set_cost = __vc; }
+ bool __is_valid() { return _M_valid; }
+ void __set_invalid() { _M_valid = false; }
+ void __opr_insert(size_t __size, size_t __count);
+ void __opr_find(size_t __size);
+
+private:
+ size_t _M_insert;
+ size_t _M_find;
+ float _M_list_cost;
+ float _M_set_cost;
+ bool _M_valid;
+};
+
+inline __list2set_info::__list2set_info(const __list2set_info& __o)
+ : __object_info_base(__o)
+{
+ _M_insert = __o._M_insert;
+ _M_find = __o._M_find;
+ _M_set_cost = __o._M_set_cost;
+ _M_list_cost = __o._M_list_cost;
+ _M_valid = __o._M_valid;
+}
+
+inline void __list2set_info::__merge(const __list2set_info& __o)
+{
+ _M_insert += __o._M_insert;
+ _M_find += __o._M_find;
+ _M_set_cost += __o._M_set_cost;
+ _M_list_cost += __o._M_list_cost;
+ _M_valid &= __o._M_valid;
+}
+
+inline void __list2set_info::__opr_insert(size_t __size, size_t __count)
+{
+ _M_insert += __count;
+ _M_list_cost += __count * __tables<0>::__list_insert_cost;
+ _M_set_cost += __count * __set_insert_cost(__size);
+}
+
+inline void __list2set_info::__opr_find(size_t __size)
+{
+ _M_insert += 1;
+ // Use avererage case complexity rathen than worst case one
+ _M_list_cost += 3.0/4.0*__size * __tables<0>::__list_find_cost;
+ _M_set_cost += __set_find_cost(__size);
+}
+
+class __list2set_stack_info: public __list2set_info {
+ public:
+ __list2set_stack_info(const __list2set_info& __o)
+ : __list2set_info(__o) {}
+};
+
+class __trace_list_to_set
+ : public __trace_base<__list2set_info, __list2set_stack_info>
+{
+ public:
+ __trace_list_to_set();
+ ~__trace_list_to_set() {}
+
+ // Insert a new node at construct with object, callstack and initial size.
+ void __insert(__object_t __obj, __stack_t __stack);
+ // Call at destruction/clean to set container final size.
+ void __destruct(const void* __obj);
+
+ // Find the node in the live map.
+ __list2set_info* __find(const void* __obj);
+
+ // Collect cost of operations.
+ void __opr_insert(const void* __obj, size_t __size, size_t __count);
+ void __invalid_operator(const void* __obj);
+ void __opr_find(const void* __obj, size_t __size);
+};
+
+inline __trace_list_to_set::__trace_list_to_set()
+ : __trace_base<__list2set_info, __list2set_stack_info>()
+{
+ __id = "list-to-set";
+}
+
+inline void __trace_list_to_set::__insert(__object_t __obj,
+ __stack_t __stack)
+{
+ __add_object(__obj, __list2set_info(__stack));
+}
+
+inline void __list2set_info::__write(FILE* __f) const
+{
+
+ fprintf(__f, "%Zu %Zu %.0f %.0f %s\n",
+ _M_insert, _M_find, _M_list_cost, _M_set_cost,
+ _M_valid ? "valid" : "invalid");
+}
+
+inline void __trace_list_to_set::__destruct(const void* __obj)
+{
+ if (!__is_on())
+ return;
+
+ __list2set_info* __res = __get_object_info(__obj);
+ if (!__res)
+ return;
+
+ __retire_object(__obj);
+}
+
+inline void __trace_list_to_set::__opr_insert(const void* __obj, size_t __size,
+ size_t __count)
+{
+ __list2set_info* __res = __get_object_info(__obj);
+ if (__res)
+ __res->__opr_insert(__size, __count);
+}
+
+inline void __trace_list_to_set::__invalid_operator(const void* __obj)
+{
+ __list2set_info* __res = __get_object_info(__obj);
+ if (__res)
+ __res->__set_invalid();
+}
+
+inline void __trace_list_to_set::__opr_find(const void* __obj, size_t __size)
+{
+ __list2set_info* __res = __get_object_info(__obj);
+ if (__res) {
+ __res->__opr_find(__size);
+ }
+}
+
+//////////////////////////////////////////////////////////////////////////////
+// Initialization and report.
+//////////////////////////////////////////////////////////////////////////////
+
+inline void __trace_list_to_set_init()
+{
+ __tables<0>::_S_list_to_set = new __trace_list_to_set();
+}
+
+inline void __trace_list_to_set_report(FILE* __f,
+ __warning_vector_t& __warnings)
+{
+ if (__tables<0>::_S_list_to_set) {
+ __tables<0>::_S_list_to_set->__collect_warnings(__warnings);
+ __tables<0>::_S_list_to_set->__write(__f);
+ }
+}
+
+//////////////////////////////////////////////////////////////////////////////
+// Implementations of instrumentation hooks.
+//////////////////////////////////////////////////////////////////////////////
+
+inline void __trace_list_to_set_construct(const void* __obj)
+{
+ if (!__profcxx_init()) return;
+
+ __tables<0>::_S_list_to_set->__insert(__obj, __get_stack());
+}
+
+inline void __trace_list_to_set_destruct(const void* __obj)
+{
+
+ if (!__profcxx_init()) return;
+
+ __tables<0>::_S_list_to_set->__destruct(__obj);
+}
+
+inline void __trace_list_to_set_insert(const void* __obj, size_t __size,
+ size_t __count = 1)
+{
+ if (!__profcxx_init()) return;
+
+ __tables<0>::_S_list_to_set->__opr_insert(__obj, __size, __count);
+}
+
+inline void __trace_list_to_set_find(const void* __obj, size_t __size)
+{
+ if (!__profcxx_init()) return;
+
+ __tables<0>::_S_list_to_set->__opr_find(__obj, __size);
+}
+
+} // namespace __cxxprof_impl
+#endif /* PROFCXX_PROFILER_LIST_TO_SET_H__ */
Index: libstdc++-v3/include/profile/impl/profiler_list_to_slist.h
===================================================================
--- libstdc++-v3/include/profile/impl/profiler_list_to_slist.h (revision 0)
+++ libstdc++-v3/include/profile/impl/profiler_list_to_slist.h (revision 0)
@@ -0,0 +1,190 @@
+// -*- C++ -*-
+//
+// Copyright (C) 2009 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library. This library is free
+// software; you can redistribute it and/or modify it under the terms
+// of the GNU General Public License as published by the Free Software
+// Foundation; either version 2, or (at your option) any later
+// version.
+
+// This library is distributed in the hope that it will be useful, but
+// WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+// General Public License for more details.
+
+// You should have received a copy of the GNU General Public License
+// along with this library; see the file COPYING. If not, write to
+// the Free Software Foundation, 59 Temple Place - Suite 330, Boston,
+// MA 02111-1307, USA.
+
+// As a special exception, you may use this file as part of a free
+// software library without restriction. Specifically, if other files
+// instantiate templates or use macros or inline functions from this
+// file, or you compile this file and link it with other files to
+// produce an executable, this file does not by itself cause the
+// resulting executable to be covered by the GNU General Public
+// License. This exception does not however invalidate any other
+// reasons why the executable file might be covered by the GNU General
+// Public License.
+
+/** @file profile/impl/profiler_list_to_slist.h
+ * @brief Diagnostics for list to slist.
+ */
+
+// Written by Changhee Jung.
+
+#ifndef PROFCXX_PROFILER_LIST_TO_SLIST_H
+#define PROFCXX_PROFILER_LIST_TO_SLIST_H 1
+
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+#include <cstdlib>
+#include <cstdio>
+#include <cstring>
+#else
+#include <stdlib.h>
+#include <stdio.h>
+#include <string.h>
+#endif
+#include "profile/impl/profiler.h"
+#include "profile/impl/profiler_node.h"
+#include "profile/impl/profiler_trace.h"
+
+namespace __cxxprof_impl
+{
+
+class __list2slist_info: public __object_info_base
+{
+ public:
+ __list2slist_info() : _M_rewind(false), _M_operations(0) {}
+ __list2slist_info(__stack_t __stack)
+ : _M_rewind(false), _M_operations(0),__object_info_base(__stack) {}
+ virtual ~__list2slist_info() {}
+ __list2slist_info(const __list2slist_info& __o) : __object_info_base(__o)
+ { _M_rewind = __o._M_rewind; _M_operations = __o._M_operations; }
+ // XXX: the magnitude should be multiplied with a constant factor F,
+ // where F is 1 when the malloc size class of list nodes is different
+ // from the malloc size class of slist nodes. When they fall into the same
+ // class, the only slist benefit is from having to set fewer links, so
+ // the factor F should be much smaller, closer to 0 than to 1.
+ // This could be implemented by passing the size classes in the config file.
+ // For now, we always assume F to be 1.
+ float __magnitude() const
+ { if (!_M_rewind) return _M_operations; else return 0; }
+ void __merge(const __list2slist_info& __o) {};
+ void __write(FILE* __f) const;
+ const char* __advice() const
+ { return "change std::list to std::forward_list or __gnu_cxx::slist"; }
+ void __opr_rewind() { _M_rewind = true; _M_valid = false;}
+ void __record_operation() { _M_operations++; }
+ bool __has_rewind() { return _M_rewind; }
+
+private:
+ bool _M_rewind;
+ size_t _M_operations;
+};
+
+class __list2slist_stack_info: public __list2slist_info {
+ public:
+ __list2slist_stack_info(const __list2slist_info& __o)
+ : __list2slist_info(__o) {}
+};
+
+class __trace_list_to_slist
+ : public __trace_base<__list2slist_info, __list2slist_stack_info>
+{
+ public:
+ ~__trace_list_to_slist() {}
+ __trace_list_to_slist()
+ : __trace_base<__list2slist_info, __list2slist_stack_info>()
+ { __id = "list-to-slist"; }
+ void __opr_rewind(const void* __obj);
+ void __record_operation(const void* __obj);
+ void __insert(const __object_t __obj, __stack_t __stack)
+ { __add_object(__obj, __list2slist_info(__stack)); }
+ void __destruct(const void* __obj);
+};
+
+inline void __list2slist_info::__write(FILE* __f) const
+{
+ fprintf(__f, "%s\n", _M_rewind ? "invalid" : "valid");
+}
+
+inline void __trace_list_to_slist::__destruct(const void* __obj)
+{
+ if (!__is_on())
+ return;
+
+ __list2slist_info* __res = __get_object_info(__obj);
+ if (!__res)
+ return;
+
+ __retire_object(__obj);
+}
+
+//////////////////////////////////////////////////////////////////////////////
+// Initialization and report.
+//////////////////////////////////////////////////////////////////////////////
+
+inline void __trace_list_to_slist_init()
+{
+ __tables<0>::_S_list_to_slist = new __trace_list_to_slist();
+}
+
+inline void __trace_list_to_slist_report(FILE* __f,
+ __warning_vector_t& __warnings)
+{
+ if (__tables<0>::_S_list_to_slist) {
+ __tables<0>::_S_list_to_slist->__collect_warnings(__warnings);
+ __tables<0>::_S_list_to_slist->__write(__f);
+ }
+}
+
+inline void __trace_list_to_slist::__opr_rewind(const void* __obj)
+{
+ __list2slist_info* __res = __get_object_info(__obj);
+ if (__res)
+ __res->__opr_rewind();
+}
+
+inline void __trace_list_to_slist::__record_operation(const void* __obj)
+{
+ __list2slist_info* __res = __get_object_info(__obj);
+ if (__res)
+ __res->__record_operation();
+}
+
+//////////////////////////////////////////////////////////////////////////////
+// Implementations of instrumentation hooks.
+//////////////////////////////////////////////////////////////////////////////
+
+inline void __trace_list_to_slist_rewind(const void* __obj)
+{
+ if (!__profcxx_init()) return;
+
+ __tables<0>::_S_list_to_slist->__opr_rewind(__obj);
+}
+
+inline void __trace_list_to_slist_operation(const void* __obj)
+{
+ if (!__profcxx_init()) return;
+
+ __tables<0>::_S_list_to_slist->__record_operation(__obj);
+}
+
+inline void __trace_list_to_slist_construct(const void* __obj)
+{
+ if (!__profcxx_init()) return;
+
+ __tables<0>::_S_list_to_slist->__insert(__obj, __get_stack());
+}
+
+inline void __trace_list_to_slist_destruct(const void* __obj)
+{
+ if (!__profcxx_init()) return;
+
+ __tables<0>::_S_list_to_slist->__destruct(__obj);
+}
+
+} // namespace __cxxprof_impl
+#endif /* PROFCXX_PROFILER_LIST_TO_SLIST_H */
Index: libstdc++-v3/include/profile/impl/profiler_trace.h
===================================================================
--- libstdc++-v3/include/profile/impl/profiler_trace.h (revision 155023)
+++ libstdc++-v3/include/profile/impl/profiler_trace.h (working copy)
@@ -54,6 +54,8 @@
#endif
#include <algorithm>
+#include <fstream>
+#include <string>
#include <utility>
#if defined _GLIBCXX_PROFILE_THREADS && defined HAVE_TLS
@@ -132,15 +134,24 @@
class __trace_map2umap;
class __trace_vector_size;
class __trace_vector_to_list;
+class __trace_list_to_slist;
+class __trace_list_to_vector;
+class __trace_list_to_set;
void __trace_vector_size_init();
void __trace_hashtable_size_init();
void __trace_hash_func_init();
void __trace_vector_to_list_init();
+void __trace_list_to_slist_init();
+void __trace_list_to_vector_init();
+void __trace_list_to_set_init();
void __trace_map_to_unordered_map_init();
void __trace_vector_size_report(FILE*, __warning_vector_t&);
void __trace_hashtable_size_report(FILE*, __warning_vector_t&);
void __trace_hash_func_report(FILE*, __warning_vector_t&);
void __trace_vector_to_list_report(FILE*, __warning_vector_t&);
+void __trace_list_to_slist_report(FILE*, __warning_vector_t&);
+void __trace_list_to_vector_report(FILE*, __warning_vector_t&);
+void __trace_list_to_set_report(FILE*, __warning_vector_t&);
void __trace_map_to_unordered_map_report(FILE*, __warning_vector_t&);
// Utility functions.
@@ -164,6 +175,33 @@
static __trace_map2umap* _S_map2umap;
static __trace_vector_size* _S_vector_size;
static __trace_vector_to_list* _S_vector_to_list;
+ static __trace_list_to_slist* _S_list_to_slist;
+ static __trace_list_to_vector* _S_list_to_vector;
+ static __trace_list_to_set* _S_list_to_set;
+
+ static float __vector_shift_cost_factor;
+ static float __vector_iterate_cost_factor;
+ static float __vector_resize_cost_factor;
+
+ static float __list_shift_cost_factor;
+ static float __list_iterate_cost_factor;
+ static float __list_resize_cost_factor;
+
+ static float __set_insert_cost_factor;
+ static float __set_find_cost_factor;
+
+ static float __list_insert_cost;
+ static float __list_find_cost ;
+
+ static float __map_insert_cost_factor ;
+ static float __map_erase_cost_factor ;
+ static float __map_find_cost_factor ;
+ static float __map_iterate_cost;
+
+ static float __umap_insert_cost;
+ static float __umap_erase_cost ;
+ static float __umap_find_cost ;
+ static float __umap_iterate_cost;
};
template <int _Unused>
@@ -176,7 +214,55 @@
__trace_vector_size* __tables<_Unused>::_S_vector_size = NULL;
template <int _Unused>
__trace_vector_to_list* __tables<_Unused>::_S_vector_to_list = NULL;
+template <int _Unused>
+__trace_list_to_slist* __tables<_Unused>::_S_list_to_slist = NULL;
+template <int _Unused>
+__trace_list_to_vector* __tables<_Unused>::_S_list_to_vector = NULL;
+template <int _Unused>
+__trace_list_to_set* __tables<_Unused>::_S_list_to_set = NULL;
+template <int _Unused>
+float __tables<_Unused>::__vector_shift_cost_factor = 1;
+template <int _Unused>
+float __tables<_Unused>::__vector_iterate_cost_factor = 1;
+template <int _Unused>
+float __tables<_Unused>::__vector_resize_cost_factor = 1;
+
+template <int _Unused>
+float __tables<_Unused>::__list_shift_cost_factor = 0;
+template <int _Unused>
+float __tables<_Unused>::__list_iterate_cost_factor = 10;
+template <int _Unused>
+float __tables<_Unused>::__list_resize_cost_factor = 0;
+
+template <int _Unused>
+float __tables<_Unused>::__set_insert_cost_factor = 1.2;
+template <int _Unused>
+float __tables<_Unused>::__set_find_cost_factor = 1.0;
+
+template <int _Unused>
+float __tables<_Unused>::__list_insert_cost = 1.0;
+template <int _Unused>
+float __tables<_Unused>::__list_find_cost = 1.0;
+
+template <int _Unused>
+float __tables<_Unused>::__map_insert_cost_factor = 1.5;
+template <int _Unused>
+float __tables<_Unused>::__map_erase_cost_factor = 1.5;
+template <int _Unused>
+float __tables<_Unused>::__map_find_cost_factor = 1;
+template <int _Unused>
+float __tables<_Unused>::__map_iterate_cost = 2.3;
+
+template <int _Unused>
+float __tables<_Unused>::__umap_insert_cost = 12.0;
+template <int _Unused>
+float __tables<_Unused>::__umap_erase_cost = 12.0;
+template <int _Unused>
+float __tables<_Unused>::__umap_find_cost = 10.0;
+template <int _Unused>
+float __tables<_Unused>::__umap_iterate_cost = 1.7;
+
/** @brief Storage for user defined parameters. Has only static fields. */
template <int _Unused=0>
class __settings {
@@ -439,7 +525,6 @@
size_t root_len = strlen(__settings<0>::_S_trace_file_name);
size_t ext_len = strlen(extension);
char* file_name = new char[root_len + 1 + ext_len + 1];
- char* p = file_name;
memcpy(file_name, __settings<0>::_S_trace_file_name, root_len);
*(file_name + root_len) = '.';
memcpy(file_name + root_len + 1, extension, ext_len + 1);
@@ -470,6 +555,9 @@
__trace_hashtable_size_report(__raw_file, __warnings);
__trace_hash_func_report(__raw_file, __warnings);
__trace_vector_to_list_report(__raw_file, __warnings);
+ __trace_list_to_slist_report(__raw_file, __warnings);
+ __trace_list_to_vector_report(__raw_file, __warnings);
+ __trace_list_to_set_report(__raw_file, __warnings);
__trace_map_to_unordered_map_report(__raw_file, __warnings);
fclose(__raw_file);
@@ -512,6 +600,82 @@
}
}
+inline void __read_cost_factors()
+{
+ std::string conf_file_name(__settings<0>::_S_trace_file_name);
+ conf_file_name += ".conf";
+
+ std::ifstream __conf_file( conf_file_name.c_str());
+
+ if (__conf_file.is_open()) {
+ std::string line;
+
+ while (getline ( __conf_file, line) ) {
+ std::string::size_type i = line.find_first_not_of ( " \t\n\v" );
+
+ if (line.length() <= 0 || line[i] == '#') {
+ // Skip empty lines or comments.
+ continue;
+ }
+
+ // Trim.
+ line.erase(remove(line.begin(), line.end(), ' '), line.end());
+ std::string::size_type pos = line.find("=");
+ std::string __factor_name = line.substr(0, pos);
+ std::string::size_type end = line.find_first_of(";\n");
+ std::string __factor_value = line.substr(pos + 1, end - pos);
+
+ setenv(__factor_name.c_str(), __factor_value.c_str(), 0);
+ }
+ }
+}
+
+inline void __set_cost_factors()
+{
+ char* __env_cost_factor;
+ if (__env_cost_factor = getenv("__vector_shift_cost_factor"))
+ __tables<0>::__vector_shift_cost_factor = atof(__env_cost_factor);
+ if (__env_cost_factor = getenv("__vector_iterate_cost_factor"))
+ __tables<0>::__vector_iterate_cost_factor = atof(__env_cost_factor);
+ if (__env_cost_factor = getenv("__vector_resize_cost_factor"))
+ __tables<0>::__vector_resize_cost_factor = atof(__env_cost_factor);
+
+ if (__env_cost_factor = getenv("__list_shift_cost_factor"))
+ __tables<0>::__list_shift_cost_factor = atof(__env_cost_factor);
+ if (__env_cost_factor = getenv("__list_iterate_cost_factor"))
+ __tables<0>::__list_iterate_cost_factor = atof(__env_cost_factor);
+ if (__env_cost_factor = getenv("__list_resize_cost_factor"))
+ __tables<0>::__list_resize_cost_factor = atof(__env_cost_factor);
+
+ if (__env_cost_factor = getenv("__set_insert_cost_factor"))
+ __tables<0>::__set_insert_cost_factor = atof(__env_cost_factor);
+ if (__env_cost_factor = getenv("__set_find_cost_factor"))
+ __tables<0>::__set_find_cost_factor = atof(__env_cost_factor);
+
+ if (__env_cost_factor = getenv("__list_insert_cost"))
+ __tables<0>::__list_insert_cost = atof(__env_cost_factor);
+ if (__env_cost_factor = getenv("__list_find_cost"))
+ __tables<0>::__list_find_cost = atof(__env_cost_factor);
+
+ if (__env_cost_factor = getenv("__map_insert_cost_factor"))
+ __tables<0>::__map_insert_cost_factor = atof(__env_cost_factor);
+ if (__env_cost_factor = getenv("__map_erase_cost_factor"))
+ __tables<0>::__map_erase_cost_factor = atof(__env_cost_factor);
+ if (__env_cost_factor = getenv("__map_find_cost_factor"))
+ __tables<0>::__map_find_cost_factor = atof(__env_cost_factor);
+ if (__env_cost_factor = getenv("__map_iterate_cost"))
+ __tables<0>::__map_iterate_cost = atof(__env_cost_factor);
+
+ if (__env_cost_factor = getenv("__umap_insert_cost"))
+ __tables<0>::__umap_insert_cost = atof(__env_cost_factor);
+ if (__env_cost_factor = getenv("__umap_erase_cost"))
+ __tables<0>::__umap_erase_cost = atof(__env_cost_factor);
+ if (__env_cost_factor = getenv("__umap_find_cost"))
+ __tables<0>::__umap_find_cost = atof(__env_cost_factor);
+ if (__env_cost_factor = getenv("__umap_iterate_cost"))
+ __tables<0>::__umap_iterate_cost = atof(__env_cost_factor);
+}
+
inline void __profcxx_init_unconditional()
{
__mutex<0>::__lock(__mutex<0>::__global_lock);
@@ -529,11 +693,16 @@
__set_max_stack_trace_depth();
__set_max_mem();
__set_trace_path();
+ __read_cost_factors();
+ __set_cost_factors();
__trace_vector_size_init();
__trace_hashtable_size_init();
__trace_hash_func_init();
__trace_vector_to_list_init();
+ __trace_list_to_slist_init();
+ __trace_list_to_vector_init();
+ __trace_list_to_set_init();
__trace_map_to_unordered_map_init();
atexit(__report);
Index: libstdc++-v3/include/profile/impl/profiler_vector_to_list.h
===================================================================
--- libstdc++-v3/include/profile/impl/profiler_vector_to_list.h (revision 155023)
+++ libstdc++-v3/include/profile/impl/profiler_vector_to_list.h (working copy)
@@ -28,8 +28,8 @@
// reasons why the executable file might be covered by the GNU General
// Public License.
-/** @file profile/impl/profiler_trace.h
- * @brief Data structures to represent profiling traces.
+/** @file profile/impl/profiler_vector_to_list.h
+ * @brief diagnostics for vector to list.
*/
// Written by Lixia Liu and Silvius Rus.
@@ -80,8 +80,9 @@
void __set_invalid() { _M_valid = false; }
void __opr_insert(size_t __pos, size_t __num);
- void __opr_iterate(size_t __num) { _M_iterate += __num; }
+ void __opr_iterate(size_t __num);
void __resize(size_t __from, size_t __to);
+ void __opr_find(size_t __size);
private:
size_t _M_shift_count;
@@ -123,6 +124,17 @@
_M_resize += __from;
}
+inline void __vector2list_info::__opr_iterate(size_t __num)
+{
+ _M_iterate += __num;
+}
+
+inline void __vector2list_info::__opr_find(size_t __size)
+{
+ // Use average case complexity
+ _M_iterate += 3.0 / 4.0 * __size;
+}
+
/** @brief A vector-to-list instrumentation line in the stack table. */
class __vector2list_stack_info: public __vector2list_info {
public:
@@ -153,6 +165,8 @@
void __resize(const void* __obj, size_t __from, size_t __to);
float __vector_cost(size_t __shift, size_t __iterate, size_t __resize);
float __list_cost(size_t __shift, size_t __iterate, size_t __resize);
+ void __opr_find(const void* __obj, size_t __size);
+
};
inline __trace_vector_to_list::__trace_vector_to_list()
@@ -176,25 +190,29 @@
// Cost model. XXX: get this from the cost model database instead.
// Vector operation cost:
// - Cost per shift: 1
-// - Cost per access: 1
+// - Cost per iterate: 1
// - Cost per resize: 1
// List operation cost:
// - Cost per shift: 0
-// - Cost per access: 10
+// - Cost per iterate: 10
// - Cost per resize: 0
inline float __trace_vector_to_list::__vector_cost(size_t __shift,
size_t __iterate,
size_t __resize)
{
- return __shift * 1 + __iterate * 1 + __resize * 1;
+ return __shift * __tables<0>::__vector_shift_cost_factor +
+ __iterate * __tables<0>::__vector_iterate_cost_factor +
+ __resize * __tables<0>::__vector_resize_cost_factor;
}
inline float __trace_vector_to_list::__list_cost(size_t __shift,
size_t __iterate,
size_t __resize)
{
- return __shift * 0 + __iterate * 10 + __resize * 0;
+ return __shift * __tables<0>::__list_shift_cost_factor +
+ __iterate * __tables<0>::__list_iterate_cost_factor +
+ __resize * __tables<0>::__list_resize_cost_factor;
}
inline void __trace_vector_to_list::__destruct(const void* __obj)
@@ -247,6 +265,14 @@
__res->__resize(__from, __to);
}
+inline void __trace_vector_to_list::__opr_find(const void* __obj,
+ size_t __size)
+{
+ __vector2list_info* __res = __get_object_info(__obj);
+ if (__res)
+ __res->__opr_find(__size);
+}
+
//////////////////////////////////////////////////////////////////////////////
// Initialization and report.
//////////////////////////////////////////////////////////////////////////////
@@ -292,7 +318,7 @@
}
-inline void __trace_vector_to_list_iterate(const void* __obj, size_t __num)
+inline void __trace_vector_to_list_iterate(const void* __obj, size_t __num = 1)
{
if (!__profcxx_init()) return;
@@ -314,5 +340,12 @@
__tables<0>::_S_vector_to_list->__resize(__obj, __from, __to);
}
+inline void __trace_vector_to_list_find(const void* __obj, size_t __size)
+{
+ if (!__profcxx_init()) return;
+
+ __tables<0>::_S_vector_to_list->__opr_find(__obj, __size);
+}
+
} // namespace __cxxprof_impl
#endif /* PROFCXX_PROFILER_VECTOR_TO_LIST_H__ */
Index: libstdc++-v3/include/profile/impl/profiler_list_to_vector.h
===================================================================
--- libstdc++-v3/include/profile/impl/profiler_list_to_vector.h (revision 0)
+++ libstdc++-v3/include/profile/impl/profiler_list_to_vector.h (revision 0)
@@ -0,0 +1,320 @@
+// -*- C++ -*-
+//
+// Copyright (C) 2009 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library. This library is free
+// software; you can redistribute it and/or modify it under the terms
+// of the GNU General Public License as published by the Free Software
+// Foundation; either version 2, or (at your option) any later
+// version.
+
+// This library is distributed in the hope that it will be useful, but
+// WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+// General Public License for more details.
+
+// You should have received a copy of the GNU General Public License
+// along with this library; see the file COPYING. If not, write to
+// the Free Software Foundation, 59 Temple Place - Suite 330, Boston,
+// MA 02111-1307, USA.
+
+// As a special exception, you may use this file as part of a free
+// software library without restriction. Specifically, if other files
+// instantiate templates or use macros or inline functions from this
+// file, or you compile this file and link it with other files to
+// produce an executable, this file does not by itself cause the
+// resulting executable to be covered by the GNU General Public
+// License. This exception does not however invalidate any other
+// reasons why the executable file might be covered by the GNU General
+// Public License.
+
+/** @file profile/impl/profiler_list_to_vector.h
+ * @brief diagnostics for list to vector.
+ */
+
+// Written by Changhee Jung.
+
+#ifndef PROFCXX_PROFILER_LIST_TO_VECTOR_H__
+#define PROFCXX_PROFILER_LIST_TO_VECTOR_H__ 1
+
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+#include <cstdio>
+#include <cstdlib>
+#include <cstring>
+#else
+#include <stdio.h>
+#include <stdint.h>
+#include <string.h>
+#endif
+#include <string>
+#include <sstream>
+#include "profile/impl/profiler.h"
+#include "profile/impl/profiler_node.h"
+#include "profile/impl/profiler_trace.h"
+
+namespace __cxxprof_impl
+{
+
+/** @brief A list-to-vector instrumentation line in the object table. */
+class __list2vector_info: public __object_info_base
+{
+ public:
+ __list2vector_info()
+ :_M_shift_count(0), _M_iterate(0), _M_resize(0), _M_list_cost(0),
+ _M_vector_cost(0), _M_valid(true), _M_max_size(0) {}
+ __list2vector_info(__stack_t __stack)
+ : __object_info_base(__stack), _M_shift_count(0), _M_iterate(0),
+ _M_resize(0), _M_list_cost(0), _M_vector_cost(0), _M_valid(true),
+ _M_max_size(0) {}
+ virtual ~__list2vector_info() {}
+ __list2vector_info(const __list2vector_info& __o);
+ void __merge(const __list2vector_info& __o);
+ void __write(FILE* __f) const;
+ float __magnitude() const { return _M_list_cost - _M_vector_cost; }
+ const char* __advice() const;
+ size_t __shift_count() { return _M_shift_count; }
+ size_t __iterate() { return _M_iterate; }
+ float __list_cost() { return _M_list_cost; }
+ size_t __resize() { return _M_resize; }
+ void __set_list_cost(float __lc) { _M_list_cost = __lc; }
+ void __set_vector_cost(float __vc) { _M_vector_cost = __vc; }
+ bool __is_valid() { return _M_valid; }
+ void __set_invalid() { _M_valid = false; }
+
+ void __opr_insert(size_t __shift, size_t __size);
+ void __opr_iterate(size_t __num) { _M_iterate += __num;}
+
+ void __resize(size_t __from, size_t __to);
+
+private:
+ size_t _M_shift_count;
+ size_t _M_iterate;
+ size_t _M_resize;
+ float _M_list_cost;
+ float _M_vector_cost;
+ bool _M_valid;
+ size_t _M_max_size;
+};
+
+inline __list2vector_info::__list2vector_info(const __list2vector_info& __o)
+ : __object_info_base(__o)
+{
+ _M_shift_count = __o._M_shift_count;
+ _M_iterate = __o._M_iterate;
+ _M_vector_cost = __o._M_vector_cost;
+ _M_list_cost = __o._M_list_cost;
+ _M_valid = __o._M_valid;
+ _M_resize = __o._M_resize;
+ _M_max_size = __o._M_max_size;
+}
+
+inline const char* __list2vector_info::__advice() const {
+ std::stringstream __sstream;
+ __sstream
+ << "change std::list to std::vector and its initial size from 0 to "
+ << _M_max_size;
+ return __sstream.str().c_str();
+}
+
+inline void __list2vector_info::__merge(const __list2vector_info& __o)
+{
+ _M_shift_count += __o._M_shift_count;
+ _M_iterate += __o._M_iterate;
+ _M_vector_cost += __o._M_vector_cost;
+ _M_list_cost += __o._M_list_cost;
+ _M_valid &= __o._M_valid;
+ _M_resize += __o._M_resize;
+ _M_max_size = __max( _M_max_size, __o._M_max_size);
+}
+
+inline void __list2vector_info::__opr_insert(size_t __shift, size_t __size)
+{
+ _M_shift_count += __shift;
+ _M_max_size = __max(_M_max_size, __size);
+}
+
+inline void __list2vector_info::__resize(size_t __from, size_t __to)
+{
+ _M_resize += __from;
+}
+
+class __list2vector_stack_info: public __list2vector_info {
+ public:
+ __list2vector_stack_info(const __list2vector_info& __o)
+ : __list2vector_info(__o) {}
+};
+
+class __trace_list_to_vector
+ : public __trace_base<__list2vector_info, __list2vector_stack_info>
+{
+ public:
+ __trace_list_to_vector();
+ ~__trace_list_to_vector() {}
+
+ // Insert a new node at construct with object, callstack and initial size.
+ void __insert(__object_t __obj, __stack_t __stack);
+ // Call at destruction/clean to set container final size.
+ void __destruct(const void* __obj);
+
+ // Find the node in the live map.
+ __list2vector_info* __find(const void* __obj);
+
+ // Collect cost of operations.
+ void __opr_insert(const void* __obj, size_t __shift, size_t __size);
+ void __opr_iterate(const void* __obj, size_t __num);
+ void __invalid_operator(const void* __obj);
+ void __resize(const void* __obj, size_t __from, size_t __to);
+ float __vector_cost(size_t __shift, size_t __iterate);
+ float __list_cost(size_t __shift, size_t __iterate);
+};
+
+inline __trace_list_to_vector::__trace_list_to_vector()
+ : __trace_base<__list2vector_info, __list2vector_stack_info>()
+{
+ __id = "list-to-vector";
+}
+
+inline void __trace_list_to_vector::__insert(__object_t __obj,
+ __stack_t __stack)
+{
+ __add_object(__obj, __list2vector_info(__stack));
+}
+
+inline void __list2vector_info::__write(FILE* __f) const
+{
+ fprintf(__f, "%Zu %Zu %Zu %.0f %.0f\n",
+ _M_shift_count, _M_resize, _M_iterate, _M_vector_cost, _M_list_cost);
+}
+
+inline float __trace_list_to_vector::__vector_cost(size_t __shift,
+ size_t __iterate)
+{
+ // The resulting vector will use a 'reserve' method.
+ return __shift * __tables<0>::__vector_shift_cost_factor +
+ __iterate * __tables<0>::__vector_iterate_cost_factor ;
+}
+
+inline float __trace_list_to_vector::__list_cost(size_t __shift,
+ size_t __iterate)
+{
+ return __shift * __tables<0>::__list_shift_cost_factor +
+ __iterate * __tables<0>::__list_iterate_cost_factor ;
+}
+
+inline void __trace_list_to_vector::__destruct(const void* __obj)
+{
+ if (!__is_on())
+ return;
+
+ __list2vector_info* __res = __get_object_info(__obj);
+ if (!__res)
+ return;
+
+ float __vc = __vector_cost(__res->__shift_count(), __res->__iterate());
+ float __lc = __list_cost(__res->__shift_count(), __res->__iterate());
+ __res->__set_vector_cost(__vc);
+ __res->__set_list_cost(__lc);
+ __retire_object(__obj);
+}
+
+inline void __trace_list_to_vector::__opr_insert(const void* __obj,
+ size_t __shift, size_t __size)
+{
+ __list2vector_info* __res = __get_object_info(__obj);
+ if (__res)
+ __res->__opr_insert(__shift, __size);
+}
+
+inline void __trace_list_to_vector::__opr_iterate(const void* __obj,
+ size_t __num)
+{
+ __list2vector_info* __res = __get_object_info(__obj);
+ if (__res) {
+ __res->__opr_iterate(__num);
+ }
+}
+
+inline void __trace_list_to_vector::__invalid_operator(const void* __obj)
+{
+ __list2vector_info* __res = __get_object_info(__obj);
+ if (__res)
+ __res->__set_invalid();
+}
+
+inline void __trace_list_to_vector::__resize(const void* __obj, size_t __from,
+ size_t __to)
+{
+ __list2vector_info* __res = __get_object_info(__obj);
+ if (__res)
+ __res->__resize(__from, __to);
+}
+
+//////////////////////////////////////////////////////////////////////////////
+// Initialization and report.
+//////////////////////////////////////////////////////////////////////////////
+
+inline void __trace_list_to_vector_init()
+{
+ __tables<0>::_S_list_to_vector = new __trace_list_to_vector();
+}
+
+inline void __trace_list_to_vector_report(FILE* __f,
+ __warning_vector_t& __warnings)
+{
+ if (__tables<0>::_S_list_to_vector) {
+ __tables<0>::_S_list_to_vector->__collect_warnings(__warnings);
+ __tables<0>::_S_list_to_vector->__write(__f);
+ }
+}
+
+//////////////////////////////////////////////////////////////////////////////
+// Implementations of instrumentation hooks.
+//////////////////////////////////////////////////////////////////////////////
+
+inline void __trace_list_to_vector_construct(const void* __obj)
+{
+ if (!__profcxx_init()) return;
+
+ __tables<0>::_S_list_to_vector->__insert(__obj, __get_stack());
+}
+
+inline void __trace_list_to_vector_destruct(const void* __obj)
+{
+ if (!__profcxx_init()) return;
+
+ __tables<0>::_S_list_to_vector->__destruct(__obj);
+}
+
+inline void __trace_list_to_vector_insert(const void* __obj,
+ size_t __shift, size_t __size)
+{
+ if (!__profcxx_init()) return;
+
+ __tables<0>::_S_list_to_vector->__opr_insert(__obj, __shift, __size);
+}
+
+
+inline void __trace_list_to_vector_iterate(const void* __obj, size_t __num = 1)
+{
+ if (!__profcxx_init()) return;
+
+ __tables<0>::_S_list_to_vector->__opr_iterate(__obj, __num);
+}
+
+inline void __trace_list_to_vector_invalid_operator(const void* __obj)
+{
+ if (!__profcxx_init()) return;
+
+ __tables<0>::_S_list_to_vector->__invalid_operator(__obj);
+}
+
+inline void __trace_list_to_vector_resize(const void* __obj,
+ size_t __from, size_t __to)
+{
+ if (!__profcxx_init()) return;
+
+ __tables<0>::_S_list_to_vector->__resize(__obj, __from, __to);
+}
+
+} // namespace __cxxprof_impl
+#endif /* PROFCXX_PROFILER_LIST_TO_VECTOR_H__ */
Index: libstdc++-v3/include/profile/impl/profiler.h
===================================================================
--- libstdc++-v3/include/profile/impl/profiler.h (revision 155023)
+++ libstdc++-v3/include/profile/impl/profiler.h (working copy)
@@ -120,6 +120,27 @@
void __trace_vector_to_list_iterate(const void*, size_t);
void __trace_vector_to_list_invalid_operator(const void*);
void __trace_vector_to_list_resize(const void*, size_t, size_t);
+void __trace_vector_to_list_find(const void*, size_t);
+
+void __trace_list_to_slist_destruct(const void*);
+void __trace_list_to_slist_construct(const void*);
+void __trace_list_to_slist_rewind(const void*);
+void __trace_list_to_slist_operation(const void*);
+
+void __trace_list_to_vector_destruct(const void*);
+void __trace_list_to_vector_construct(const void*);
+void __trace_list_to_vector_insert(const void*, size_t, size_t);
+void __trace_list_to_vector_iterate(const void*, size_t);
+void __trace_list_to_vector_invalid_operator(const void*);
+void __trace_list_to_vector_resize(const void*, size_t, size_t);
+
+void __trace_list_to_set_destruct(const void*);
+void __trace_list_to_set_construct(const void*);
+void __trace_list_to_set_insert(const void*, size_t, size_t);
+void __trace_list_to_set_iterate(const void*, size_t);
+void __trace_list_to_set_invalid_operator(const void*);
+void __trace_list_to_set_find(const void*, size_t);
+
void __trace_map_to_unordered_map_construct(const void*);
void __trace_map_to_unordered_map_invalidate(const void*);
void __trace_map_to_unordered_map_insert(const void*, size_t, size_t);
@@ -129,16 +150,39 @@
void __trace_map_to_unordered_map_destruct(const void*);
} // namespace __cxxprof_impl
-// Master switch turns on all diagnostics.
+// Master switch turns on all diagnostics that are not explicitly turned off.
#ifdef _GLIBCXX_PROFILE
+#ifndef _GLIBCXX_PROFILE_NO_HASHTABLE_TOO_SMALL
#define _GLIBCXX_PROFILE_HASHTABLE_TOO_SMALL
+#endif
+#ifndef _GLIBCXX_PROFILE_NO_HASHTABLE_TOO_LARGE
#define _GLIBCXX_PROFILE_HASHTABLE_TOO_LARGE
+#endif
+#ifndef _GLIBCXX_PROFILE_NO_VECTOR_TOO_SMALL
#define _GLIBCXX_PROFILE_VECTOR_TOO_SMALL
+#endif
+#ifndef _GLIBCXX_PROFILE_NO_VECTOR_TOO_LARGE
#define _GLIBCXX_PROFILE_VECTOR_TOO_LARGE
+#endif
+#ifndef _GLIBCXX_PROFILE_NO_INEFFICIENT_HASH
#define _GLIBCXX_PROFILE_INEFFICIENT_HASH
+#endif
+#ifndef _GLIBCXX_PROFILE_NO_VECTOR_TO_LIST
#define _GLIBCXX_PROFILE_VECTOR_TO_LIST
+#endif
+#ifndef _GLIBCXX_PROFILE_NO_LIST_TO_SLIST
+#define _GLIBCXX_PROFILE_LIST_TO_SLIST
+#endif
+#ifndef _GLIBCXX_PROFILE_NO_LIST_TO_VECTOR
+#define _GLIBCXX_PROFILE_LIST_TO_VECTOR
+#endif
+#ifndef _GLIBCXX_PROFILE_NO_LIST_TO_SET
+#define _GLIBCXX_PROFILE_LIST_TO_SET
+#endif
+#ifndef _GLIBCXX_PROFILE_NO_MAP_TO_UNORDERED_MAP
#define _GLIBCXX_PROFILE_MAP_TO_UNORDERED_MAP
#endif
+#endif
// Expose global management routines to user code.
#ifdef _GLIBCXX_PROFILE
@@ -164,10 +208,8 @@
#endif
// Turn on/off instrumentation for HASHTABLE_TOO_SMALL and HASHTABLE_TOO_LARGE.
-#if ((defined(_GLIBCXX_PROFILE_HASHTABLE_TOO_SMALL) \
- && !defined(_NO_GLIBCXX_PROFILE_HASHTABLE_TOO_SMALL)) \
- || (defined(_GLIBCXX_PROFILE_HASHTABLE_TOO_LARGE) \
- && !defined(_NO_GLIBCXX_PROFILE_HASHTABLE_TOO_LARGE)))
+#if (defined(_GLIBCXX_PROFILE_HASHTABLE_TOO_SMALL) \
+ || defined(_GLIBCXX_PROFILE_HASHTABLE_TOO_LARGE))
#define __profcxx_hashtable_resize(__x...) \
_GLIBCXX_PROFILE_IMPL_REENTRANCE_GUARD( \
__cxxprof_impl::__trace_hashtable_size_resize(__x))
@@ -184,10 +226,8 @@
#endif
// Turn on/off instrumentation for VECTOR_TOO_SMALL and VECTOR_TOO_LARGE.
-#if ((defined(_GLIBCXX_PROFILE_VECTOR_TOO_SMALL) \
- && !defined(_NO_GLIBCXX_PROFILE_VECTOR_TOO_SMALL)) \
- || (defined(_GLIBCXX_PROFILE_VECTOR_TOO_LARGE) \
- && !defined(_NO_GLIBCXX_PROFILE_VECTOR_TOO_LARGE)))
+#if (defined(_GLIBCXX_PROFILE_VECTOR_TOO_SMALL) \
+ || defined(_GLIBCXX_PROFILE_VECTOR_TOO_LARGE))
#define __profcxx_vector_resize(__x...) \
_GLIBCXX_PROFILE_IMPL_REENTRANCE_GUARD( \
__cxxprof_impl::__trace_vector_size_resize(__x))
@@ -204,8 +244,7 @@
#endif
// Turn on/off instrumentation for INEFFICIENT_HASH.
-#if (defined(_GLIBCXX_PROFILE_INEFFICIENT_HASH) \
- && !defined(_NO_GLIBCXX_PROFILE_INEFFICIENT_HASH))
+#if defined(_GLIBCXX_PROFILE_INEFFICIENT_HASH)
#define __profcxx_hashtable_construct2(__x...) \
_GLIBCXX_PROFILE_IMPL_REENTRANCE_GUARD( \
__cxxprof_impl::__trace_hash_func_construct(__x))
@@ -218,8 +257,7 @@
#endif
// Turn on/off instrumentation for VECTOR_TO_LIST.
-#if (defined(_GLIBCXX_PROFILE_VECTOR_TO_LIST) \
- && !defined(_NO_GLIBCXX_PROFILE_VECTOR_TO_LIST))
+#if defined(_GLIBCXX_PROFILE_VECTOR_TO_LIST)
#define __profcxx_vector_construct2(__x...) \
_GLIBCXX_PROFILE_IMPL_REENTRANCE_GUARD( \
__cxxprof_impl::__trace_vector_to_list_construct(__x))
@@ -238,6 +276,9 @@
#define __profcxx_vector_resize2(__x...) \
_GLIBCXX_PROFILE_IMPL_REENTRANCE_GUARD( \
__cxxprof_impl::__trace_vector_to_list_resize(__x))
+#define __profcxx_vector_find(__x...) \
+ _GLIBCXX_PROFILE_IMPL_REENTRANCE_GUARD( \
+ __cxxprof_impl::__trace_vector_to_list_find(__x))
#else
#define __profcxx_vector_destruct2(__x...)
#define __profcxx_vector_construct2(__x...)
@@ -245,11 +286,78 @@
#define __profcxx_vector_iterate(__x...)
#define __profcxx_vector_invalid_operator(__x...)
#define __profcxx_vector_resize2(__x...)
+#define __profcxx_vector_find(__x...)
#endif
+// Turn on/off instrumentation for LIST_TO_VECTOR.
+#if defined(_GLIBCXX_PROFILE_LIST_TO_VECTOR)
+#define __profcxx_list_construct2(__x...) \
+ _GLIBCXX_PROFILE_IMPL_REENTRANCE_GUARD( \
+ __cxxprof_impl::__trace_list_to_vector_construct(__x))
+#define __profcxx_list_destruct2(__x...) \
+ _GLIBCXX_PROFILE_IMPL_REENTRANCE_GUARD( \
+ __cxxprof_impl::__trace_list_to_vector_destruct(__x))
+#define __profcxx_list_insert(__x...) \
+ _GLIBCXX_PROFILE_IMPL_REENTRANCE_GUARD( \
+ __cxxprof_impl::__trace_list_to_vector_insert(__x))
+#define __profcxx_list_iterate(__x...) \
+ _GLIBCXX_PROFILE_IMPL_REENTRANCE_GUARD( \
+ __cxxprof_impl::__trace_list_to_vector_iterate(__x))
+#define __profcxx_list_invalid_operator(__x...) \
+ _GLIBCXX_PROFILE_IMPL_REENTRANCE_GUARD( \
+ __cxxprof_impl::__trace_list_to_vector_invalid_operator(__x))
+#else
+#define __profcxx_list_destruct2(__x...)
+#define __profcxx_list_construct2(__x...)
+#define __profcxx_list_insert(__x...)
+#define __profcxx_list_iterate(__x...)
+#define __profcxx_list_invalid_operator(__x...)
+#endif
+
+// Turn on/off instrumentation for LIST_TO_SLIST.
+#if defined(_GLIBCXX_PROFILE_LIST_TO_SLIST)
+#define __profcxx_list_rewind(__x...) \
+ _GLIBCXX_PROFILE_IMPL_REENTRANCE_GUARD( \
+ __cxxprof_impl::__trace_list_to_slist_rewind(__x))
+#define __profcxx_list_operation(__x...) \
+ _GLIBCXX_PROFILE_IMPL_REENTRANCE_GUARD( \
+ __cxxprof_impl::__trace_list_to_slist_operation(__x))
+#define __profcxx_list_destruct(__x...) \
+ _GLIBCXX_PROFILE_IMPL_REENTRANCE_GUARD( \
+ __cxxprof_impl::__trace_list_to_slist_destruct(__x))
+#define __profcxx_list_construct(__x...) \
+ _GLIBCXX_PROFILE_IMPL_REENTRANCE_GUARD( \
+ __cxxprof_impl::__trace_list_to_slist_construct(__x))
+#else
+#define __profcxx_list_rewind(__x...)
+#define __profcxx_list_operation(__x...)
+#define __profcxx_list_destruct(__x...)
+#define __profcxx_list_construct(__x...)
+#endif
+
+// Turn on/off instrumentation for LIST_TO_SET.
+#if defined(_GLIBCXX_PROFILE_LIST_TO_SET)
+#define __profcxx_list_construct3(__x...) \
+ _GLIBCXX_PROFILE_IMPL_REENTRANCE_GUARD( \
+ __cxxprof_impl::__trace_list_to_set_construct(__x))
+#define __profcxx_list_destruct3(__x...) \
+ _GLIBCXX_PROFILE_IMPL_REENTRANCE_GUARD( \
+ __cxxprof_impl::__trace_list_to_set_destruct(__x))
+#define __profcxx_list_insert3(__x...) \
+ _GLIBCXX_PROFILE_IMPL_REENTRANCE_GUARD( \
+ __cxxprof_impl::__trace_list_to_set_insert(__x))
+#define __profcxx_list_find3(__x...) \
+ _GLIBCXX_PROFILE_IMPL_REENTRANCE_GUARD( \
+ __cxxprof_impl::__trace_list_to_set_find(__x))
+#else
+#define __profcxx_list_destruct3(__x...)
+#define __profcxx_list_construct3(__x...)
+#define __profcxx_list_insert3(__x...)
+#define __profcxx_list_find3(__x...)
+#endif
+
// Turn on/off instrumentation for MAP_TO_UNORDERED_MAP.
-#if (defined(_GLIBCXX_PROFILE_MAP_TO_UNORDERED_MAP) \
- && !defined(_NO_GLIBCXX_PROFILE_MAP_TO_UNORDERED_MAP))
+#if defined(_GLIBCXX_PROFILE_MAP_TO_UNORDERED_MAP)
#define __profcxx_map_to_unordered_map_construct(__x...) \
_GLIBCXX_PROFILE_IMPL_REENTRANCE_GUARD( \
__cxxprof_impl::__trace_map_to_unordered_map_construct(__x))
@@ -322,5 +430,8 @@
#include "profile/impl/profiler_map_to_unordered_map.h"
#include "profile/impl/profiler_vector_size.h"
#include "profile/impl/profiler_vector_to_list.h"
+#include "profile/impl/profiler_list_to_slist.h"
+#include "profile/impl/profiler_list_to_vector.h"
+#include "profile/impl/profiler_list_to_set.h"
#endif // PROFCXX_PROFILER_H__
Index: libstdc++-v3/include/profile/impl/profiler_map_to_unordered_map.h
===================================================================
--- libstdc++-v3/include/profile/impl/profiler_map_to_unordered_map.h (revision 155023)
+++ libstdc++-v3/include/profile/impl/profiler_map_to_unordered_map.h (working copy)
@@ -53,31 +53,10 @@
namespace __cxxprof_impl
{
-// Cost model. XXX: this must be taken from the machine model instead.
-// Map operations:
-// - insert: 1.5 * log(size)
-// - erase: 1.5 * log(size)
-// - find: log(size)
-// - iterate: 2.3
-// Unordered map operations:
-// - insert: 12
-// - erase: 12
-// - find: 10
-// - iterate: 1.7
-
-const float __map_insert_cost_factor = 1.5;
-const float __map_erase_cost_factor = 1.5;
-const float __map_find_cost_factor = 1;
-const float __map_iterate_cost = 2.3;
-
-const float __umap_insert_cost = 12.0;
-const float __umap_erase_cost = 12.0;
-const float __umap_find_cost = 10.0;
-const float __umap_iterate_cost = 1.7;
-
inline int __log2(size_t __size)
{
- for (int __bit_count = sizeof(size_t) - 1; __bit_count >= 0; --__bit_count) {
+ for (int __bit_count = sizeof(size_t) - 1; __bit_count >= 0; -- __bit_count)
+ {
if ((2 << __bit_count) & __size) {
return __bit_count;
}
@@ -87,17 +66,20 @@
inline float __map_insert_cost(size_t __size)
{
- return __map_insert_cost_factor * static_cast<float>(__log2(__size));
+ return __tables<0>::__map_insert_cost_factor * static_cast<float>(
+ __log2(__size));
}
inline float __map_erase_cost(size_t __size)
{
- return __map_erase_cost_factor * static_cast<float>(__log2(__size));
+ return __tables<0>::__map_erase_cost_factor * static_cast<float>(
+ __log2(__size));
}
inline float __map_find_cost(size_t __size)
{
- return __map_find_cost_factor * static_cast<float>(__log2(__size));
+ return __tables<0>::__map_find_cost_factor * static_cast<float>(
+ __log2(__size));
}
/** @brief A map-to-unordered_map instrumentation line in the object table. */
@@ -163,28 +145,28 @@
{
_M_insert += __count;
_M_map_cost += __count * __map_insert_cost(__size);
- _M_umap_cost += __count * __umap_insert_cost;
+ _M_umap_cost += __count * __tables<0>::__umap_insert_cost;
}
inline void __map2umap_info:: __record_erase(size_t __size, size_t __count)
{
_M_erase += __count;
_M_map_cost += __count * __map_erase_cost(__size);
- _M_umap_cost += __count * __umap_erase_cost;
+ _M_umap_cost += __count * __tables<0>::__umap_erase_cost;
}
inline void __map2umap_info:: __record_find(size_t __size)
{
_M_find += 1;
_M_map_cost += __map_find_cost(__size);
- _M_umap_cost += __umap_find_cost;
+ _M_umap_cost += __tables<0>::__umap_find_cost;
}
inline void __map2umap_info:: __record_iterate(size_t __count)
{
_M_iterate += __count;
- _M_map_cost += __count * __map_iterate_cost;
- _M_umap_cost += __count * __umap_iterate_cost;
+ _M_map_cost += __count * __tables<0>::__map_iterate_cost;
+ _M_umap_cost += __count * __tables<0>::__umap_iterate_cost;
}
inline void __map2umap_info:: __record_invalidate()
Index: libstdc++-v3/include/profile/vector
===================================================================
--- libstdc++-v3/include/profile/vector (revision 155023)
+++ libstdc++-v3/include/profile/vector (working copy)
@@ -37,12 +37,12 @@
#include <vector>
#include <utility>
#include <profile/base.h>
+#include <profile/iterator_tracker.h>
namespace std
{
namespace __profile
{
- /** @brief Vector wrapper with performance instrumentation. */
template<typename _Tp,
typename _Allocator = std::allocator<_Tp> >
class vector
@@ -54,17 +54,21 @@
typedef typename _Base::reference reference;
typedef typename _Base::const_reference const_reference;
- typedef typename _Base::iterator iterator;
- typedef typename _Base::const_iterator const_iterator;
+ typedef __iterator_tracker<typename _Base::iterator, vector>
+ iterator;
+ typedef __iterator_tracker<typename _Base::const_iterator, vector>
+ const_iterator;
typedef typename _Base::size_type size_type;
typedef typename _Base::difference_type difference_type;
- typedef _Tp value_type;
- typedef _Allocator allocator_type;
+ typedef _Tp value_type;
+ typedef _Allocator allocator_type;
typedef typename _Base::pointer pointer;
typedef typename _Base::const_pointer const_pointer;
-
+ typedef std::reverse_iterator<iterator> reverse_iterator;
+ typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
+
_Base&
_M_base() { return *this; }
@@ -157,6 +161,58 @@
using _Base::assign;
using _Base::get_allocator;
+
+ // iterators:
+ iterator
+ begin()
+ { return iterator(_Base::begin(), this); }
+
+ const_iterator
+ begin() const
+ { return const_iterator(_Base::begin(), this); }
+
+ iterator
+ end()
+ { return iterator(_Base::end(), this); }
+
+ const_iterator
+ end() const
+ { return const_iterator(_Base::end(), this); }
+
+ reverse_iterator
+ rbegin()
+ { return reverse_iterator(end()); }
+
+ const_reverse_iterator
+ rbegin() const
+ { return const_reverse_iterator(end()); }
+
+ reverse_iterator
+ rend()
+ { return reverse_iterator(begin()); }
+
+ const_reverse_iterator
+ rend() const
+ { return const_reverse_iterator(begin()); }
+
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+ const_iterator
+ cbegin() const
+ { return const_iterator(_Base::begin(), this); }
+
+ const_iterator
+ cend() const
+ { return const_iterator(_Base::end(), this); }
+
+ const_reverse_iterator
+ crbegin() const
+ { return const_reverse_iterator(end()); }
+
+ const_reverse_iterator
+ crend() const
+ { return const_reverse_iterator(begin()); }
+#endif
+
// 23.2.4.2 capacity:
using _Base::size;
using _Base::max_size;
@@ -225,6 +281,15 @@
}
#ifdef __GXX_EXPERIMENTAL_CXX0X__
+ template<typename... _Args>
+ iterator
+ emplace(iterator __position, _Args&&... __args)
+ {
+ typename _Base::iterator __res = _Base::emplace(__position.base(),
+ std::forward<_Args>(__args)...);
+ return iterator(__res, this);
+ }
+
void
push_back(_Tp&& __x)
{
@@ -238,22 +303,24 @@
iterator
insert(iterator __position, const _Tp& __x)
{
- __profcxx_vector_insert(this, __position-_Base::begin(), this->size());
+ __profcxx_vector_insert(this, __position.base() - _Base::begin(),
+ this->size());
size_type __old_size = this->capacity();
- typename _Base::iterator __res = _Base::insert(__position,__x);
+ typename _Base::iterator __res = _Base::insert(__position.base(), __x);
_M_profile_resize(this, __old_size, this->capacity());
- return __res;
+ return iterator(__res, this);
}
#ifdef __GXX_EXPERIMENTAL_CXX0X__
iterator
insert(iterator __position, _Tp&& __x)
{
- __profcxx_vector_insert(this, __position-_Base::begin(), this->size());
+ __profcxx_vector_insert(this, __position.base() - _Base::begin(),
+ this->size());
size_type __old_size = this->capacity();
- typename _Base::iterator __res = _Base::insert(__position,__x);
+ typename _Base::iterator __res = _Base::insert(__position.base(), __x);
_M_profile_resize(this, __old_size, this->capacity());
- return __res;
+ return iterator(__res, this);
}
void
@@ -262,8 +329,11 @@
#endif
void
-
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+ swap(vector&& __x)
+#else
swap(vector& __x)
+#endif
{
_Base::swap(__x);
}
@@ -272,9 +342,10 @@
void
insert(iterator __position, size_type __n, const _Tp& __x)
{
- __profcxx_vector_insert(this, __position-_Base::begin(), this->size());
+ __profcxx_vector_insert(this, __position.base() - _Base::begin(),
+ this->size());
size_type __old_size = this->capacity();
- _Base::insert(__position, __n, __x);
+ _Base::insert(__position.base(), __n, __x);
_M_profile_resize(this, __old_size, this->capacity());
}
@@ -283,12 +354,31 @@
insert(iterator __position,
_InputIterator __first, _InputIterator __last)
{
- __profcxx_vector_insert(this, __position-_Base::begin(), this->size());
+ __profcxx_vector_insert(this, __position.base()-_Base::begin(),
+ this->size());
size_type __old_size = this->capacity();
- _Base::insert(__position, __first, __last);
+ _Base::insert(__position.base(), __first, __last);
_M_profile_resize(this, __old_size, this->capacity());
}
+
+ iterator
+ erase(iterator __position)
+ {
+ typename _Base::iterator __res = _Base::erase(__position.base());
+ return iterator(__res, this);
+ }
+
+ iterator
+ erase(iterator __first, iterator __last)
+ {
+ // _GLIBCXX_RESOLVE_LIB_DEFECTS
+ // 151. can't currently clear() empty container
+ typename _Base::iterator __res = _Base::erase(__first.base(),
+ __last.base());
+ return iterator(__res, this);
+ }
+
void
clear()
{
@@ -297,17 +387,14 @@
_Base::clear();
}
- // iterators:
- iterator
- begin()
+ inline void _M_profile_find() const
{
- return _Base::begin();
+ __profcxx_vector_find(this, size());
}
- const_iterator
- begin() const
+ inline void _M_profile_iterate(int __rewind = 0) const
{
- return _Base::begin();
+ __profcxx_vector_iterate(this);
}
private:
@@ -362,6 +449,18 @@
swap(vector<_Tp, _Alloc>& __lhs, vector<_Tp, _Alloc>& __rhs)
{ __lhs.swap(__rhs); }
+#ifdef __GXX_EXPERIMENTAL_CXX0X__
+ template<typename _Tp, typename _Alloc>
+ inline void
+ swap(vector<_Tp, _Alloc>&& __lhs, vector<_Tp, _Alloc>& __rhs)
+ { __lhs.swap(__rhs); }
+
+ template<typename _Tp, typename _Alloc>
+ inline void
+ swap(vector<_Tp, _Alloc>& __lhs, vector<_Tp, _Alloc>&& __rhs)
+ { __lhs.swap(__rhs); }
+#endif
+
} // namespace __profile
using _GLIBCXX_STD_D::_S_word_bit;
} // namespace std
Index: libstdc++-v3/include/profile/algo.h
===================================================================
--- libstdc++-v3/include/profile/algo.h (revision 0)
+++ libstdc++-v3/include/profile/algo.h (revision 0)
@@ -0,0 +1,93 @@
+// -*- C++ -*-
+
+// Copyright (C) 2009 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library. This library is free
+// software; you can redistribute it and/or modify it under the terms
+// of the GNU General Public License as published by the Free Software
+// Foundation; either version 3, or (at your option) any later
+// version.
+
+// This library is distributed in the hope that it will be useful, but
+// WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+// General Public License for more details.
+
+// Under Section 7 of GPL version 3, you are granted additional
+// permissions described in the GCC Runtime Library Exception, version
+// 3.1, as published by the Free Software Foundation.
+
+// You should have received a copy of the GNU General Public License and
+// a copy of the GCC Runtime Library Exception along with this program;
+// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
+// <http://www.gnu.org/licenses/>.
+
+/** @file parallel/algo.h
+ * @brief Parallel STL function calls corresponding to the stl_algo.h header.
+ *
+ * The functions defined here mainly do case switches and
+ * call the actual parallelized versions in other files.
+ * Inlining policy: Functions that basically only contain one function call,
+ * are declared inline.
+ * This file is a GNU parallel extension to the Standard C++ Library.
+ */
+
+#ifndef _GLIBCXX_PROFILE_ALGO_H
+#define _GLIBCXX_PROFILE_ALGO_H 1
+
+#include <bits/stl_algo.h>
+#include <profile/base.h>
+#include <profile/iterator_tracker.h>
+
+namespace std
+{
+namespace __profile
+{
+
+ template<typename _Tp>
+ struct __is_iterator_tracker
+ {
+ enum { __value = 0 };
+ typedef __false_type __type;
+ };
+
+ template<typename _Iterator, typename _Container>
+ struct __is_iterator_tracker<__iterator_tracker<_Iterator, _Container> >
+ {
+ enum { __value = 1 };
+ typedef __true_type __type;
+ };
+
+ template<typename _IIter, typename _Tp>
+ inline _IIter
+ find(_IIter __begin, _IIter __end, const _Tp& __val)
+ {
+ typedef typename __is_iterator_tracker<_IIter>::__type _IterTracker;
+ return __cxxprof_find(__begin, __end, __val, _IterTracker());
+ }
+
+ template<typename _IIter, typename _Tp>
+ inline _IIter
+ __cxxprof_find( _IIter __begin, _IIter __end, const _Tp& __val,
+ __false_type)
+ {
+ return _GLIBCXX_STD_ALGO::find(__begin, __end, __val);
+ }
+
+ template<typename _IterTracker, typename _Tp>
+ inline _IterTracker
+ __cxxprof_find( _IterTracker __begin, _IterTracker __end, const _Tp& __val,
+ __true_type)
+ {
+ __begin._M_find();
+ typename _IterTracker::_Base_iterator __res =
+ _GLIBCXX_STD_ALGO::find(__begin.base(), __end.base(), __val);
+ return _IterTracker(__res, __begin._M_get_sequence());
+ }
+
+
+
+} // end namespace __profile
+} // end namespace std
+
+#endif
Index: libstdc++-v3/include/profile/list
===================================================================
--- libstdc++-v3/include/profile/list (revision 155023)
+++ libstdc++-v3/include/profile/list (working copy)
@@ -30,13 +30,15 @@
#define _GLIBCXX_PROFILE_LIST 1
#include <list>
+#include <profile/base.h>
+#include <profile/iterator_tracker.h>
namespace std
{
namespace __profile
{
/** @brief List wrapper with performance instrumentation. */
- template<typename _Tp, typename _Allocator = std::allocator<_Tp> >
+template<typename _Tp, typename _Allocator = std::allocator<_Tp> >
class list
: public _GLIBCXX_STD_D::list<_Tp, _Allocator>
{
@@ -46,8 +48,10 @@
typedef typename _Base::reference reference;
typedef typename _Base::const_reference const_reference;
- typedef typename _Base::iterator iterator;
- typedef typename _Base::const_iterator const_iterator;
+ typedef __iterator_tracker<typename _Base::iterator, list>
+ iterator;
+ typedef __iterator_tracker<typename _Base::const_iterator, list>
+ const_iterator;
typedef typename _Base::size_type size_type;
typedef typename _Base::difference_type difference_type;
@@ -61,36 +65,68 @@
// 23.2.2.1 construct/copy/destroy:
explicit list(const _Allocator& __a = _Allocator())
- : _Base(__a) { }
+ : _Base(__a)
+ {
+ __profcxx_list_construct(this); // list2slist
+ __profcxx_list_construct2(this); // list2vector
+ __profcxx_list_construct3(this); // list2set
+ }
explicit list(size_type __n, const _Tp& __value = _Tp(),
const _Allocator& __a = _Allocator())
- : _Base(__n, __value, __a) { }
+ : _Base(__n, __value, __a)
+ {
+ __profcxx_list_construct(this);
+ __profcxx_list_construct2(this);
+ __profcxx_list_construct3(this);
+ }
template<class _InputIterator>
list(_InputIterator __first, _InputIterator __last,
const _Allocator& __a = _Allocator())
: _Base(__first, __last, __a)
- { }
+ {
+ __profcxx_list_construct(this);
+ __profcxx_list_construct2(this);
+ __profcxx_list_construct3(this);
+ }
list(const list& __x)
- : _Base(__x) { }
+ : _Base(__x)
+ {
+ __profcxx_list_construct(this);
+ __profcxx_list_construct2(this);
+ __profcxx_list_construct3(this);
+ }
list(const _Base& __x)
- : _Base(__x) { }
+ : _Base(__x)
+ {
+ __profcxx_list_construct(this);
+ __profcxx_list_construct2(this);
+ __profcxx_list_construct3(this);
+ }
#ifdef __GXX_EXPERIMENTAL_CXX0X__
list(list&& __x)
: _Base(std::forward<list>(__x))
- { }
+ {
+ __profcxx_list_construct(this);
+ __profcxx_list_construct2(this);
+ __profcxx_list_construct3(this);
+ }
list(initializer_list<value_type> __l,
const allocator_type& __a = allocator_type())
: _Base(__l, __a) { }
#endif
- ~list() { }
+ ~list() {
+ __profcxx_list_destruct(this);
+ __profcxx_list_destruct2(this);
+ __profcxx_list_destruct3(this);
+ }
list&
operator=(const list& __x)
@@ -141,27 +177,39 @@
// iterators:
iterator
begin()
- { return iterator(_Base::begin()); }
+ { return iterator(_Base::begin(), this); }
const_iterator
begin() const
- { return const_iterator(_Base::begin()); }
+ { return const_iterator(_Base::begin(), this); }
iterator
end()
- { return iterator(_Base::end()); }
+ {
+ __profcxx_list_rewind(this);
+ return iterator(_Base::end(), this);
+ }
const_iterator
end() const
- { return const_iterator(_Base::end()); }
+ {
+ __profcxx_list_rewind(this);
+ return const_iterator(_Base::end(), this);
+ }
reverse_iterator
rbegin()
- { return reverse_iterator(end()); }
+ {
+ __profcxx_list_rewind(this);
+ return reverse_iterator(end());
+ }
const_reverse_iterator
rbegin() const
- { return const_reverse_iterator(end()); }
+ {
+ __profcxx_list_rewind(this);
+ return const_reverse_iterator(end());
+ }
reverse_iterator
rend()
@@ -174,11 +222,11 @@
#ifdef __GXX_EXPERIMENTAL_CXX0X__
const_iterator
cbegin() const
- { return const_iterator(_Base::begin()); }
+ { return const_iterator(_Base::begin(), this); }
const_iterator
cend() const
- { return const_iterator(_Base::end()); }
+ { return const_iterator(_Base::end(), this); }
const_reverse_iterator
crbegin() const
@@ -216,17 +264,25 @@
reference
back()
{
+ __profcxx_list_rewind(this);
return _Base::back();
}
const_reference
back() const
{
+ __profcxx_list_rewind(this);
return _Base::back();
}
// 23.2.2.3 modifiers:
- using _Base::push_front;
+ void
+ push_front(const value_type& __x)
+ {
+ __profcxx_list_invalid_operator(this);
+ __profcxx_list_operation(this);
+ _Base::push_front(__x);
+ }
#ifdef __GXX_EXPERIMENTAL_CXX0X__
using _Base::emplace_front;
@@ -235,7 +291,7 @@
void
pop_front()
{
- iterator __victim = begin();
+ __profcxx_list_operation(this);
_Base::pop_front();
}
@@ -251,6 +307,7 @@
iterator __victim = end();
--__victim;
_Base::pop_back();
+ __profcxx_list_rewind(this);
}
#ifdef __GXX_EXPERIMENTAL_CXX0X__
@@ -258,21 +315,29 @@
iterator
emplace(iterator __position, _Args&&... __args)
{
- return iterator(_Base::emplace(__position,
- std::forward<_Args>(__args)...));
+ return iterator(_Base::emplace(__position.base(),
+ std::forward<_Args>(__args)...));
}
#endif
iterator
insert(iterator __position, const _Tp& __x)
{
- return iterator(_Base::insert(__position, __x));
+ size_type __size = size();
+ _M_profile_insert(this, __position, __size);
+ __profcxx_list_insert3(this, __size);
+ return iterator(_Base::insert(__position.base(), __x), this);
}
#ifdef __GXX_EXPERIMENTAL_CXX0X__
iterator
insert(iterator __position, _Tp&& __x)
- { return emplace(__position, std::move(__x)); }
+ {
+ size_type __size = size();
+ _M_profile_insert(this, __position, __size);
+ __profcxx_list_insert3(this, __size);
+ return emplace(__position.base(), std::move(__x));
+ }
void
insert(iterator __p, initializer_list<value_type> __l)
@@ -284,21 +349,27 @@
void
insert(iterator __position, size_type __n, const _Tp& __x)
{
- _Base::insert(__position, __n, __x);
+ size_type __size = size();
+ _M_profile_insert(this, __position, __size);
+ __profcxx_list_insert3(this, __size, __n);
+ _Base::insert(__position.base(), __n, __x);
}
template<class _InputIterator>
void
insert(iterator __position, _InputIterator __first,
_InputIterator __last)
- {
- _Base::insert(__position, __first, __last);
- }
+ {
+ size_type __size = size();
+ _M_profile_insert(this, __position, __size);
+ _Base::insert(__position.base(), __first, __last);
+ __profcxx_list_insert3(this, __size, size() - __size);
+ }
iterator
erase(iterator __position)
{
- return iterator(_Base::erase(__position));
+ return iterator(_Base::erase(__position.base()), this);
}
iterator
@@ -306,7 +377,7 @@
{
// _GLIBCXX_RESOLVE_LIB_DEFECTS
// 151. can't currently clear() empty container
- return iterator(_Base::erase(__position, __last));
+ return iterator(_Base::erase(__position.base(), __last.base()), this);
}
void
@@ -329,7 +400,7 @@
splice(iterator __position, list& __x)
#endif
{
- this->splice(__position, _GLIBCXX_MOVE(__x), __x.begin(), __x.end());
+ this->splice(__position.base(), _GLIBCXX_MOVE(__x), __x.begin(), __x.end());
}
void
@@ -343,8 +414,8 @@
// after implementing the relevant bits of N1599.
// _GLIBCXX_RESOLVE_LIB_DEFECTS
- _Base::splice(__position, _GLIBCXX_MOVE(__x._M_base()),
- __i);
+ _Base::splice(__position.base(), _GLIBCXX_MOVE(__x._M_base()),
+ __i.base());
}
void
@@ -359,8 +430,8 @@
// We used to perform the splice_alloc check: not anymore, redundant
// after implementing the relevant bits of N1599.
- _Base::splice(__position, _GLIBCXX_MOVE(__x._M_base()),
- __first, __last);
+ _Base::splice(__position.base(), _GLIBCXX_MOVE(__x._M_base()),
+ __first.base(), __last.base());
}
void
@@ -381,6 +452,7 @@
{
for (iterator __x = begin(); __x != _Base::end(); )
{
+ __profcxx_list_operation(this);
if (__pred(*__x))
__x = erase(__x);
else
@@ -398,6 +470,7 @@
iterator __next = __first;
while (++__next != __last)
{
+ __profcxx_list_operation(this);
if (*__first == *__next)
erase(__next);
else
@@ -417,6 +490,7 @@
iterator __next = __first;
while (++__next != __last)
{
+ __profcxx_list_operation(this);
if (__binary_pred(*__first, *__next))
erase(__next);
else
@@ -471,6 +545,30 @@
const _Base&
_M_base() const { return *this; }
+ inline void _M_profile_find() const
+ {
+ __profcxx_list_find3(this, size());
+ }
+
+ inline void _M_profile_iterate(int __rewind = 0) const
+ {
+ __profcxx_list_operation(this);
+ __profcxx_list_iterate(this);
+ if (__rewind)
+ __profcxx_list_rewind(this);
+ }
+
+ private:
+ size_type _M_profile_insert(void* obj, iterator __pos, size_type __size)
+ {
+ size_type __shift = 0;
+ typename _Base::iterator __it = __pos.base();
+ for ( ; __it!=_Base::end(); __it++)
+ __shift++;
+ __profcxx_list_rewind(this);
+ __profcxx_list_operation(this);
+ __profcxx_list_insert(this, __shift, __size);
+ }
};
template<typename _Tp, typename _Alloc>
Index: libstdc++-v3/include/bits/stl_algo.h
===================================================================
--- libstdc++-v3/include/bits/stl_algo.h (revision 155023)
+++ libstdc++-v3/include/bits/stl_algo.h (working copy)
@@ -4278,6 +4278,7 @@
return __f;
}
+#if !defined(_GLIBCXX_PROFILE)
/**
* @brief Find the first occurrence of a value in a sequence.
* @ingroup non_mutating_algorithms
@@ -4300,6 +4301,7 @@
return std::__find(__first, __last, __val,
std::__iterator_category(__first));
}
+#endif
/**
* @brief Find the first element in a sequence for which a
@@ -6164,4 +6166,41 @@
_GLIBCXX_END_NESTED_NAMESPACE
+#if defined(_GLIBCXX_PROFILE)
+_GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD_ALGO)
+
+ // TODO: instrument find_somthing like a find_end
+
+ /**
+ * @brief Find the first occurrence of a value in a sequence.
+ * @ingroup non_mutating_algorithms
+ * @param first An input iterator.
+ * @param last An input iterator.
+ * @param val The value to find.
+ * @return The first iterator @c i in the range @p [first,last)
+ * such that @c *i == @p val, or @p last if no such iterator exists.
+ */
+ template<typename _InputIterator, typename _Tp>
+ inline _InputIterator
+ find(_InputIterator __first, _InputIterator __last,
+ const _Tp& __val)
+ {
+ // concept requirements
+ __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
+ __glibcxx_function_requires(_EqualOpConcept<
+ typename iterator_traits<_InputIterator>::value_type, _Tp>)
+ __glibcxx_requires_valid_range(__first, __last);
+ return std::__find(__first, __last, __val,
+ std::__iterator_category(__first));
+
+ }
+
+_GLIBCXX_END_NESTED_NAMESPACE
+#endif
+
+
+
+
+
+
#endif /* _STL_ALGO_H */
Index: libstdc++-v3/include/bits/c++config
===================================================================
--- libstdc++-v3/include/bits/c++config (revision 155023)
+++ libstdc++-v3/include/bits/c++config (working copy)
@@ -165,10 +165,19 @@
# error Cannot use -D_GLIBCXX_PROFILE with -D_GLIBCXX_DEBUG or \
-D_GLIBCXX_PARALLEL
# endif
+
+# define _GLIBCXX_STD_P __profile
+
+// The original algorithm functions are hidden and existing in the following
+// namespace. Now, user program sees the wrapper functions in the '__profile'
+// namespace.
+# define _GLIBCXX_STD_ALGO __profile_algo
+
# define _GLIBCXX_STD_D __norm
-# define _GLIBCXX_STD_P _GLIBCXX_STD
# define _GLIBCXX_STD_PR __norm
-# define _GLIBCXX_STD __cxx1998
+// This namespace is no longer necessary
+//# define _GLIBCXX_STD __cxx1998
+
# define _GLIBCXX_BEGIN_NAMESPACE(X) namespace X _GLIBCXX_VISIBILITY_ATTR(default) {
# define _GLIBCXX_END_NAMESPACE }
# endif
Index: libstdc++-v3/include/Makefile.am
===================================================================
--- libstdc++-v3/include/Makefile.am (revision 155023)
+++ libstdc++-v3/include/Makefile.am (working copy)
@@ -781,6 +781,9 @@
profile_srcdir = ${glibcxx_srcdir}/include/profile
profile_builddir = ./profile
profile_headers = \
+ ${profile_srcdir}/algo.h \
+ ${profile_srcdir}/algorithm \
+ ${profile_srcdir}/iterator_tracker.h \
${profile_srcdir}/base.h \
${profile_srcdir}/unordered_map \
${profile_srcdir}/unordered_set \
@@ -807,7 +810,10 @@
${profile_impl_srcdir}/profiler_state.h \
${profile_impl_srcdir}/profiler_trace.h \
${profile_impl_srcdir}/profiler_vector_size.h \
- ${profile_impl_srcdir}/profiler_vector_to_list.h
+ ${profile_impl_srcdir}/profiler_vector_to_list.h \
+ ${profile_impl_srcdir}/profiler_list_to_slist.h \
+ ${profile_impl_srcdir}/profiler_list_to_vector.h \
+ ${profile_impl_srcdir}/profiler_list_to_set.h
# Some of the different "C" header models need extra files.
# Some "C" header schemes require the "C" compatibility headers.