C / C++ / MFC

8-Apr-02 22:26

I have a program where the user creates a list of objects:

class MyObject{
char name[32];
double m_FixedVariables[FIXED_SIZE];
double* m_VarVector1;
duble* m_VarVector2;
};

I have created a separate heap for all these objects using HeapCreate. The two variable vectors have the same size, but the user may add or delete elements. I have created a separate block of memory for the vectors with VirtualAlloc, and a scheme where I expand or shrink this block as needed using MEM_RESERVE, MEM_COMMIT, etc. To me this seems very compact and efficient, but all you gurus will say that I should use std::vector instead. Otherwise, I will sooner or later run into trouble ("Arrays are evil!").But I have no idea how the memory allocation will work with std::vector, will the heap management be as efficient?

Christian Graus8-Apr-02 23:21

Christian Graus

8-Apr-02 23:21

Vector impliments a grow policy so that it can limit the number of times it needs to recreate itself. It is unlikely to be as efficient as the custom code you are writing.

If you need this level of efficiency, I'd advise to write your own container so that it exposes random access iterators, so you can copy between it and STL containers, and use the provided algorithms, use it with streams, etc.

A pointer is a random access iterator, so it's not much harder than providing begin() and end() methods.

Christian

The tragedy of cyberspace - that so much can travel so far, and yet mean so little.

"I'm somewhat suspicious of STL though. My (test,experimental) program worked first time. Whats that all about??!?!
- Jon Hulatt, 22/3/2002

Haakon S.9-Apr-02 0:20

9-Apr-02 0:20

Thank, you Christian. I take your reply as an encouragement, not a warning. I will toddle along the path I have choosen for a little longer and see where it takes me. The vectors will be around as a fallback.

Regards, Haakon.

Joao Vaz9-Apr-02 1:07

9-Apr-02 1:07

The containers in STL normally implement a allocation strategie of 2*n elements, so if you request for instance 24 elements the vector will allocate space for 48 elem +/- , this is for performance reasons, since pre-allocating memory it's more cheap than allocating the memory one step at the time. But the normal allocator strategy is slow when you are always allocating small objects on the heap, then if this is your case perhaps you need a custom block allocator, this is tricky business. For a good book explaining custom allocators and their use with STL, I advise you to buy Modern C++ Design by Andrei Alexandrescu , it's a great book and it have a full chapter explaining the allocator philosophy on STL and the implementation of a custom allocator for efficient use with small objects on the heap.
Check his site: http://www.moderncppdesign.com

and the source code of Loki(c++ advanced library), that includes the custom allocator, a note here, VC6++ neither VS. NET fully compiles this library due to lack of support of pts(partial template specialization), The sp1 of VS.net will compile this Smile | :)

loki source code

Cheers,

Joao Vaz

Haakon S.9-Apr-02 1:50

9-Apr-02 1:50

Thank you for your advice, Joao.

Maybe I will buy the book. However, you say that custom block allocators are tricky. It appears to me that if I do my own allocation/reallocation I'm in full control. I don't do very fancy stuff on my variable arrays (e.g. sorting), it is mostly sequential access. But I do a very large number of iterative calculations on them, and I have a vague idea that if I keep my memory compact I keep these calculations run faster. The routine must constantly load new elements into the cache for computing, and the elements should therefore contain no dead meat. (Is this rubbish, or..?)For the same reason I will probably use CString (4 bytes long) instead of char m_name[32], but from where will the memory be allocated for the contents of the CString? My heap created with HeapCreate, or the default process heap? Is <string> any better?

There are certainly a very large number of difficult choises to make for us poor beginners....

Regards, Haakon Confused | :confused:

Joao Vaz9-Apr-02 3:48

9-Apr-02 3:48

Haakon, CString is a MFC class , not a STL class, in STL we have the string template class.

The CString class internally will by default allocate the memory by a factor of 2, and internally maintains lists(not sure how many) of memory blocks , it controls the used memory blocks and unused memory blocks,
it guards the size and the nº of slots available for allocating in the used slots due to requests of different sizes, then when we ask to allocate something, it will search for the best size match on the slots, if it finds it uses the slot, if not it will request a unused block from another list and will allocate accordingly. This algorithm is used to prevent to minime memory fragmentation and improve allocattion time. A proper and much more correct and accurate explanation of this is on MFC Internals.

The stl string implememention is faster than the mfc counterpart, and it uses similar(or more complex) algorithms.

For articles talking about allocators check this articles, both from by Matt Austern, the chair of the C++ standardization committee’s library working group.

1º The Standard Librarian: What Are Allocators Good For?

2º
The Standard Librarian: A Debugging Allocator

After reading this, perhaps you will feel the wish for not doing custom allocators ...

A note, implementing a block allocator for vector it's more tricky, because the standars mandates that the elements can be accessed on contiguous memory blocks .

ex:

vector<100> x;
while (...) { doSomething(&v[i++]); }

For other example of custom block allocator see here at CodeProject
A Custom Block Allocator for Speeding Up VC++ STL
By Joaquín M López Muñoz

As a sidenote this allocator don't work with vector neither deque(this containers allocates chunks like I tried to explaining).

Cheers,

Joao Vaz

Tim Smith9-Apr-02 4:10

Tim Smith

9-Apr-02 4:10

Damn...

I am a bit shocked that the STL list, map, and sets don't allocate nodes in buckets. Not only do you increase allocation performance, you increase memory performance by reducing the number of page faults. The theory being that when the map nodes are allocated in buckets, you greatly reduce the chance that the nodes are spread out all over the memory address space.

Tim Smith

I know what you're thinking punk, you're thinking did he spell check this document? Well, to tell you the truth I kinda forgot myself in all this excitement. But being this here's CodeProject, the most powerful forums in the world and would blow your head clean off, you've got to ask yourself one question, Do I feel lucky? Well do ya punk?

Joao Vaz9-Apr-02 4:49

9-Apr-02 4:49

Tim Smith wrote:
you greatly reduce the chance that the nodes are spread out all over the memory address space.

Yeap, it's true, but for that you have hash_map and other hash* that will included on the next standard and normally every STL library that I'm aware provides some sort of hash counterparts.
Of course it's a pitty, because of the lack of time the hash implementations didn't went incorporated on the standard Cry | :((

, but oh well, for this, we have the possibility of breaking our heads with custom allocators. It's a shame that typedef templates don't exist on standard, because it's very ugly to deal with the rebind template hack for simulating a typedef template Mad | :mad:

used in constructing a custom allocator ... Even after reading several times the chapter of Effective STL on allocators and Modern C++ Design, I fell nauseous(spelled correctly ?) ...
Frown | :(

Sometimes I wish the STL could be made more simpler ...

Cheers,

Joao Vaz

Haakon S.9-Apr-02 8:17

9-Apr-02 8:17

Thank you, Joao.

I appreciate your help and will carefully read the articles you refer to, and try to figure out about allocators. Forget the spell checker, it's the content that matters. You come out clear and precise!

(In my previous reply I mentioned stl::string as an alternative to CString, but I enclosed it in brackets - that made it disappear from the text!)

Regards, Haakon.

Smile | :)

Joao Vaz9-Apr-02 9:56

9-Apr-02 9:56

Haakon S. wrote:
Forget the spell checker

90% of the time I use it, now the others 10% are a complete disgrace Dead | X|

Sorry for the errors Cry | :((

, sometimes I write so fast and don't check my poor english Mad | :mad:

Damn it, damn it ...

Okay, have fun reading the articles Smile | :)

Joao Vaz

Tim Smith9-Apr-02 8:44

Tim Smith

9-Apr-02 8:44

Using buckets in maps really has nothing to do with hash. It is just a standard optimization. It really comes into play more when your maps are stored on disk. But, the same still holds true for memory maps.

Tim Smith

I know what you're thinking punk, you're thinking did he spell check this document? Well, to tell you the truth I kinda forgot myself in all this excitement. But being this here's CodeProject, the most powerful forums in the world and would blow your head clean off, you've got to ask yourself one question, Do I feel lucky? Well do ya punk?

Joao Vaz9-Apr-02 10:03