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

Last change on this file since 541 was 541, checked in by kulshres, 5 years ago

correct paths in internal headers too.

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

  • Property svn:keywords set to Id
File size: 8.2 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 541 2014-08-15 14:11:16Z 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#include <adolc/internal/common.h>
68#include <list>
69
70class StoreManager {
71protected:
72  static size_t const initialSize = 4;
73  double myGcTriggerRatio;
74  size_t myGcTriggerMaxSize;
75public:
76  StoreManager() : myGcTriggerRatio(1.5), myGcTriggerMaxSize(initialSize) {}
77  virtual ~StoreManager() {}
78  virtual locint next_loc() = 0;
79  virtual void free_loc(locint) = 0;
80  virtual void ensure_block(size_t n) = 0;
81  void setStoreManagerControl(double gcTriggerRatio, size_t gcTriggerMaxSize) { myGcTriggerRatio=gcTriggerRatio; myGcTriggerMaxSize=gcTriggerMaxSize;}
82  double gcTriggerRatio() const {return myGcTriggerRatio;}
83  size_t gcTriggerMaxSize() const {return myGcTriggerMaxSize;}
84
85//   // effectively the current size of the store array
86  virtual size_t maxSize() const = 0;
87
88//   // the number of slots currently in use
89  virtual size_t size() const = 0;
90};
91
92class StoreManagerLocint : public StoreManager {
93protected:
94  double * &storePtr;
95  locint * indexFree;
96  locint head;
97  size_t &maxsize;
98  size_t &currentfill;
99private:
100  void grow();
101public:
102
103  StoreManagerLocint(double * &storePtr, size_t &size, size_t &numlives);
104  StoreManagerLocint(const StoreManagerLocint *const stm, double * &storePtr, size_t &size, size_t &numLives);
105
106  virtual ~StoreManagerLocint();
107  virtual inline size_t size() const { return currentfill; }
108
109  virtual inline size_t maxSize() const { return maxsize; }
110
111  virtual inline bool realloc_on_next_loc() const { 
112      return (head == 0);
113  }
114
115  virtual locint next_loc();
116  virtual void free_loc(locint loc); 
117  virtual void ensure_block(size_t n) {}
118};
119
120class StoreManagerLocintBlock : public StoreManager {
121protected:
122    double * &storePtr;
123    struct FreeBlock {
124        locint next; // next location
125        size_t size; // number of following free locations
126        FreeBlock(): next(0), size(0) {}
127        FreeBlock(const struct FreeBlock &block) :
128            next(block.next),size(block.size) {}
129        bool operator<(const struct FreeBlock& b) const {
130            return (next < b.next);
131        }
132    };
133
134    std::list<struct FreeBlock> indexFree;
135    size_t &maxsize;
136    size_t &currentfill;
137
138    void consolidateBlocks();
139#ifdef ADOLC_LOCDEBUG
140    unsigned int ensure_blockCallsSinceLastConsolidateBlocks;
141#endif
142private:
143    /**
144     * when minGrow is specified we asssume that we have already
145     * search the blocks and found no block with minGrow locations in it
146     */
147    void grow(size_t minGrow=0 );
148public:
149    StoreManagerLocintBlock(double * &storePtr, size_t &size, size_t &numlives);
150    StoreManagerLocintBlock(const StoreManagerLocintBlock *const stm, double * &storePtr, size_t &size, size_t &numLives);
151
152    virtual ~StoreManagerLocintBlock();
153    virtual inline size_t size() const { return currentfill; }
154
155    virtual inline size_t maxSize() const { return maxsize; }
156
157    virtual locint next_loc();
158    virtual void free_loc(locint loc);
159    virtual void ensure_block(size_t n);
160};
161
162#if 0
163/* This implementation is unsafe in that using tace_on with keep=1 and
164   reverse mode directly afterwards will yield incorrect results.
165   For all other purposes it seem to work just fine, so it's left here
166   for reference as a comment.
167*/
168
169/* unsafe - use with care */
170
171class StoreManagerInSitu : public StoreManager {
172  //  static size_t const initialeGroesse = 512;
173protected:
174  double * &storePtr;
175  struct Link {
176    struct Link *next;
177  };
178  Link *head;
179  size_t groesse;
180  size_t anzahl;
181public:
182  size_t maxIndexUsed;
183
184  StoreManager(double * &storePtr) :
185    storePtr(storePtr),
186    head(0),
187    groesse(initialeGroesse),
188    anzahl(0),
189    maxIndexUsed(0)
190  {
191    // while a place in store is unused we want to place
192    // a Link stucture (i.e. a pointer) there
193    assert(sizeof(double) >= sizeof(void*));
194    assert(sizeof(double) >= sizeof(Link));
195    std::cerr << "StoreManager::StoreManager()\n";
196  }
197
198  virtual ~StoreManager() {
199    if (storePtr) {
200      delete [] storePtr;
201      storePtr = 0;
202    }
203    std::cerr << "StoreManager::~StoreManager()\n";
204  }
205
206  virtual inline size_t size() const { return anzahl; }
207
208  virtual inline size_t maxSize() const { return groesse; }
209
210  virtual locint next_loc(size_t n = 1) {
211    assert(n == 1);
212    if (head == 0) {
213      grow();
214    }
215    assert(head);
216    double * const dPtr = reinterpret_cast<double*>(head);
217    head = head->next;
218    ++anzahl;
219    locint const result = dPtr - storePtr;
220    maxIndexUsed = std::max((locint)maxIndexUsed, result);
221    return result;
222  }
223
224  virtual void free_loc(locint loc) {
225    assert(loc < groesse);
226    Link *returned = reinterpret_cast<Link*>(storePtr + loc);
227    returned->next = head;
228    head = returned;
229    --anzahl;
230  }
231private:
232  void grow() {
233    size_t const alteGroesse = groesse;
234    groesse *= 2;
235    assert(alteGroesse == initialeGroesse or size() == alteGroesse);
236    std::cerr << "StoreManager::grow(): increase size to " << groesse << "\n";
237    double *const oldStore = storePtr;
238    std::cerr << "StoreManager::grow(): allocate " << groesse * sizeof(double) << " B\n";
239    storePtr = new double[groesse];
240    size_t i = 0;
241    if (alteGroesse != initialeGroesse) { // nicht beim ersten Mal
242      std::cerr << "StoreManager::grow(): copy values\n";
243      for ( ; i < alteGroesse; ++i) {
244        storePtr[i] = oldStore[i];
245      }
246      std::cerr << "StoreManager::grow(): free " << alteGroesse * sizeof(double) << " B\n";
247      delete [] oldStore;
248    }
249    head = reinterpret_cast<Link*>(storePtr + i);
250    for ( ; i < groesse-1; ++i) {
251      reinterpret_cast<Link*>(storePtr + i)->next
252        = reinterpret_cast<Link*>(storePtr + i + 1);
253    }
254    reinterpret_cast<Link*>(storePtr + i)->next = 0;
255  }
256
257};
258#endif /* 0 */
259
260#endif /* ADOL_C__STOREMANAGER_H */
261
Note: See TracBrowser for help on using the repository browser.