diff options
Diffstat (limited to 'libstdc++-v3/testsuite/util/performance')
21 files changed, 3064 insertions, 0 deletions
diff --git a/libstdc++-v3/testsuite/util/performance/assoc/mem_usage/erase_test.hpp b/libstdc++-v3/testsuite/util/performance/assoc/mem_usage/erase_test.hpp new file mode 100644 index 000000000..6ad797a66 --- /dev/null +++ b/libstdc++-v3/testsuite/util/performance/assoc/mem_usage/erase_test.hpp @@ -0,0 +1,109 @@ +// -*- C++ -*- + +// Copyright (C) 2005, 2006, 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. + +// You should have received a copy of the GNU General Public License +// along with this library; see the file COPYING3. If not see +// <http://www.gnu.org/licenses/>. + + +// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. + +// Permission to use, copy, modify, sell, and distribute this software +// is hereby granted without fee, provided that the above copyright +// notice appears in all copies, and that both that copyright notice +// and this permission notice appear in supporting documentation. None +// of the above authors, nor IBM Haifa Research Laboratories, make any +// representation about the suitability of this software for any +// purpose. It is provided "as is" without express or implied +// warranty. + +/** + * @file erase_test.hpp + * Contains a generic erase test. + */ + +#ifndef PB_DS_ERASE_TEST_HPP +#define PB_DS_ERASE_TEST_HPP + +#include <iterator> +#include <testsuite_allocator.h> +#include <ext/pb_ds/detail/type_utils.hpp> +#include <performance/io/xml_formatter.hpp> +#include <common_type/assoc/string_form.hpp> + +namespace __gnu_pbds +{ + namespace test + { + template<typename It> + class erase_test + { + public: + erase_test(It ins_b, size_t ins_vn, size_t ins_vs, size_t ins_vm) + : m_ins_b(ins_b), m_ins_vn(ins_vn), m_ins_vs(ins_vs), m_ins_vm(ins_vm) + { } + + template<typename Cntnr> + void + operator()(Cntnr); + + private: + erase_test(const erase_test&); + + const It m_ins_b; + const size_t m_ins_vn; + const size_t m_ins_vs; + const size_t m_ins_vm; + }; + + template<typename It> + template<typename Cntnr> + void + erase_test<It>:: + operator()(Cntnr) + { + typedef string_form<Cntnr> sform_type; + typedef xml_result_set_performance_formatter formatter_type; + formatter_type res_set_fmt(sform_type::name(), sform_type::desc()); + + for (size_t i = 0; m_ins_vn + i * m_ins_vs < m_ins_vm; ++i) + { + const size_t ins_size = m_ins_vn + i * m_ins_vs; + + It ins_it_b = m_ins_b; + It ins_it_e = m_ins_b; + std::advance(ins_it_e, ins_size); + + typedef __gnu_test::tracker_allocator_counter counter_type; + __gnu_test::tracker_allocator<char> alloc; + const size_t init_mem = counter_type::get_allocation_count() + - counter_type::get_deallocation_count(); + Cntnr cntnr(ins_it_b, ins_it_e); + + while (cntnr.size() > 1) + cntnr.erase(*cntnr.begin()); + + const size_t final_mem = counter_type::get_allocation_count() + - counter_type::get_deallocation_count(); + assert(final_mem > init_mem); + const size_t delta_mem = final_mem - init_mem; + res_set_fmt.add_res(ins_size, static_cast<double>(delta_mem)); + } + } + } // namespace test +} // namespace __gnu_pbds + +#endif + diff --git a/libstdc++-v3/testsuite/util/performance/assoc/mem_usage/multimap_insert_test.hpp b/libstdc++-v3/testsuite/util/performance/assoc/mem_usage/multimap_insert_test.hpp new file mode 100644 index 000000000..110dd923f --- /dev/null +++ b/libstdc++-v3/testsuite/util/performance/assoc/mem_usage/multimap_insert_test.hpp @@ -0,0 +1,144 @@ +// -*- C++ -*- + +// Copyright (C) 2005, 2006, 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. + +// You should have received a copy of the GNU General Public License +// along with this library; see the file COPYING3. If not see +// <http://www.gnu.org/licenses/>. + + +// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. + +// Permission to use, copy, modify, sell, and distribute this software +// is hereby granted without fee, provided that the above copyright +// notice appears in all copies, and that both that copyright notice +// and this permission notice appear in supporting documentation. None +// of the above authors, nor IBM Haifa Research Laboratories, make any +// representation about the suitability of this software for any +// purpose. It is provided "as is" without express or implied +// warranty. + +/** + * @file multimap_insert_test.hpp + * Contains a generic multimap_insert_test test. + */ + +#ifndef PB_DS_MULTIMAP_INSERT_TEST_HPP +#define PB_DS_MULTIMAP_INSERT_TEST_HPP + +#include <iterator> +#include <ext/pb_ds/detail/type_utils.hpp> +#include <testsuite_allocator.h> +#include <performance/io/xml_formatter.hpp> +#include <common_type/assoc/string_form.hpp> + +namespace __gnu_pbds +{ + namespace test + { + template<typename It, bool Native> + class multimap_insert_test + { + public: + multimap_insert_test(It b, size_t ins_vn, size_t ins_vs, size_t ins_vm): + m_ins_b(b), m_ins_vn(ins_vn), m_ins_vs(ins_vs), m_ins_vm(ins_vm) + { } + + template<typename Cntnr> + void + operator()(Cntnr); + + private: + multimap_insert_test(const multimap_insert_test&); + + template<typename Cntnr> + size_t + insert(Cntnr, It ins_it_b, It ins_it_e, __gnu_pbds::detail::true_type); + + template<typename Cntnr> + size_t + insert(Cntnr, It ins_it_b, It ins_it_e, __gnu_pbds::detail::false_type); + + const It m_ins_b; + const size_t m_ins_vn; + const size_t m_ins_vs; + const size_t m_ins_vm; + }; + + template<typename It, bool Native> + template<typename Cntnr> + void + multimap_insert_test<It, Native>:: + operator()(Cntnr) + { + typedef xml_result_set_performance_formatter formatter_type; + formatter_type res_set_fmt(string_form<Cntnr>::name(), + string_form<Cntnr>::desc()); + + for (size_t i = 0; m_ins_vn + i * m_ins_vs < m_ins_vm; ++i) + { + const size_t ins_size = m_ins_vn + i * m_ins_vs; + It ins_it_b = m_ins_b; + It ins_it_e = m_ins_b; + std::advance(ins_it_e, ins_size); + + const size_t delta_mem = insert(Cntnr(), ins_it_b, ins_it_e, + __gnu_pbds::detail::integral_constant<int,Native>()); + + res_set_fmt.add_res(ins_size, static_cast<double>(delta_mem)); + } + } + + template<typename It, bool Native> + template<typename Cntnr> + size_t + multimap_insert_test<It, Native>:: + insert(Cntnr, It ins_it_b, It ins_it_e, __gnu_pbds::detail::true_type) + { + typedef __gnu_test::tracker_allocator_counter counter_type; + __gnu_test::tracker_allocator<char> alloc; + const size_t init_mem = counter_type::get_allocation_count() + - counter_type::get_deallocation_count(); + Cntnr cntnr; + for (It ins_it = ins_it_b; ins_it != ins_it_e; ++ins_it) + cntnr.insert((typename Cntnr::const_reference)(*ins_it)); + const size_t final_mem = counter_type::get_allocation_count() + - counter_type::get_deallocation_count(); + assert(final_mem > init_mem); + return (final_mem - init_mem); + } + + template<typename It, bool Native> + template<typename Cntnr> + size_t + multimap_insert_test<It, Native>:: + insert(Cntnr, It ins_it_b, It ins_it_e, __gnu_pbds::detail::false_type) + { + typedef __gnu_test::tracker_allocator_counter counter_type; + __gnu_test::tracker_allocator<char> alloc; + const size_t init_mem = counter_type::get_allocation_count() + - counter_type::get_deallocation_count(); + Cntnr cntnr; + for (It ins_it = ins_it_b; ins_it != ins_it_e; ++ins_it) + cntnr[ins_it->first].insert(ins_it->second); + const size_t final_mem = counter_type::get_allocation_count() + - counter_type::get_deallocation_count(); + assert(final_mem > init_mem); + return (final_mem - init_mem); + } + } // namespace test +} // namespace __gnu_pbds + +#endif + diff --git a/libstdc++-v3/testsuite/util/performance/assoc/multimap_common_type.hpp b/libstdc++-v3/testsuite/util/performance/assoc/multimap_common_type.hpp new file mode 100644 index 000000000..e31abe106 --- /dev/null +++ b/libstdc++-v3/testsuite/util/performance/assoc/multimap_common_type.hpp @@ -0,0 +1,223 @@ +// -*- C++ -*- + +// Copyright (C) 2005, 2006, 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. + +// You should have received a copy of the GNU General Public License +// along with this library; see the file COPYING3. If not see +// <http://www.gnu.org/licenses/>. + + +// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. + +// Permission to use, copy, modify, sell, and distribute this software +// is hereby granted without fee, provided that the above copyright +// notice appears in all copies, and that both that copyright notice +// and this permission notice appear in supporting documentation. None +// of the above authors, nor IBM Haifa Research Laboratories, make any +// representation about the suitability of this software for any +// purpose. It is provided "as is" without express or implied +// warranty. + +/** + * @file multimap_common_type.hpp + * Contains types for a generic multimap_insert_test test. + */ + +#ifndef PB_DS_MULTIMAP_RANDOM_INT_INSERT_TEST_COMMON_TYPE_HPP +#define PB_DS_MULTIMAP_RANDOM_INT_INSERT_TEST_COMMON_TYPE_HPP + +#include <hash_fn/string_hash_fn.hpp> +#include <common_type/assoc/common_type.hpp> + +namespace __gnu_pbds +{ + namespace test + { + namespace detail + { + struct int_hash : public std::unary_function<int, size_t> + { + inline size_t + operator()(const int i) const + { return (static_cast<size_t>(i)); } + }; + + template<typename Key, typename Allocator = std::allocator<char> > + struct hash_set_tl_t + { + typedef + typename __gnu_pbds::test::hash_common_types< + Key, + __gnu_pbds::null_mapped_type, + int_hash, + std::equal_to<Key>, + Allocator>::performance_min_tl + type; + }; + + template<typename Key, typename Allocator = std::allocator<char> > + struct lu_set_tl_t + { + typedef + typename __gnu_pbds::test::lu_common_types< + Key, + __gnu_pbds::null_mapped_type, + std::equal_to< + Key>, + Allocator>::performance_min_tl + type; + }; + + template<typename Key, + class Sec_Tl, + typename Allocator = std::allocator<char> > + struct hash_mmap_tl_t + { + private: + typedef + typename __gnu_pbds::detail::__conditional_type< + __gnu_pbds::detail::is_same< + int, + Key>::value, + int_hash, + string_hash_fn>::__type + hash_fn_t; + + template<typename Cntnr_T> + struct hash_mmap_transform + { + typedef + typename __gnu_pbds::test::hash_common_types< + Key, + Cntnr_T, + hash_fn_t, + std::equal_to< + Key>, + Allocator>::performance_min_tl + type; + }; + + public: + typedef + typename __gnu_cxx::typelist::flatten< + typename __gnu_cxx::typelist::transform< + Sec_Tl, + hash_mmap_transform>::type>::type + type; + }; + + template<typename Key, + class Sec_Tl, + typename Allocator = std::allocator<char> > + struct tree_mmap_tl_t + { + private: + template<typename Cntnr_T> + struct tree_mmap_transform + { + typedef + typename __gnu_pbds::test::tree_common_types< + Key, + Cntnr_T, + std::less< + Key>, + __gnu_pbds::null_tree_node_update, + Allocator>::performance_min_tl + type; + }; + + public: + typedef + typename __gnu_cxx::typelist::flatten< + typename __gnu_cxx::typelist::transform< + Sec_Tl, + tree_mmap_transform>::type>::type + type; + }; + + template<typename Key, typename Mapped, typename Allocator> + struct hash_hash_mmap_tl_t + { + private: + typedef typename hash_set_tl_t<Mapped, Allocator>::type sec_tl_t; + + public: + typedef typename hash_mmap_tl_t<Key, sec_tl_t, Allocator>::type type; + }; + + template<typename Key, typename Mapped, typename Allocator> + struct tree_hash_mmap_tl_t + { + private: + typedef typename hash_set_tl_t<Mapped, Allocator>::type sec_tl_t; + + public: + typedef typename tree_mmap_tl_t<Key, sec_tl_t, Allocator>::type type; + }; + + template<typename Key, typename Mapped, typename Allocator> + struct tree_lu_mmap_tl_t + { + private: + typedef typename lu_set_tl_t<Mapped, Allocator>::type sec_tl_t; + + public: + typedef typename tree_mmap_tl_t<Key, sec_tl_t, Allocator>::type type; + }; + + template<typename Key, typename Mapped, typename Allocator> + struct hash_lu_mmap_tl_t + { + private: + typedef typename lu_set_tl_t<Mapped, Allocator>::type sec_tl_t; + + public: + typedef typename hash_mmap_tl_t<Key, sec_tl_t, Allocator>::type type; + }; + } // namespace detail + + template<typename Key, typename Mapped, typename Allocator> + struct mmap_tl_t + { + private: + typedef + typename detail::hash_hash_mmap_tl_t<Key, Mapped, Allocator>::type + hh_mmap_tl_t; + + typedef + typename detail::hash_lu_mmap_tl_t<Key, Mapped, Allocator>::type + hl_mmap_tl_t; + + typedef + typename detail::tree_hash_mmap_tl_t<Key, Mapped, Allocator>::type + th_mmap_tl_t; + + typedef + typename detail::tree_lu_mmap_tl_t<Key, Mapped, Allocator>::type + tl_mmap_tl_t; + + public: + typedef + typename __gnu_cxx::typelist::append<hl_mmap_tl_t, + typename __gnu_cxx::typelist::append<hh_mmap_tl_t, + typename __gnu_cxx::typelist::append<th_mmap_tl_t, + tl_mmap_tl_t>::type>::type>::type + type; + }; + + } // namespace test +} // namespace __gnu_pbds + +#endif + diff --git a/libstdc++-v3/testsuite/util/performance/assoc/timing/common_type.hpp b/libstdc++-v3/testsuite/util/performance/assoc/timing/common_type.hpp new file mode 100644 index 000000000..a553afeab --- /dev/null +++ b/libstdc++-v3/testsuite/util/performance/assoc/timing/common_type.hpp @@ -0,0 +1,103 @@ +// -*- C++ -*- + +// Copyright (C) 2005, 2006, 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. + +// You should have received a copy of the GNU General Public License +// along with this library; see the file COPYING3. If not see +// <http://www.gnu.org/licenses/>. + + +// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. + +// Permission to use, copy, modify, sell, and distribute this software +// is hereby granted without fee, provided that the above copyright +// notice appears in all copies, and that both that copyright notice +// and this permission notice appear in supporting documentation. None +// of the above authors, nor IBM Haifa Research Laboratories, make any +// representation about the suitability of this software for any +// purpose. It is provided "as is" without express or implied +// warranty. + +/** + * @file common_type.hpp + * Contains types for a generic multimap_insert_test test. + */ + +#ifndef PB_DS_MULTIMAP_RANDOM_INT_INSERT_TEST_COMMON_TYPE_HPP +#define PB_DS_MULTIMAP_RANDOM_INT_INSERT_TEST_COMMON_TYPE_HPP + +#include <common_type/assoc/common_type.hpp> + +namespace __gnu_pbds +{ + + namespace test + { + + typedef + __gnu_pbds::test::hash_common_types< + int, + __gnu_pbds::null_mapped_type>::tl + hash_set_tl_t; + + template<typename Cntnr_T> + struct hash_mmap_transform + { + typedef + typename __gnu_pbds::test::hash_common_types< + int, + __gnu_pbds::compound_data_type< + Cntnr_T> >::tl + type; + }; + + typedef + __gnu_cxx::typelist::flatten< + __gnu_cxx::typelist::transform< + hash_set_tl_t, + hash_mmap_transform>::type>::type + hash_mmap_tl_t; + + typedef + __gnu_pbds::test::tree_common_types< + int, + __gnu_pbds::null_mapped_type>::tl + tree_set_tl_t; + + template<typename Cntnr_T> + struct tree_mmap_transform + { + typedef + typename __gnu_pbds::test::tree_common_types< + int, + __gnu_pbds::compound_data_type< + Cntnr_T> >::tl + type; + }; + + typedef + __gnu_cxx::typelist::flatten< + __gnu_cxx::typelist::transform< + tree_set_tl_t, + tree_mmap_transform>::type>::type + tree_mmap_tl_t; + + typedef hash_mmap_tl_t mmap_tl_t; + + } // namespace test + +} // namespace __gnu_pbds + +#endif // #ifndef PB_DS_MULTIMAP_RANDOM_INT_INSERT_TEST_COMMON_TYPE_HPP + diff --git a/libstdc++-v3/testsuite/util/performance/assoc/timing/find_test.hpp b/libstdc++-v3/testsuite/util/performance/assoc/timing/find_test.hpp new file mode 100644 index 000000000..f53a1273c --- /dev/null +++ b/libstdc++-v3/testsuite/util/performance/assoc/timing/find_test.hpp @@ -0,0 +1,166 @@ +// -*- C++ -*- + +// Copyright (C) 2005, 2006, 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. + +// You should have received a copy of the GNU General Public License +// along with this library; see the file COPYING3. If not see +// <http://www.gnu.org/licenses/>. + + +// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. + +// Permission to use, copy, modify, sell, and distribute this software +// is hereby granted without fee, provided that the above copyright +// notice appears in all copies, and that both that copyright notice +// and this permission notice appear in supporting documentation. None +// of the above authors, nor IBM Haifa Research Laboratories, make any +// representation about the suitability of this software for any +// purpose. It is provided "as is" without express or implied +// warranty. + +/** + * @file find_test.hpp + * Contains a generic find test. + */ + +#ifndef PB_DS_FIND_TEST_HPP +#define PB_DS_FIND_TEST_HPP + +#include <performance/time/timing_test_base.hpp> +#include <performance/io/xml_formatter.hpp> +#include <common_type/assoc/string_form.hpp> +#include <iterator> + +namespace __gnu_pbds +{ + namespace test + { + namespace detail + { + template<typename It, class Cntnr, bool LOR> + class find_find_functor + { + public: + find_find_functor(Cntnr& contnr, It fnd_it_b, It fnd_it_e) + : m_contnr(contnr), m_fnd_it_b(fnd_it_b), m_fnd_it_e(fnd_it_e) + { } + + void + operator()(std::size_t resolution) + { + for (std::size_t i = 0; i < resolution; ++i) + { + It fnd_it = m_fnd_it_b; + while (fnd_it != m_fnd_it_e) + ++m_contnr.find((fnd_it++)->first)->second; + } + } + + private: + Cntnr& m_contnr; + const It m_fnd_it_b; + const It m_fnd_it_e; + }; + + template<typename It, class Cntnr> + class find_find_functor<It, Cntnr, true> + { + public: + find_find_functor(Cntnr& contnr, It fnd_it_b, It fnd_it_e) + : m_contnr(contnr), m_fnd_it_b(fnd_it_b), m_fnd_it_e(fnd_it_e) + { } + + void + operator()(std::size_t resolution) + { + It fnd_it = m_fnd_it_b; + while (fnd_it != m_fnd_it_e) + { + for (std::size_t i = 0; i < resolution; ++i) + ++m_contnr.find(fnd_it->first)->second; + ++fnd_it; + } + } + + private: + Cntnr& m_contnr; + const It m_fnd_it_b; + const It m_fnd_it_e; + }; + } // namespace detail + + template<typename It, bool LOR = false> + class find_test : private __gnu_pbds::test::detail::timing_test_base + { + public: + find_test(It ins_b, It fnd_it_b, size_t ins_vn, size_t ins_vs, + size_t ins_vm, size_t fnd_vn, size_t fnd_vs, size_t fnd_vm): + m_ins_b(ins_b), m_fnd_it_b(fnd_it_b), m_ins_vn(ins_vn), m_ins_vs(ins_vs), + m_ins_vm(ins_vm), m_fnd_vn(fnd_vn), m_fnd_vs(fnd_vs), m_fnd_vm(fnd_vm) + { } + + template<typename Cntnr> + void + operator()(Cntnr); + + private: + find_test(const find_test& ); + + private: + const It m_ins_b; + const It m_fnd_it_b; + const size_t m_ins_vn; + const size_t m_ins_vs; + const size_t m_ins_vm; + const size_t m_fnd_vn; + const size_t m_fnd_vs; + const size_t m_fnd_vm; + }; + + template<typename It, bool LOR> + template<typename Cntnr> + void + find_test<It, LOR>:: + operator()(Cntnr) + { + typedef string_form<Cntnr> sform_type; + typedef xml_result_set_performance_formatter formatter_type; + formatter_type res_set_fmt(sform_type::name(), sform_type::desc()); + + for (size_t i = 0; m_ins_vn + i * m_ins_vs < m_ins_vm; ++i) + { + const size_t v = m_ins_vn + i * m_ins_vs; + const size_t fnd_size = m_fnd_vn + i * m_fnd_vs; + It ins_it_b = m_ins_b; + It ins_it_e = m_ins_b; + std::advance(ins_it_e, v); + + Cntnr test_container(ins_it_b, ins_it_e); + It fnd_it_b = m_fnd_it_b; + It fnd_it_e = m_fnd_it_b; + std::advance(fnd_it_e, fnd_size); + + __gnu_pbds::test::detail::find_find_functor<It, Cntnr, LOR> + fn(test_container, fnd_it_b, fnd_it_e); + + const double res = + __gnu_pbds::test::detail::timing_test_base::operator()(fn); + res_set_fmt.add_res(v, res / fnd_size); + } + } + } // namespace test +} // namespace __gnu_pbds + +#endif + diff --git a/libstdc++-v3/testsuite/util/performance/assoc/timing/insert_test.hpp b/libstdc++-v3/testsuite/util/performance/assoc/timing/insert_test.hpp new file mode 100644 index 000000000..e71d755ba --- /dev/null +++ b/libstdc++-v3/testsuite/util/performance/assoc/timing/insert_test.hpp @@ -0,0 +1,143 @@ +// -*- C++ -*- + +// Copyright (C) 2005, 2006, 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. + +// You should have received a copy of the GNU General Public License +// along with this library; see the file COPYING3. If not see +// <http://www.gnu.org/licenses/>. + + +// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. + +// Permission to use, copy, modify, sell, and distribute this software +// is hereby granted without fee, provided that the above copyright +// notice appears in all copies, and that both that copyright notice +// and this permission notice appear in supporting documentation. None +// of the above authors, nor IBM Haifa Research Laboratories, make any +// representation about the suitability of this software for any +// purpose. It is provided "as is" without express or implied +// warranty. + +/** + * @file insert_test.hpp + * Contains an insert performance test. + */ + +#ifndef PB_DS_INSERT_TEST_HPP +#define PB_DS_INSERT_TEST_HPP + +#include <performance/time/timing_test_base.hpp> +#include <ext/pb_ds/detail/type_utils.hpp> +#include <performance/io/xml_formatter.hpp> +#include <common_type/assoc/string_form.hpp> +#include <iterator> + +namespace __gnu_pbds +{ + namespace test + { + namespace detail + { + template<typename It, class Cntnr> + class insert_insert_functor + { + public: + insert_insert_functor(It ins_it_b, It ins_it_e) + : m_ins_it_b(ins_it_b), m_ins_it_e(ins_it_e) + { } + + void + operator()(std::size_t resolution) + { + for (std::size_t i = 0; i < resolution; ++i) + { + Cntnr cntnr; + for (It ins_it = m_ins_it_b; ins_it != m_ins_it_e; ++ins_it) + cntnr.insert((typename Cntnr::const_reference)(*ins_it)); + } + } + + private: + const It m_ins_it_b; + const It m_ins_it_e; + }; + } // namespace detail + + template<typename It> + class insert_test : private __gnu_pbds::test::detail::timing_test_base + { + public: + insert_test(It ins_b, size_t ins_vn, size_t ins_vs, size_t ins_vm) + : m_ins_b(ins_b), m_ins_vn(ins_vn), m_ins_vs(ins_vs), m_ins_vm(ins_vm) + { } + + template<typename Cntnr> + void + operator()(Cntnr); + + private: + insert_test(const insert_test& ); + + template<typename Cntnr> + void + insert(Cntnr, It ins_it_b, It ins_it_e); + + const It m_ins_b; + const size_t m_ins_vn; + const size_t m_ins_vs; + const size_t m_ins_vm; + }; + + template<typename It> + template<typename Cntnr> + void + insert_test<It>:: + operator()(Cntnr) + { + typedef xml_result_set_performance_formatter formatter_type; + formatter_type res_set_fmt(string_form<Cntnr>::name(), + string_form<Cntnr>::desc()); + + for (size_t i = 0; m_ins_vn + i* m_ins_vs < m_ins_vm; ++i) + { + const size_t v = m_ins_vn + i* m_ins_vs; + It ins_it_b = m_ins_b; + It ins_it_e = m_ins_b; + std::advance(ins_it_e, v); + + __gnu_pbds::test::detail::insert_insert_functor<It, Cntnr> + fn(ins_it_b, ins_it_e); + + const double res = + __gnu_pbds::test::detail::timing_test_base::operator()(fn); + + res_set_fmt.add_res(v, res / v); + } + } + + template<typename It> + template<typename Cntnr> + void + insert_test<It>:: + insert(Cntnr, It ins_it_b, It ins_it_e) + { + Cntnr cntnr; + for (It ins_it = ins_it_b; ins_it != ins_it_e; ++ins_it) + cntnr.insert((typename Cntnr::const_reference)(*ins_it)); + } + } // namespace test +} // namespace __gnu_pbds + +#endif + diff --git a/libstdc++-v3/testsuite/util/performance/assoc/timing/multimap_find_test.hpp b/libstdc++-v3/testsuite/util/performance/assoc/timing/multimap_find_test.hpp new file mode 100644 index 000000000..7e3f95bfc --- /dev/null +++ b/libstdc++-v3/testsuite/util/performance/assoc/timing/multimap_find_test.hpp @@ -0,0 +1,191 @@ +// -*- C++ -*- + +// Copyright (C) 2005, 2006, 2007, 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. + +// You should have received a copy of the GNU General Public License +// along with this library; see the file COPYING3. If not see +// <http://www.gnu.org/licenses/>. + + +// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. + +// Permission to use, copy, modify, sell, and distribute this software +// is hereby granted without fee, provided that the above copyright +// notice appears in all copies, and that both that copyright notice +// and this permission notice appear in supporting documentation. None +// of the above authors, nor IBM Haifa Research Laboratories, make any +// representation about the suitability of this software for any +// purpose. It is provided "as is" without express or implied +// warranty. + +/** + * @file multimap_find_test.hpp + * Contains a generic multimap_find_test test. + */ + +#ifndef PB_DS_MULTIMAP_INSERT_TEST_HPP +#define PB_DS_MULTIMAP_INSERT_TEST_HPP + +#include <performance/time/timing_test_base.hpp> +#include <performance/io/xml_formatter.hpp> +#include <common_type/assoc/string_form.hpp> +#include <iterator> + +namespace __gnu_pbds +{ + namespace test + { + namespace detail + { + template<typename It, class Cntnr, bool Native> + class multimap_find_functor + { + public: + multimap_find_functor(const Cntnr& container, It fnd_it_b, It fnd_it_e) + : m_r_container(container), m_fnd_it_b(fnd_it_b), m_fnd_it_e(fnd_it_e) + { } + + void + operator()(std::size_t resolution) + { + size_t not_found_count = 0; + typedef typename Cntnr::const_point_iterator iterator_type; + for (std::size_t i = 0; i < resolution; ++i) + { + iterator_type end = m_r_container.end(); + for (It fnd_it = m_fnd_it_b; fnd_it != m_fnd_it_e; ++fnd_it) + { + iterator_type it = m_r_container.find(fnd_it->first); + if (it == end || + it->second.find(fnd_it->second) == it->second.end()) + ++not_found_count; + } + } + + if (not_found_count != 0) + std::abort(); + } + + private: + const Cntnr& m_r_container; + const It m_fnd_it_b; + const It m_fnd_it_e; + }; + + template<typename It, class Cntnr> + class multimap_find_functor<It, Cntnr, true> + { + public: + multimap_find_functor(const Cntnr& container, It fnd_it_b, It fnd_it_e) + : m_r_container(container), m_fnd_it_b(fnd_it_b), m_fnd_it_e(fnd_it_e) + { } + + void + operator()(std::size_t resolution) + { + typedef typename Cntnr::const_reference const_reference; + size_t not_found_count = 0; + for (std::size_t i = 0; i < resolution; ++i) + { + Cntnr cntnr; + for (It fnd_it = m_fnd_it_b; fnd_it != m_fnd_it_e; ++fnd_it) + if (m_r_container.find(const_reference(*fnd_it)) + == m_r_container.end()) + ++not_found_count; + } + + if (not_found_count != 0) + std::abort(); + } + + private: + const Cntnr& m_r_container; + const It m_fnd_it_b; + const It m_fnd_it_e; + }; + } // namespace detail + + + template<typename It, bool Native> + class multimap_find_test + : private __gnu_pbds::test::detail::timing_test_base + { + public: + multimap_find_test(It ins_b, size_t ins_vn, size_t vs, size_t ins_vm) + : m_ins_b(ins_b), m_ins_vn(ins_vn), m_ins_vs(vs), m_ins_vm(ins_vm) + { } + + template<typename Cntnr> + void + operator()(Cntnr); + + private: + multimap_find_test(const multimap_find_test&); + + template<typename Cntnr> + Cntnr + init(It ins_b, It ins_e, Cntnr, __gnu_pbds::detail::true_type) + { return Cntnr(ins_b, ins_e); } + + template<typename Cntnr> + Cntnr + init(It ins_b, It ins_e, Cntnr, __gnu_pbds::detail::false_type) + { + Cntnr ret; + for (It it = ins_b; it != ins_e; ++it) + ret[it->first].insert(it->second); + return ret; + } + + const It m_ins_b; + const size_t m_ins_vn; + const size_t m_ins_vs; + const size_t m_ins_vm; + }; + + + template<typename It, bool Native> + template<typename Cntnr> + void + multimap_find_test<It, Native>:: + operator()(Cntnr) + { + typedef xml_result_set_performance_formatter formatter_type; + formatter_type res_set_fmt(string_form<Cntnr>::name(), + string_form<Cntnr>::desc()); + + for (size_t i = 0; m_ins_vn + i * m_ins_vs < m_ins_vm; ++i) + { + const size_t v = m_ins_vn + i * m_ins_vs; + It ins_it_b = m_ins_b; + It ins_it_e = m_ins_b; + std::advance(ins_it_e, v); + + Cntnr c = init(ins_it_b, ins_it_e, Cntnr(), + __gnu_pbds::detail::integral_constant<int,Native>()); + + __gnu_pbds::test::detail::multimap_find_functor<It, Cntnr, Native> + fn(c, ins_it_b, ins_it_e); + + const double res = + __gnu_pbds::test::detail::timing_test_base::operator()(fn); + + res_set_fmt.add_res(v, res / v); + } + } + } // namespace test +} // namespace __gnu_pbds + +#endif + diff --git a/libstdc++-v3/testsuite/util/performance/assoc/timing/multimap_insert_test.hpp b/libstdc++-v3/testsuite/util/performance/assoc/timing/multimap_insert_test.hpp new file mode 100644 index 000000000..2e8539857 --- /dev/null +++ b/libstdc++-v3/testsuite/util/performance/assoc/timing/multimap_insert_test.hpp @@ -0,0 +1,151 @@ +// -*- C++ -*- + +// Copyright (C) 2005, 2006, 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. + +// You should have received a copy of the GNU General Public License +// along with this library; see the file COPYING3. If not see +// <http://www.gnu.org/licenses/>. + + +// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. + +// Permission to use, copy, modify, sell, and distribute this software +// is hereby granted without fee, provided that the above copyright +// notice appears in all copies, and that both that copyright notice +// and this permission notice appear in supporting documentation. None +// of the above authors, nor IBM Haifa Research Laboratories, make any +// representation about the suitability of this software for any +// purpose. It is provided "as is" without express or implied +// warranty. + +/** + * @file multimap_insert_test.hpp + * Contains a generic multimap_insert_test test. + */ + +#ifndef PB_DS_MULTIMAP_INSERT_TEST_HPP +#define PB_DS_MULTIMAP_INSERT_TEST_HPP + +#include <performance/time/timing_test_base.hpp> +#include <performance/io/xml_formatter.hpp> +#include <common_type/assoc/string_form.hpp> +#include <iterator> + +namespace __gnu_pbds +{ + namespace test + { + namespace detail + { + template<typename It, class Cntnr, bool Native> + class multimap_insert_functor + { + public: + multimap_insert_functor(It ins_it_b, It ins_it_e) + : m_ins_it_b(ins_it_b), m_ins_it_e(ins_it_e) + { } + + void + operator()(std::size_t resolution) + { + for (std::size_t i = 0; i < resolution; ++i) + { + Cntnr cntnr; + for (It ins_it = m_ins_it_b; ins_it != m_ins_it_e; ++ins_it) + cntnr[ins_it->first].insert(ins_it->second); + } + } + + private: + const It m_ins_it_b; + const It m_ins_it_e; + }; + + template<typename It, class Cntnr> + class multimap_insert_functor<It, Cntnr, true> + { + public: + multimap_insert_functor(It ins_it_b, It ins_it_e) + : m_ins_it_b(ins_it_b), m_ins_it_e(ins_it_e) + { } + + void + operator()(std::size_t resolution) + { + for (std::size_t i = 0; i < resolution; ++i) + { + Cntnr cntnr; + for (It ins_it = m_ins_it_b; ins_it != m_ins_it_e; ++ins_it) + cntnr.insert((typename Cntnr::const_reference)(*ins_it)); + } + } + + private: + const It m_ins_it_b; + const It m_ins_it_e; + }; + } // namespace detail + + template<typename It, bool Native> + class multimap_insert_test + : private __gnu_pbds::test::detail::timing_test_base + { + public: + multimap_insert_test(It b, size_t ins_vn, size_t ins_vs, size_t ins_vm) + : m_ins_b(b), m_ins_vn(ins_vn), m_ins_vs(ins_vs), m_ins_vm(ins_vm) + { } + + template<typename Cntnr> + void + operator()(Cntnr); + + private: + multimap_insert_test(const multimap_insert_test&); + + const It m_ins_b; + const size_t m_ins_vn; + const size_t m_ins_vs; + const size_t m_ins_vm; + }; + + template<typename It, bool Native> + template<typename Cntnr> + void + multimap_insert_test<It, Native>:: + operator()(Cntnr) + { + typedef xml_result_set_performance_formatter formatter_type; + formatter_type res_set_fmt(string_form<Cntnr>::name(), + string_form<Cntnr>::desc()); + + for (size_t i = 0; m_ins_vn + i * m_ins_vs < m_ins_vm; ++i) + { + const size_t v = m_ins_vn + i * m_ins_vs; + It ins_it_b = m_ins_b; + It ins_it_e = m_ins_b; + std::advance(ins_it_e, v); + + __gnu_pbds::test::detail::multimap_insert_functor<It, Cntnr, Native> + fn(ins_it_b, ins_it_e); + + const double res = + __gnu_pbds::test::detail::timing_test_base::operator()(fn); + res_set_fmt.add_res(v, res / v); + } + } + } // namespace test +} // namespace __gnu_pbds + +#endif + diff --git a/libstdc++-v3/testsuite/util/performance/assoc/timing/subscript_find_test.hpp b/libstdc++-v3/testsuite/util/performance/assoc/timing/subscript_find_test.hpp new file mode 100644 index 000000000..d37121b8c --- /dev/null +++ b/libstdc++-v3/testsuite/util/performance/assoc/timing/subscript_find_test.hpp @@ -0,0 +1,144 @@ +// -*- C++ -*- + +// Copyright (C) 2005, 2006, 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. + +// You should have received a copy of the GNU General Public License +// along with this library; see the file COPYING3. If not see +// <http://www.gnu.org/licenses/>. + + +// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. + +// Permission to use, copy, modify, sell, and distribute this software +// is hereby granted without fee, provided that the above copyright +// notice appears in all copies, and that both that copyright notice +// and this permission notice appear in supporting documentation. None +// of the above authors, nor IBM Haifa Research Laboratories, make any +// representation about the suitability of this software for any +// purpose. It is provided "as is" without express or implied +// warranty. + +/** + * @file subscript_find_test.hpp + * Contains a generic subscript_find_test test. + */ + +#ifndef PB_DS_SUBSCRIPT_TEST_HPP +#define PB_DS_SUBSCRIPT_TEST_HPP + +#include <performance/time/timing_test_base.hpp> +#include <common_type/assoc/string_form.hpp> +#include <iterator> + +namespace __gnu_pbds +{ + namespace test + { + namespace detail + { + template<typename It, class Cntnr> + class subscript_find_functor + { + public: + subscript_find_functor(Cntnr& container, It fnd_it_b, It fnd_it_e) + : m_r_container(container), m_fnd_it_b(fnd_it_b), m_fnd_it_e(fnd_it_e) + { } + + void + operator()(std::size_t resolution) + { + for (std::size_t i = 0; i < resolution; ++i) + { + It fnd_it = m_fnd_it_b; + while (fnd_it != m_fnd_it_e) + ++m_r_container[(fnd_it++)->first]; + ++fnd_it; + } + } + + private: + Cntnr& m_r_container; + const It m_fnd_it_b; + const It m_fnd_it_e; + }; + + } // namespace detail + + template<typename It> + class subscript_find_test : private __gnu_pbds::test::detail::timing_test_base + { + public: + subscript_find_test(It ins_b, It b, size_t ins_vn, size_t ins_vs, + size_t ins_vm, size_t vn, size_t vs, size_t vm) + : m_ins_b(ins_b), m_fnd_b(b), m_ins_vn(ins_vn), m_ins_vs(ins_vs), + m_ins_vm(ins_vm), m_fnd_vn(vn), m_fnd_vs(vs), m_fnd_vm(vm) + { } + + template<typename Cntnr> + void + operator()(Cntnr); + + private: + subscript_find_test(const subscript_find_test&); + + private: + const It m_ins_b; + const It m_fnd_b; + const size_t m_ins_vn; + const size_t m_ins_vs; + const size_t m_ins_vm; + const size_t m_fnd_vn; + const size_t m_fnd_vs; + const size_t m_fnd_vm; + }; + + template<typename It> + template<typename Cntnr> + void + subscript_find_test<It>:: + operator()(Cntnr) + { + typedef xml_result_set_performance_formatter formatter_type; + formatter_type res_set_fmt(string_form<Cntnr>::name(), + string_form<Cntnr>::desc()); + + for (size_t i = 0; m_ins_vn + i* m_ins_vs < m_ins_vm; ++i) + { + const size_t v = m_ins_vn + i* m_ins_vs; + const size_t fnd_size = m_fnd_vn + i* m_fnd_vs; + + It ins_it_b = m_ins_b; + It ins_it_e = m_ins_b; + std::advance(ins_it_e, v); + + Cntnr test_container(ins_it_b, ins_it_e); + + It fnd_it_b = m_fnd_b; + It fnd_it_e = m_fnd_b; + std::advance(fnd_it_e, fnd_size); + + __gnu_pbds::test::detail::subscript_find_functor<It, Cntnr> + fn(test_container, fnd_it_b, fnd_it_e); + + const double res = + __gnu_pbds::test::detail::timing_test_base::operator()(fn); + + res_set_fmt.add_res(v, res / fnd_size); + } + } + } // namespace test +} // namespace __gnu_pbds + +#endif + diff --git a/libstdc++-v3/testsuite/util/performance/assoc/timing/subscript_insert_test.hpp b/libstdc++-v3/testsuite/util/performance/assoc/timing/subscript_insert_test.hpp new file mode 100644 index 000000000..10925fd60 --- /dev/null +++ b/libstdc++-v3/testsuite/util/performance/assoc/timing/subscript_insert_test.hpp @@ -0,0 +1,134 @@ +// -*- C++ -*- + +// Copyright (C) 2005, 2006, 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. + +// You should have received a copy of the GNU General Public License +// along with this library; see the file COPYING3. If not see +// <http://www.gnu.org/licenses/>. + + +// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. + +// Permission to use, copy, modify, sell, and distribute this software +// is hereby granted without fee, provided that the above copyright +// notice appears in all copies, and that both that copyright notice +// and this permission notice appear in supporting documentation. None +// of the above authors, nor IBM Haifa Research Laboratories, make any +// representation about the suitability of this software for any +// purpose. It is provided "as is" without express or implied +// warranty. + +/** + * @file subscript_insert_test.hpp + * Contains a generic subscript_insert_test test. + */ + +#ifndef PB_DS_SUBSCRIPT_TEST_HPP +#define PB_DS_SUBSCRIPT_TEST_HPP + +#include <performance/time/timing_test_base.hpp> +#include <performance/io/xml_formatter.hpp> +#include <common_type/assoc/string_form.hpp> +#include <iterator> + +namespace __gnu_pbds +{ + namespace test + { + namespace detail + { + template<typename It, class Cntnr> + class subscript_insert_functor + { + public: + subscript_insert_functor(It ins_it_b, It ins_it_e) + : m_ins_it_b(ins_it_b), m_ins_it_e(ins_it_e) + { } + + void + operator()(std::size_t resolution) + { + for (std::size_t i = 0; i < resolution; ++i) + { + Cntnr cntnr; + for (It ins_it = m_ins_it_b; ins_it != m_ins_it_e; ++ins_it) + ++cntnr[ins_it->first]; + } + } + + private: + const It m_ins_it_b; + const It m_ins_it_e; + }; + + } // namespace detail + + template<typename It> + class subscript_insert_test : private __gnu_pbds::test::detail::timing_test_base + { + public: + subscript_insert_test(It ins_b, It b, size_t ins_vn, size_t ins_vs, + size_t ins_vm, size_t vn, size_t vs, size_t vm) + : m_ins_b(ins_b), m_fnd_b(b), m_ins_vn(ins_vn), m_ins_vs(ins_vs), + m_ins_vm(ins_vm), m_fnd_vn(vn), m_fnd_vs(vs), m_fnd_vm(vm) + { } + + template<typename Cntnr> + void + operator()(Cntnr); + + private: + subscript_insert_test(const subscript_insert_test& ); + + private: + const It m_ins_b; + const It m_fnd_b; + const size_t m_ins_vn; + const size_t m_ins_vs; + const size_t m_ins_vm; + const size_t m_fnd_vn; + const size_t m_fnd_vs; + const size_t m_fnd_vm; + }; + + template<typename It> + template<typename Cntnr> + void + subscript_insert_test<It>:: + operator()(Cntnr) + { + typedef xml_result_set_performance_formatter formatter_type; + formatter_type res_set_fmt(string_form<Cntnr>::name(), + string_form<Cntnr>::desc()); + + for (size_t i = 0; m_ins_vn + i * m_ins_vs < m_ins_vm; ++i) + { + const size_t v = m_ins_vn + i * m_ins_vs; + It ins_it_b = m_ins_b; + It ins_it_e = m_ins_b; + std::advance(ins_it_e, v); + __gnu_pbds::test::detail::subscript_insert_functor<It, Cntnr> + fn(ins_it_b, ins_it_e); + + const double res = + __gnu_pbds::test::detail::timing_test_base::operator()(fn); + + res_set_fmt.add_res(v, res / v); + } + } + } // namespace test +} // namespace __gnu_pbds + +#endif + diff --git a/libstdc++-v3/testsuite/util/performance/assoc/timing/tree_order_statistics_test.hpp b/libstdc++-v3/testsuite/util/performance/assoc/timing/tree_order_statistics_test.hpp new file mode 100644 index 000000000..0fb028687 --- /dev/null +++ b/libstdc++-v3/testsuite/util/performance/assoc/timing/tree_order_statistics_test.hpp @@ -0,0 +1,176 @@ +// -*- C++ -*- + +// Copyright (C) 2005, 2006, 2007, 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. + +// You should have received a copy of the GNU General Public License +// along with this library; see the file COPYING3. If not see +// <http://www.gnu.org/licenses/>. + + +// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. + +// Permission to use, copy, modify, sell, and distribute this software +// is hereby granted without fee, provided that the above copyright +// notice appears in all copies, and that both that copyright notice +// and this permission notice appear in supporting documentation. None +// of the above authors, nor IBM Haifa Research Laboratories, make any +// representation about the suitability of this software for any +// purpose. It is provided "as is" without express or implied +// warranty. + +/** + * @file tree_order_statistics_test.hpp + * Contains a test for order_statisticsing trees + */ + +#ifndef PB_DS_TREE_ORDER_STATISTICS_TEST_HPP +#define PB_DS_TREE_ORDER_STATISTICS_TEST_HPP + +#include <performance/time/timing_test_base.hpp> +#include <performance/io/xml_formatter.hpp> +#include <common_type/assoc/string_form.hpp> +#include <ext/pb_ds/detail/type_utils.hpp> +#include <iterator> +#include <cstdlib> + +namespace __gnu_pbds +{ + namespace test + { + namespace detail + { + template<typename Cntnr, bool Native> + class order_statistics_functor + { + public: + order_statistics_functor(Cntnr& container) : m_r_container(container) + { } + + void + operator()(std::size_t resolution) + { + enum + { + support_detected = + __gnu_pbds::test::detail::tree_supports_order_statistics<Cntnr>::value + }; + + PB_DS_STATIC_ASSERT(correct_type, support_detected); + + for (std::size_t i = 0; i < resolution; ++i) + { + typename Cntnr::const_iterator it = m_r_container.begin(); + typename Cntnr::const_iterator e = m_r_container.end(); + const size_t max_size = m_r_container.size(); + while (it != e) + if (m_r_container.order_of_key(*(it++)) > max_size) + std::abort(); + } + } + + private: + Cntnr& m_r_container; + }; + + template<typename Cntnr> + class order_statistics_functor<Cntnr, false> + { + public: + order_statistics_functor(Cntnr& container) : m_r_container(container) + { } + + void + operator()(std::size_t resolution) + { + for (std::size_t i = 0; i < resolution; ++i) + { + typedef typename Cntnr::const_iterator const_iterator; + const_iterator b = m_r_container.begin(); + const_iterator e = m_r_container.end(); + const_iterator it = b; + const size_t max_size = m_r_container.size(); + while (it != e) + { + const_iterator f_it = m_r_container.find(*(it++)); + if (static_cast<size_t>(std::distance(b, f_it)) > max_size) + std::abort(); + } + } + } + + private: + Cntnr& m_r_container; + }; + } // namespace detail + + template<bool Support_Order_Statistics> + class tree_order_statistics_test + : private __gnu_pbds::test::detail::timing_test_base + { + public: + tree_order_statistics_test(size_t vn, size_t vs, size_t vm) + : m_vn(vn), m_vs(vs), m_vm(vm) + { } + + template<typename Cntnr> + void + operator()(Cntnr); + + private: + tree_order_statistics_test(const tree_order_statistics_test& ); + + template<typename Cntnr> + void + order_statistics(Cntnr& r_container, __gnu_pbds::detail::true_type); + + template<typename Cntnr> + void + order_statistics(Cntnr& r_container, __gnu_pbds::detail::false_type); + + private: + const size_t m_vn; + const size_t m_vs; + const size_t m_vm; + }; + + template<bool Support_Order_Statistics> + template<typename Cntnr> + void + tree_order_statistics_test<Support_Order_Statistics>:: + operator()(Cntnr) + { + typedef xml_result_set_performance_formatter formatter_type; + formatter_type res_set_fmt(string_form<Cntnr>::name(), + string_form<Cntnr>::desc()); + + for (size_t v = m_vn; v < m_vm; v += m_vs) + { + Cntnr cntnr; + for (size_t ins = 0; ins < v; ++ ins) + cntnr.insert((typename Cntnr::value_type)ins); + + __gnu_pbds::test::detail::order_statistics_functor<Cntnr, Support_Order_Statistics> + fn(cntnr); + + const double res = + __gnu_pbds::test::detail::timing_test_base::operator()(fn); + + res_set_fmt.add_res(v, res / v); + } + } + } // namespace test +} // namespace __gnu_pbds + +#endif + diff --git a/libstdc++-v3/testsuite/util/performance/assoc/timing/tree_split_join_test.hpp b/libstdc++-v3/testsuite/util/performance/assoc/timing/tree_split_join_test.hpp new file mode 100644 index 000000000..6872291df --- /dev/null +++ b/libstdc++-v3/testsuite/util/performance/assoc/timing/tree_split_join_test.hpp @@ -0,0 +1,158 @@ +// -*- C++ -*- + +// Copyright (C) 2005, 2006, 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. + +// You should have received a copy of the GNU General Public License +// along with this library; see the file COPYING3. If not see +// <http://www.gnu.org/licenses/>. + + +// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. + +// Permission to use, copy, modify, sell, and distribute this software +// is hereby granted without fee, provided that the above copyright +// notice appears in all copies, and that both that copyright notice +// and this permission notice appear in supporting documentation. None +// of the above authors, nor IBM Haifa Research Laboratories, make any +// representation about the suitability of this software for any +// purpose. It is provided "as is" without express or implied +// warranty. + +/** + * @file tree_split_join_test.hpp + * Contains a test for splitting and joining trees + */ + +#ifndef PB_DS_TREE_SPLIT_JOIN_TEST_HPP +#define PB_DS_TREE_SPLIT_JOIN_TEST_HPP + +#include <performance/time/timing_test_base.hpp> +#include <performance/io/xml_formatter.hpp> +#include <common_type/assoc/string_form.hpp> +#include <iterator> + +namespace __gnu_pbds +{ + namespace test + { + namespace detail + { + template<typename Cntnr, bool Support_Split_Join> + class split_join_functor + { + public: + split_join_functor(Cntnr& r_container) : m_r_container(r_container) + { } + + void + operator()(std::size_t resolution) + { + for (std::size_t i = 0; i < resolution; ++i) + { + typename Cntnr::const_iterator mid_it = m_r_container.begin(); + std::advance(mid_it, m_r_container.size() / 2); + Cntnr other; + m_r_container.split(*mid_it, other); + m_r_container.join(other); + } + } + + private: + Cntnr& m_r_container; + }; + + template<typename Cntnr> + class split_join_functor<Cntnr, false> + { + public: + split_join_functor(Cntnr& r_container) : m_r_container(r_container) + { } + + void + operator()(std::size_t resolution) + { + for (std::size_t i = 0; i < resolution; ++i) + { + typename Cntnr::iterator mid_it = m_r_container.begin(); + std::advance(mid_it, m_r_container.size() / 2); + + Cntnr other(mid_it, m_r_container.end()); + m_r_container.erase(mid_it, m_r_container.end()); + + m_r_container.insert(other.begin(), other.end()); + other.clear(); + } + } + + private: + Cntnr& m_r_container; + }; + } // namespace detail + + template<bool Support_Split_Join> + class tree_split_join_test : private __gnu_pbds::test::detail::timing_test_base + { + public: + tree_split_join_test(size_t vn, size_t vs, size_t vm); + + template<typename Cntnr> + void + operator()(Cntnr); + + private: + tree_split_join_test(const tree_split_join_test& ); + + private: + const size_t m_vn; + const size_t m_vs; + const size_t m_vm; + }; + + template<bool Support_Split_Join> + tree_split_join_test<Support_Split_Join>:: + tree_split_join_test(size_t vn, size_t vs, size_t vm) : + m_vn(vn), + m_vs(vs), + m_vm(vm) + { } + + template<bool Support_Split_Join> + template<typename Cntnr> + void + tree_split_join_test<Support_Split_Join>:: + operator()(Cntnr) + { + typedef xml_result_set_performance_formatter formatter_type; + formatter_type res_set_fmt(string_form<Cntnr>::name(), + string_form<Cntnr>::desc()); + + for (size_t v = m_vn; v < m_vm; v += m_vs) + { + Cntnr cntnr; + for (size_t ins = 0; ins < v; ++ ins) + cntnr.insert((typename Cntnr::value_type)ins); + + __gnu_pbds::test::detail::split_join_functor<Cntnr, Support_Split_Join> + fn(cntnr); + + const double res = + __gnu_pbds::test::detail::timing_test_base::operator()(fn); + res_set_fmt.add_res(v, res); + } + } + } // namespace test +} // namespace __gnu_pbds + +#endif + diff --git a/libstdc++-v3/testsuite/util/performance/io/xml_formatter.hpp b/libstdc++-v3/testsuite/util/performance/io/xml_formatter.hpp new file mode 100644 index 000000000..535964bdd --- /dev/null +++ b/libstdc++-v3/testsuite/util/performance/io/xml_formatter.hpp @@ -0,0 +1,78 @@ +// -*- C++ -*- + +// Copyright (C) 2005, 2006, 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. + +// You should have received a copy of the GNU General Public License +// along with this library; see the file COPYING3. If not see +// <http://www.gnu.org/licenses/>. + + +// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. + +// Permission to use, copy, modify, sell, and distribute this software +// is hereby granted without fee, provided that the above copyright +// notice appears in all copies, and that both that copyright notice +// and this permission notice appear in supporting documentation. None +// of the above authors, nor IBM Haifa Research Laboratories, make any +// representation about the suitability of this software for any +// purpose. It is provided "as is" without express or implied +// warranty. + +/** + * @file xml_formatter.hpp + * Contains an XML formatter for performance tests. + */ + +#ifndef PB_DS_XML_TEST_PERFORMANCE_FORMATTER_HPP +#define PB_DS_XML_TEST_PERFORMANCE_FORMATTER_HPP + +#include <string> +#include <iostream> +#include <io/xml_test_formatter.hpp> + +namespace __gnu_pbds +{ + namespace test + { + class xml_test_performance_formatter : public xml_test_formatter + { + public: + xml_test_performance_formatter(const std::string& r_x_name, const std::string& r_y_name) + { + std::cout << make_xml_tag("x_name", r_x_name); + std::cout << make_xml_tag("y_name", r_y_name); + } + }; + + class xml_result_set_performance_formatter : public xml_result_set_formatter + { + public: + xml_result_set_performance_formatter(const std::string& r_container_name, const std::string& r_container_desc) + : xml_result_set_formatter(r_container_name, r_container_desc) + { + { } + } + + void + add_res(size_t x, double y) + { + const unsigned long ul = static_cast<unsigned long>(x); + const std::string res = make_xml_tag("result", "x", ul, "y", y); + std::cout << res; + } + }; + } // namespace test +} // namespace __gnu_pbds + +#endif // #ifndef PB_DS_XML_TEST_PERFORMANCE_FORMATTER_HPP diff --git a/libstdc++-v3/testsuite/util/performance/priority_queue/mem_usage/pop_test.hpp b/libstdc++-v3/testsuite/util/performance/priority_queue/mem_usage/pop_test.hpp new file mode 100644 index 000000000..3a98813df --- /dev/null +++ b/libstdc++-v3/testsuite/util/performance/priority_queue/mem_usage/pop_test.hpp @@ -0,0 +1,111 @@ +// -*- C++ -*- + +// Copyright (C) 2005, 2006, 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. + +// You should have received a copy of the GNU General Public License +// along with this library; see the file COPYING3. If not see +// <http://www.gnu.org/licenses/>. + + +// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. + +// Permission to use, copy, modify, sell, and distribute this software +// is hereby granted without fee, provided that the above copyright +// notice appears in all copies, and that both that copyright notice +// and this permission notice appear in supporting documentation. None +// of the above authors, nor IBM Haifa Research Laboratories, make any +// representation about the suitability of this software for any +// purpose. It is provided "as is" without express or implied +// warranty. + +/** + * @file pop_test.hpp + * Contains a generic pop test. + */ + +#ifndef PB_DS_POP_TEST_HPP +#define PB_DS_POP_TEST_HPP + +#include <iterator> +#include <testsuite_allocator.h> +#include <ext/pb_ds/detail/type_utils.hpp> +#include <performance/io/xml_formatter.hpp> +#include <common_type/priority_queue/string_form.hpp> + +namespace __gnu_pbds +{ + namespace test + { + template<typename It> + class pop_test + { + public: + pop_test(It ins_b, size_t ins_vn, size_t ins_vs, size_t ins_vm) + : m_ins_b(ins_b), m_ins_vn(ins_vn), m_ins_vs(ins_vs), m_ins_vm(ins_vm) + { } + + template<typename Cntnr> + void + operator()(Cntnr); + + private: + pop_test(const pop_test&); + + const It m_ins_b; + const size_t m_ins_vn; + const size_t m_ins_vs; + const size_t m_ins_vm; + }; + + template<typename It> + template<typename Cntnr> + void + pop_test<It>:: + operator()(Cntnr) + { + typedef xml_result_set_performance_formatter formatter_type; + formatter_type res_set_fmt(string_form<Cntnr>::name(), + string_form<Cntnr>::desc()); + + for (size_t i = 0; m_ins_vn + i * m_ins_vs < m_ins_vm; ++i) + { + const size_t ins_size = m_ins_vn + i * m_ins_vs; + It ins_it_b = m_ins_b; + It ins_it_e = m_ins_b; + std::advance(ins_it_e, ins_size); + + typedef __gnu_test::tracker_allocator_counter counter_type; + __gnu_test::tracker_allocator<char> alloc; + + const size_t init_mem = counter_type::get_allocation_count() + - counter_type::get_deallocation_count(); + Cntnr cntnr; + for (It ins_it = ins_it_b; ins_it != ins_it_e; ++ins_it) + cntnr.push(ins_it->first); + + while (cntnr.size() > 1) + cntnr.pop(); + + const size_t final_mem = counter_type::get_allocation_count() + - counter_type::get_deallocation_count(); + assert(final_mem > init_mem); + const size_t delta_mem = final_mem - init_mem; + res_set_fmt.add_res(ins_size, static_cast<double>(delta_mem)); + } + } + } // namespace test +} // namespace __gnu_pbds + +#endif + diff --git a/libstdc++-v3/testsuite/util/performance/priority_queue/timing/join_test.hpp b/libstdc++-v3/testsuite/util/performance/priority_queue/timing/join_test.hpp new file mode 100644 index 000000000..1281f40c3 --- /dev/null +++ b/libstdc++-v3/testsuite/util/performance/priority_queue/timing/join_test.hpp @@ -0,0 +1,167 @@ +// -*- C++ -*- + +// Copyright (C) 2005, 2006, 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. + +// You should have received a copy of the GNU General Public License +// along with this library; see the file COPYING3. If not see +// <http://www.gnu.org/licenses/>. + + +// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. + +// Permission to use, copy, modify, sell, and distribute this software +// is hereby granted without fee, provided that the above copyright +// notice appears in all copies, and that both that copyright notice +// and this permission notice appear in supporting documentation. None +// of the above authors, nor IBM Haifa Research Laboratories, make any +// representation about the suitability of this software for any +// purpose. It is provided "as is" without express or implied +// warranty. + +/** + * @file join_test.hpp + * Contains a join performance test. + */ + +#ifndef PB_DS_JOIN_TEST_HPP +#define PB_DS_JOIN_TEST_HPP + +#include <performance/time/timing_test_base.hpp> +#include <ext/pb_ds/detail/type_utils.hpp> +#include <performance/io/xml_formatter.hpp> +#include <common_type/priority_queue/string_form.hpp> +#include <iterator> + +namespace __gnu_pbds +{ + namespace test + { + namespace detail + { + template<typename It, typename Cntnr> + class double_push_functor + { + const It _M_begin; + const It _M_end; + + public: + double_push_functor(It b, It e) : _M_begin(b), _M_end(e) { } + + void + operator()(std::size_t resolution) + { + typedef typename Cntnr::const_reference const_reference; + for (std::size_t n = 0; n < resolution; ++n) + { + Cntnr c0; + Cntnr c1; + for (It it = _M_begin; it != _M_end; ++it) + { + c0.push(const_reference(it->first)); + c1.push(const_reference(it->first)); + } + } + } + }; + + template<typename It, typename Cntnr> + class double_push_join_functor + { + const It _M_begin; + const It _M_end; + + public: + double_push_join_functor(It b, It e) : _M_begin(b), _M_end(e) { } + + void + operator()(std::size_t resolution) + { + typedef typename Cntnr::const_reference const_reference; + for (std::size_t n = 0; n < resolution; ++n) + { + Cntnr c0; + Cntnr c1; + for (It it = _M_begin; it != _M_end; ++it) + { + c0.push(const_reference(it->first)); + c1.push(const_reference(it->first)); + } + c0.join(c1); + } + } + }; + } // namespace detail + + template<typename It> + class join_test : private __gnu_pbds::test::detail::timing_test_base + { + public: + join_test(It ins_b, size_t ins_vn, size_t ins_vs, size_t ins_vm) + : m_ins_b(ins_b), m_ins_vn(ins_vn), m_ins_vs(ins_vs), m_ins_vm(ins_vm) + { } + + template<typename Cntnr> + void + operator()(Cntnr) + { + using __gnu_pbds::test::detail::double_push_functor; + using __gnu_pbds::test::detail::double_push_join_functor; + typedef __gnu_pbds::test::detail::timing_test_base base_type; + typedef double_push_functor<It, Cntnr> psh_fnct; + typedef double_push_join_functor<It, Cntnr> psh_jn_fnct; + + typedef xml_result_set_performance_formatter formatter_type; + formatter_type res(string_form<Cntnr>::name(), + string_form<Cntnr>::desc()); + + for (size_t n = 0; m_ins_vn + n* m_ins_vs < m_ins_vm; ++n) + { + const size_t v = m_ins_vn + n * m_ins_vs; + It b = m_ins_b; + It e = m_ins_b; + std::advance(e, v); + + psh_fnct double_push_fn(b, e); + const double dbl_psh_res = base_type::operator()(double_push_fn); + psh_jn_fnct dbl_psh_jn_fn(b, e); + const double dbl_psh_jn_res = base_type::operator()(dbl_psh_jn_fn); + const double min_res = double(timing_test_base::min_time_res()); + const double effective_delta = std::max(dbl_psh_jn_res - dbl_psh_res, min_res); + res.add_res(v, effective_delta / v); + } + } + + private: + join_test(const join_test&); + + template<typename Cntnr> + void + join(Cntnr, It b, It e) + { + Cntnr cntnr; + typedef typename Cntnr::const_reference const_reference; + for (It it = b; it != e; ++it) + cntnr.join(const_reference(*it)); + } + + const It m_ins_b; + const size_t m_ins_vn; + const size_t m_ins_vs; + const size_t m_ins_vm; + }; + } // namespace test +} // namespace __gnu_pbds + +#endif + diff --git a/libstdc++-v3/testsuite/util/performance/priority_queue/timing/modify_test.hpp b/libstdc++-v3/testsuite/util/performance/priority_queue/timing/modify_test.hpp new file mode 100644 index 000000000..01e082058 --- /dev/null +++ b/libstdc++-v3/testsuite/util/performance/priority_queue/timing/modify_test.hpp @@ -0,0 +1,329 @@ +// -*- C++ -*- + +// Copyright (C) 2005, 2006, 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. + +// You should have received a copy of the GNU General Public License +// along with this library; see the file COPYING3. If not see +// <http://www.gnu.org/licenses/>. + + +// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. + +// Permission to use, copy, modify, sell, and distribute this software +// is hereby granted without fee, provided that the above copyright +// notice appears in all copies, and that both that copyright notice +// and this permission notice appear in supporting documentation. None +// of the above authors, nor IBM Haifa Research Laboratories, make any +// representation about the suitability of this software for any +// purpose. It is provided "as is" without express or implied +// warranty. + +/** + * @file modify_test.hpp + * Contains a modify performance test. + */ + +#ifndef PB_DS_JOIN_TEST_HPP +#define PB_DS_JOIN_TEST_HPP + +#include <performance/time/timing_test_base.hpp> +#include <ext/pb_ds/detail/type_utils.hpp> +#include <performance/io/xml_formatter.hpp> +#include <common_type/priority_queue/string_form.hpp> +#include <iterator> + +namespace __gnu_pbds +{ + namespace test + { + namespace detail + { + // Primary templates. + template<typename It, class Cntnr, class Tag> + class push_functor + { + public: + push_functor(It ins_it_b, It ins_it_e) + : m_ins_it_b(ins_it_b), m_ins_it_e(ins_it_e) + { } + + void + operator()(std::size_t resolution) + { + typedef typename Cntnr::point_iterator point_iterator; + typedef typename Cntnr::const_reference const_reference; + for (std::size_t i = 0; i < resolution; ++i) + { + Cntnr c; + typedef std::vector<point_iterator> it_vec_t; + it_vec_t m_a_its; + for (It ins_it = m_ins_it_b; ins_it != m_ins_it_e; ++ins_it) + m_a_its.push_back(c.push(const_reference(ins_it->first))); + } + } + + private: + const It m_ins_it_b; + const It m_ins_it_e; + }; + + template<typename It, class Cntnr, class Tag> + class push_modify_functor + { + private: + typedef typename Cntnr::point_iterator point_iterator; + typedef typename Cntnr::const_reference const_reference; + typedef typename Cntnr::value_type value_type; + + public: + push_modify_functor(It ins_it_b, It ins_it_e, value_type mod_val) + : m_ins_it_b(ins_it_b), m_ins_it_e(ins_it_e), m_mod_val(mod_val) + { } + + void + operator()(std::size_t resolution) + { + for (std::size_t i = 0; i < resolution; ++i) + { + Cntnr c; + typedef std::vector<typename Cntnr::point_iterator> it_vec_t; + it_vec_t m_a_its; + for (It ins_it = m_ins_it_b; ins_it != m_ins_it_e; ++ins_it) + m_a_its.push_back(c.push(const_reference(ins_it->first))); + + typename it_vec_t::iterator mod_it = m_a_its.begin(); + while (mod_it != m_a_its.end()) + c.modify(*mod_it++, m_mod_val); + } + } + + private: + const It m_ins_it_b; + const It m_ins_it_e; + const value_type m_mod_val; + }; + + // Specializations. + template<typename It, class Cntnr> + class push_functor<It, Cntnr, __gnu_pbds::binary_heap_tag> + { + public: + push_functor(It ins_it_b, It ins_it_e) + : m_ins_it_b(ins_it_b), m_ins_it_e(ins_it_e) + { } + + void + operator()(std::size_t resolution) + { + typedef typename Cntnr::const_reference const_reference; + for (std::size_t i = 0; i < resolution; ++i) + { + Cntnr c; + for (It ins_it = m_ins_it_b; ins_it != m_ins_it_e; ++ins_it) + c.push(const_reference(ins_it->first)); + } + } + + private: + const It m_ins_it_b; + const It m_ins_it_e; + }; + + template<typename It, class Cntnr> + class push_functor<It, Cntnr, __gnu_pbds::test::native_pq_tag> + { + public: + push_functor(It ins_it_b, It ins_it_e) + : m_ins_it_b(ins_it_b), m_ins_it_e(ins_it_e) + { } + + void + operator()(std::size_t resolution) + { + typedef typename Cntnr::const_reference const_reference; + for (std::size_t i = 0; i < resolution; ++i) + { + Cntnr c; + + for (It ins_it = m_ins_it_b; ins_it != m_ins_it_e; ++ins_it) + c.push(const_reference(ins_it->first)); + } + } + + private: + const It m_ins_it_b; + const It m_ins_it_e; + }; + + + template<typename It, class Cntnr> + class push_modify_functor<It, Cntnr, __gnu_pbds::binary_heap_tag> + { + private: + typedef typename Cntnr::iterator iterator; + typedef typename Cntnr::const_reference const_reference; + typedef typename Cntnr::value_type value_type; + + public: + push_modify_functor(It ins_it_b, It ins_it_e, value_type mod_val) + : m_ins_it_b(ins_it_b), m_ins_it_e(ins_it_e), m_mod_val(mod_val) + { } + + void + operator()(std::size_t resolution) + { + for (std::size_t i = 0; i < resolution; ++i) + { + Cntnr c; + It ins_it; + for (ins_it = m_ins_it_b; ins_it != m_ins_it_e; ++ins_it) + c.push(const_reference(ins_it->first)); + + for (ins_it = m_ins_it_b; ins_it != m_ins_it_e; ++ins_it) + { + bool modified = false; + for (iterator it = c.begin(); !modified && it != c.end(); ++it) + if (*it == ins_it->first) + { + c.modify(it, m_mod_val); + modified = true; + } + } + } + } + + private: + const It m_ins_it_b; + const It m_ins_it_e; + const value_type m_mod_val; + }; + + template<typename It, class Cntnr> + class push_modify_functor<It, Cntnr, __gnu_pbds::test::native_pq_tag> + { + private: + typedef typename Cntnr::value_type value_type; + typedef typename Cntnr::const_reference const_reference; + + public: + push_modify_functor(It ins_it_b, It ins_it_e, value_type mod_val) + : m_ins_it_b(ins_it_b), m_ins_it_e(ins_it_e), m_mod_val(mod_val) + { } + + void + operator()(std::size_t resolution) + { + for (std::size_t i = 0; i < resolution; ++i) + { + Cntnr c; + It ins_it; + for (ins_it = m_ins_it_b; ins_it != m_ins_it_e; ++ins_it) + c.push(const_reference(ins_it->first)); + for (ins_it = m_ins_it_b; ins_it != m_ins_it_e; ++ins_it) + c.modify(ins_it->first, m_mod_val); + } + } + + private: + const It m_ins_it_b; + const It m_ins_it_e; + const value_type m_mod_val; + }; + } // namespace detail + + template<typename It> + class modify_test : private __gnu_pbds::test::detail::timing_test_base + { + public: + modify_test(It b, size_t vn, size_t vs, size_t vm, bool modify_up) + : m_ins_b(b), m_ins_vn(vn), m_ins_vs(vs), m_ins_vm(vm), + m_modify_up(modify_up) + { } + + template<typename Cntnr> + void + operator()(Cntnr); + + private: + modify_test(const modify_test&); + + template<typename Cntnr> + void + modify(Cntnr, It ins_it_b, It ins_it_e) + { + typedef typename Cntnr::const_reference const_reference; + Cntnr cntnr; + for (It ins_it = ins_it_b; ins_it != ins_it_e; ++ins_it) + cntnr.modify(const_reference(*ins_it)); + } + + const It m_ins_b; + const size_t m_ins_vn; + const size_t m_ins_vs; + const size_t m_ins_vm; + const bool m_modify_up; + }; + + template<typename It> + template<typename Cntnr> + void + modify_test<It>:: + operator()(Cntnr) + { + typedef typename Cntnr::value_type value_type; + typedef typename Cntnr::container_category container_category; + typedef typename Cntnr::const_reference const_reference; + typedef detail::timing_test_base timing_test_base; + typedef detail::push_functor<It, Cntnr, container_category> psh_fnct; + typedef detail::push_modify_functor<It, Cntnr, container_category> psh_mod_fnct; + typedef xml_result_set_performance_formatter formatter_type; + formatter_type res_set_fmt(string_form<Cntnr>::name(), + string_form<Cntnr>::desc()); + + for (size_t i = 0; m_ins_vn + i * m_ins_vs < m_ins_vm; ++i) + { + const size_t v = m_ins_vn + i * m_ins_vs; + It b = m_ins_b; + It e = m_ins_b; + std::advance(e, v); + + psh_fnct psh_fn(b, e); + const double psh_res = timing_test_base::operator()(psh_fn); + + value_type val = b->first; + { + Cntnr mod_val_container; + for (It mod_val_it = b; mod_val_it != e; ++mod_val_it) + { + value_type pot = mod_val_it->first; + if (m_modify_up == mod_val_container.get_cmp_fn()(val, pot)) + val = pot; + } + } + + psh_mod_fnct psh_mod_fn(b, e, val); + const double psh_mod_res = timing_test_base::operator()(psh_mod_fn); + + const double min_res = double(timing_test_base::min_time_res()); + const double effective_delta = std::max(psh_mod_res - psh_res, + min_res); + + res_set_fmt.add_res(v, effective_delta / v); + } + } + } // namespace test +} // namespace __gnu_pbds + +#endif + diff --git a/libstdc++-v3/testsuite/util/performance/priority_queue/timing/push_pop_test.hpp b/libstdc++-v3/testsuite/util/performance/priority_queue/timing/push_pop_test.hpp new file mode 100644 index 000000000..d3a9a736e --- /dev/null +++ b/libstdc++-v3/testsuite/util/performance/priority_queue/timing/push_pop_test.hpp @@ -0,0 +1,141 @@ +// -*- C++ -*- + +// Copyright (C) 2005, 2006, 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. + +// You should have received a copy of the GNU General Public License +// along with this library; see the file COPYING3. If not see +// <http://www.gnu.org/licenses/>. + + +// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. + +// Permission to use, copy, modify, sell, and distribute this software +// is hereby granted without fee, provided that the above copyright +// notice appears in all copies, and that both that copyright notice +// and this permission notice appear in supporting documentation. None +// of the above authors, nor IBM Haifa Research Laboratories, make any +// representation about the suitability of this software for any +// purpose. It is provided "as is" without express or implied +// warranty. + +/** + * @file push_pop_test.hpp + * Contains a push performance test. + */ + +#ifndef PB_DS_PUSH_TEST_HPP +#define PB_DS_PUSH_TEST_HPP + +#include <performance/time/timing_test_base.hpp> +#include <ext/pb_ds/detail/type_utils.hpp> +#include <performance/io/xml_formatter.hpp> +#include <common_type/priority_queue/string_form.hpp> +#include <iterator> + +namespace __gnu_pbds +{ + namespace test + { + namespace detail + { + template<typename It, class Cntnr> + class push_pop_push_pop_functor + { + public: + push_pop_push_pop_functor(It ins_it_b, It ins_it_e) + : m_ins_it_b(ins_it_b), m_ins_it_e(ins_it_e) + { } + + void + operator()(std::size_t resolution) + { + for (std::size_t i = 0; i < resolution; ++i) + { + Cntnr cntnr; + for (It ins_it = m_ins_it_b; ins_it != m_ins_it_e; ++ins_it) + cntnr.push((typename Cntnr::const_reference)(ins_it->first)); + while (!cntnr.empty()) + cntnr.pop(); + } + } + + private: + const It m_ins_it_b; + const It m_ins_it_e; + }; + + } // namespace detail + + template<typename It> + class push_pop_test : private __gnu_pbds::test::detail::timing_test_base + { + public: + push_pop_test(It ins_b, size_t ins_vn, size_t ins_vs, size_t ins_vm) + : m_ins_b(ins_b), m_ins_vn(ins_vn), m_ins_vs(ins_vs), m_ins_vm(ins_vm) + { } + + template<typename Cntnr> + void + operator()(Cntnr); + + private: + push_pop_test(const push_pop_test&); + + template<typename Cntnr> + void + push(Cntnr, It ins_it_b, It ins_it_e) + { + Cntnr cntnr; + for (It ins_it = ins_it_b; ins_it != ins_it_e; ++ins_it) + cntnr.push((typename Cntnr::const_reference)(*ins_it)); + } + + const It m_ins_b; + const size_t m_ins_vn; + const size_t m_ins_vs; + const size_t m_ins_vm; + }; + + + template<typename It> + template<typename Cntnr> + void + push_pop_test<It>:: + operator()(Cntnr) + { + typedef xml_result_set_performance_formatter formatter_type; + formatter_type res_set_fmt(string_form<Cntnr>::name(), + string_form<Cntnr>::desc()); + + for (size_t i = 0; m_ins_vn + i * m_ins_vs < m_ins_vm; ++i) + { + const size_t v = m_ins_vn + i * m_ins_vs; + It ins_it_b = m_ins_b; + It ins_it_e = m_ins_b; + std::advance(ins_it_e, v); + + __gnu_pbds::test::detail::push_pop_push_pop_functor<It, Cntnr> + fn(ins_it_b, ins_it_e); + + const double res = + __gnu_pbds::test::detail::timing_test_base::operator()(fn); + + res_set_fmt.add_res(v, res / v); + } + } + } // namespace test +} // namespace __gnu_pbds + +#endif + diff --git a/libstdc++-v3/testsuite/util/performance/priority_queue/timing/push_test.hpp b/libstdc++-v3/testsuite/util/performance/priority_queue/timing/push_test.hpp new file mode 100644 index 000000000..b398a7549 --- /dev/null +++ b/libstdc++-v3/testsuite/util/performance/priority_queue/timing/push_test.hpp @@ -0,0 +1,144 @@ +// -*- C++ -*- + +// Copyright (C) 2005, 2006, 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. + +// You should have received a copy of the GNU General Public License +// along with this library; see the file COPYING3. If not see +// <http://www.gnu.org/licenses/>. + + +// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. + +// Permission to use, copy, modify, sell, and distribute this software +// is hereby granted without fee, provided that the above copyright +// notice appears in all copies, and that both that copyright notice +// and this permission notice appear in supporting documentation. None +// of the above authors, nor IBM Haifa Research Laboratories, make any +// representation about the suitability of this software for any +// purpose. It is provided "as is" without express or implied +// warranty. + +/** + * @file push_test.hpp + * Contains a push performance test. + */ + +#ifndef PB_DS_PUSH_TEST_HPP +#define PB_DS_PUSH_TEST_HPP + +#include <performance/time/timing_test_base.hpp> +#include <ext/pb_ds/detail/type_utils.hpp> +#include <performance/io/xml_formatter.hpp> +#include <common_type/priority_queue/string_form.hpp> +#include <iterator> + +namespace __gnu_pbds +{ + namespace test + { + namespace detail + { + template<typename It, class Cntnr> + class push_push_functor + { + public: + push_push_functor(It ins_it_b, It ins_it_e) + : m_ins_it_b(ins_it_b), m_ins_it_e(ins_it_e) + { } + + void + operator()(std::size_t resolution) + { + for (std::size_t i = 0; i < resolution; ++i) + { + Cntnr cntnr; + for (It ins_it = m_ins_it_b; ins_it != m_ins_it_e; ++ins_it) + cntnr.push((typename Cntnr::const_reference)(ins_it->first)); + } + } + + private: + const It m_ins_it_b; + const It m_ins_it_e; + }; + } // namespace detail + + template<typename It> + class push_test : private __gnu_pbds::test::detail::timing_test_base + { + public: + push_test(It ins_b, size_t ins_vn, size_t ins_vs, size_t ins_vm) + : m_ins_b(ins_b), m_ins_vn(ins_vn), m_ins_vs(ins_vs), m_ins_vm(ins_vm) + { } + + template<typename Cntnr> + void + operator()(Cntnr); + + private: + push_test(const push_test& ); + + template<typename Cntnr> + void + push(Cntnr, It ins_it_b, It ins_it_e); + + const It m_ins_b; + const size_t m_ins_vn; + const size_t m_ins_vs; + const size_t m_ins_vm; + }; + + + template<typename It> + template<typename Cntnr> + void + push_test<It>:: + operator()(Cntnr) + { + typedef xml_result_set_performance_formatter formatter_type; + formatter_type res_set_fmt(string_form<Cntnr>::name(), + string_form<Cntnr>::desc()); + + for (size_t i = 0; m_ins_vn + i * m_ins_vs < m_ins_vm; ++i) + { + const size_t v = m_ins_vn + i * m_ins_vs; + It ins_it_b = m_ins_b; + It ins_it_e = m_ins_b; + std::advance(ins_it_e, v); + + __gnu_pbds::test::detail::push_push_functor<It, Cntnr> + fn(ins_it_b, ins_it_e); + + const double res = + __gnu_pbds::test::detail::timing_test_base::operator()(fn); + + res_set_fmt.add_res(v, res / v); + } + } + + template<typename It> + template<typename Cntnr> + void + push_test<It>:: + push(Cntnr, It ins_it_b, It ins_it_e) + { + Cntnr cntnr; + for (It ins_it = ins_it_b; ins_it != ins_it_e; ++ins_it) + cntnr.push((typename Cntnr::const_reference)(*ins_it)); + } + } // namespace test +} // namespace __gnu_pbds + +#endif + diff --git a/libstdc++-v3/testsuite/util/performance/time/elapsed_timer.cc b/libstdc++-v3/testsuite/util/performance/time/elapsed_timer.cc new file mode 100644 index 000000000..6b46402fe --- /dev/null +++ b/libstdc++-v3/testsuite/util/performance/time/elapsed_timer.cc @@ -0,0 +1,68 @@ +// -*- C++ -*- + +// Copyright (C) 2005, 2006, 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. + +// You should have received a copy of the GNU General Public License +// along with this library; see the file COPYING3. If not see +// <http://www.gnu.org/licenses/>. + + +// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. + +// Permission to use, copy, modify, sell, and distribute this software +// is hereby granted without fee, provided that the above copyright +// notice appears in all copies, and that both that copyright notice +// and this permission notice appear in supporting documentation. None +// of the above authors, nor IBM Haifa Research Laboratories, make any +// representation about the suitability of this software for any +// purpose. It is provided "as is" without express or implied +// warranty. + +/** + * @file elapsed_timer.cpp + * Contains utilities for tests. + */ + +#include <util/performance/time/elapsed_timer.hpp> + +namespace __gnu_pbds +{ + + namespace test + { + + elapsed_timer:: + elapsed_timer() + { + reset(); + } + + void + elapsed_timer:: + reset() + { + m_start = ::clock(); + } + + elapsed_timer:: + operator double() const + { + const clock_t now = ::clock(); + + return (((double)now - m_start) / CLOCKS_PER_SEC); + } + + } // namespace test + +} // namespace __gnu_pbds diff --git a/libstdc++-v3/testsuite/util/performance/time/elapsed_timer.hpp b/libstdc++-v3/testsuite/util/performance/time/elapsed_timer.hpp new file mode 100644 index 000000000..5f7937b92 --- /dev/null +++ b/libstdc++-v3/testsuite/util/performance/time/elapsed_timer.hpp @@ -0,0 +1,67 @@ +// -*- C++ -*- + +// Copyright (C) 2005, 2006, 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. + +// You should have received a copy of the GNU General Public License +// along with this library; see the file COPYING3. If not see +// <http://www.gnu.org/licenses/>. + + +// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. + +// Permission to use, copy, modify, sell, and distribute this software +// is hereby granted without fee, provided that the above copyright +// notice appears in all copies, and that both that copyright notice +// and this permission notice appear in supporting documentation. None +// of the above authors, nor IBM Haifa Research Laboratories, make any +// representation about the suitability of this software for any +// purpose. It is provided "as is" without express or implied +// warranty. + +/** + * @file elapsed_timer.hpp + * Contains time utilities for tests. + */ + +#ifndef PB_DS_TEST_TIME_HPP +#define PB_DS_TEST_TIME_HPP + +#include <time.h> +#include <iosfwd> + +namespace __gnu_pbds +{ + + namespace test + { + + class elapsed_timer + { + public: + elapsed_timer(); + + void + reset(); + + operator double() const; + + protected: + clock_t m_start; + }; + + } // namespace test + +} // namespace __gnu_pbds + +#endif // #ifndef PB_DS_TEST_TIME_HPP diff --git a/libstdc++-v3/testsuite/util/performance/time/timing_test_base.hpp b/libstdc++-v3/testsuite/util/performance/time/timing_test_base.hpp new file mode 100644 index 000000000..961583273 --- /dev/null +++ b/libstdc++-v3/testsuite/util/performance/time/timing_test_base.hpp @@ -0,0 +1,117 @@ +// -*- C++ -*- + +// Copyright (C) 2005, 2006, 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. + +// You should have received a copy of the GNU General Public License +// along with this library; see the file COPYING3. If not see +// <http://www.gnu.org/licenses/>. + + +// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. + +// Permission to use, copy, modify, sell, and distribute this software +// is hereby granted without fee, provided that the above copyright +// notice appears in all copies, and that both that copyright notice +// and this permission notice appear in supporting documentation. None +// of the above authors, nor IBM Haifa Research Laboratories, make any +// representation about the suitability of this software for any +// purpose. It is provided "as is" without express or implied +// warranty. + +/** + * @file timing_test_base.hpp + * Contains a base class for timing tests. + */ + +#ifndef PB_DS_TIMING_TEST_BASE_HPP +#define PB_DS_TIMING_TEST_BASE_HPP + +#include <performance/time/elapsed_timer.hpp> +#include <statistic/result_recorder.hpp> + +namespace __gnu_pbds +{ + namespace test + { + namespace detail + { + class timing_test_base + { + protected: + template<typename Functor> + double + operator()(Functor& fn); + + static double + min_time_res(); + + private: + template<typename Functor> + std::size_t + get_min_resolution(Functor&); + + template<typename Functor> + double + run_at_resolution(Functor&, std::size_t); + }; + + template<typename Functor> + double + timing_test_base::operator()(Functor& fn) + { + const std::size_t resolution = get_min_resolution(fn); + __gnu_pbds::test::detail::result_recorder<double> rec; + double res; + do + res = run_at_resolution(fn, resolution); + while (rec.add_result(res) == false); + res = rec.get_sample_mean() / resolution; + return res; + } + + double + timing_test_base::min_time_res() + { return 1e-7; } + + template<typename Functor> + std::size_t + timing_test_base::get_min_resolution(Functor& fn) + { + std::size_t guess = 0; + const double epsilon_val = min_time_res(); + double res; + do + { + guess = guess * 2 + 1; + res = run_at_resolution(fn, guess); + } + while (res < epsilon_val); + return guess; + } + + template<typename Functor> + double + timing_test_base::run_at_resolution(Functor& fn, std::size_t resolution) + { + elapsed_timer res; + fn(resolution); + return res; + } + + } // namespace detail + } // namespace test +} // namespace __gnu_pbds + +#endif + |