1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
|
/***************************************************************************
* tests/containers/test_pqueue.cpp
*
* Part of the STXXL. See http://stxxl.sourceforge.net
*
* Copyright (C) 2003 Roman Dementiev <dementiev@mpi-sb.mpg.de>
* Copyright (C) 2009 Andreas Beckmann <beckmann@cs.uni-frankfurt.de>
*
* Distributed under the Boost Software License, Version 1.0.
* (See accompanying file LICENSE_1_0.txt or copy at
* http://www.boost.org/LICENSE_1_0.txt)
**************************************************************************/
//! \example containers/test_pqueue.cpp
//! This is an example of how to use \c stxxl::PRIORITY_QUEUE_GENERATOR
//! and \c stxxl::priority_queue
#include <limits>
#include <stxxl/priority_queue>
#include <stxxl/timer>
#define RECORD_SIZE 128
struct my_type
{
typedef int key_type;
key_type key;
char data[RECORD_SIZE - sizeof(key_type)];
my_type() { }
explicit my_type(key_type k) : key(k)
{
#if STXXL_WITH_VALGRIND
memset(data, 0, sizeof(data));
#endif
}
};
std::ostream& operator << (std::ostream& o, const my_type& obj)
{
o << obj.key;
return o;
}
struct my_cmp : std::binary_function<my_type, my_type, bool> // greater
{
bool operator () (const my_type& a, const my_type& b) const
{
return a.key > b.key;
}
my_type min_value() const
{
return my_type(std::numeric_limits<my_type::key_type>::max());
}
};
// forced instantiation
const unsigned volume = 1024 * 1024; // in KiB
template class stxxl::PRIORITY_QUEUE_GENERATOR<my_type, my_cmp, 32* 1024* 1024, volume / sizeof(my_type)>;
int main()
{
/*
unsigned BufferSize1_ = 32, // equalize procedure call overheads etc.
unsigned N_ = 512, // bandwidth
unsigned IntKMAX_ = 64, // maximal arity for internal mergers
unsigned IntLevels_ = 4,
unsigned BlockSize_ = (2*1024*1024),
unsigned ExtKMAX_ = 64, // maximal arity for external mergers
unsigned ExtLevels_ = 2,
*/
//typedef priority_queue<priority_queue_config<my_type,my_cmp,
// 32,512,64,3,(4*1024),0x7fffffff,1> > pq_type;
typedef stxxl::PRIORITY_QUEUE_GENERATOR<my_type, my_cmp, 32* 1024* 1024, volume / sizeof(my_type)> gen;
typedef gen::result pq_type;
typedef pq_type::block_type block_type;
STXXL_MSG("Block size: " << block_type::raw_size);
STXXL_MSG("AI: " << gen::AI);
STXXL_MSG("X : " << gen::X);
STXXL_MSG("N : " << gen::N);
STXXL_MSG("AE: " << gen::AE);
stxxl::timer Timer;
Timer.start();
const unsigned mem_for_pools = 128 * 1024 * 1024;
stxxl::read_write_pool<block_type> pool((mem_for_pools / 2) / block_type::raw_size, (mem_for_pools / 2) / block_type::raw_size);
pq_type p(pool);
stxxl::int64 nelements = stxxl::int64(volume * 1024 / sizeof(my_type)), i;
STXXL_MSG("Internal memory consumption of the priority queue: " << p.mem_cons() << " B");
STXXL_MSG("Max elements: " << nelements);
for (i = 0; i < nelements; i++)
{
if ((i % (1024 * 1024)) == 0)
STXXL_MSG("Inserting element " << i);
p.push(my_type(int(nelements - i)));
}
Timer.stop();
STXXL_MSG("Time spent for filling: " << Timer.seconds() << " s");
STXXL_CHECK(p.size() == (stxxl::uint64)nelements);
#if 0
// test swap
pq_type p1(pool);
std::swap(p, p1);
std::swap(p, p1);
#endif
STXXL_MSG("Internal memory consumption of the priority queue: " << p.mem_cons() << " B");
Timer.reset();
Timer.start();
for (i = 0; i < (nelements); ++i)
{
STXXL_CHECK(!p.empty());
//STXXL_MSG( p.top() );
STXXL_CHECK(p.top().key == i + 1);
p.pop();
if ((i % (1024 * 1024)) == 0)
STXXL_MSG("Element " << i << " popped");
}
Timer.stop();
STXXL_MSG("Time spent for removing elements: " << Timer.seconds() << " s");
STXXL_CHECK(p.size() == 0);
STXXL_CHECK(p.empty());
STXXL_MSG("Internal memory consumption of the priority queue: " << p.mem_cons() << " B");
}
|
