source: trunk/ADOL-C/src/storemanager.h @ 635

Last change on this file since 635 was 635, checked in by kulshres, 4 years ago

Build with boost library

Signed-off-by: Kshitij Kulshreshtha <kshitij@…>

  • Property svn:keywords set to Id
File size: 8.8 KB
Line 
1// -*- c++ -*- hello emacs...
2/*----------------------------------------------------------------------------
3 ADOL-C--  Automatic Differentiation by Overloading in C++ - simplified
4 File:     storemanager.h
5 Revision: $Id: storemanager.h 635 2015-08-20 18:09:58Z kulshres $
6 Contents: storemanager.h contains definitions of abstract interface
7           class StoreManager and some derived classes implementing the
8           desired functionality.
9
10 Copyright (c) 2006 Johannes Willkomm <johannes.willkomm@rwth-aachen.de>
11               2011-2013 Kshitij Kulshreshtha <kshitij@math.upb.de>
12               2012 Benjamin Letschert <letschi@mail.upb.de>
13               2013 Jean Utke <utke@mcs.anl.gov>
14
15 This file is part of ADOL-C.
16
17 The classes StoreManagerXYZ basically takes the global double *store pointer
18 into their obhut and implement next_loc and free_loc.
19
20 They basic idea is taken from "The C++ Programming Language" by Bjarne
21 Stroustrup, from the chapter 19 on iterators and allocators.
22
23 To understand how and why they work do the following:
24 1) Have a look at StoreManagerInSitu and convince yourself that it is
25    exactly the same as the solution presented in the Stroustrup book,
26    except that we always have just one big array instead of a linked
27    list of chunks.
28
29    This means in particular that we have to copy the values from the
30    old array into the lower half of the new one (we always double the size).
31
32 2) Have a look at StoreManagerLocint and convince yourself that these do
33    the same as StoreManagerInSitu except that the linked list of free
34    slots is maintained in a completely different portion of memory. This
35    means the values in freed slots remain untouched until they are
36    allocated again.
37
38
39 3) Have a look a class StoreManagerLocintBlock. This class uses a list of
40    of free blocks of different sizes instead of free locations.
41
42 class StoreManagerInSitu
43 An unsafe implementation is provided as well, but commented out.
44 It does not use the indexFeld array which saves between
45 25% and 50% memory relative to the above safe implementation.
46
47 It is most closely modelled after the example found in the
48 Stroustrup book.
49
50 It appears that it works very well, if one does not use the
51 trace_on(tag, 1); ... trace_off(); reverse(); way of using ADOL-C.
52 If the first sweep is forward it works fine.
53 Therefore I left it in here as a comment so an interested user
54 with acute main memory scarcity may give it a try.
55           
56
57 History:
58          20120427 bl:     add blocking store management
59          20110208 kk:     incorporated in ADOL-C; moved some code arround
60          20060507 jw:     begin
61
62----------------------------------------------------------------------------*/
63
64#ifndef ADOL_C__STOREMANAGER_H
65#define ADOL_C__STOREMANAGER_H
66
67#if defined(ADOLC_INTERNAL)
68#    if HAVE_CONFIG_H
69#        include "config.h"
70#    endif
71#endif
72#include <forward_list>
73#if defined(HAVE_BOOST_POOL_POOL_ALLOC_HPP) && defined(HAVE_BOOST_SYSTEM)
74#include <boost/pool/pool_alloc.hpp>
75#define USE_BOOST_POOL 1
76#else
77#define USE_BOOST_POOL 0
78#endif
79#include <adolc/internal/common.h>
80
81class Keeper;
82
83class StoreManager {
84  friend class Keeper;
85protected:
86  static size_t const initialSize = 4;
87  double myGcTriggerRatio;
88  size_t myGcTriggerMaxSize;
89  virtual void grow(size_t mingrow = 0) = 0;
90public:
91  StoreManager() : myGcTriggerRatio(1.5), myGcTriggerMaxSize(initialSize) {}
92  virtual ~StoreManager() {}
93  virtual locint next_loc() = 0;
94  virtual void free_loc(locint) = 0;
95  virtual void ensure_block(size_t n) = 0;
96  void setStoreManagerControl(double gcTriggerRatio, size_t gcTriggerMaxSize) { myGcTriggerRatio=gcTriggerRatio; myGcTriggerMaxSize=gcTriggerMaxSize;}
97  double gcTriggerRatio() const {return myGcTriggerRatio;}
98  size_t gcTriggerMaxSize() const {return myGcTriggerMaxSize;}
99
100//   // effectively the current size of the store array
101  virtual size_t maxSize() const = 0;
102
103//   // the number of slots currently in use
104  virtual size_t size() const = 0;
105};
106
107class StoreManagerLocint : public StoreManager {
108protected:
109  double * &storePtr;
110  locint * indexFree;
111  locint head;
112  size_t &maxsize;
113  size_t &currentfill;
114  virtual void grow(size_t mingrow = 0);
115public:
116
117  StoreManagerLocint(double * &storePtr, size_t &size, size_t &numlives);
118  StoreManagerLocint(const StoreManagerLocint *const stm, double * &storePtr, size_t &size, size_t &numLives);
119
120  virtual ~StoreManagerLocint();
121  virtual inline size_t size() const { return currentfill; }
122
123  virtual inline size_t maxSize() const { return maxsize; }
124
125  virtual inline bool realloc_on_next_loc() const { 
126      return (head == 0);
127  }
128
129  virtual locint next_loc();
130  virtual void free_loc(locint loc); 
131  virtual void ensure_block(size_t n) {}
132};
133
134class StoreManagerLocintBlock : public StoreManager {
135protected:
136    double * &storePtr;
137    struct FreeBlock {
138        locint next; // next location
139        size_t size; // number of following free locations
140        FreeBlock(): next(0), size(0) {}
141        FreeBlock(const struct FreeBlock &block) :
142            next(block.next),size(block.size) {}
143        FreeBlock(const locint& n, const size_t& s) :
144            next(n), size(s) {}
145        bool operator<(const struct FreeBlock& b) const {
146            return (next < b.next);
147        }
148    };
149
150    std::forward_list<struct FreeBlock
151#if USE_BOOST_POOL
152                      , boost::fast_pool_allocator<struct FreeBlock> 
153#endif
154                      >  indexFree;
155    size_t &maxsize;
156    size_t &currentfill;
157
158    void consolidateBlocks();
159#ifdef ADOLC_LOCDEBUG
160    unsigned int ensure_blockCallsSinceLastConsolidateBlocks;
161#endif
162    /**
163     * when minGrow is specified we asssume that we have already
164     * search the blocks and found no block with minGrow locations in it
165     */
166    virtual void grow(size_t minGrow=0 );
167public:
168    StoreManagerLocintBlock(double * &storePtr, size_t &size, size_t &numlives);
169    StoreManagerLocintBlock(const StoreManagerLocintBlock *const stm, double * &storePtr, size_t &size, size_t &numLives);
170
171    virtual ~StoreManagerLocintBlock();
172    virtual inline size_t size() const { return currentfill; }
173
174    virtual inline size_t maxSize() const { return maxsize; }
175
176    virtual locint next_loc();
177    virtual void free_loc(locint loc);
178    virtual void ensure_block(size_t n);
179};
180
181#if 0
182/* This implementation is unsafe in that using tace_on with keep=1 and
183   reverse mode directly afterwards will yield incorrect results.
184   For all other purposes it seem to work just fine, so it's left here
185   for reference as a comment.
186*/
187
188/* unsafe - use with care */
189
190class StoreManagerInSitu : public StoreManager {
191  //  static size_t const initialeGroesse = 512;
192protected:
193  double * &storePtr;
194  struct Link {
195    struct Link *next;
196  };
197  Link *head;
198  size_t groesse;
199  size_t anzahl;
200public:
201  size_t maxIndexUsed;
202
203  StoreManager(double * &storePtr) :
204    storePtr(storePtr),
205    head(0),
206    groesse(initialeGroesse),
207    anzahl(0),
208    maxIndexUsed(0)
209  {
210    // while a place in store is unused we want to place
211    // a Link stucture (i.e. a pointer) there
212    assert(sizeof(double) >= sizeof(void*));
213    assert(sizeof(double) >= sizeof(Link));
214    std::cerr << "StoreManager::StoreManager()\n";
215  }
216
217  virtual ~StoreManager() {
218    if (storePtr) {
219      delete [] storePtr;
220      storePtr = 0;
221    }
222    std::cerr << "StoreManager::~StoreManager()\n";
223  }
224
225  virtual inline size_t size() const { return anzahl; }
226
227  virtual inline size_t maxSize() const { return groesse; }
228
229  virtual locint next_loc(size_t n = 1) {
230    assert(n == 1);
231    if (head == 0) {
232      grow();
233    }
234    assert(head);
235    double * const dPtr = reinterpret_cast<double*>(head);
236    head = head->next;
237    ++anzahl;
238    locint const result = dPtr - storePtr;
239    maxIndexUsed = std::max((locint)maxIndexUsed, result);
240    return result;
241  }
242
243  virtual void free_loc(locint loc) {
244    assert(loc < groesse);
245    Link *returned = reinterpret_cast<Link*>(storePtr + loc);
246    returned->next = head;
247    head = returned;
248    --anzahl;
249  }
250private:
251  void grow() {
252    size_t const alteGroesse = groesse;
253    groesse *= 2;
254    assert(alteGroesse == initialeGroesse or size() == alteGroesse);
255    std::cerr << "StoreManager::grow(): increase size to " << groesse << "\n";
256    double *const oldStore = storePtr;
257    std::cerr << "StoreManager::grow(): allocate " << groesse * sizeof(double) << " B\n";
258    storePtr = new double[groesse];
259    size_t i = 0;
260    if (alteGroesse != initialeGroesse) { // nicht beim ersten Mal
261      std::cerr << "StoreManager::grow(): copy values\n";
262      for ( ; i < alteGroesse; ++i) {
263        storePtr[i] = oldStore[i];
264      }
265      std::cerr << "StoreManager::grow(): free " << alteGroesse * sizeof(double) << " B\n";
266      delete [] oldStore;
267    }
268    head = reinterpret_cast<Link*>(storePtr + i);
269    for ( ; i < groesse-1; ++i) {
270      reinterpret_cast<Link*>(storePtr + i)->next
271        = reinterpret_cast<Link*>(storePtr + i + 1);
272    }
273    reinterpret_cast<Link*>(storePtr + i)->next = 0;
274  }
275
276};
277#endif /* 0 */
278
279#endif /* ADOL_C__STOREMANAGER_H */
280
Note: See TracBrowser for help on using the repository browser.