stxxl::PRIORITY_QUEUE_GENERATOR
and stxxl::priority_queue
00001 /*************************************************************************** 00002 * containers/test_pqueue.cpp 00003 * 00004 * Part of the STXXL. See http://stxxl.sourceforge.net 00005 * 00006 * Copyright (C) 2003 Roman Dementiev <dementiev@mpi-sb.mpg.de> 00007 * 00008 * Distributed under the Boost Software License, Version 1.0. 00009 * (See accompanying file LICENSE_1_0.txt or copy at 00010 * http://www.boost.org/LICENSE_1_0.txt) 00011 **************************************************************************/ 00012 00016 00017 #include <limits> 00018 #include <stxxl/priority_queue> 00019 00020 #define RECORD_SIZE 128 00021 00022 struct my_type 00023 { 00024 typedef int key_type; 00025 key_type key; 00026 char data[RECORD_SIZE - sizeof(key_type)]; 00027 my_type() { } 00028 explicit my_type(key_type k) : key(k) 00029 { 00030 #ifdef STXXL_VALGRIND_AVOID_UNINITIALIZED_WRITE_ERRORS 00031 memset(data, 0, sizeof(data)); 00032 #endif 00033 } 00034 }; 00035 00036 std::ostream & operator << (std::ostream & o, const my_type & obj) 00037 { 00038 o << obj.key; 00039 return o; 00040 } 00041 00042 struct my_cmp : std::binary_function<my_type, my_type, bool> // greater 00043 { 00044 bool operator () (const my_type & a, const my_type & b) const 00045 { 00046 return a.key > b.key; 00047 } 00048 00049 my_type min_value() const 00050 { 00051 return my_type((std::numeric_limits<my_type::key_type>::max)()); 00052 } 00053 }; 00054 00055 int main() 00056 { 00057 /* 00058 unsigned BufferSize1_ = 32, // equalize procedure call overheads etc. 00059 unsigned N_ = 512, // bandwidth 00060 unsigned IntKMAX_ = 64, // maximal arity for internal mergers 00061 unsigned IntLevels_ = 4, 00062 unsigned BlockSize_ = (2*1024*1024), 00063 unsigned ExtKMAX_ = 64, // maximal arity for external mergers 00064 unsigned ExtLevels_ = 2, 00065 */ 00066 //typedef priority_queue<priority_queue_config<my_type,my_cmp, 00067 // 32,512,64,3,(4*1024),0x7fffffff,1> > pq_type; 00068 const unsigned volume = 1024 * 1024; // in KB 00069 typedef stxxl::PRIORITY_QUEUE_GENERATOR<my_type, my_cmp, 32 * 1024 * 1024, volume / sizeof(my_type)> gen; 00070 typedef gen::result pq_type; 00071 typedef pq_type::block_type block_type; 00072 00073 STXXL_MSG("Block size: " << block_type::raw_size); 00074 STXXL_MSG("AI: " << gen::AI); 00075 STXXL_MSG("X : " << gen::X); 00076 STXXL_MSG("N : " << gen::N); 00077 STXXL_MSG("AE: " << gen::AE); 00078 00079 stxxl::timer Timer; 00080 Timer.start(); 00081 00082 const unsigned mem_for_pools = 128 * 1024 * 1024; 00083 stxxl::prefetch_pool<block_type> p_pool((mem_for_pools / 2) / block_type::raw_size); 00084 stxxl::write_pool<block_type> w_pool((mem_for_pools / 2) / block_type::raw_size); 00085 pq_type p(p_pool, w_pool); 00086 00087 stxxl::int64 nelements = stxxl::int64(volume * 1024 / sizeof(my_type)), i; 00088 STXXL_MSG("Internal memory consumption of the priority queue: " << p.mem_cons() << " bytes"); 00089 STXXL_MSG("Max elements: " << nelements); 00090 for (i = 0; i < nelements; i++) 00091 { 00092 if ((i % (1024 * 1024)) == 0) 00093 STXXL_MSG("Inserting element " << i); 00094 p.push(my_type(nelements - i)); 00095 } 00096 Timer.stop(); 00097 STXXL_MSG("Time spent for filling: " << Timer.seconds() << " sec"); 00098 00099 // test swap 00100 pq_type p1(p_pool, w_pool); 00101 std::swap(p, p1); 00102 std::swap(p, p1); 00103 00104 STXXL_MSG("Internal memory consumption of the priority queue: " << p.mem_cons() << " bytes"); 00105 Timer.reset(); 00106 Timer.start(); 00107 for (i = 0; i < (nelements); ++i) 00108 { 00109 assert(!p.empty()); 00110 //STXXL_MSG( p.top() ); 00111 assert(p.top().key == i + 1); 00112 p.pop(); 00113 if ((i % (1024 * 1024)) == 0) 00114 STXXL_MSG("Element " << i << " popped"); 00115 } 00116 Timer.stop(); 00117 00118 STXXL_MSG("Time spent for removing elements: " << Timer.seconds() << " sec"); 00119 STXXL_MSG("Internal memory consumption of the priority queue: " << p.mem_cons() << " bytes"); 00120 }