ROOT  6.06/09
Reference Guide
StackAllocator.h
Go to the documentation of this file.
1 // @(#)root/minuit2:$Id$
2 // Authors: M. Winkler, F. James, L. Moneta, A. Zsenei 2003-2005
3 
4 /**********************************************************************
5  * *
6  * Copyright (c) 2005 LCG ROOT Math team, CERN/PH-SFT *
7  * *
8  **********************************************************************/
9 
10 #ifndef ROOT_Minuit2_StackAllocator
11 #define ROOT_Minuit2_StackAllocator
12 
13 #include "Minuit2/MnConfig.h"
14 
15 // comment out this line and recompile if you want to gain additional
16 // performance (the gain is mainly for "simple" functions which are easy
17 // to calculate and vanishes quickly if going to cost-intensive functions)
18 // the library is no longer thread save however
19 
20 #ifdef MN_USE_STACK_ALLOC
21 #define _MN_NO_THREAD_SAVE_
22 #endif
23 
24 //#include <iostream>
25 
26 
27 
28 #include <cstdlib>
29 #include <new>
30 
31 namespace ROOT {
32 
33  namespace Minuit2 {
34 
35 
36 
37 /// define stack allocator symbol
38 
39 
40 
41 class StackOverflow {};
42 class StackError {};
43 // using namespace std;
44 
45 /** StackAllocator controls the memory allocation/deallocation of Minuit. If
46  _MN_NO_THREAD_SAVE_ is defined, memory is taken from a pre-allocated piece
47  of heap memory which is then used like a stack, otherwise via standard
48  malloc/free. Note that defining _MN_NO_THREAD_SAVE_ makes the code thread-
49  unsave. The gain in performance is mainly for cost-cheap FCN functions.
50  */
51 
53 
54 public:
55 
56 // enum {default_size = 1048576};
57  enum {default_size = 524288};
58 
60 #ifdef _MN_NO_THREAD_SAVE_
61  //std::cout<<"StackAllocator Allocate "<<default_size<<std::endl;
62  fStack = new unsigned char[default_size];
63 #endif
64  fStackOffset = 0;
65  fBlockCount = 0;
66  }
67 
69 #ifdef _MN_NO_THREAD_SAVE_
70  //std::cout<<"StackAllocator destruct "<<fStackOffset<<std::endl;
71  if(fStack) delete [] fStack;
72 #endif
73  }
74 
75  void* Allocate( size_t nBytes) {
76 #ifdef _MN_NO_THREAD_SAVE_
77  if(fStack == 0) fStack = new unsigned char[default_size];
78  int nAlloc = AlignedSize(nBytes);
79  CheckOverflow(nAlloc);
80 
81 // std::cout << "Allocating " << nAlloc << " bytes, requested = " << nBytes << std::endl;
82 
83  // write the start position of the next block at the start of the block
85  // write the start position of the new block at the end of the block
86  WriteInt( fStackOffset + nAlloc - sizeof(int), fStackOffset);
87 
88  void* result = fStack + fStackOffset + sizeof(int);
89  fStackOffset += nAlloc;
90  fBlockCount++;
91 
92 #ifdef DEBUG_ALLOCATOR
94 #endif
95 
96 #else
97  void* result = malloc(nBytes);
98  if (!result) throw std::bad_alloc();
99 #endif
100 
101  return result;
102  }
103 
104  void Deallocate( void* p) {
105 #ifdef _MN_NO_THREAD_SAVE_
106  // int previousOffset = ReadInt( fStackOffset - sizeof(int));
107  int delBlock = ToInt(p);
108  int nextBlock = ReadInt( delBlock);
109  int previousBlock = ReadInt( nextBlock - sizeof(int));
110  if ( nextBlock == fStackOffset) {
111  // deallocating last allocated
112  fStackOffset = previousBlock;
113  }
114  else {
115  // overwrite previous adr of next block
116  int nextNextBlock = ReadInt(nextBlock);
117  WriteInt( nextNextBlock - sizeof(int), previousBlock);
118  // overwrite head of deleted block
119  WriteInt( previousBlock, nextNextBlock);
120  }
121  fBlockCount--;
122 
123 #ifdef DEBUG_ALLOCATOR
125 #endif
126 #else
127  free(p);
128 #endif
129  // std::cout << "Block at " << delBlock
130  // << " deallocated, fStackOffset = " << fStackOffset << std::endl;
131  }
132 
133  int ReadInt( int offset) {
134  int* ip = (int*)(fStack+offset);
135 
136  // std::cout << "read " << *ip << " from offset " << offset << std::endl;
137 
138  return *ip;
139  }
140 
141  void WriteInt( int offset, int Value) {
142 
143  // std::cout << "writing " << Value << " to offset " << offset << std::endl;
144 
145  int* ip = reinterpret_cast<int*>(fStack+offset);
146  *ip = Value;
147  }
148 
149  int ToInt( void* p) {
150  unsigned char* pc = static_cast<unsigned char*>(p);
151 
152  // std::cout << "toInt: p = " << p << " fStack = " << (void*) fStack << std::endl;
153  // VC 7.1 warning:conversin from __w64 int to int
154  int userBlock = pc - fStack;
155  return userBlock - sizeof(int); // correct for starting int
156  }
157 
158  int AlignedSize( int nBytes) {
159  const int fAlignment = 4;
160  int needed = nBytes % fAlignment == 0 ? nBytes : (nBytes/fAlignment+1)*fAlignment;
161  return needed + 2*sizeof(int);
162  }
163 
164  void CheckOverflow( int n) {
165  if (fStackOffset + n >= default_size) {
166  //std::cout << " no more space on stack allocator" << std::endl;
167  throw StackOverflow();
168  }
169  }
170 
172 
173  //std::cout << "checking consistency for " << fBlockCount << " blocks"<< std::endl;
174 
175  // loop over all blocks
176  int beg = 0;
177  int end = fStackOffset;
178  int nblocks = 0;
179  while (beg < fStackOffset) {
180  end = ReadInt( beg);
181 
182  // std::cout << "beg = " << beg << " end = " << end
183  // << " fStackOffset = " << fStackOffset << std::endl;
184 
185  int beg2 = ReadInt( end - sizeof(int));
186  if ( beg != beg2) {
187  //std::cout << " beg != beg2 " << std::endl;
188  return false;
189  }
190  nblocks++;
191  beg = end;
192  }
193  if (end != fStackOffset) {
194  //std::cout << " end != fStackOffset" << std::endl;
195  return false;
196  }
197  if (nblocks != fBlockCount) {
198  //std::cout << "nblocks != fBlockCount" << std::endl;
199  return false;
200  }
201  //std::cout << "Allocator is in consistent state, nblocks = " << nblocks << std::endl;
202  return true;
203  }
204 
205 private:
206 
207  unsigned char* fStack;
208 // unsigned char fStack[default_size];
211 
212 };
213 
214 
215 
217 
218  // t.b.d need to use same trick as Boost singleton.hpp to be sure that
219  // StackAllocator is created before main()
220 
221  public:
222 
223 
224  static StackAllocator & Get() {
225  static StackAllocator gStackAllocator;
226  return gStackAllocator;
227  }
228 };
229 
230 
231 
232  } // namespace Minuit2
233 
234 } // namespace ROOT
235 
236 #endif
define stack allocator symbol
Namespace for new ROOT classes and functions.
Definition: ROOT.py:1
StackAllocator controls the memory allocation/deallocation of Minuit.
Vc_ALWAYS_INLINE void free(T *p)
Frees memory that was allocated with Vc::malloc.
Definition: memory.h:94
void * Allocate(size_t nBytes)
double result[121]
static StackAllocator & Get()
void WriteInt(int offset, int Value)
Vc_ALWAYS_INLINE_L T *Vc_ALWAYS_INLINE_R malloc(size_t n)
Allocates memory on the Heap with alignment and padding suitable for vectorized access.
Definition: memory.h:67
const Int_t n
Definition: legend1.C:16
const char * Value
Definition: TXMLSetup.cxx:73