Dynamic memory using "new" and malloc()

First off there are no rules on how malloc() and free() have to be implemented. I've replaced them numerous times when I didn't like their performance for some piece of code I was working on. Beyond that, there is also the specific std::vector implementation to contend with, and also there is hardware caching and stuff like that. In general if you aren't growing a vector a lot, it's access time will probably be pretty consistent. But that again depends on how you are accessing the elements. If you run though them in order that will most likely be faster than jumping around randomly because of hardware caching. That doesn't really have much to do with allocation however.

I don't really use std::vector myself except for trivial stuff because I like to have control over exactly what's going on. I rarely even use the standard malloc/new and free/delete anymore for the same reasons. If you know how you are going to use the heap, you can almost always beat the standard routines by replacing them. Depends on what you are writing though. It might not be worth it for a lot of applications.

std::vector memory is guaranteed to be contiguous and accessing it in order is the best possible thing. It doesn't matter which allocator the memory came from, it will be contiguous.

Accessing any memory in order is cache-friendly and the best possible thing to do.

What @ryt is interested about, possibly, is that allocating and deallocating memory in random order, using any allocator, creates fragmentation. After some time, unless you take measures, you might be left with many 'holes' which add up to a lot of overall available space, but you won't be able to put your big contiguous array (vector) there at all.

I wanna add that Gnollrunner is right. BUT. You really, really shouldn't go into optimising your structures and allocators, unless you first MEASURE that you suffer from their performance. That goes for any premature optimisation :)

On 11/15/2018 at 4:52 PM, pcmaster said:

What @ryt is interested about, possibly, is that allocating and deallocating memory in random order, using any allocator, creates fragmentation. After some time, unless you take measures, you might be left with many 'holes' which add up to a lot of overall available space, but you won't be able to put your big contiguous array (vector) there at all.

I'm just curious how standard implementations of new and malloc() work. Do they use continuous memory allocation or something else?
Because as you sad the memory could end up fragmented and we could arrive at the case where we have enough free memory but not a block (with continuous memory) big enough that we can use another new. In this case we would have to resort to some other implementation that does not use continuous memory and therefore not an O(1).

There can be no resorting to anything, the promise of contiguity shall not be broken - if you demand a block, you're guaranteed to get a block or nothing.

Imagine that the pool administred by an allocator is 16B and the granularity is 1B with zero overhead (totally fine for our demonstration). You allocate eight times 2B. All is good. Then you deallocate every other allocation you got. All is good, there's 8B free. Yet, when you now try to allocate 4B, the allocation shall fail and you get nothing. It is THAT simple.

9 hours ago, ryt said:

resort to some other implementation that does not use continuous memory

Allocators either garbage collect and compact the heap (in garbage collecting runtimes), ask the OS for more memory to expand the heap (ex: VirtualAlloc), return null, throw an exception, or produce some other type of error.

Successfully allocated memory is ALWAYS contiguous from the perspective of the program (code assumes that data structures are always arranged the same way). However, protected mode virtual memory allows the addresses that the program uses to map to different actual physical RAM (or even hard drives)

9 hours ago, ryt said:

I'm just curious how standard implementations of new and malloc() work. Do they use continuous memory allocation or something else?
Because as you sad the memory could end up fragmented and we could arrive at the case where we have enough free memory but not a block (with continuous memory) big enough that we can use another new. In this case we would have to resort to some other implementation that does not use continuous memory and therefore not an O(1).

First off, again there is no "standard implementation" only standard behavior. However there are probably some commonality between implementations.

You can imagine memory being an unused paper tape. When you allocate something you draw a line on it. From the begging of the tape to the line is what you allocated. Now if you allocate again draw a line after the first one. That chunk is from the first line to the second line and so forth. But now if de-allocate something you might have a space in the middle that's unused. However it's only the size of the piece of memory that you previously allocated there. It's up to the memory manager to figure out what to do with it. It has to save it somehow so if you allocate new piece of memory that is smaller than that space it can give that piece back to you. However let's say all your following allocations are all bigger than that space. In that case it will never be reused and you have a hole.

Now it can get even more complex. Let's say you allocate a piece of memory smaller than that space, so it gets reused. But it's slightly smaller, so a sub-piece of memory that's not big enough to be useful for anything is left over at the end. So now you have a sliver of lost memory. So this is where the memory manager comes in. It might think in advance that this situation is sub-optimal and try to give you a different chunk of memory instead.

Then there is the situation where you de-allocate two chunks of memory next to each other. The allocator has to be smart enough to merge them into a bigger chunk. There are really a lot of variables. That's why there are a lot of implementations.

Years ago I worked on IBM workstations. Someone brought a program to me and said it was crashing on exit or rather it would go into and infinite loop. After debugging it for a while. I found that it got stuck in the memory deallocator. But it did eventually end after 10 minutes. He was allocating millions of tiny objects. On a hunch I simply replaced mallaoc/free with my own routines and boom, it fixed the problem. The standard implementation was simply way sub-optimal for his particular memory usage model.

In general for a lot of things I use slab allocators. You can read up on them. But again they aren't good for everything. It all depends on what you are doing. For a lot of gaming stuff, some form of slab allocation probably works pretty well though. They are basically good where you have a lot of objects of similar size, or objects can be categorized in groups of similar sizes. Strings are it's downfall but you can do a different heaps for those. I use a lot "placement new" in C++ to allocate in different heaps. You can read up on that too. Over the years I have built up a big library of different heap libraries. I try to pic the ones that best suit my job.

If you are really trying to optimize memory, there is a lot you can do, but you should try to figure out if it's an issue first. For many people the built in routines work well enough.

On 11/15/2018 at 2:59 PM, ryt said:

If this is true than accessing such memory (through []) would not have access time of O(1) but some other, more complex.

This isn't true at all because accessing through the []-operator is just convinience. What the compiler in the background does (normally) is to move the base pointer by certain ammount of bytes and return the result. Accessing an element in a plain array of integer simply is

int* myArray = new int[20];

//int x = myArray[7] ->
int x = *(myArray + (sizeof(int) * 7));

delete[] myArray;

What I learned during study was that the OS maintains a list of memory chunks when you delete something. Any new allocation request is then passed through the list of returned chunks so if something matching is found, an allocation will return that chunk or at least a new piece of it. This is the reason why memory fragmentation occures more and more the longer a program runs.

I used to force run my own memory management and allocator classes whenever possible, also as @Gnollrunner wrote in his first post, use my own STL like container classes. I wrote Array (dynamic resizing), Vector (dynamic add/remove), Stack, Queue, HashTable, Map and whatever I used to need in my code. All of these are based on Array because what you get when allocating memory using the API features of C/C++ is a block of memory of certain size. Malloc isn't interested in the kind of cobject you want to place in there except for its size on the platform.

What I do when allocating memory for an array of integers is to calculate the padded size of the type and multiply this with the ammount of elements I want to place inside memory.

In C/C++ it is a mighty tool to shift pointers left or right some bytes, this can result in a much better performance.

While C/C++ dosen't has any garbage collection (SmartPtr dosen't count because it just deletes it's contents on leaving scope) this is the reason for the ammount of garbage collection libs out in the wild. Games heavy rely on good memory management because they do even more allocation/deallocation than a normal office program does.

There are some models how memory management and garbage collection work. One approach is for example to put ranges of memory in buckets of different size so you know when allocating an integer, it will always stay in a heap reagion whos size wont exceed certain limit while an other approach is to return smart pointer objects instead of plain ones so on garbage collection there is a chance to move objects arround in memory without causing data corruption on access

The simple answer is yes.

Although there are no "standard" implementations, dynamic memory allocation and de-allocation is non-deterministic, and the only way to map a contiguous memory address space into non-deterministic allocations and de-allocations is to use something like a linked list or a mark-and-sweep algorithm (or some other non-O(1) strategy).

Even more fraught is that a single central memory allocator on a multi-threaded multi-processor environment (and they all are these days, even your toaster) you can one big lock to slow things down further.

If profiling reveals that memory allocation is an issue, the strategy is generally to allocate all memory up front on startup and never use the central system allocator again. This is the norm in real time and embedded systems where the vagaries of malloc() can not be tolerated, and has become standard practice in many games for the same reason.

4 hours ago, Bregma said:

If profiling reveals that memory allocation is an issue, the strategy is generally to allocate all memory up front on startup and never use the central system allocator again.

For most stuff just allocating in chunks is fine. With reasonable sized chunks the amount of CPU time you are going to save allocating everything up front is probably negligible. This is especially true with 64 bit machines where you have a lot of address space available. You can reserve a huge chunk of address space up front, and then actually add the memory in as you need it without having to predict ahead of time how much memory you will actually end up using.

As @Nypyren has sad that that memory is ALWAYS continuously allocated from program perspective and as @Shaarigan showed that with pointer arithmetic we can always access direct memory with a just pointer addition, it seems that it should always be valid something like

*(myArray + (sizeof(int) * 7));

Further, it seems a bit odd that a OS would take this array, put it in a non-continuous memory and pay attention to return us myArray[7] from some other memory other than the one located at *[7] (it sounds that this could be really CPU expensive)!
Also, when we compile a C++ program, it gets compiled to a binary file with CPU instructions, which work with "real" addresses, so it should point to [7].

On the other hand, as @Bregma and others have mentioned, that this is non-deterministic and that a container with internal pointers to other elements could be used (which could store array objects anywhere, not continuously), like a linked-list.

This leaves me a bit more confused. I always thought that *(myArray + 7) should increase memory address by 7 and return the result from there. But if new() did not store it in a continuous block in the first place, than this should not be possible or there is some other code (OS) that handles this arithmetic.

All I was interested is how malloc()/new() do it? Is it more a OS specific side or do they have the control? What if there is no OS and we program in C++, how would malloc/new then behave for array allocation?

Quote

Further, it seems a bit odd that a OS would take this array, put it in a non-continuous memory and pay attention to return us myArray[7] from some other memory other than the one located at *[7] (it sounds that this could be really CPU expensive)!

Are you talking about virtual memory?

Quote

I always thought that *(myArray + 7) should increase memory address by 7 and return the result from there.

It does.

Quote

But if new() did not store it in a continuous block in the first place, than this should not be possible or there is some other code (OS) that handles this arithmetic. 

As far as you're concerned the memory that malloc() and new return *is* contiguous. Sure, there's probably some virtual memory fun happening behind the scenes, but that's probably not something you need to worry about too much. As far as your code is concerned new and malloc() *always* return contiguous blocks of memory.

Quote

What if there is no OS and we program in C++, how would malloc/new then behave for array allocation? 

Without an OS there would be no virtual memory system in the way, or *any* memory management system for that matter. You could directly access physical memory without even bothering to allocate it.

I think @ryt is perhaps confusing a single allocation returned from malloc(), and how the system memory allocator manages groups of allocations. When you call malloc, the pointer you get back is a contiguous chunk of memory of size (however much you requested). This memory isn't chunked nor does it exist at multiple locations in 'actual' memory (ignoring funniness with virtual memory).

When you free this memory back to the system, the system allocator can manage this chunk however it sees fit - this entire chunk might be kept track of in a linked-list, or may be part of a pool of similarly-sized chunks, etc.

12 hours ago, ryt said:

myArray[7]

Is just the short form of

*(myArray + (sizeof(TYPE) * offset))

as the array accessor is implemented as an opperator. C++ nor C don't know anything about what an array is except some convinience functions build into the compiler. An array and a pointer to a block of memory are in fact the same, a range of bytes in RAM so one won't need to worry about any difference in terminology

9 hours ago, Shaarigan said:

Is just the short form of

*(myArray + (sizeof(TYPE) * offset))

as the array accessor is implemented as an opperator.

Actually myArray[offset] is the same *(myArray + offset), without the sizeof, because both array indexing and pointer arithmetic already operate on units of sizeof(TYPE).

9 hours ago, Shaarigan said:

*(myArray + (sizeof(TYPE) * offset))

C++ nor C don't know anything about what an array is except some convinience functions build into the compiler. An array and a pointer to a block of memory are in fact the same, a range of bytes in RAM so one won't need to worry about any difference in terminology

This is not true at all. An array holds data. A pointer points to data that is held elsewhere - either in another variable or on the heap. You can verify this with the sizeof operator: sizeof(someArray) is the number of array elements times the size of each element, whereas sizeof(somePointer) is either 4 or 8 depending on whether you compile for 32 bit mode or 64 bit mode.

It is true that an array value (i.e. an array variable) "decays" into a pointer in some contexts, but there are things you can do with arrays that you can't do with pointers. For example, you can call this function on an array but not a pointer:

template<class T, std::size_t N> constexpr std::size_t array_size(T(&)[N]) {
  return N;
}

21 hours ago, BradDaBug said:

Are you talking about virtual memory?

Nope, this would be more from a OS standpoint. I'm just interested from a program perspective and if I can Always relay that it's a continuous block of memory.

I found this topic Implementing malloc and free about implementing malloc and free using OS calls. I'm not quite at this level so I don't understand it all at this time but I'll try my best to pass it.

As I understood, the author keeps a list of FREE blocks in a linked-list, but once he finds available memory he creates a block of memory (requested memory) in a continuous memory and returns this memory from malloc().

So it must be that a linked-list is only to keep a track of available memory and the actual allocated memory is always continuous?

1 minute ago, ryt said:

So it must be that a linked-list is only to keep a track of available memory and the actual allocated memory is always continuous.

That is correct. An allocation returned by a memory allocator (malloc, your own custom allocator, whatever) is always a contiguous chunk of memory to the caller. If there is no contiguous chunk large enough, this is an indication of memory fragmentation.

The allocator itself can manage ranges of allocations however it sees fit (in a linked-list, a pool, etc.).

Again, there are a ton of different ways of implementig memory allocation. Some are better for certain sizes of objects. With C++ you have placement new so you can define the range you want your heap(s) to work under.

malloc and free must work for a fairly large range because they are meant to be general. But in all cases memory must be contiguous.

I've spent a large amount of time writing head implementations over the years.

3 hours ago, a light breeze said:

This is n ot true at all. An array holds data. A pointer points to data that is held elsewhere - either in another variable or on the heap.

An array is just compiler/language convinience, in the end they are pointers to memory regardless of if it is on heap, stack or part of another class.

const char* text = "Hello World";

is as same a pointer as also an array and can be allocated on the stack. It can be indexed by the indexer operator [] and also be shifted using *(text + 5) while a cast from a literal string into an array pointer is compiler convinience because the standard says so.

Templates are resolved by the compiler too so this is also something standard compilant and compiler dependent if your template recognizes arrays or throw an error. That most used compilers for C++ support this is true but there are still differences in how they are resolved sometimes.

And yes, the compiler also adds the sizeof operator to the array shift implicite because it knows that this type is intended to be of certain type.