🔒 Locked

Container class questions

Started by Baiame Jul 24, 2007 at 10:43 PM 19 replies 1.5k views

Original Post

Jul 24, 2007 at 10:43 PM

Hello. I started writing a dynamic array class, mostly as a learning experience (but also for possible future use). As it's how Flavian Brebion is doing it for Infinity, I'm using the C memory management functions. I thank him for his assistance. So far it looks like this:

template <typename _type> class DynamicArray
{
public:
	DynamicArray<_type>(unsigned int reservedMemory = 0);
	~DynamicArray();
	void append(const _type& element);
	_type operator[](int params){return *(arrayLocation+params);};

protected:
	size_t objectSize;
	_type* arrayLocation;
	unsigned int maxSize;
	unsigned int numElements;
};

template <typename _type> DynamicArray<_type>::DynamicArray(unsigned int reservedMemory) : 
	objectSize(sizeof(_type)),
	arrayLocation((_type*) malloc(reservedMemory * objectSize)),
	maxSize(reservedMemory),
	numElements(0)
{}

template <typename _type> void DynamicArray< _type >::append(const _type& element)
{
	if(numElements >= maxSize)
	{
		arrayLocation = (_type*) realloc((void*)arrayLocation, (numElements+1)*objectSize); 
		maxSize+=1;
	}

	new(arrayLocation + numElements) _type(element);
	numElements++;
}

template <typename _type> DynamicArray<_type>::~DynamicArray()
{
	_type* arrayLocationCopy = arrayLocation;

	for(unsigned int x = 0; x < numElements; x++)
	{
		arrayLocationCopy->~_type();
		arrayLocationCopy++;
	};

	free(arrayLocation);
}

It's incomplete. Anyway, at first I couldn't figure out how to destruct elements; integral types don't require destruction (I think?) while objects do. I tried this on a whim:

~_type();

and it surprisingly compiled without error. Is that syntax correct? Also, if you have any suggestions based on what I've shown, please share them. There's relatively little information out there on writing container classes.

phil_t

Jul 24, 2007 at 10:56 PM

Yes, that's right - assuming you're using placement new, which you are.

For some reason, there have been a whole bunch of threads lately on people writing their own dynamic arrays. Scan down the thread list and you'll see them. At least one of them goes into this topic.

ToohrVyk

Jul 25, 2007 at 1:32 AM

Quote:
arrayLocation = (_type*) realloc((void*)arrayLocation, (numElements+1)*objectSize);

Do remember that realloc basically finds a new buffer in memory, forcefully copies the bytes from the old buffer to the new one without any regard for what the memory actually represents, then brutally frees the old buffer without any form of contents destruction. So, if _type is not a POD type, your container will simply stop working for mysterious reasons at the worst possible moment.

Rule: non-POD objects cannot be copied byte-by-byte, they must be initialized in the new buffer as copies of the objects in the old buffer, and the originals must then be destructed. There is simply no way to achieve this using realloc: you will have to malloc a new buffer, do the copy, do the destruction, and free the old one.

Baiame

Jul 25, 2007 at 2:07 PM

Quote:
Original post by phil_t
Yes, that's right - assuming you're using placement new, which you are.

For some reason, there have been a whole bunch of threads lately on people writing their own dynamic arrays. Scan down the thread list and you'll see them. At least one of them goes into this topic.

Ah, thanks for clearing that up, and informing me of the other topics. I'll have a look.

Quote:
Original post by ToohrVyk
Rule: non-POD objects cannot be copied byte-by-byte, they must be initialized in the new buffer as copies of the objects in the old buffer, and the originals must then be destructed. There is simply no way to achieve this using realloc: you will have to malloc a new buffer, do the copy, do the destruction, and free the old one.

Thanks. That's why I started this topic: something was bound to be wrong with my code.

However, that's not exactly what realloc() does, is it? If it can resize the memory block while retaining contiguity, it does (without affecting anything already in the block). So I guess I need to write a function that does either what you've described or realloc() as appropriate. Which necessitates a noob question. How do I check if a memory location is already allocated?

[Edited by - Baiame on July 25, 2007 3:07:02 PM]

Antheus

Jul 25, 2007 at 2:18 PM

Quote:
However, that's not exactly what realloc() does, is it? If it can resize the memory block while retaining contiguity, it does (without affecting anything already in the block). So I guess I need to write a function that does either what you've described or realloc() as appropriate. Which necessitates a noob question. How do I check if a memory location is already allocated?

Let's not go there.

Where and how memory is allocated is unknown - it's not specified or standardized - the compiler writers looked into it, and made it work on given platform. It has also received a lot of review (every application ever written) and works most of the time. But, what may work on XP Pro SP2 on AMD can break Vista, on Intel processor, or under gcc. There are zero guarantees, except what documentation for new states - it allocates a chunk of memory, or throws bad_alloc.

You have exactly two options for managing memory:
1) Pre-allocate buffer, then override new to provide pointers from there
2) Let new allocate it

That's it. malloc/realloc are bad. Unless you're overriding global new handler, you really really don't want to mess with them.

PS. 1) would be the option that allows you to check if area of memory is already allocated, since you'd be allocating chunks by yourself.

Your allocation code must also respect data alignment, so you'll need to possible over-allocate by 16 bytes to be able to align the memory on a boundary (and even that is considered a hack, since it can theoretically fail)

ToohrVyk

Jul 25, 2007 at 2:31 PM

Quote:
Original post by Baiame
However, that's not exactly what realloc() does, is it? If it can resize the memory block while retaining contiguity, it does (without affecting anything already in the block). So I guess I need to write a function that does either what you've described or realloc() as appropriate. Which necessitates a noob question. How do I check if a memory location is already allocated?

You can't know whether realloc can resize the buffer without moving its contents or not before you actually call the function. So, if your container contains non-POD objects, you have to move the contents of the buffer to a temporary buffer before calling realloc (just in case it moves the buffer), which kind of defeats the purpose. C++ provides no standard equivalent of realloc.

In short: have your generic class allocate-copy-destruct-deallocate, and then specialize your class for known POD types (int et al) to use realloc.

Baiame

Jul 25, 2007 at 3:34 PM

Quote:
Original post by Antheus
Where and how memory is allocated is unknown...

I thought that allocation checks would be more standardized. Can you please point to a couple ways of doing it? Overriding the new operator seems a bit excessive at this stage.

Quote:
Original post by Antheus
Your allocation code must also respect data alignment, so you'll need to possible over-allocate by 16 bytes to be able to align the memory on a boundary (and even that is considered a hack, since it can theoretically fail)

I had read about memory alignment, and I'll take it into account.

Quote:
Original post by ToohrVyk
You can't know whether realloc can resize the buffer without moving its contents or not before you actually call the function.

I know. But realloc() obviously does some kind of checks for memory occupation- that's what I want to do. Of course the program would end up basically doing the same thing twice, but it'd still be far faster than copying each element to a new buffer every time the array resizes. Flavian pointed to faster resizing as one of the advantages of his dynamic array over the STL vector (he definitely achieved it using realloc() in some way, but I'm not sure whether he overrided new).

ToohrVyk

Jul 25, 2007 at 3:45 PM

Quote:
I know. But realloc() obviously does some kind of checks for memory occupation- that's what I want to do.

All the checks are internal to the library. realloc from a given standard C library implementation knows whether memory is occupied or not because that memory was allocated and handled by that very same library implementation. If you were to use realloc from a different implementation, it just wouldn't work, because it relies on implementation-specific helper functions. Since your program is not a part of the standard library, it can only use the public parts of it.

Even worse, the C++ memory models involves contiguous buffers. It has no concept of "memory being available past the end of a buffer". So, not only do the libraries not provide this checking functionality, but it is explicitly described as non-portable by the standard.

Quote:
Of course the program would end up basically doing the same thing twice, but it'd still be far faster than copying each element to a new buffer every time the array resizes. Flavian pointed to faster resizing as one of the advantages of his dynamic array over the STL vector (he definitely achieved it using realloc() in some way, but I'm not sure whether he overrided new).

Sadly, you have no choice here: if you wish to use a realloc-like feature with non-POD objects (POD objects, again, are a breeze), you will have to keep track of memory yourself, by allocating a very large buffer from the OS or library, and then using this buffer to allocate sub-buffers to the rest of your program.

rip-off

Jul 25, 2007 at 4:12 PM

By over-allocating and using placement new, you are already implementing what realloc tries to do, the only difference is you reserve the memory forever so you are guaranteed that after a reallocation you will have to add lots more elements before another reallocation occurs.

Antheus

Jul 25, 2007 at 4:16 PM

Quote:
I know. But realloc() obviously does some kind of checks for memory occupation- that's what I want to do. Of course the program would end up basically doing the same thing twice, but it'd still be far faster than copying each element to a new buffer every time the array resizes. Flavian pointed to faster resizing as one of the advantages of his dynamic array over the STL vector (he definitely achieved it using realloc() in some way, but I'm not sure whether he overrided new).

Always read the whole story:

Quoted from googled reference:

(POD types only):

Quote:
Now it sounds obvious, but when I allocated memory in my CArray class, I used malloc/realloc/free, and there's no object constructor/destruction with those. I didn't have much trouble so far because as soon as my classes start to become complex, I prefer to store pointers to them. But every once in a while, I store an object itself, and that's where leaks and bugs appear.

(use standard library):

Quote:
Second lesson learnt: the std::vector class is not slow. It is bug-free ( unlike mine ), and performs pretty much as fast.

(Copying is where you lose time, not re-allocating - also, constructors/destructors must be called)

Quote:
The first one being: using malloc/realloc avoids the copy/fill mechanism used in std::vector, meaning no construction/destructions needed when the array grows. A first good point for me. Of course, this time I had to take care of correctly constructing/destructing objects, meaning playing with "placement new" and other goodies.. but no big deal.

Final lesson:

Quote:
After this, I benchmarked my classes: the old ( buggy ) one, std::vector, and my new CArray class. Verdict: std::vector and my old class are on par as far as performance goes, but my new CArray class, in the context of appending millions of elements, is in average 2 to 3.5 times faster ! So I haven't wasted my time, finally.

Quote:
Another good point: because I knew what is the most frequent usage I'm doing in my engine of my CArray class ( namely, appending data ), I could optimize the case and even create a special interface to append many elements to the array. I called this the "beginAppend/doAppend/endAppend" mechanism.

USE STANDARD LIBRARY, unless you're solving a particular, non-standard behaviour.

malloc/realloc are secondary in this story - it's different allocation strategy for batch additions that makes things fast - it also uses special interface - std::vector's performance is irrelevant, and couldn't be improved, only understanding of the problem solved helped.

You could achieve that with an accessor to std::vector, that would batch additions, and submit them to std::vector as a batch, after calling resize (or reserve, I forget).

Baiame

Jul 25, 2007 at 8:31 PM

Quote:
Original post by ToohrVyk
All the checks are internal to the library.

I didn't know there was no public interface for that. Guess that's out of the question.

Quote:
Original post by rip-off
By over-allocating and using placement new, you are already implementing what realloc tries to do, the only difference is you reserve the memory forever so you are guaranteed that after a reallocation you will have to add lots more elements before another reallocation occurs.

Quote:
Original post by ToohrVyk
Sadly, you have no choice here: if you wish to use a realloc-like feature with non-POD objects (POD objects, again, are a breeze), you will have to keep track of memory yourself, by allocating a very large buffer from the OS or library, and then using this buffer to allocate sub-buffers to the rest of your program.

Well, I might do it eventually, but not right now.

Quote:
Original post by Antheus
Always read the whole story: ...

It was that dev journal that inspired me to write a dynamic array in the first place. I read it thoroughly, several times, and I even consulted with Flavian on it for clarification. I've read the whole story and more.

Quote:
Original post by Antheus
USE STANDARD LIBRARY, unless you're solving a particular, non-standard behaviour.

I was expecting someone to say that. As I said, I'm doing this primarily as a learning experience. In all likelyhood I'll end up using std::vector. Even if I was writing the class for actual use, I would obviously have fully considered std::vector.

Anyway, I think I figured it out. free() only allows memory to be re-allocated; it doesn't actually change its contents. So you can check whether the pointers before and after realloc() are the same. If they are, you do nothing (the block was resized); if they're not, you still have all the data available for copying. In the latter case, you can subsequently destroy the objects stored in the deallocated memory. At least that's the theory. Might be a bit too hackish for actual use. I'm also uncertain of whether realloc() calls free() or does the same operation; if not, it wouldn't work at all.

EDIT- Okay, it won't work. Though all the tests I did had the expected output when run from within the IDE, they don't when run externally. This'd be really easy if realloc() didn't free the old memory.

EDIT 2- Under what kind of circumstances does realloc() with a memory block (including memory access after realloc) storing non-POD objects fail? I just tried it in MSVC++ 2005, and it worked perfectly.

[Edited by - Baiame on July 26, 2007 12:31:25 AM]

ToohrVyk

Jul 26, 2007 at 1:11 AM

Quote:
Original post by Baiame
Anyway, I think I figured it out. free() only allows memory to be re-allocated; it doesn't actually change its contents.

No. free() does not allow memory to be re-allocated. free() destroys the memory, it's gone, disappeared, vaporized, annihilated, nothing. Memory you release with free() doesn't even have any contents anymore, so wondering whether its contents remain the same is nonsense: the memory doesn't exist anymore, its contents don't exist anymore, there is no possibility for something that doesn't exist to remain the same.

Quote:
if they're not, you still have all the data available for copying.

No, you don't. When you call realloc(), the old buffer is annihilated and a pointer to a new buffer (with the correct size and the correct initial segment) is returned. The value of the pointer that was passed in becomes invalid, so using it in any way (this includes dereferencing it, adding an offset to it or, yes, comparing it with the returned pointer) results in undefined behaviour, which may well give you results that are the opposite of what you expect.

You seem to rely on undefined behaviour too much. This is a very bad idea because:

You don't know how these things work behind the scenes.
Even if you did, that knowledge would be restricted to a given compiler and library and hardware, and thus non-portable and subject to change.
You will tend to mix up guaranteed, safe and sane behaviour with lucky shots that happened to work on your compiler and library and hardware.

Quote:
EDIT 2- Under what kind of circumstances does realloc() with a memory block (including memory access after realloc) storing non-POD objects fail? I just tried it in MSVC++ 2005, and it worked perfectly.

This is known as undefined behaviour. The answer is, it will fail at the worst possible moment. Possibly when you publish a new version of your game demo without keeping the previous one around, or during your monthly code review at your company. It will quite possibly also involve murderous axe-wielding neurotic peer reviewers of your code spontaneously knocking at your door after midnight.

Zahlman

Jul 26, 2007 at 4:15 PM

Quote:
Original post by ToohrVyk
Even if you did, that knowledge would be restricted to a given compiler and library and hardware

And in some cases, there is still no knowledge, because another running process could claim the memory you freed and do as it likes with it.

Baiame

Jul 26, 2007 at 7:03 PM

Quote:
Original post by ToohrVykNo. free() does not allow memory to be re-allocated.

Do you mean to say that free() doesn't leave the memory up for grabs to other parts of the program or other programs?

Anyway, I'm aware of all that now. What I described were the then-apparent properties of free(), but it must've just been some assertion(s) that VS2005 made. I won't use non-POD types with realloc (I'd consider it if it only failed under few circumstances, but I suppose it's too hard to even know those circumstances).

I've been thinking of another issue with dynamic arrays: insertion and deletion. Deletion of any element is obviously necessary for an array storing game entities. But due to the need for contiguity, it requires a (potentially) ridiculous amount of copying. How about a dynamic array of pointers to elements? The only thing that would need resizing would be the array itself, which would obviously store a POD type, so you could use C memory management functions. The stored objects themselves could be anywhere. Might be an opportunity to make something that's actually useful. What's such a data structure called?

Antheus

Jul 26, 2007 at 7:11 PM

Quote:
I've been thinking of another issue with dynamic arrays: insertion and deletion. Deletion of any element is obviously necessary for an array storing game entities. But due to the need for contiguity, it requires a (potentially) ridiculous amount of copying. How about a dynamic array of pointers to elements? The only thing that would need resizing would be the array itself, which would obviously store a POD type, so you could use C memory management functions. The stored objects themselves could be anywhere. Might be an opportunity to make something that's actually useful. What's such a data structure called?

Pre-allocated free lists.

Those maintain memory contiguity as well. Allocating objects will fragment the heap, so storing only pointers didn't win you much, the fragmentation is now merely handled by the OS.

C-style management brings no benefit. New calls malloc, and if needed, invokes a constructor. That's it.

With memory management there's always trade-offs. Custom free lists above are trivially implemented with standard classes with zero performance loss, but complete type safety.

Baiame

Jul 26, 2007 at 8:27 PM

Quote:
Original post by Antheus
C-style management brings no benefit. New calls malloc, and if needed, invokes a constructor. That's it.

Well, you have realloc(), which is faster than always allocating a new buffer and doing a per-element copy. I just meant that resizing/insertion/deletion of the dynamic array holding pointers would be fast.

Quote:
Original post by Antheus
Allocating objects will fragment the heap, so storing only pointers didn't win you much, the fragmentation is now merely handled by the OS.

Thanks for pointing that out, didn't think of that (haven't actually thought about the problem of heap fragmentation before). Is there any chance that the OS handles fragmentation fast enough such that a "pre-allocated free list" is worth it for situations where fast insertion, deletion, and random access are needed?

I guess the problem of insertion/deletion in a game context isn't so bad; you probably only need to insert at the end of the array, and objects that are frequently destroyed will generally be towards the end of the array.

Antheus

Jul 26, 2007 at 8:38 PM

Quote:
Is there any chance that the OS handles fragmentation fast enough such that a "pre-allocated free list" is worth it for situations where fast insertion, deletion, and random access are needed?

It's so bad, that most console titles statically allocate memory chunks, and don't let OS allocate a single byte.

OS and compiler give you zero guarantee. Even about realloc. No ifs or buts.

To get full control over allocations, full control over fragmentation, and fastest possible, yet still C++-standard compliant allocations, look into memory block managers and custom allocators. The later are the least of two evils, since they allow you to use standard library, which is, for all practical purposes, optimal.

For general purpose random allocations of large amount of objects, they'll outperform new by a factor of 2. For special cases this will go as high as factor of 50 (PPT) compared to standard containers.

The "only" downside is, that your allocations can now fail if you exhaust such pre-allocated pools.

C++ language can only be pushed a tiny bit over standard library. But applying domain knowledge of the problem (number of allocations, pattern, sequence, count, ...) can help you increase this into almost absurd rates.

Just keep in mind that this isn't a silver bullet. It's more like a suicide bullet, since the pitfalls that arise from that, both from design as well as implementation perspective are huge. Only do this as a last resort.

Baiame

Jul 27, 2007 at 1:11 PM

Quote:
Original post by Antheus
It's so bad, that most console titles statically allocate memory chunks, and don't let OS allocate a single byte.

Ah. That's a shame.

Quote:
Original post by Antheus
To get full control over allocations, full control over fragmentation, and fastest possible, yet still C++-standard compliant allocations, look into memory block managers and custom allocators. The later are the least of two evils, since they allow you to use standard library, which is, for all practical purposes, optimal.

I'll read about them eventually, but I think that's a learning experience for another day. My humble dynamic array has served its purpose. Thanks everyone.

Baiame

Jul 29, 2007 at 12:50 AM

Quote:
Original post by Baiame
My humble dynamic array has served its purpose.

Or HAS it?

I was bored and decided to try making a good dynamic array for storage of pointers to objects and/or integral types only. It's pretty much the same as the last but with loads of functions added (fast append, insert, fast insert, replace, resize, trim, and functions to get the current and reserved numbers of elements so far). But I'm getting a bit confused now. Usage would obviously be something like:
dynArrayInstance.append(new SomeClass);

Which is all well and good if the array is of SomeClass* type. But what about destruction? This is how the elements are destroyed now:

_type* arrayLocationCopy = arrayLocation;	for(unsigned int x = 0; x < numElements; x++)	{		arrayLocationCopy->~_type(); //INVESTIGATE		arrayLocationCopy++;	};

Considering that arrayLocationCopy is a pointer to _type, and that _type is SomeClass*, doesn't arrayLocationCopy->~type() only destroy the SomeClass* pointer and not the value pointed to by the pointer? Am I right in thinking that:

*arrayLocationCopy->~_type();

is correct? Of course, that wouldn't work if _type was an integral type. Is there any compile-time conditionals I can use to ensure that if _type is a pointer, the above line is compiled?

Secondly, considering that the class will only ever store pointers and/or integral types, can't I skip past destruction of array members entirely (and just overwrite/free/whatever them directly)?

Zahlman

Jul 29, 2007 at 1:22 AM

Your array didn't allocate any of the pointed-at things; it only allocated space for the pointers. So it should only clean up after the pointers, and should only deallocate the space used for the pointers. The pointed-at things are the user's responsibility.

std::vector works this way also.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.