STXXL  1.4-dev
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
block_prefetcher.h
Go to the documentation of this file.
1 /***************************************************************************
2  * include/stxxl/bits/mng/block_prefetcher.h
3  *
4  * Part of the STXXL. See http://stxxl.sourceforge.net
5  *
6  * Copyright (C) 2002-2004 Roman Dementiev <[email protected]>
7  * Copyright (C) 2009, 2010 Johannes Singler <[email protected]>
8  * Copyright (C) 2009 Andreas Beckmann <[email protected]>
9  *
10  * Distributed under the Boost Software License, Version 1.0.
11  * (See accompanying file LICENSE_1_0.txt or copy at
12  * http://www.boost.org/LICENSE_1_0.txt)
13  **************************************************************************/
14 
15 #ifndef STXXL_MNG_BLOCK_PREFETCHER_HEADER
16 #define STXXL_MNG_BLOCK_PREFETCHER_HEADER
17 
18 #include <vector>
19 #include <queue>
20 
22 #include <stxxl/bits/io/request.h>
23 #include <stxxl/bits/io/iostats.h>
24 #include <stxxl/bits/noncopyable.h>
25 
27 
28 //! \addtogroup schedlayer
29 //! \{
30 
32 {
35 
36 public:
38  : switch_(_switch), on_compl(on_compl)
39  { }
40 
41  void operator () (request* req)
42  {
43  // call before setting switch to on, otherwise, user has no way to wait
44  // for the completion handler to be executed
45  on_compl(req);
46  switch_.on();
47  }
48 };
49 
50 //! Encapsulates asynchronous prefetching engine.
51 //!
52 //! \c block_prefetcher overlaps I/Os with consumption of read data.
53 //! Utilizes optimal asynchronous prefetch scheduling (by Peter Sanders et.al.)
54 template <typename BlockType, typename BidIteratorType>
56 {
57 public:
58  typedef BlockType block_type;
59  typedef BidIteratorType bid_iterator_type;
60 
61  typedef typename block_type::bid_type bid_type;
62 
63 protected:
67 
69 
72 
74 
78 
81 
83 
85  {
86  STXXL_VERBOSE1("block_prefetcher: waiting block " << iblock);
87  {
88  stats::scoped_wait_timer wait_timer(stats::WAIT_OP_READ);
89 
90  completed[iblock].wait_for_on();
91  }
92  STXXL_VERBOSE1("block_prefetcher: finished waiting block " << iblock);
93  int_type ibuffer = pref_buffer[iblock];
94  STXXL_VERBOSE1("block_prefetcher: returning buffer " << ibuffer);
95  assert(ibuffer >= 0 && ibuffer < nreadblocks);
96  return (read_buffers + ibuffer);
97  }
98 
99 public:
100  //! Constructs an object and immediately starts prefetching.
101  //! \param _cons_begin \c bid_iterator pointing to the \c bid of the first block to be consumed
102  //! \param _cons_end \c bid_iterator pointing to the \c bid of the ( \b last + 1 ) block of consumption sequence
103  //! \param _pref_seq gives the prefetch order, is a pointer to the integer array that contains
104  //! the indices of the blocks in the consumption sequence
105  //! \param _prefetch_buf_size amount of prefetch buffers to use
106  //! \param do_after_fetch unknown
108  bid_iterator_type _cons_begin,
109  bid_iterator_type _cons_end,
110  int_type* _pref_seq,
111  int_type _prefetch_buf_size,
112  completion_handler do_after_fetch = completion_handler())
113  : consume_seq_begin(_cons_begin),
114  consume_seq_end(_cons_end),
115  seq_length(_cons_end - _cons_begin),
116  prefetch_seq(_pref_seq),
117  nextread(STXXL_MIN(unsigned_type(_prefetch_buf_size), seq_length)),
118  nextconsume(0),
119  nreadblocks(nextread),
120  do_after_fetch(do_after_fetch)
121  {
122  STXXL_VERBOSE1("block_prefetcher: seq_length=" << seq_length);
123  STXXL_VERBOSE1("block_prefetcher: _prefetch_buf_size=" << _prefetch_buf_size);
124  assert(seq_length > 0);
125  assert(_prefetch_buf_size > 0);
126  int_type i;
127  read_buffers = new block_type[nreadblocks];
128  read_reqs = new request_ptr[nreadblocks];
129  read_bids = new bid_type[nreadblocks];
130  pref_buffer = new int_type[seq_length];
131 
132  std::fill(pref_buffer, pref_buffer + seq_length, -1);
133 
134  completed = new onoff_switch[seq_length];
135 
136  for (i = 0; i < nreadblocks; ++i)
137  {
138  assert(prefetch_seq[i] < int_type(seq_length));
139  assert(prefetch_seq[i] >= 0);
140  read_bids[i] = *(consume_seq_begin + prefetch_seq[i]);
141  STXXL_VERBOSE1("block_prefetcher: reading block " << i <<
142  " prefetch_seq[" << i << "]=" << prefetch_seq[i] <<
143  " @ " << &read_buffers[i] <<
144  " @ " << read_bids[i]);
145  read_reqs[i] = read_buffers[i].read(
146  read_bids[i],
147  set_switch_handler(*(completed + prefetch_seq[i]), do_after_fetch));
148  pref_buffer[prefetch_seq[i]] = i;
149  }
150  }
151  //! Pulls next unconsumed block from the consumption sequence.
152  //! \return Pointer to the already prefetched block from the internal buffer pool
154  {
155  STXXL_VERBOSE1("block_prefetcher: pulling a block");
156  return wait(nextconsume++);
157  }
158  //! Exchanges buffers between prefetcher and application.
159  //! \param buffer pointer to the consumed buffer. After call if return value is true \c buffer
160  //! contains valid pointer to the next unconsumed prefetched buffer.
161  //! \remark parameter \c buffer must be value returned by \c pull_block() or \c block_consumed() methods
162  //! \return \c false if there are no blocks to prefetch left, \c true if consumption sequence is not emptied
163  bool block_consumed(block_type*& buffer)
164  {
165  int_type ibuffer = buffer - read_buffers;
166  STXXL_VERBOSE1("block_prefetcher: buffer " << ibuffer << " consumed");
167  if (read_reqs[ibuffer].valid())
168  read_reqs[ibuffer]->wait();
169 
170  read_reqs[ibuffer] = NULL;
171 
172  if (nextread < seq_length)
173  {
174  assert(ibuffer >= 0 && ibuffer < nreadblocks);
175  int_type next_2_prefetch = prefetch_seq[nextread++];
176  STXXL_VERBOSE1("block_prefetcher: prefetching block " << next_2_prefetch);
177 
178  assert((next_2_prefetch < int_type(seq_length)) && (next_2_prefetch >= 0));
179  assert(!completed[next_2_prefetch].is_on());
180 
181  pref_buffer[next_2_prefetch] = ibuffer;
182  read_bids[ibuffer] = *(consume_seq_begin + next_2_prefetch);
183  read_reqs[ibuffer] = read_buffers[ibuffer].read(
184  read_bids[ibuffer],
185  set_switch_handler(*(completed + next_2_prefetch), do_after_fetch)
186  );
187  }
188 
189  if (nextconsume >= seq_length)
190  return false;
191 
192  buffer = wait(nextconsume++);
193 
194  return true;
195  }
196 
197  //! No more consumable blocks available, but can't delete the prefetcher,
198  //! because not all blocks may have been returned, yet.
199  bool empty() const
200  {
201  return nextconsume >= seq_length;
202  }
203 
204  //! Index of the next element in the consume sequence.
206  {
207  return nextconsume;
208  }
209 
210  //! Frees used memory.
212  {
213  for (int_type i = 0; i < nreadblocks; ++i)
214  if (read_reqs[i].valid())
215  read_reqs[i]->wait();
216 
217  delete[] read_reqs;
218  delete[] read_bids;
219  delete[] completed;
220  delete[] pref_buffer;
221  delete[] read_buffers;
222  }
223 };
224 
225 //! \}
226 
228 
229 #endif // !STXXL_MNG_BLOCK_PREFETCHER_HEADER
Completion handler class (Loki-style).
const Type & STXXL_MIN(const Type &a, const Type &b)
Definition: utils.h:146
bool empty() const
No more consumable blocks available, but can&#39;t delete the prefetcher, because not all blocks may have...
block_type::bid_type bid_type
completion_handler on_compl
bid_iterator_type consume_seq_end
set_switch_handler(onoff_switch &_switch, const completion_handler &on_compl)
BidIteratorType bid_iterator_type
Encapsulates asynchronous prefetching engine.
bid_iterator_type consume_seq_begin
block_prefetcher(bid_iterator_type _cons_begin, bid_iterator_type _cons_end, int_type *_pref_seq, int_type _prefetch_buf_size, completion_handler do_after_fetch=completion_handler())
Constructs an object and immediately starts prefetching.
choose_int_types< my_pointer_size >::int_type int_type
Definition: types.h:63
#define STXXL_BEGIN_NAMESPACE
Definition: namespace.h:16
unsigned_type pos() const
Index of the next element in the consume sequence.
#define STXXL_VERBOSE1(x)
Definition: verbose.h:113
block_type * wait(int_type iblock)
bool block_consumed(block_type *&buffer)
Exchanges buffers between prefetcher and application.
choose_int_types< my_pointer_size >::unsigned_type unsigned_type
Definition: types.h:64
block_type * pull_block()
Pulls next unconsumed block from the consumption sequence.
Request object encapsulating basic properties like file and offset.
Definition: request.h:38
completion_handler do_after_fetch
#define STXXL_END_NAMESPACE
Definition: namespace.h:17
const int_type nreadblocks
~block_prefetcher()
Frees used memory.