I assume that the project has been abandoned since a some pull requests are pending.

Anyways, I will address a few things here for those coming to this repository in search of knowledge from this code base.

Problems with using "AllocationHeader"

• Wasted Memory: AllocationHeader as is used in this repository simply adds overhead in terms of wasted padding memory. Regardless of the fact that the memory (m_start_ptr + m_offset) is already aligned, AllocationHeader header wastes as low as alignment bytes or padding + alignment bytes of memory.
• Probable Cache Misses: Since the AllocationHeader is stored before the memory pointer that allocate gives away, there is a probability of cache miss when using free if the memory pulled in does not align with cache boundary. It might be a small cost or a big one depending upon how many times free is called. It's bad since the entire point of a custom allocator is performance with solid metrics of memory usage.
• Current Implementation of AllocationHeader stores garbage: As has been addressed in issue #8, AllocationHeader currently stores garbage since it stores the address of a stack allocated AllocationHeader that would go out of scope once it goes out of scope i.e. as soon as the allocate function ends

AllocationHeader allocationHeader{padding};
AllocationHeader * headerPtr = (AllocationHeader*) headerAddress;
headerPtr = &allocationHeader;   // <---------- allocationHeader would go out of scope

A better way of implementing is to use push/begin constructs that would store the offset of stack and pop/end which would reinstate the stack allocator back to the pushed offset.

Hi!
First off, this is an amazing article, and it has really helped me out as a beginner to C/C++. Unfortunately, there lies my problem: as a beginner, I am rather new to how all of this works, so please forgive me if this comes off as an unsophisticated question.

With that said, the purpose of the stack allocator (or any other allocator), as I understand it, is to segment off a piece of memory in the heap, then from elsewhere in your codebase allocate pieces of that block of memory for individual use, and free it back when you are done. Thus, one (i.e. me, the beginner) would expect that upon allocating memory via myStack -> Allocate(64, 8), it would return a pointer to the memory you allocated so that you may edit it, and then free it when you are finished.

Unfortunately for me, while it does return a pointer, I find myself unable to use it as such: upon assigning it (via allocatedMem = &myValue), the compiler throws an error stating that void* is not a ponter-to-object type. (Also, assigning it would be fruitless, as then it would no longer point to the allocated memory.)

The tl;dr of it is: how do I use memory that I allocate? Are there some steps that I am missing, or is my beginner-ness just getting in the way of me thinking clearly?

Thanks in advance, -cellman123

Hi mtrebi,

Thanks for the modification of making it running on Windows first. However I found places that confuse me a lot in FreeListAllocator.

First, is it a must that we have two header type "AdditionalHeader" & "FreeHeader"? I believe an additional header with storing size & padding is enough. And the m_free_list may become type of "SinglyLinkedList", Node type may become "SinglyLinkedList::Node".

Secondly, in the alloc implementation of FreeListAllocator. When adding new block/node due to rest of available memory. Checking "rest > 0" is not enough I believe, because every block must have a header. I checked "rest > sizeof(AdditionalHeader)" instead of "rest > 0", since I only have one additional header. If 0 < rest < sizeof(AdditionalHeader) then we cannot make it a block right?

How do you think of the thoughts above? I am just trying to figure out if it is necessary to have two headers and storing the block size repeatedly. Thanks and would love to hear from you.

nvm, just delete it please, I missed something

Getting some build errors, screenshot attached.
Environment:
Win10, VS 2017

I would recommend doctest although I'm affiliated with it...

2>c:\projects\memory-allocation\src\benchmark.cpp(34): error C2131: expression did not evaluate to a constant
2>c:\projects\memory-allocation\src\benchmark.cpp(34): note: failure was caused by a read of a variable outside its lifetime
2>c:\projects\memory-allocation\src\benchmark.cpp(34): note: see usage of 'this'
2>c:\projects\memory-allocation\src\benchmark.cpp(40): warning C4018: '<': signed/unsigned mismatch

Seems this problem similar to this one https://stackoverflow.com/questions/33423502/expression-did-not-evaluate-to-a-constant-c?utm_medium=organic&utm_source=google_rich_qa&utm_campaign=google_rich_qa

I just wanted to start by saying how much I appreciate the code you shared. It's been really helpful for someone like me who's curious about how memory allocation works.

As I was going through the code, I came across something interesting about arena allocators. I have a question that I've been wondering about, and I'm hoping you could help me understand it better.

In the arena allocator concept, I noticed that a big chunk of memory is allocated using "malloc" just once. Then, whenever more memory is needed, it's taken from this big chunk. This sounds like a smart way to avoid calling "malloc" many times, which is great for making things faster. But I got a bit stuck on a thought.

Isn't "malloc" already a memory allocator? It's a tool that uses its own special methods to get memory from the computer. So, when we use an arena allocator, are we sort of using "malloc" to make a special area for memory, and then we use the arena thing to get memory from that special area? This feels like using one memory tool (the arena thing) on top of another one we already had (the "malloc" thing). Using sbrk() might be another option?

I'm really interested in your take on this. Could you share your thoughts?

Thanks a bunch!

show how to use this lib

As discussed in readme.md, the pool allocator initialize freeNodeList with O(N) complexity. However before any free() is invoked, it behaves like a LinearAllocator.

So we could just leave the freeNodeList empty, and add an Offset variable to indicate current free node, and increase this Offset whenever allocation is performed. When free() is called, we add the freed space into freeNodeList, which will be looked upon first for later allocations.

First of all thanks for such a good example and comparison of how memory allocator works.

Sadly, after I followed the instruction and compiled it in VS, compiler told me I can't use "void* address [m_nOperations]" since m_nOperations is not a constant. How did you get it work?

Thank you for sharing your code and ppt for Dynamic memory. There is only part 1 of your Dynamic memory tutorials and it is really nice to read and to learn. If it is possible, can you share the rest of the docs ! Thank you very much !

Hi,

Deleted*

I was actually wrong! :)

Cheers,
Jose

hi,
So lucky,I meet your github, your code of memory-allocator is very nice.But i can not understand the chart.
(Time complexity of allocations/free blocksize = 4096)From the result of code(execute main), i don't get any correlation. I would be very grateful if you can answer my puzzlement. thank you.

Compilation Error

When compiling with Clang on Xcode, I get the following error

../src/StackAllocator.cpp:39:39: error: non-constant-expression cannot be narrowed from type 'std::size_t' (aka 'unsigned long') to 'char' in initializer list [-Wc++11-narrowing]
    AllocationHeader allocationHeader{padding};
                                      ^~~~~~~
../src/StackAllocator.cpp:39:39: note: insert an explicit cast to silence this issue
    AllocationHeader allocationHeader{padding};
                                      ^~~~~~~
                                      static_cast<char>( )

Compiler Details

Apple clang version 12.0.0 (clang-1200.0.32.28)
Target: x86_64-apple-darwin19.6.0
Thread model: posix
InstalledDir: /Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin

In case padding can go beyond 255, it makes sense to make AllocationHeader::padding a size_t instead of a char as suggested by @talhasaruhan in #8.

In StackAllocator you're doing this:

AllocationHeader allocationHeader{padding}; AllocationHeader * headerPtr = (AllocationHeader*) headerAddress; headerPtr = &allocationHeader;

Which doesn't copy the AllocationHeader object that's created on the stack into the memory position.

You should either use

memcpy(headerAddress, &allocationHeader, sizeof(AllocationHeader))

or just use placement new operator to create the object at the memory location.

I've tested this and just as I expected, you're actually getting garbage when you're reading the header in the Free function.

There seems to be a bug in this line.
headerPtr = &allocationHeader;

Should be changed to *headerPtr = allocationHeader; otherwise the padding value is not recorded in the header memory.
I tested the original code, and the stack head address mismatches after one allocation and one free.

Shouldn't the smallestDiff be updated along with the bestBlock in here?
if (it->data.blockSize >= requiredSpace && (it->data.blockSize - requiredSpace < smallestDiff)) {
bestBlock = it;
}

smallestDiff = it->data.blockSize would be added.

look at this picture above plz...we know that the type of "rest ", "data.blockSize" and "requiredSize" is std::size_t.
However, std::size_t is unsigned __int64. So they are unsigned. if you do "rest = affectedNode->data.blockSize - requiredSize", it will always get a value greater than zero. when "data.blockSize < requiredSize", it will be a great trouble ("rest" will be a Huge unsigned number).....
a better way is:

i'm not sure.
alloc/free is important for Performance.
is virutal function make a deal

Hi
There is a bug in your Free List Allocator when alignmentPadding is not zero like on 32 bit systems.

One bug is here obviously and newFreeNode address is inside of the current block when alignmentPadding is not zero.