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

Last change on this file since 435 was 435, checked in by kulshres, 6 years ago

less work in free_loc() for StoreManagerLocintBlock?

but work still needs to be done in ensure_block()

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

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