00001 /*************************************************************************** 00002 * containers/pq_benchmark.cpp 00003 * 00004 * Part of the STXXL. See http://stxxl.sourceforge.net 00005 * 00006 * Copyright (C) 2006 Roman Dementiev <dementiev@ira.uka.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 00019 00020 00021 #include <stxxl/priority_queue> 00022 00023 #define TOTAL_PQ_MEM_SIZE (768 * 1024 * 1024) 00024 00025 #define PQ_MEM_SIZE (512 * 1024 * 1024) 00026 00027 #define PREFETCH_POOL_SIZE ((TOTAL_PQ_MEM_SIZE - PQ_MEM_SIZE) / 2) 00028 #define WRITE_POOL_SIZE (PREFETCH_POOL_SIZE) 00029 00030 00031 #define MAX_ELEMENTS (2000 * 1024 * 1024) 00032 00033 00034 struct my_record 00035 { 00036 int key; 00037 int data; 00038 my_record() : key(0), data(0) { } 00039 my_record(int k, int d) : key(k), data(d) { } 00040 }; 00041 00042 std::ostream & operator << (std::ostream & o, const my_record & obj) 00043 { 00044 o << obj.key << " " << obj.data; 00045 return o; 00046 } 00047 00048 bool operator == (const my_record & a, const my_record & b) 00049 { 00050 return a.key == b.key; 00051 } 00052 00053 bool operator != (const my_record & a, const my_record & b) 00054 { 00055 return a.key != b.key; 00056 } 00057 00058 bool operator < (const my_record & a, const my_record & b) 00059 { 00060 return a.key < b.key; 00061 } 00062 00063 bool operator > (const my_record & a, const my_record & b) 00064 { 00065 return a.key > b.key; 00066 } 00067 00068 00069 struct comp_type : std::binary_function<my_record, my_record, bool> 00070 { 00071 bool operator () (const my_record & a, const my_record & b) const 00072 { 00073 return a > b; 00074 } 00075 static my_record min_value() 00076 { 00077 return my_record((std::numeric_limits<int>::max)(), 0); 00078 } 00079 }; 00080 00081 00082 typedef stxxl::PRIORITY_QUEUE_GENERATOR<my_record, comp_type, 00083 PQ_MEM_SIZE, MAX_ELEMENTS / (1024 / 8)>::result pq_type; 00084 00085 typedef pq_type::block_type block_type; 00086 00087 #define BLOCK_SIZE block_type::raw_size 00088 00089 00090 #if 1 00091 unsigned ran32State = 0xdeadbeef; 00092 inline int myrand() 00093 { 00094 return ((int)((ran32State = 1664525 * ran32State + 1013904223) >> 1)) - 1; 00095 } 00096 #else // a longer pseudo random sequence 00097 long long unsigned ran32State = 0xdeadbeef; 00098 inline long long unsigned myrand() 00099 { 00100 return (ran32State = (ran32State * 0x5DEECE66DULL + 0xBULL) & 0xFFFFFFFFFFFFULL); 00101 } 00102 #endif 00103 00104 00105 void run_stxxl_insert_all_delete_all(stxxl::uint64 ops) 00106 { 00107 stxxl::prefetch_pool<block_type> p_pool(PREFETCH_POOL_SIZE / BLOCK_SIZE); 00108 stxxl::write_pool<block_type> w_pool(WRITE_POOL_SIZE / BLOCK_SIZE); 00109 00110 pq_type PQ(p_pool, w_pool); 00111 00112 stxxl::uint64 i; 00113 00114 my_record cur; 00115 00116 stxxl::stats * Stats = stxxl::stats::get_instance(); 00117 Stats->reset(); 00118 00119 stxxl::timer Timer; 00120 Timer.start(); 00121 00122 for (i = 0; i < ops; ++i) 00123 { 00124 cur.key = myrand(); 00125 PQ.push(cur); 00126 } 00127 00128 Timer.stop(); 00129 00130 STXXL_MSG("Records in PQ: " << PQ.size()); 00131 if (i != PQ.size()) 00132 { 00133 STXXL_MSG("Size does not match"); 00134 abort(); 00135 } 00136 00137 STXXL_MSG("Insertions elapsed time: " << (Timer.mseconds() / 1000.) << 00138 " seconds : " << (double(ops) / (Timer.mseconds() / 1000.)) << " key/data pairs per sec"); 00139 00140 std::cout << *Stats; 00141 Stats->reset(); 00142 00144 Timer.reset(); 00145 Timer.start(); 00146 00147 for (i = 0; i < ops; ++i) 00148 { 00149 PQ.pop(); 00150 } 00151 00152 Timer.stop(); 00153 00154 STXXL_MSG("Records in PQ: " << PQ.size()); 00155 if (!PQ.empty()) 00156 { 00157 STXXL_MSG("PQ must be empty"); 00158 abort(); 00159 } 00160 00161 STXXL_MSG("Deletions elapsed time: " << (Timer.mseconds() / 1000.) << 00162 " seconds : " << (double(ops) / (Timer.mseconds() / 1000.)) << " key/data pairs per sec"); 00163 00164 std::cout << *Stats; 00165 } 00166 00167 00168 void run_stxxl_intermixed(stxxl::uint64 ops) 00169 { 00170 stxxl::prefetch_pool<block_type> p_pool(PREFETCH_POOL_SIZE / BLOCK_SIZE); 00171 stxxl::write_pool<block_type> w_pool(WRITE_POOL_SIZE / BLOCK_SIZE); 00172 00173 pq_type PQ(p_pool, w_pool); 00174 00175 stxxl::uint64 i; 00176 00177 my_record cur; 00178 00179 stxxl::stats * Stats = stxxl::stats::get_instance(); 00180 Stats->reset(); 00181 00182 stxxl::timer Timer; 00183 Timer.start(); 00184 00185 for (i = 0; i < ops; ++i) 00186 { 00187 cur.key = myrand(); 00188 PQ.push(cur); 00189 } 00190 00191 Timer.stop(); 00192 00193 STXXL_MSG("Records in PQ: " << PQ.size()); 00194 if (i != PQ.size()) 00195 { 00196 STXXL_MSG("Size does not match"); 00197 abort(); 00198 } 00199 00200 STXXL_MSG("Insertions elapsed time: " << (Timer.mseconds() / 1000.) << 00201 " seconds : " << (double(ops) / (Timer.mseconds() / 1000.)) << " key/data pairs per sec"); 00202 00203 std::cout << *Stats; 00204 Stats->reset(); 00205 00207 Timer.reset(); 00208 Timer.start(); 00209 00210 for (i = 0; i < ops; ++i) 00211 { 00212 int o = myrand() % 3; 00213 if (o == 0) 00214 { 00215 cur.key = myrand(); 00216 PQ.push(cur); 00217 } 00218 else 00219 { 00220 assert(!PQ.empty()); 00221 PQ.pop(); 00222 } 00223 } 00224 00225 Timer.stop(); 00226 00227 STXXL_MSG("Records in PQ: " << PQ.size()); 00228 00229 STXXL_MSG("Deletions/Insertion elapsed time: " << (Timer.mseconds() / 1000.) << 00230 " seconds : " << (double(ops) / (Timer.mseconds() / 1000.)) << " key/data pairs per sec"); 00231 00232 std::cout << *Stats; 00233 } 00234 00235 int main(int argc, char * argv[]) 00236 { 00237 STXXL_MSG("stxxl::pq lock size: " << BLOCK_SIZE << " bytes"); 00238 00239 #ifdef STXXL_DIRECT_IO_OFF 00240 STXXL_MSG("STXXL_DIRECT_IO_OFF is defined"); 00241 #else 00242 STXXL_MSG("STXXL_DIRECT_IO_OFF is NOT defined"); 00243 #endif 00244 00245 if (argc < 3) 00246 { 00247 STXXL_MSG("Usage: " << argv[0] << " version #ops"); 00248 STXXL_MSG("\t version = 1: insert-all-delete-all stxxl pq"); 00249 STXXL_MSG("\t version = 2: intermixed insert/delete stxxl pq"); 00250 return -1; 00251 } 00252 00253 int version = atoi(argv[1]); 00254 stxxl::int64 ops = stxxl::atoint64(argv[2]); 00255 00256 00257 STXXL_MSG("Running version : " << version); 00258 STXXL_MSG("Operations to perform: " << ops); 00259 00260 switch (version) 00261 { 00262 case 1: 00263 run_stxxl_insert_all_delete_all(ops); 00264 break; 00265 case 2: 00266 run_stxxl_intermixed(ops); 00267 break; 00268 default: 00269 STXXL_MSG("Unsupported version " << version); 00270 } 00271 }