containers/pq_benchmark.cpp

This is a benchmark mentioned in the paper R. Dementiev, L. Kettner, P. Sanders "STXXL: standard template library for XXL data sets" Software: Practice and Experience Volume 38, Issue 6, Pages 589-637, May 2008 DOI: 10.1002/spe.844

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 }

Generated on Thu Jun 4 10:21:44 2009 for Stxxl by  doxygen 1.4.7