source: stable/2.4/ADOL-C/src/storemanager.h @ 397

Last change on this file since 397 was 352, checked in by kulshres, 7 years ago

Rewrite of the StoreManagerLocintBlock? class

From: Jean Utke <utke@…>

and change in variable names as suggested to do away with mixing
english and german names.

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

This also combines the following commits on Jean's branch:

commit 79f770c3d2ab865a38301d1f86fa7c5b1b5d8dcf
Author: Jean Utke <utke@…>
Date: Sat Sep 22 01:15:58 2012 -0500

the previous fix was still insufficient because it inadvertently left
0 size blocks in the front of the list and the comment that the
newly allocated blocks should be pushed to the end apparently applied
only to the grow routine but not to next_loc so I went and did a more
wholesale change of what I think might work and what incidentally also
seems a little more straitghtforward. This is still a limited change
and I am still dubious about the constructor when non-zero values for
anxahl and groesse are passed
And ALSO these variable names OUGHT to be changed to something reasonable. :-)

commit f463cfcef971df5354709f430083a651ee543713
Author: Jean Utke <utke@…>
Date: Fri Sep 21 18:25:21 2012 -0500

fixing up earlier change in 3e9a21e76d1cb2ee10c220fa7a2f4d0dc8ae8e09
this earlier change was wrong too because while it expanded to
indexFeld with maximal location it still was wrong because
locations with bigger values could already be handed out.
So we restore part of the older code BUT then track if
we actually updated any existing IndexFeld? instance and if not
make a new one.

commit c7892ac99dea373e3eb7d5b7812230b18cf76ce3
Author: Jean Utke <utke@…>
Date: Fri Sep 21 17:32:37 2012 -0500

it is more efficient to use empty instead of size in these conditions

commit 3e9a21e76d1cb2ee10c220fa7a2f4d0dc8ae8e09
Author: Jean Utke <utke@…>
Date: Fri Sep 21 17:23:34 2012 -0500

fixed the behavior where the condition essentially makes the assumption
that the INDEXFELD must include the tail of the handed out locints as
if the locints were allocated in freed in LIFO fashion similar to the old
allocation scheme that this trying to avoid... details are below quoted from an e-mail
also changed some debug messages
================= Details =============

Below you see how the remaining open locations are tracked in just one remaining "IndexFeld?"
instance in the list where size counts down as locations are handed out in next_loc.

INDEXFELD ( 41772 , 3)
next_loc() , anzahl= 65534, groesse= 65536
next_loc: 41772 fill: 65534 max: 65536
INDEXFELD ( 41773 , 2)
next_loc() , anzahl= 65535, groesse= 65536
next_loc: 41773 fill: 65535 max: 65536
INDEXFELD ( 41774 , 1)
next_loc() , anzahl= 65536, groesse= 65536
next_loc: 41774 fill: 65536 max: 65536
INDEXFELD ( 41775 , 0)

Here we are now at the point where - after handing out location 41775
we have to grow so grow() is called:

StoreManagerIntegerBlock::grow(): increase size from 65536 to 131072 entries (currently 65536 entries used)
StoreManagerInteger::grow(): allocate 1048576 B doubles and 2097152 B LinkBlocks?
StoreManagerInteger::grow(): copy values
StoreManagerInteger::grow(): free 524288 + 1048576 B

Unfortunately the logic that should now modify the one remaining INDEXFELD mistakenly
assumes that there has to be an INDEXFELD satisfying something very much like
having locints (de)allocated in LIFO fashion as in the old ADOLC:

"iter->next + iter->size == alteGroesse"

but as you can see the one remaining one doesn't so
then this iter->size is *NOT updated*:
but we continue anyway:
Growing:
INDEXFELD ( 41775 , 0)

and now the next time we call next_loc we happily find the one IndexFeld? instance whose size is 0 and do:

indexFeld.front().size--;

and we get *... DRUMROLL ...* the wraparound for size:

INDEXFELD ( 41776 , 18446744073709551615)

and from there on things go downhill....

File size: 7.6 KB
Line 
1// -*- c++ -*- hello emacs...
2/*----------------------------------------------------------------------------
3 ADOL-C--  Automatic Differentiation by Overloading in C++ - simplified
4 File:     storemanager.h
5 Revision: $Id$
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    };
126
127    list<struct FreeBlock> indexFree;
128    size_t &maxsize;
129    size_t &currentfill;
130private:
131    /**
132     * when minGrow is specified we asssume that we have already
133     * search the blocks and found no block with minGrow locations in it
134     */
135    void grow(size_t minGrow=0 );
136public:
137    StoreManagerLocintBlock(double * &storePtr, size_t &size, size_t &numlives);
138    StoreManagerLocintBlock(const StoreManagerLocintBlock *const stm, double * &storePtr, size_t &size, size_t &numLives);
139
140    virtual ~StoreManagerLocintBlock();
141    virtual inline size_t size() const { return currentfill; }
142
143    virtual inline size_t maxSize() const { return maxsize; }
144
145    virtual locint next_loc();
146    virtual void free_loc(locint loc);
147    virtual void ensure_block(size_t n);
148};
149
150#if 0
151/* This implementation is unsafe in that using tace_on with keep=1 and
152   reverse mode directly afterwards will yield incorrect results.
153   For all other purposes it seem to work just fine, so it's left here
154   for reference as a comment.
155*/
156
157/* unsafe - use with care */
158
159class StoreManagerInSitu : public StoreManager {
160  //  static size_t const initialeGroesse = 512;
161protected:
162  double * &storePtr;
163  struct Link {
164    struct Link *next;
165  };
166  Link *head;
167  size_t groesse;
168  size_t anzahl;
169public:
170  size_t maxIndexUsed;
171
172  StoreManager(double * &storePtr) :
173    storePtr(storePtr),
174    head(0),
175    groesse(initialeGroesse),
176    anzahl(0),
177    maxIndexUsed(0)
178  {
179    // while a place in store is unused we want to place
180    // a Link stucture (i.e. a pointer) there
181    assert(sizeof(double) >= sizeof(void*));
182    assert(sizeof(double) >= sizeof(Link));
183    std::cerr << "StoreManager::StoreManager()\n";
184  }
185
186  virtual ~StoreManager() {
187    if (storePtr) {
188      delete [] storePtr;
189      storePtr = 0;
190    }
191    std::cerr << "StoreManager::~StoreManager()\n";
192  }
193
194  virtual inline size_t size() const { return anzahl; }
195
196  virtual inline size_t maxSize() const { return groesse; }
197
198  virtual locint next_loc(size_t n = 1) {
199    assert(n == 1);
200    if (head == 0) {
201      grow();
202    }
203    assert(head);
204    double * const dPtr = reinterpret_cast<double*>(head);
205    head = head->next;
206    ++anzahl;
207    locint const result = dPtr - storePtr;
208    maxIndexUsed = std::max((locint)maxIndexUsed, result);
209    return result;
210  }
211
212  virtual void free_loc(locint loc) {
213    assert(loc < groesse);
214    Link *returned = reinterpret_cast<Link*>(storePtr + loc);
215    returned->next = head;
216    head = returned;
217    --anzahl;
218  }
219private:
220  void grow() {
221    size_t const alteGroesse = groesse;
222    groesse *= 2;
223    assert(alteGroesse == initialeGroesse or size() == alteGroesse);
224    std::cerr << "StoreManager::grow(): increase size to " << groesse << "\n";
225    double *const oldStore = storePtr;
226    std::cerr << "StoreManager::grow(): allocate " << groesse * sizeof(double) << " B\n";
227    storePtr = new double[groesse];
228    size_t i = 0;
229    if (alteGroesse != initialeGroesse) { // nicht beim ersten Mal
230      std::cerr << "StoreManager::grow(): copy values\n";
231      for ( ; i < alteGroesse; ++i) {
232        storePtr[i] = oldStore[i];
233      }
234      std::cerr << "StoreManager::grow(): free " << alteGroesse * sizeof(double) << " B\n";
235      delete [] oldStore;
236    }
237    head = reinterpret_cast<Link*>(storePtr + i);
238    for ( ; i < groesse-1; ++i) {
239      reinterpret_cast<Link*>(storePtr + i)->next
240        = reinterpret_cast<Link*>(storePtr + i + 1);
241    }
242    reinterpret_cast<Link*>(storePtr + i)->next = 0;
243  }
244
245};
246#endif /* 0 */
247
248#endif /* ADOL_C__STOREMANAGER_H */
249
Note: See TracBrowser for help on using the repository browser.