mtrebi / memory-allocators Goto Github PK
View Code? Open in Web Editor NEWCustom memory allocators in C++ to improve the performance of dynamic memory allocation
License: MIT License
Custom memory allocators in C++ to improve the performance of dynamic memory allocation
License: MIT License
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
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?
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.
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'm not sure.
alloc/free is important for Performance.
is virutal function make a deal
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>( )
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.
nvm, just delete it please, I missed something
Hi,
Deleted*
I was actually wrong! :)
Cheers,
Jose
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.
I would recommend doctest although I'm affiliated with it...
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.
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 !
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:
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.
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!
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.
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.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.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 endsAllocationHeader 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 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.
show how to use this lib
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.
This is essential for modern applications.
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.