The multithreaded treatment in the article is naive: grab a lock, do the operation, release the lock. You won't get much concurrency that way in mutlithreaded applications with many concurrent memory operations. A prior research project of mine was a lock-free memory allocator: http://www.cs.vt.edu/~scschnei/streamflow
That link has source code and a published paper.
Research that is not my own: TCMalloc, which is a part of Google's perftools library, is an excellent multithreaded allocator. Despite using locks, it was actually the best competitor in terms of speed. TCMalloc description: http://goog-perftools.sourceforge.net/doc/tcmalloc.html
The Hoard memory allocator was one of the first in the literature to address the mutlithreaded case: http://www.hoard.org/
Writing your own allocator is a great exercise; I've recommend it as a means to learn systems programming in C. But if implementing your own is often not worth the effort in a real application. If memory allocation is an issue in your application, there's probably an existing allocator that solves the problem better than you can.
Writing your own allocator is a great exercise; I've recommend it as a means to learn systems programming in C. But if implementing your own is often not worth the effort in a real application. If memory allocation is an issue in your application, there's probably an existing allocator that solves the problem better than you can.
It is a pretty trivial stuff though. First half describes typical "slab allocator". The other half covers the use of free lists, and that's in a context of speeding up their own clumsy bitmap-based free block tracking code. All this is supported by dmalloc (?), which is IIRC a default GNU libc allocator.
The discussion of multithreading issues is very basic too - just simple single-lock wrapper of all API calls. That's just dumb if you pardon my French. No mentioning of granular locking or lock-free options.
Also, on a more general note - writing custom memory manager is an option of last resort when optimizing existing code that cannot be refactored. That's because writing a manager is meant to negate the effects of a bad application design; so if latter can be fixed, there's really no need for a manager.
Consider their own example of allocating 5000000 objects, each with its own new() call. This is what the std::vector is for - it coalesces all new calls into one and then constructs the instances. If, in a real world, these 5 million objects are not allocated all at once, then vector still can be used as an application-level pool of objects. In the end, this is an application-specific allocation quirk and it needs to be dealt with at the application level, not in libc.
If you can afford 3 people to work on it full-time you can do beatuful things. For example you can have vast areas of code walled-off with auto-release pools (not objecive-c pools that are scoped to a stack frame, but a custom one that's got lifetime of your choice), allowing people in those areas to concentrate on complex algorithms, not memory micromanagement. Then you can have other areas of your code deal with memory directly for highest resource utilization.
Anohter thing you can do make sure to decommit all deallocated pages, and allocate all objects at the boundary of a page. Thus all buffer overruns and hanging referneces will result in a page fault, not a hard to debug corruption.
In grad school, one of our professors wrote a memory leak checker for C/C++ and sprung it on his compiler construction class two weeks from the end of the semester. He pronounced that no one with memory leaks in their project would pass his course. My friends were taking the class and everyone enrolled in it despaired of passing. As a joke, to try and bring some levity to the situation, I suggested that they just register every allocation they made on a huge list, then free everything right before program termination. Well, they were so desperate, they went and implemented it. Others in the class heard about this, and soon every single student enrolled in the class had implemented the same scheme.
Later on, I became the TA for that professor for the same compiler construction class. I don't think he knows to this day.
Writing a good memory manager isn't all that trivial. You have to address heap fragmentation, and there are tons and tons of edge cases. It's also not a place where you want any bugs in your code.
I wrote one [http://associatedtechs.com/rob/memory.cpp.html] about 6 years ago because the development environment I was using at the time had a pretty crummy built-in C++ memory manager. I was messing around with stress-testing some code and was having some pretty extreme fragmentation problems.
I'm not proud of it and it's incomplete, but what's there works OK and performed a lot better than the built-in memory manager, both in terms of speed and heap fragmentation. It uses a modified best-fit algorithm. It doesn't handle running out of memory very well, though.
Can I really do anything similar in C? I'm not sure. The tutorial makes use of overloading operators new and delete which (both operators and overloading feature) are only available in C++.
I think the title is misleading; as far as I know, term "C/C++" is a blanket and should be avoided.
There is basically nothing you can do in C but can't do in C++; the overloading is basically syntactical sugar. In fact, there are things you can explicitly do in C but can't do in C++ (at least if you insist on doing them the "C++ way"). Example: as far as I know, C++ doesn't let you use virtual constructors; C can implement this through function pointers.
Of course, if you treat C++ as a superset of C and just do things "the C way" in cases when "the C++ way" doesn't work, obviously C++ can do everything C can.
The lack of an equivalent of offsetof in C++ is a real pity. This effectively prohibits using C-style data containers, whereby container's control data is embedded into the data instance itself. This sort of thing:
struct record
{
int foo;
int bar;
...
list_item item; // keeps 'record' on some list
tree_item item; // keeps 'record' on some tree
};
There's no concise and memory-efficient way of doing the same in C++.
The multithreaded treatment in the article is naive: grab a lock, do the operation, release the lock. You won't get much concurrency that way in mutlithreaded applications with many concurrent memory operations. A prior research project of mine was a lock-free memory allocator: http://www.cs.vt.edu/~scschnei/streamflow
That link has source code and a published paper.
Research that is not my own: TCMalloc, which is a part of Google's perftools library, is an excellent multithreaded allocator. Despite using locks, it was actually the best competitor in terms of speed. TCMalloc description: http://goog-perftools.sourceforge.net/doc/tcmalloc.html
The Hoard memory allocator was one of the first in the literature to address the mutlithreaded case: http://www.hoard.org/
Writing your own allocator is a great exercise; I've recommend it as a means to learn systems programming in C. But if implementing your own is often not worth the effort in a real application. If memory allocation is an issue in your application, there's probably an existing allocator that solves the problem better than you can.