Some strange type-problem

Hey!

I need some help with a strange behaviour on different types.

I have a class ("clsMem" - see below) used to organize data in memory, which shoud be faster then normal memory-management.

The class has a delimiter-value (min). If a amount of memory smaller then min is requested, allocatoion works linear (N bytes requested -> N bytes reserved), otherwise (if requested memory exeeds min), a block of the size 2^X will be reseved, where X is minimal possible value to sotre the requested data (like ie. requested: 102 byte, reserved: 128 byte, X = 7).
Allocating memory does not return a pointer, but an id (some kind of handle) which can be used to access data independent of the current physical position.

Memory is not really freed!

Every rereved block has group-id (grp) which corrosonds with the mentioned X like this (if min has a value of ie. 16): Requested: 6 byte -> group-id = 6; Requested: 10 byte -> group-id = 10; Requested: 16-31 byte -> group-id = 17; Requested: 32-63 byte -> group-id = 18 etc. Like this, the number of groups is limited. If min has a value of 128, 128+5 group-id's are needed, for data-blocks of 128^5 bytes.

For each group, a dynamic array (clsDynArray<int> emptyS[_MEM_MAX]) is created. If some data is not neended anymore, it's id is sored in the corresponding array for later use. If a amont of memory with the same group is requested, the block will be recyceld without further allocations.

The problem is the "clsDynArray<char> grp;" implementation. If min is > 127, some more then 127 grops are needed. For this, the char-type in "clsDynArray<char> grp" is not enough. Therefore "grp" shoud be declared as something like "clsDynArray<int>" or "clsDynArray<short>". But both doesn't work.

Whatever type i try except of type char, keeps cought in an endless loop and i have no idea why. Maybe someone else finds out...


Thank you for reading!

Best,
Frank



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
const int _SHORT_MEM  = 1;//128;
const int _MAX_MEM    = _SHORT_MEM+64;

class clsMem {
    public:
        virtual ~clsMem() {};
        clsMem() : min(_SHORT_MEM) {  };
        
        inline void         free        (const int &id) {   if (id == 0) return;            int idx = grp[id];              emptyS[idx].Push(id);   };

        inline int          alloc       (int bytes = 1) {  
            register int id(pos.uLen);                      register int newGrp(0);         register  int size(1); 
                  
            if (bytes > min) {
                newGrp =  bytes <= min ? bytes : log2(bytes)+1;   
                size   =  bytes <= min ? bytes : min<<(newGrp-min+1);
            }    
            else  { newGrp = bytes;  size = bytes;  }
        
            if     (emptyS[newGrp].uLen <= 0) {             register char *tp(&*data);      pos.Push(data.resizeBy(size)); 
                if (tp != &*data)                           grp.Push(newGrp);       
            }
            else                                            id = *emptyS[newGrp].Pop();     return id;
           };
        };  

        inline int          BlockSize   (const int &id) {   return grp[id] <= min ? grp[id] : min<<(grp[id]-min+1);}


        const  int min; 
 
        clsDynArray<int>            emptyS[_MAX_MEM];         
        clsDynArray<unsigned int>   pos;
        clsDynArray<char>           grp;       
        clsDynArray<char>           data;
};


DynArray declaration:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
template <class T> struct clsDynArray {
    public:
        virtual ~clsDynArray();
        clsDynArray(unsigned int min = 100, unsigned char fakt = 2);
        
        inline void         Clear       () {wxMessageBox("clsDynArray->Clear() fehlt noch");}
        
        inline unsigned int resizeBy    (const int &count);
        inline T            *Pop        (const int count = 1);        
        inline unsigned int Push        (const T &data);        
        inline T            &operator[] (const register unsigned int &idx);        
        inline T            *operator() (const register unsigned int  idx);        
        inline T            &operator*  () {    return *ptr;        };        
       
        unsigned int        max; 
        unsigned int        uLen;            
        T                   *ptr; 
        const unsigned char fkt; 
};


DynArray implementation:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
template <class T> clsDynArray<T> ::~clsDynArray() {                            delete[] ptr; }
template <class T> clsDynArray<T> :: clsDynArray(unsigned int min, unsigned char fakt) : max(min), fkt(fakt), uLen(0), ptr((T*)malloc(min * sizeof(T))) {} 

template <class T> unsigned int    clsDynArray<T> :: resizeBy(const int &count) {     register unsigned int tmp(max), nc(uLen + count);  
    while (nc > tmp) tmp  *= fkt;               if    (tmp != max)              ptr = (T*)::realloc(ptr, tmp * sizeof(T));        max = tmp;        
    tmp = uLen;                                 uLen = nc;                      new (&ptr[tmp]) T [uLen-tmp];   
    return tmp ;
}
template <class T> T              &clsDynArray<T> :: operator[](const unsigned int &idx) {      if(idx >= uLen)  resizeBy(1 - uLen + idx);   return  ptr[idx];   }
template <class T> T              *clsDynArray<T> :: operator()(const unsigned int  idx) {      if(idx >= uLen)  resizeBy(1 - uLen + idx);   return &ptr[idx];   }

template <class T> unsigned int    clsDynArray<T> :: Push(const T &data){       unsigned int tmp(uLen); ::memcpy(operator()(uLen), &data, sizeof(T)); return tmp;       } 
      
template <class T> T              *clsDynArray<T> :: Pop (int count){           return (uLen >= count) ? &ptr[(uLen-=count)] : (uLen > 0) ? &ptr[(uLen-=uLen)] : ptr;       }  
Last edited on
it looks like you might be trying too hard, to be honest.
allocate in bytes, dole it out (use blocks) based off the sizeof whatever you needed. It would be tricky to make it a template because you want the same static blocks of memory for everything, not based off types, and templates don't handle static on a once case but on a once per template type case.

I would personally let a static vector of bytes do the dirty work for you and see what the performance of that is like. Then all you have to track are the used blocks, and some casting magic (sort of like malloc, but with c++ you can do this with less crudeness).

if you build it with static access to the memory, you don't have to pass it around or anything. Anywhere that you need memory, you can just create a class variable of your manager class type, call it to get the memory: it will behave like a global but with all the goodness that encapsulation brings to protect it.

also inline and register are almost worthless anymore. You can time it or check the assembly but they generally don't do anything anymore because the compilers already know what to inline and what to register. You can try forceinline if your compiler has this or you can brute force inline if a function won't do it with heuristics, but in most cases this is shooting yourself in the foot. Once in a while you are right and the compiler was wrong.

I dunno what you know but if you don't do blocks, your memory pool can fragment and become unmanageable.

I hate to say start over, but... start over.

Last edited on
Puh, very fast answer! As a non-native english-speaker, i need more time to write ;)

also inline and register are almost worthless anymore. You can time it or check the assembly


I'm hobby-progrmmer and use what i'm able to. I thought about lerning assembly (especially in this project), but i think this project is a bit too complex for beginnig...

I would personally let a static vector of bytes do the dirty work for you


Normally yes, but in this case not. I have a "plan", where i need exact what i do there:
What you see is a memory-mamagement to be used by my own interpreter, which will be a (almost) full programming-language intented to control OpenGL-Graphics and maybe later some CUDA functions. Therefore it is most important to store data in structurated memory-blocks, to be transferred to the graphic-engine at once.

Therefore i can't use stl-types and simelar things, whrere i don't have control about the exact data-management. For the graphic-engine it is the best to transfer ie. 3 floats (x,y,z), 4 chars (r,g,b,a) and 2 more floats (texture-x, texture-y) in thousends of repititons at once.
Assambley would be good in this case, but this is some "another project", to lern it. At first i want to know why my class works with char but not with other types of indices...

Best,
frank
Last edited on
vectors are assured to give you a block of memory. They just do the pointer work for you and you can treat them the same. But that is up to you.

You can still use a pointer of bytes.
look..

unsigned char*buffer = new unsigned char(10000);
struct blokx{int index, bool used};
blokx blocks[10];
for(int i = 0; i < 10; i++)
{
blocks[i].used = false;
blocks[i].index = i*128;
}

double * fp = (double*) (&buffer[blocks[3].index]);

the numbers don't add up (i didnt fill in all the blocks exactly and I didnt check for the next empty block before assigning one) but this is the core of what I think you want to do. Note that fp can be treated as an array of up to 128 bytes worth of doubles. If you need more you have to mark more blocks as used but then you can have 256.. etc contigious byte blocks that can be treated as doubles which can be treated as an array of doubles, etc. You can also put a class in a block, the type does not matter.

It is much harder to do this with other types (not single byte types). I didnt debug your code but I would suspect you have indexing or allocation problems due to this for the non-char types.
Last edited on
Hmmm...

I have the following (as atring):
1
2
3
4
5
6
7
8
9
10
    int x=7f; float b=0.5;
    float arr[97+3][13][25][2];
    arr=7;
    float abc = (66.6 + 2.1) * 1.1;    //test comment
    if (abc < 60) abc = 170; 
    else { abc = 340; }
    while (arr < 1000) {
        x += 1; arr += b; abc = 66.6; abc = (abc - 0.1) * 1.001;int y=987;
    } 
    int z=9996;//arr + 1;//abc=66.6;abc=(abc-0.1)*1.001;  

This is stored in clsMem. Then it is parsed and all the elements are also stored in clsMem. The code is executed correctly. The resuli is :
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Memory size:    	788072 / 819200 byte (used/allocated)
Reallocations:  	6
Active user:    	0

TYPES:
Blocks:			Total	 	Used	Free
      Total:    	 218	 	213	 	5
0:  1 bytes:      	1	 	1	 	0
1:  2 bytes:      	48	 	48	 	0
2:  4 bytes:      	123	 	123	 	0
3:  8 bytes:      	34	 	34	 	0
4:  16 bytes:      	4	 	3	 	1
5:  32 bytes:      	2	 	1	 	1
6:  64 bytes:      	1	 	0	 	1
7:  128 bytes:      	1	 	1	 	0
8:  256 bytes:      	1	 	1	 	0
18:  262144 bytes:      	3	 	1	 	2

NAMES:
-------------
0 (210: 8 byte): 	int 	x 	= 1993
1 (211: 8 byte): 	float 	b 	= 0.500000
2 (212: 262144 byte): 	float 	arr [65000] 	= 1000.000000, 1000.000000, ...
3 (213: 8 byte): 	float 	abc 	= 66.566505
4 (214: 8 byte): 	int 	z 	= 9996

(sorry for the strange beak, don't know why it's there...)

Up to here everything works fine and around 15 differen 'clsDynArray' containig different types are used, but only this one leeds to errors, if i change the type.

I thought i made mayby something obviously wrong, which i didn't saw, but it seems, that i have to check what exactly happens in memory...

Best,
Frank
Last edited on
I don't see the error either.
I think i found it - not the program-line yet, but now i have an idea what to search...

My interpreter reports:
1
2
3
4
5
6
7
8
ITEMS:
Id: User	Bytes	Offset	Type		Data
. . . 
212:  1	260000	1616	float		1000.000000, 1000.000000, 1000.000000, ...
213:  1	4		263760	float		66.566505
214:  1	4		263768	int		9996
215:  1	4		263776	int		987
216:  0	65000	263784	FREE		---
217:  0	65000	525928	FREE		---


So, your hint was not wrong: 260000bytes used by floats are 65000 x 4bytes, but "freed" were 65000 x 1byte. I think there is something like "(float*)xxx[n]" missing, so "(char*)xxx[n]" is applied by default. In consequence some memory seems to be overwritten by other functions which i had not posted. (I'll find out...)

Thank you at all!


Best,
Frank
Last edited on
good! That is why I was saying to deal with everything in bytes... you don't have to do that but its safer / easier to manage.

Yes, if you mess up your blocks one block can bleed into another and over-write data, and its legal because you are managing it not the OS so the violation is considered OK. There are times when you can exploit this, but I advise against it.

Registered users can post here. Sign in or register to post.