This is an automated email from the git hooks/post-receive script. rene pushed a commit to branch master in repository mdds.
commit 5611093fcbb1829f7f16a5ad0a7410f3707ba677 Author: Rene Engelhard <[email protected]> Date: Thu Apr 21 14:50:48 2016 +0200 Imported Upstream version 0.6.1 --- AUTHORS | 7 +- Makefile.in | 3 + NEWS | 21 ++ configure | 36 +- configure.ac | 6 +- include/mdds/flat_segment_tree_itr.hpp | 29 +- include/mdds/mixed_type_matrix_def.inl | 1 - include/mdds/mixed_type_matrix_storage.hpp | 4 + include/mdds/multi_type_vector_def.inl | 8 +- include/mdds/multi_type_vector_trait.hpp | 2 - include/mdds/multi_type_vector_types.hpp | 4 +- misc/matrix_perf.cpp | 511 +++++++++++++++++++++++++++++ src/flat_segment_tree_test.cpp | 109 ++++-- src/mixed_type_matrix_test.cpp | 33 ++ src/multi_type_matrix_test.cpp | 49 +++ src/test_global.hpp | 2 + 16 files changed, 748 insertions(+), 77 deletions(-) diff --git a/AUTHORS b/AUTHORS index be1cab7..a0ef3db 100644 --- a/AUTHORS +++ b/AUTHORS @@ -1,3 +1,8 @@ Kohei Yoshida <[email protected]> (Maintainer) David Tardon <[email protected]> - +Markus Mohrhard <[email protected]> +Petr Mladek <[email protected]> +Caolán McNamara <[email protected]> +Philipp Thomas <[email protected]> +Stephan Bergmann <[email protected]> +Tomáš Chvátal <[email protected]> diff --git a/Makefile.in b/Makefile.in index 15770ee..d822306 100644 --- a/Makefile.in +++ b/Makefile.in @@ -21,6 +21,7 @@ EXECS= \ multi_type_vector_test_custom HEADERS= \ + $(INCDIR)/mdds/compat/unique_ptr.hpp \ $(INCDIR)/mdds/flat_segment_tree_def.inl \ $(INCDIR)/mdds/flat_segment_tree.hpp \ $(INCDIR)/mdds/flat_segment_tree_itr.hpp \ @@ -200,9 +201,11 @@ $(QUICKCHECKDIR)/flat_segment_tree: $(QUICKCHECKDIR)/flat_segment_tree.o pre install: $(HEADERS) install -d $(DESTDIR)@includedir@/mdds install -d $(DESTDIR)@includedir@/mdds/hash_container + install -d $(DESTDIR)@includedir@/mdds/compat install -d $(DESTDIR)@docdir@ install -m 644 -t $(DESTDIR)@includedir@/mdds $(INCDIR)/mdds/*.hpp install -m 644 -t $(DESTDIR)@includedir@/mdds $(INCDIR)/mdds/*.inl + install -m 644 -t $(DESTDIR)@includedir@/mdds/compat $(INCDIR)/mdds/compat/*.hpp install -m 644 -t $(DESTDIR)@includedir@/mdds/hash_container $(INCDIR)/mdds/hash_container/*.hpp install -m 644 -t $(DESTDIR)@docdir@ AUTHORS COPYING NEWS README VERSION diff --git a/NEWS b/NEWS index 920bfaf..ab7bad6 100644 --- a/NEWS +++ b/NEWS @@ -1,3 +1,24 @@ +mdds 0.6.1 + +* all + + * use property files in the Visual Studio project files, to share + some of the common custom build variables across all projects. + + * various build fixes and compiler warning eliminations. + + * fixed link error with boost 1.50. + + * fixed make installer script which previously would not install + mdds/compat headers. + +* flat_segment_tree + + * fixed a bug in its iterator implementation, which previously would + always treat the last valid position before the end position as + the end position. This fix affects both in const_iterator and + const_reverse_iterator. + mdds 0.6.0 * all diff --git a/configure b/configure index 8fffc18..476f0c7 100755 --- a/configure +++ b/configure @@ -1,6 +1,6 @@ #! /bin/sh # Guess values for system-dependent variables and create Makefiles. -# Generated by GNU Autoconf 2.68 for mdds 0.6.0. +# Generated by GNU Autoconf 2.68 for mdds 0.6.1. # # Report bugs to <[email protected]>. # @@ -559,8 +559,8 @@ MAKEFLAGS= # Identity of this package. PACKAGE_NAME='mdds' PACKAGE_TARNAME='mdds' -PACKAGE_VERSION='0.6.0' -PACKAGE_STRING='mdds 0.6.0' +PACKAGE_VERSION='0.6.1' +PACKAGE_STRING='mdds 0.6.1' PACKAGE_BUGREPORT='[email protected]' PACKAGE_URL='' @@ -1161,7 +1161,7 @@ if test "$ac_init_help" = "long"; then # Omit some internal or obsolete options to make the list less imposing. # This message is too long to be a string in the A/UX 3.1 sh. cat <<_ACEOF -\`configure' configures mdds 0.6.0 to adapt to many kinds of systems. +\`configure' configures mdds 0.6.1 to adapt to many kinds of systems. Usage: $0 [OPTION]... [VAR=VALUE]... @@ -1222,7 +1222,7 @@ fi if test -n "$ac_init_help"; then case $ac_init_help in - short | recursive ) echo "Configuration of mdds 0.6.0:";; + short | recursive ) echo "Configuration of mdds 0.6.1:";; esac cat <<\_ACEOF @@ -1306,7 +1306,7 @@ fi test -n "$ac_init_help" && exit $ac_status if $ac_init_version; then cat <<\_ACEOF -mdds configure 0.6.0 +mdds configure 0.6.1 generated by GNU Autoconf 2.68 Copyright (C) 2010 Free Software Foundation, Inc. @@ -1323,7 +1323,7 @@ cat >config.log <<_ACEOF This file contains any messages produced by compilers while running configure, to aid debugging if configure makes a mistake. -It was created by mdds $as_me 0.6.0, which was +It was created by mdds $as_me 0.6.1, which was generated by GNU Autoconf 2.68. Invocation command line was $ $0 $@ @@ -1672,7 +1672,7 @@ ac_compiler_gnu=$ac_cv_c_compiler_gnu -VERSION=0.6.0 +VERSION=0.6.1 PACKAGE_TARNAME=mdds @@ -1706,11 +1706,9 @@ if test $with_hash_container = stlport; then CPPFLAGS_NODEBUG="$CPPFLAGS_NODEBUG -DMDDS_HASH_CONTAINER_STLPORT" elif test $with_hash_container = boost; then CPPFLAGS_NODEBUG="$CPPFLAGS_NODEBUG -DMDDS_HASH_CONTAINER_BOOST" -else - CPPFLAGS_NODEBUG="$CPPFLAGS_NODEBUG -std=c++0x" fi -CPPFLAGS="$CPPFLAGS_NODEBUG -DDEBUG_NODE_BASE -DUNIT_TEST" +CPPFLAGS="$CPPFLAGS_NODEBUG -DDEBUG_NODE_BASE -DUNIT_TEST -std=c++0x" @@ -2270,7 +2268,7 @@ cat >>$CONFIG_STATUS <<\_ACEOF || ac_write_fail=1 # report actual input values of CONFIG_FILES etc. instead of their # values after options handling. ac_log=" -This file was extended by mdds $as_me 0.6.0, which was +This file was extended by mdds $as_me 0.6.1, which was generated by GNU Autoconf 2.68. Invocation command line was CONFIG_FILES = $CONFIG_FILES @@ -2323,7 +2321,7 @@ _ACEOF cat >>$CONFIG_STATUS <<_ACEOF || ac_write_fail=1 ac_cs_config="`$as_echo "$ac_configure_args" | sed 's/^ //; s/[\\""\`\$]/\\\\&/g'`" ac_cs_version="\\ -mdds config.status 0.6.0 +mdds config.status 0.6.1 configured by $0, generated by GNU Autoconf 2.68, with options \\"\$ac_cs_config\\" @@ -3439,7 +3437,7 @@ cat >>$CONFIG_STATUS <<\_ACEOF || ac_write_fail=1 # report actual input values of CONFIG_FILES etc. instead of their # values after options handling. ac_log=" -This file was extended by mdds $as_me 0.6.0, which was +This file was extended by mdds $as_me 0.6.1, which was generated by GNU Autoconf 2.68. Invocation command line was CONFIG_FILES = $CONFIG_FILES @@ -3492,7 +3490,7 @@ _ACEOF cat >>$CONFIG_STATUS <<_ACEOF || ac_write_fail=1 ac_cs_config="`$as_echo "$ac_configure_args" | sed 's/^ //; s/[\\""\`\$]/\\\\&/g'`" ac_cs_version="\\ -mdds config.status 0.6.0 +mdds config.status 0.6.1 configured by $0, generated by GNU Autoconf 2.68, with options \\"\$ac_cs_config\\" @@ -4609,7 +4607,7 @@ cat >>$CONFIG_STATUS <<\_ACEOF || ac_write_fail=1 # report actual input values of CONFIG_FILES etc. instead of their # values after options handling. ac_log=" -This file was extended by mdds $as_me 0.6.0, which was +This file was extended by mdds $as_me 0.6.1, which was generated by GNU Autoconf 2.68. Invocation command line was CONFIG_FILES = $CONFIG_FILES @@ -4662,7 +4660,7 @@ _ACEOF cat >>$CONFIG_STATUS <<_ACEOF || ac_write_fail=1 ac_cs_config="`$as_echo "$ac_configure_args" | sed 's/^ //; s/[\\""\`\$]/\\\\&/g'`" ac_cs_version="\\ -mdds config.status 0.6.0 +mdds config.status 0.6.1 configured by $0, generated by GNU Autoconf 2.68, with options \\"\$ac_cs_config\\" @@ -5780,7 +5778,7 @@ cat >>$CONFIG_STATUS <<\_ACEOF || ac_write_fail=1 # report actual input values of CONFIG_FILES etc. instead of their # values after options handling. ac_log=" -This file was extended by mdds $as_me 0.6.0, which was +This file was extended by mdds $as_me 0.6.1, which was generated by GNU Autoconf 2.68. Invocation command line was CONFIG_FILES = $CONFIG_FILES @@ -5833,7 +5831,7 @@ _ACEOF cat >>$CONFIG_STATUS <<_ACEOF || ac_write_fail=1 ac_cs_config="`$as_echo "$ac_configure_args" | sed 's/^ //; s/[\\""\`\$]/\\\\&/g'`" ac_cs_version="\\ -mdds config.status 0.6.0 +mdds config.status 0.6.1 configured by $0, generated by GNU Autoconf 2.68, with options \\"\$ac_cs_config\\" diff --git a/configure.ac b/configure.ac index ffc3ab0..973042c 100644 --- a/configure.ac +++ b/configure.ac @@ -1,4 +1,4 @@ -AC_INIT(mdds, 0.6.0, [email protected]) +AC_INIT(mdds, 0.6.1, [email protected]) VERSION=AC_PACKAGE_VERSION AC_SUBST(VERSION) @@ -39,11 +39,9 @@ if test $with_hash_container = stlport; then CPPFLAGS_NODEBUG="$CPPFLAGS_NODEBUG -DMDDS_HASH_CONTAINER_STLPORT" elif test $with_hash_container = boost; then CPPFLAGS_NODEBUG="$CPPFLAGS_NODEBUG -DMDDS_HASH_CONTAINER_BOOST" -else - CPPFLAGS_NODEBUG="$CPPFLAGS_NODEBUG -std=c++0x" fi -CPPFLAGS="$CPPFLAGS_NODEBUG -DDEBUG_NODE_BASE -DUNIT_TEST" +CPPFLAGS="$CPPFLAGS_NODEBUG -DDEBUG_NODE_BASE -DUNIT_TEST -std=c++0x" AC_SUBST(CPPFLAGS) AC_SUBST(CPPFLAGS_NODEBUG) diff --git a/include/mdds/flat_segment_tree_itr.hpp b/include/mdds/flat_segment_tree_itr.hpp index b307d69..cfb5f7c 100644 --- a/include/mdds/flat_segment_tree_itr.hpp +++ b/include/mdds/flat_segment_tree_itr.hpp @@ -1,6 +1,6 @@ /************************************************************************* * - * Copyright (c) 2010 Kohei Yoshida + * Copyright (c) 2010-2012 Kohei Yoshida * * Permission is hereby granted, free of charge, to any person * obtaining a copy of this software and associated documentation @@ -38,12 +38,12 @@ struct itr_forward_handler { typedef _FstType fst_type; - const typename fst_type::node* init_pos(const fst_type* _db, bool _end) const + static const typename fst_type::node* init_pos(const fst_type* _db, bool _end) { return _end ? _db->m_right_leaf.get() : _db->m_left_leaf.get(); } - void inc(const fst_type* _db, const typename fst_type::node*& p, bool& end) const + static void inc(const fst_type* _db, const typename fst_type::node*& p, bool& end) { if (p == _db->m_right_leaf.get()) end = true; @@ -51,7 +51,7 @@ struct itr_forward_handler p = p->right.get(); } - void dec(const typename fst_type::node*& p, bool& end) const + static void dec(const typename fst_type::node*& p, bool& end) { if (end) end = false; @@ -68,12 +68,12 @@ struct itr_reverse_handler { typedef _FstType fst_type; - const typename fst_type::node* init_pos(const fst_type* _db, bool _end) const + static const typename fst_type::node* init_pos(const fst_type* _db, bool _end) { return _end ? _db->m_left_leaf.get() : _db->m_right_leaf.get(); } - void inc(const fst_type* _db, const typename fst_type::node*& p, bool& end) const + static void inc(const fst_type* _db, const typename fst_type::node*& p, bool& end) { if (p == _db->m_left_leaf.get()) end = true; @@ -81,7 +81,7 @@ struct itr_reverse_handler p = p->left.get(); } - void dec(const typename fst_type::node*& p, bool& end) const + static void dec(const typename fst_type::node*& p, bool& end) { if (end) end = false; @@ -93,9 +93,9 @@ struct itr_reverse_handler template<typename _FstType, typename _Hdl> class const_iterator_base { + typedef _Hdl handler_type; public: typedef _FstType fst_type; - typedef _Hdl handler_type; // iterator traits typedef ::std::pair<typename fst_type::key_type, typename fst_type::value_type> value_type; @@ -110,7 +110,7 @@ public: if (!_db) return; - m_pos = m_hdl.init_pos(_db, _end); + m_pos = handler_type::init_pos(_db, _end); } explicit const_iterator_base(const fst_type* _db, const typename fst_type::node* pos) : @@ -123,20 +123,21 @@ public: { m_db = r.m_db; m_pos = r.m_pos; + m_end_pos = r.m_end_pos; return *this; } const value_type* operator++() { assert(m_pos); - m_hdl.inc(m_db, m_pos, m_end_pos); + handler_type::inc(m_db, m_pos, m_end_pos); return operator->(); } const value_type* operator--() { assert(m_pos); - m_hdl.dec(m_pos, m_end_pos); + handler_type::dec(m_pos, m_end_pos); return operator->(); } @@ -145,10 +146,7 @@ public: if (m_db != r.m_db) return false; - if (m_end_pos == r.m_end_pos) - return true; - - return (m_pos == r.m_pos); + return (m_pos == r.m_pos) && (m_end_pos == r.m_end_pos); } bool operator!=(const const_iterator_base& r) const @@ -177,7 +175,6 @@ private: return m_current_pair; } - handler_type m_hdl; const fst_type* m_db; const typename fst_type::node* m_pos; value_type m_current_pair; diff --git a/include/mdds/mixed_type_matrix_def.inl b/include/mdds/mixed_type_matrix_def.inl index 7c129ec..2c33799 100644 --- a/include/mdds/mixed_type_matrix_def.inl +++ b/include/mdds/mixed_type_matrix_def.inl @@ -44,7 +44,6 @@ mixed_type_matrix<_String,_Flag>::create_storage(size_t rows, size_t cols, matri default: throw matrix_error("unknown density type"); } - return NULL; } template<typename _String, typename _Flag> diff --git a/include/mdds/mixed_type_matrix_storage.hpp b/include/mdds/mixed_type_matrix_storage.hpp index fa0bf25..bb4e354 100644 --- a/include/mdds/mixed_type_matrix_storage.hpp +++ b/include/mdds/mixed_type_matrix_storage.hpp @@ -32,6 +32,10 @@ #include <boost/ptr_container/ptr_vector.hpp> #include <boost/ptr_container/ptr_map.hpp> +// Boost.Pool indirectly pulls in Boost.System, causing linking error +// with Boost 1.50, because some (deprecated) symbols from System are +// not found. +#define BOOST_SYSTEM_NO_DEPRECATED #include <boost/pool/object_pool.hpp> namespace mdds { diff --git a/include/mdds/multi_type_vector_def.inl b/include/mdds/multi_type_vector_def.inl index 252a260..fb72070 100644 --- a/include/mdds/multi_type_vector_def.inl +++ b/include/mdds/multi_type_vector_def.inl @@ -1148,7 +1148,7 @@ void multi_type_vector<_CellBlockFunc>::insert_empty_impl(size_type row, size_ty // Insert two new block below the current; one for the empty block being // inserted, and one for the lower part of the current non-empty block. - m_blocks.insert(m_blocks.begin()+block_index+1, 2, NULL); + m_blocks.insert(m_blocks.begin()+block_index+1, 2u, NULL); m_blocks[block_index+1] = new block(length); m_blocks[block_index+2] = new block(size_blk_next); @@ -1302,7 +1302,7 @@ void multi_type_vector<_CellBlockFunc>::insert_cells_to_middle( // Insert two new blocks. size_type n1 = row - start_row; size_type n2 = blk->m_size - n1; - m_blocks.insert(m_blocks.begin()+block_index+1, 2, NULL); + m_blocks.insert(m_blocks.begin()+block_index+1, 2u, NULL); blk->m_size = n1; m_blocks[block_index+1] = new block(length); @@ -1467,7 +1467,7 @@ void multi_type_vector<_CellBlockFunc>::set_cells_to_single_block( assert(start_row_in_block < start_row && end_row < end_row_in_block); // Insert two new blocks below the current one. - m_blocks.insert(m_blocks.begin()+block_index+1, 2, NULL); + m_blocks.insert(m_blocks.begin()+block_index+1, 2u, NULL); // first new block is for the data array being inserted. size_type new_size = end_row - start_row + 1; @@ -1985,7 +1985,7 @@ void multi_type_vector<_CellBlockFunc>::set_empty_in_single_block( // First, insert two new blocks at position past the current block. size_type lower_block_size = end_row_in_block - end_row; - m_blocks.insert(m_blocks.begin()+block_index+1, 2, NULL); + m_blocks.insert(m_blocks.begin()+block_index+1, 2u, NULL); m_blocks[block_index+1] = new block(empty_block_size); // empty block. m_blocks[block_index+2] = new block(lower_block_size); diff --git a/include/mdds/multi_type_vector_trait.hpp b/include/mdds/multi_type_vector_trait.hpp index 4c468d3..466ed8f 100644 --- a/include/mdds/multi_type_vector_trait.hpp +++ b/include/mdds/multi_type_vector_trait.hpp @@ -95,7 +95,6 @@ base_element_block* element_block_func_base::create_new_block(element_t type, si default: throw general_error("create_new_block: failed to create a new block of unknown type."); } - return NULL; } base_element_block* element_block_func_base::clone_block(const base_element_block& block) @@ -123,7 +122,6 @@ base_element_block* element_block_func_base::clone_block(const base_element_bloc default: throw general_error("clone_block: failed to clone a block of unknown type."); } - return NULL; } void element_block_func_base::delete_block(base_element_block* p) diff --git a/include/mdds/multi_type_vector_types.hpp b/include/mdds/multi_type_vector_types.hpp index f27ac88..f72b641 100644 --- a/include/mdds/multi_type_vector_types.hpp +++ b/include/mdds/multi_type_vector_types.hpp @@ -302,7 +302,7 @@ protected: noncopyable_element_block(size_t n, const _Data& val) : base_type(n, val) {} public: - static _Self* clone_block(const base_element_block& blk) + static _Self* clone_block(const base_element_block&) { throw element_block_error("attempted to clone a noncopyable element block."); } @@ -355,6 +355,7 @@ struct managed_element_block : public copyable_element_block<managed_element_blo typedef managed_element_block<_TypeId,_Data> self_type; using base_type::get; + using base_type::set_value; using base_type::m_array; managed_element_block() : base_type() {} @@ -402,6 +403,7 @@ struct noncopyable_managed_element_block : public noncopyable_element_block<nonc using base_type::get; using base_type::m_array; + using base_type::set_value; noncopyable_managed_element_block() : base_type() {} noncopyable_managed_element_block(size_t n) : base_type(n) {} diff --git a/misc/matrix_perf.cpp b/misc/matrix_perf.cpp new file mode 100644 index 0000000..617d5da --- /dev/null +++ b/misc/matrix_perf.cpp @@ -0,0 +1,511 @@ + +#include <cstdlib> +#include <iostream> +#include <sys/time.h> + +#include <mdds/mixed_type_matrix.hpp> +#include <mdds/multi_type_matrix.hpp> + +double get_current_time() +{ +#ifdef _WIN32 + FILETIME ft; + __int64 *time64 = reinterpret_cast<__int64 *>(&ft); + GetSystemTimeAsFileTime(&ft); + return *time64 / 10000000.0; +#else + timeval tv; + gettimeofday(&tv, NULL); + return tv.tv_sec + tv.tv_usec / 1000000.0; +#endif +} + +class stack_watch +{ +public: + explicit stack_watch() : m_start_time(get_current_time()) {} + void reset() { m_start_time = get_current_time(); } + double get_duration() const { return get_current_time() - m_start_time; } + +private: + double m_start_time; +}; + +using namespace std; + +typedef mdds::mixed_type_matrix<std::string, bool> mixed_mx_type; +typedef mdds::multi_type_matrix<mdds::mtm::std_string_trait> multi_mx_type; + +namespace { + +class sum_all_values : public std::unary_function<multi_mx_type::element_block_node_type, void> +{ + double m_sum; +public: + sum_all_values() : m_sum(0.0) {} + void operator() (const multi_mx_type::element_block_node_type& blk) + { + if (!blk.data) + return; + + if (mdds::mtv::get_block_type(*blk.data) != mdds::mtv::element_type_numeric) + return; + + using mdds::mtv::numeric_element_block; + numeric_element_block::const_iterator it = numeric_element_block::begin(*blk.data); + numeric_element_block::const_iterator it_end = numeric_element_block::end(*blk.data); + for (; it != it_end; ++it) + m_sum += *it; + } + + double get() const { return m_sum; } +}; + +class count_all_values : public std::unary_function<multi_mx_type::element_block_node_type, void> +{ + long m_count; +public: + count_all_values() : m_count(0) {} + void operator() (const multi_mx_type::element_block_node_type& blk) + { + if (!blk.data) + return; + + if (mdds::mtv::get_block_type(*blk.data) != mdds::mtv::element_type_numeric) + return; + + m_count += blk.size; + } + + long get() const { return m_count; } +}; + +template<typename _Mx> +void init_manual_loop(_Mx& mx, size_t row_size, size_t col_size) +{ + double val = 0.0; + for (size_t row = 0; row < row_size; ++row) + { + for (size_t col = 0; col < col_size; ++col) + { + mx.set(row, col, val); + val += 0.00001; + } + } +} + +void init_value_vector(vector<double>& vals, size_t row_size, size_t col_size) +{ + vals.reserve(row_size*col_size); + + double val = 0.0; + for (size_t row = 0; row < row_size; ++row) + { + for (size_t col = 0; col < col_size; ++col) + { + vals.push_back(val); + val += 0.00001; + } + } +} + +template<typename _Mx> +double sum_manual_loop(const _Mx& mx, size_t row_size, size_t col_size) +{ + double sum = 0.0; + for (size_t row = 0; row < row_size; ++row) + for (size_t col = 0; col < col_size; ++col) + sum += mx.get_numeric(row, col); + + return sum; +} + +double sum_iterator(const mixed_mx_type& mx) +{ + double sum = 0.0; + mixed_mx_type::const_iterator it = mx.begin(), it_end = mx.end(); + for (; it != it_end; ++it) + { + if (it->m_type == mdds::element_numeric) + sum += it->m_numeric; + } + return sum; +} + +} + +void perf_construction() +{ + cout << "---" << endl; + size_t row_size = 20000, col_size = 8000; + { + stack_watch sw; + mixed_mx_type mx(row_size, col_size, mdds::matrix_density_filled_zero); + cout << "construction filled zero: " << sw.get_duration() << " sec (mixed_type_matrix, filled)" << endl; + } + + { + stack_watch sw; + mixed_mx_type mx(row_size, col_size, mdds::matrix_density_sparse_zero); + cout << "construction filled zero: " << sw.get_duration() << " sec (mixed_type_matrix, sparse)" << endl; + } + + { + stack_watch sw; + multi_mx_type mx(row_size, col_size, 0.0); + cout << "construction filled zero: " << sw.get_duration() << " sec (multi_type_matrix)" << endl; + } + + { + stack_watch sw; + mixed_mx_type mx(row_size, col_size, mdds::matrix_density_filled_empty); + cout << "construction filled empty: " << sw.get_duration() << " sec (mixed_type_matrix, filled)" << endl; + } + + { + stack_watch sw; + mixed_mx_type mx(row_size, col_size, mdds::matrix_density_sparse_empty); + cout << "construction filled empty: " << sw.get_duration() << " sec (mixed_type_matrix, sparse)" << endl; + } + + { + stack_watch sw; + multi_mx_type mx(row_size, col_size); + cout << "construction filled empty: " << sw.get_duration() << " sec (multi_type_matrix)" << endl; + } +} + +void perf_insertion() +{ + cout << "---" << endl; + size_t row_size = 10000; + size_t col_size = 1000; + { + mixed_mx_type mx(row_size, col_size, mdds::matrix_density_filled_zero); + stack_watch sw; + init_manual_loop(mx, row_size, col_size); + cout << "insertion via loop: " << sw.get_duration() << " sec (mixed_type_matrix, filled zero)" << endl; + } + + { + multi_mx_type mx(row_size, col_size); + stack_watch sw; + init_manual_loop(mx, row_size, col_size); + cout << "insertion via loop: " << sw.get_duration() << " sec (multi_type_matrix, init empty)" << endl; + } + + { + multi_mx_type mx(row_size, col_size, 0.0); + stack_watch sw; + init_manual_loop(mx, row_size, col_size); + cout << "insertion via loop: " << sw.get_duration() << " sec (multi_type_matrix, init zero)" << endl; + } + + { + multi_mx_type mx(row_size, col_size); + std::vector<double> vals; + + stack_watch sw; + init_value_vector(vals, row_size, col_size); + mx.set(0, 0, vals.begin(), vals.end()); + cout << "insertion via single set call: " << sw.get_duration() << " sec (multi_type_matrix, init empty, value initialization included)" << endl; + } + + { + multi_mx_type mx(row_size, col_size); + std::vector<double> vals; + init_value_vector(vals, row_size, col_size); + + stack_watch sw; + mx.set(0, 0, vals.begin(), vals.end()); + cout << "insertion via single set call: " << sw.get_duration() << " sec (multi_type_matrix, init empty, value initialization excluded)" << endl; + } + + { + multi_mx_type mx(row_size, col_size, 0.0); + std::vector<double> vals; + vals.reserve(row_size*col_size); + + stack_watch sw; + init_value_vector(vals, row_size, col_size); + mx.set(0, 0, vals.begin(), vals.end()); + cout << "insertion via single set call: " << sw.get_duration() << " sec (multi_type_matrix, init zero, value initialization included)" << endl; + } + + { + multi_mx_type mx(row_size, col_size, 0.0); + std::vector<double> vals; + init_value_vector(vals, row_size, col_size); + + stack_watch sw; + mx.set(0, 0, vals.begin(), vals.end()); + cout << "insertion via single set call: " << sw.get_duration() << " sec (multi_type_matrix, init zero, value initialization excluded)" << endl; + } +} + +void perf_sum_all_values() +{ + cout << "---" << endl; + size_t row_size = 10000; + size_t col_size = 1000; + { + mixed_mx_type mx(row_size, col_size, mdds::matrix_density_filled_zero); + init_manual_loop(mx, row_size, col_size); + + { + stack_watch sw; + double sum = sum_manual_loop(mx, row_size, col_size); + cout << "sum all values (" << sum << ") : " << sw.get_duration() << " sec (mixed_type_matrix, manual loop)" << endl; + } + + { + stack_watch sw; + double sum = sum_iterator(mx); + cout << "sum all values (" << sum << ") : " << sw.get_duration() << " sec (mixed_type_matrix, iterator)" << endl; + } + + { + stack_watch sw; + long count = 0; + for (size_t row = 0; row < row_size; ++row) + for (size_t col = 0; col < col_size; ++col) + { + if (mx.get_type(row, col) == mdds::element_numeric) + ++count; + } + + cout << "count all values (" << count << ") : " << sw.get_duration() << " sec (mixed_type_matrix, manual loop)" << endl; + } + + { + stack_watch sw; + long count = 0; + mixed_mx_type::const_iterator it = mx.begin(), it_end = mx.end(); + for (; it != it_end; ++it) + { + if (it->m_type == mdds::element_numeric) + ++count; + } + + cout << "count all values (" << count << ") : " << sw.get_duration() << " sec (mixed_type_matrix, iterator)" << endl; + } + } + + { + multi_mx_type mx(row_size, col_size, 0.0); + init_manual_loop(mx, row_size, col_size); + + { + stack_watch sw; + double sum = sum_manual_loop(mx, row_size, col_size); + cout << "sum all values (" << sum << ") : " << sw.get_duration() << " sec (multi_type_matrix, manual loop)" << endl; + } + + { + stack_watch sw; + sum_all_values func; + mx.walk(func); + cout << "sum all values (" << func.get() << ") : " << sw.get_duration() << " sec (multi_type_matrix, walk)" << endl; + } + + { + stack_watch sw; + count_all_values func; + mx.walk(func); + cout << "count all values (" << func.get() << ") : " << sw.get_duration() << " sec (multi_type_matrix, walk)" << endl; + } + } +} + +void perf_sum_all_values_multi_block() +{ + cout << "---" << endl; + size_t row_size = 10000; + size_t col_size = 1000; + double step = 0.00001; + { + mixed_mx_type mx(row_size, col_size, mdds::matrix_density_filled_zero); + double val = 0.0; + for (size_t row = 0; row < row_size; ++row) + { + for (size_t col = 0; col < col_size; ++col) + { + if ((col % 3) == 0) + { + mx.set_empty(row, col); + } + else + { + mx.set(row, col, val); + val += step; + } + } + } + + { + stack_watch sw; + double sum = sum_manual_loop(mx, row_size, col_size); + cout << "sum all values multi-block (" << sum << ") : " << sw.get_duration() << " sec (mixed_type_matrix, manual loop)" << endl; + } + + { + stack_watch sw; + double sum = sum_iterator(mx); + cout << "sum all values multi-block (" << sum << ") : " << sw.get_duration() << " sec (mixed_type_matrix, iterator)" << endl; + } + + { + stack_watch sw; + long count = 0; + for (size_t row = 0; row < row_size; ++row) + for (size_t col = 0; col < col_size; ++col) + { + if (mx.get_type(row, col) == mdds::element_numeric) + ++count; + } + + cout << "count all values multi-block (" << count << ") : " << sw.get_duration() << " sec (mixed_type_matrix, manual loop)" << endl; + } + + { + stack_watch sw; + long count = 0; + mixed_mx_type::const_iterator it = mx.begin(), it_end = mx.end(); + for (; it != it_end; ++it) + { + if (it->m_type == mdds::element_numeric) + ++count; + } + + cout << "count all values multi-block (" << count << ") : " << sw.get_duration() << " sec (mixed_type_matrix, iterator)" << endl; + } + } + + { + multi_mx_type mx(row_size, col_size); + double val = 0.0; + vector<double> vals; + vals.reserve(row_size); + for (size_t col = 0; col < col_size; ++col) + { + if ((col % 3) == 0) + continue; + + vals.clear(); + for (size_t row = 0; row < row_size; ++row) + { + vals.push_back(val); + val += step; + } + + mx.set(0, col, vals.begin(), vals.end()); + } + + { + stack_watch sw; + double sum = sum_manual_loop(mx, row_size, col_size); + cout << "sum all values multi-block (" << sum << ") : " << sw.get_duration() << " sec (multi_type_matrix, manual loop)" << endl; + } + + { + stack_watch sw; + sum_all_values func; + mx.walk(func); + cout << "sum all values multi-block (" << func.get() << ") : " << sw.get_duration() << " sec (multi_type_matrix, walk)" << endl; + } + + { + stack_watch sw; + count_all_values func; + mx.walk(func); + cout << "count all values multi-block (" << func.get() << ") : " << sw.get_duration() << " sec (multi_type_matrix, walk)" << endl; + } + } +} + +void perf_init_with_value() +{ + cout << "---" << endl; + size_t row_size = 10000; + size_t col_size = 2000; + double val = 12.3; + { + stack_watch sw; + mixed_mx_type mx(row_size, col_size, mdds::matrix_density_filled_zero); + for (size_t row = 0; row < row_size; ++row) + for (size_t col = 0; col < col_size; ++col) + mx.set(row, col, val); + cout << "init with value: " << sw.get_duration() << " sec (mixed_type_matrix, filled zero, manual loop)" << endl; + } + + { + stack_watch sw; + multi_mx_type mx(row_size, col_size, 0.0); + for (size_t row = 0; row < row_size; ++row) + for (size_t col = 0; col < col_size; ++col) + mx.set(row, col, val); + cout << "init with value: " << sw.get_duration() << " sec (multi_type_matrix, manual loop)" << endl; + } + + { + stack_watch sw; + multi_mx_type(row_size, col_size, val); + cout << "init with value: " << sw.get_duration() << " sec (multi_type_matrix, constructor)" << endl; + } + + { + stack_watch sw; + multi_mx_type mx(row_size, col_size); + vector<double> vals(row_size*col_size, val); + mx.set(0, 0, vals.begin(), vals.end()); + cout << "init with value: " << sw.get_duration() << " sec (multi_type_matrix, vector + set)" << endl; + } +} + +void perf_heap_vs_array() +{ + cout << "---" << endl; + size_t row_size = 20000, col_size = 3000; + { + mixed_mx_type mx(row_size, col_size, mdds::matrix_density_filled_empty); + init_manual_loop(mx, row_size, col_size); + stack_watch sw; + double sum = 0.0; + for (size_t row = 0; row < row_size; ++row) + for (size_t col = 0; col < col_size; ++col) + sum += mx.get_numeric(row, col); + cout << "sum with values on the heap (mixed_type_matrix): " << sw.get_duration() << " sec (" << sum << ")" << endl; + } + + { + mixed_mx_type mx(row_size, col_size, mdds::matrix_density_filled_zero); + init_manual_loop(mx, row_size, col_size); + stack_watch sw; + double sum = 0.0; + for (size_t row = 0; row < row_size; ++row) + for (size_t col = 0; col < col_size; ++col) + sum += mx.get_numeric(row, col); + cout << "sum with array values (mixed_type_matrix): " << sw.get_duration() << " sec (" << sum << ")" << endl; + } + + { + multi_mx_type mx(row_size, col_size, 0.0); + init_manual_loop(mx, row_size, col_size); + sum_all_values func; + stack_watch sw; + mx.walk(func); + double sum = func.get(); + cout << "sum with array values (multi_type_matrix): " << sw.get_duration() << " sec (" << sum << ")" << endl; + } +} + +int main() +{ + perf_construction(); + perf_insertion(); + perf_sum_all_values(); + perf_sum_all_values_multi_block(); + perf_init_with_value(); + perf_heap_vs_array(); + return EXIT_SUCCESS; +} diff --git a/src/flat_segment_tree_test.cpp b/src/flat_segment_tree_test.cpp index 8d873a8..5dd0504 100644 --- a/src/flat_segment_tree_test.cpp +++ b/src/flat_segment_tree_test.cpp @@ -1,6 +1,6 @@ /************************************************************************* * - * Copyright (c) 2008-2009 Kohei Yoshida + * Copyright (c) 2008-2012 Kohei Yoshida * * Permission is hereby granted, free of charge, to any person * obtaining a copy of this software and associated documentation @@ -999,43 +999,94 @@ struct leaf_node_functor : public unary_function<void, pair<key_type, value_type void fst_test_const_iterator() { - stack_printer __stack_printer__("::fst_test_const_reverse_iterator"); + stack_printer __stack_printer__("::fst_test_const_iterator"); - typedef unsigned int key_type; - typedef unsigned short value_type; - unsigned short max_value = numeric_limits<value_type>::max(); - typedef flat_segment_tree<key_type, value_type> container_type; + { + typedef unsigned int key_type; + typedef unsigned short value_type; + unsigned short max_value = numeric_limits<value_type>::max(); + typedef flat_segment_tree<key_type, value_type> container_type; - container_type db(0, 1000, max_value); + container_type db(0, 1000, max_value); - build_and_dump(db); - { - unsigned int k[] = {0, 1000}; - unsigned short v[] = {max_value}; - assert(check_leaf_nodes(db, k, v, ARRAY_SIZE(k))); + build_and_dump(db); + { + unsigned int k[] = {0, 1000}; + unsigned short v[] = {max_value}; + assert(check_leaf_nodes(db, k, v, ARRAY_SIZE(k))); + } + + db.insert_front(10, 20, 10); + db.insert_front(20, 50, 20); + db.insert_front(100, 300, 55); + build_and_dump(db); + { + unsigned int k[] = {0, 10, 20, 50, 100, 300, 1000}; + unsigned short v[] = {max_value, 10, 20, max_value, 55, max_value}; + assert(check_leaf_nodes(db, k, v, ARRAY_SIZE(k))); + fprintf(stdout, "fst_test_const_iterator: leaf nodes valid\n"); + + // Check the forward iterator's integrity. + assert(is_iterator_valid(db.begin(), db.end(), k, v, ARRAY_SIZE(k))); + fprintf(stdout, "fst_test_const_iterator: forward iterator valid\n"); + + // Check the reverse iterator's integrity. + assert(is_iterator_valid(db.rbegin(), db.rend(), k, v, ARRAY_SIZE(k))); + fprintf(stdout, "fst_test_const_iterator: reverse iterator valid\n"); + } + + // Make sure it works with for_each. + for_each(db.begin(), db.end(), leaf_node_functor<key_type, value_type>()); } - db.insert_front(10, 20, 10); - db.insert_front(20, 50, 20); - db.insert_front(100, 300, 55); - build_and_dump(db); { - unsigned int k[] = {0, 10, 20, 50, 100, 300, 1000}; - unsigned short v[] = {max_value, 10, 20, max_value, 55, max_value}; - assert(check_leaf_nodes(db, k, v, ARRAY_SIZE(k))); - fprintf(stdout, "fst_test_const_iterator: leaf nodes valid\n"); - - // Check the forward iterator's integrity. - assert(is_iterator_valid(db.begin(), db.end(), k, v, ARRAY_SIZE(k))); - fprintf(stdout, "fst_test_const_iterator: forward iterator valid\n"); + typedef flat_segment_tree<int, bool> container_type; + container_type db(0, 100, true); + db.insert_front(0, 50, false); - // Check the reverse iterator's integrity. - assert(is_iterator_valid(db.rbegin(), db.rend(), k, v, ARRAY_SIZE(k))); - fprintf(stdout, "fst_test_const_iterator: reverse iterator valid\n"); + { + cout << "-- forward" << endl; + container_type::const_iterator it = db.begin(), it_end = db.end(); + // 0 -> 50 -> 100 -> end + cout << "key: " << it->first << " value: " << it->second << endl; + assert(it->first == 0); + assert(it->second == false); + ++it; + cout << "key: " << it->first << " value: " << it->second << endl; + assert(it->first == 50); + assert(it->second == true); + ++it; + cout << "key: " << it->first << " value: " << it->second << endl; + assert(it->first == 100); + assert(it != it_end); + ++it; + assert(it == it_end); + } + { + cout << "-- reverse" << endl; + container_type::const_reverse_iterator it = db.rbegin(), it_end = db.rend(); + // 100 -> 50 -> 0 -> end + cout << "key: " << it->first << " value: " << it->second << endl; + assert(it->first == 100); + ++it; + cout << "key: " << it->first << " value: " << it->second << endl; + assert(it->first == 50); + assert(it->second == true); + ++it; + cout << "key: " << it->first << " value: " << it->second << endl; + assert(it->first == 0); + assert(it->second == false); + assert(it != it_end); + ++it; + assert(it == it_end); + } } +} + +void fst_test_reverse_iterator() +{ + stack_printer __stack_printer__("::fst_test_reverse_iterator"); - // Make sure it works with for_each. - for_each(db.begin(), db.end(), leaf_node_functor<key_type, value_type>()); } template<typename key_type, typename value_type> diff --git a/src/mixed_type_matrix_test.cpp b/src/mixed_type_matrix_test.cpp index ad0228e..edcf40a 100644 --- a/src/mixed_type_matrix_test.cpp +++ b/src/mixed_type_matrix_test.cpp @@ -913,6 +913,38 @@ void mtm_perf_test_storage_set_numeric() cout << endl; } +void mtm_perf_test_iterate_elements() +{ + cout << "measuring performance on iterating over all numeric elements." << endl; + size_t rowsize = 100000; + size_t colsize = 1000; + cout << "row size: " << rowsize << " column size: " << colsize << endl; + mx_type mx(rowsize, colsize, matrix_density_filled_zero); + { + stack_watch sw; + double val = 1.0; + for (size_t i = 0; i < rowsize; ++i) + { + for (size_t j = 0; j < colsize; ++j) + { + mx.set(i, j, val); + val += 0.001; + } + } + cout << "element values inserted. (duration: " << sw.get_duration() << " sec)" << endl; + } + + { + stack_watch sw; + double val = 0.0; + mx_type::const_iterator it = mx.begin(), it_end = mx.end(); + for (; it != it_end; ++it) + val += it->m_numeric; + + cout << "all element values added. (answer: " << val << ") (duration: " << sw.get_duration() << " sec)" << endl; + } +} + int main(int argc, char** argv) { cmd_options opt; @@ -956,6 +988,7 @@ int main(int argc, char** argv) { mtm_perf_test_storage_creation(); mtm_perf_test_storage_set_numeric(); + mtm_perf_test_iterate_elements(); } cout << "Test finished successfully!" << endl; diff --git a/src/multi_type_matrix_test.cpp b/src/multi_type_matrix_test.cpp index 5aff72f..1f51816 100644 --- a/src/multi_type_matrix_test.cpp +++ b/src/multi_type_matrix_test.cpp @@ -834,6 +834,54 @@ void mtm_perf_test_storage_set_numeric() cout << endl; } +struct sum_all_values +{ + double result; + + sum_all_values() : result(0.0) {} + + void operator() (const mtx_type::element_block_node_type& blk) + { + mtv::numeric_element_block::const_iterator it = mtv::numeric_element_block::begin(*blk.data); + mtv::numeric_element_block::const_iterator it_end = mtv::numeric_element_block::end(*blk.data); + for (; it != it_end; ++it) + result += *it; + } +}; + +void mtm_perf_test_iterate_elements() +{ + cout << "measuring performance on iterating over all numeric elements." << endl; + size_t rowsize = 100000; + size_t colsize = 1000; + cout << "row size: " << rowsize << " column size: " << colsize << endl; + mtx_type mx(rowsize, colsize, 0.0); + { + stack_watch sw; + double val = 1.0; + std::vector<double> vals; + vals.reserve(rowsize*colsize); + for (size_t i = 0; i < rowsize; ++i) + { + for (size_t j = 0; j < colsize; ++j) + { + vals.push_back(val); + val += 0.001; + } + } + mx.set(0, 0, vals.begin(), vals.end()); + cout << "element values inserted. (duration: " << sw.get_duration() << " sec)" << endl; + } + + { + stack_watch sw; + sum_all_values func; + mx.walk(func); + double val = func.result; + cout << "all element values added. (answer: " << val << ") (duration: " << sw.get_duration() << " sec)" << endl; + } +} + int main (int argc, char **argv) { cmd_options opt; @@ -860,6 +908,7 @@ int main (int argc, char **argv) { mtm_perf_test_storage_creation(); mtm_perf_test_storage_set_numeric(); + mtm_perf_test_iterate_elements(); } cout << "Test finished successfully!" << endl; diff --git a/src/test_global.hpp b/src/test_global.hpp index e50afba..a8537ba 100644 --- a/src/test_global.hpp +++ b/src/test_global.hpp @@ -45,7 +45,9 @@ typedef unsigned char uint8_t; typedef unsigned short uint16_t; typedef unsigned int uint32_t; +#if _MSC_VER < 1600 typedef char int8_t; +#endif typedef short int16_t; typedef int int32_t; #endif -- Alioth's /usr/local/bin/git-commit-notice on /srv/git.debian.org/git/pkg-openoffice/mdds.git
