containers/test_pqueue.cpp

This is an example of how to use 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 }

Generated on Thu Jun 4 10:30:00 2009 for Stxxl by  doxygen 1.4.7