Skip to main content
GameDev.net gamedev.net
🔒 Locked

Time for allocating via OS or manually

Started by Endar Apr 4, 2010 at 9:49 PM 8 replies 2.4k views
Original Post
Endar
Endar
I've written my own version of a basic heap, that just allocates a large block of memory from the OS on creation, and then just keeps a list of allocated and free blocks, and divvies them up when I ask. I just timed allocating using my own heap as opposed to new and malloc. I was under the impression that allocating from the OS was slow due to the time it takes for the OS to allocate a page. It seems that I was either wrong, or I just write terrible, terrible code :D Allocating 1024 blocks of 1mb each (1gb): new: 1.692 sec malloc: 1.602 sec my heap: 2.457 sec Allocating 10,000 blocks of 1k each (1gb): new: 0.086 sec malloc: 0.086 sec my heap: 2.211 sec Allocating 100,000 blocks of 100 bytes each: new: 0.563 sec malloc: 0.540 sec my heap: ... got tired of waiting Allocating 1,048,576 blocks of 1k each (~1.1gb): new: 10.016 sec malloc: 9.988 sec my heap: ... i got tired of waiting I'll do some more in depth profiling around the larger blocks of code in the allocate function for my own heap, but it looks like (as expected) it's the increase in the number of allocations that is the problem. I suspect because I'm using a linked list of the free blocks and another linked list of the allocated blocks, the cache is getting a beating. Anyone have any more advice? Is this just going to be the same case as most of the other std C lib code where unless I'm writing for something really specialized, my code is almost always going to be slower?
[size="2"][size=2]Mort, Duke of Sto Helit: NON TIMETIS MESSOR -- Don't Fear The Reaper
Hodgman
Hodgman
It's likely that new/malloc are using an allocator which has been written/tested/updated over the last decade and is algorithmically pretty optimal for the general case.

Personally I only use my own allocation code for specific purposes, such as objects that have a lifetime of "one frame". This allocator just increments a pointer in a big heap and resets the pointer back to the beginning of the heap each frame.

IIRC boost has some allocators which might be able to outperform yours, without you having to go studying allocation routines for months yourself ;)

[edit]The other time I avoid the built in allocators is when I've got to do lots of allocation in multithreaded code, as the built in ones usually achieve thread-safety through locking -- instead if you've got your own heap classes, you can create a separate heap per thread to avoid synchronisation overhead.
rubicondev
rubicondev
It might be optimal as a catch all, but a catch all is not what's needed for a specific task such as this. Also, "optimal" doesn't mean "fast".

Take a look at the code yourself, you can get the debug stuff from Microsoft. You'll be on about page 5 of the source before you see any actual allocation code taking place. The rest of it is pool management, thread/interprocess management and a mass of other things I can only guess at. There's some locking stuff in there too, but I'm not sure if that's actually a problem - they can often be hidden.

If you need to do a lot of dynamic allocation during the running of your game, you should absolutely write your own allocator. It should be miles faster, so you probably need to look at your code again - maybe with some real world numbers.

Do you, for example, maintain a "free" list as well as a "used" list?
------------------------------Great Little War Game
japro
japro
What would be an example of a custom allocater that is "way faster" than new?
I once had a simulation code that created lots of small objects each step so I followed the advice of some book (i don't remember which) and implemented an allocater that simply had a chunk of memore and a bunch of pointers that were inserted in a stack. All new did was basically: {if(!stack.empty()) return stack.pop();} and delete just pushed the pointer back onto the stack. It was slower than using new... Not by much but still. How am I supposed to "beat" new when it is faster than popping an element off a stack?
Antheus
Antheus
Quote:
What would be an example of a custom allocater that is "way faster" than new?
template < class T, size_t N > struct MyHeap {  T data[N];    size_t curr;  T * alloc() { return &data[curr++]; }  void free(); { curr = 0; }};


And that is about it. This type of allocator will be anywhere between 10-50 times faster than any generic one. By not tracking allocations at all each allocation is about ~1 cycle or so.

This type of allocator is staple for anything simulation-like, where things are updated in discrete steps, so intermediate state can be discarded in between.

The above is not suitable for persistent objects. Here, the typical pop-and-swap approach works:
void MyHeap::remove(T * x) {  curr--;  swap(*x, curr);}
The gains come from not preserving the order of elements.

Add error checking as needed, it shouldn't matter much.


The above techniques work in some managed languages as well, especially with structs in C#.
Adam_42
Adam_42
With a linked free and used list, allocation should be no more than a few thousand cycles per alloc with cache misses. Even for 10,000 blocks you're taking 0.22ms per alloc, assuming a 3GHz CPU that's over half a million cycles per alloc.

That seems a bit high for taking a block from one linked list, splitting it in two, and adding one of those to one end of another list.

Is your linked list is doubly linked to make insertion and removal O(1)?
Beyond_Repair
Beyond_Repair
Edit: I've missed the party, but whatever, this point deserves reiteration.

malloc is "slow" because it tends to deal with a general case. If you try to write an allocator with similar generality you most likely won't do any better than the huge number of people who have implemented and researched this.

What *may* make a custom allocator faster when generality is sacrificed is if the resulting memory blocks can be laid out for better cache behavior, as well as the allocation itself simply taking less time.

The code Antheus posted is a good example...

As always with optimization, don't bother customizing memory allocation until profiling, unless you know in advance a particular data structure will be responsible for a large part of the application's memory usage. Just as the saying "90% of the execution time is spent on 10% of the code", the number of memory accesses and consumption may be heavily concentrated to a subset of the app.
rubicondev
rubicondev
Quote:
Original post by japro
What would be an example of a custom allocater that is "way faster" than new?


This would be the first port of call:

return PreInitialisedObjects[Next++];


The next would be a pool allocator

And then there would be a replacement general purpose malloc. I'm not sure if it's faster than new but it was two orders of magnitude faster than malloc back when I used one in a vanilla c engine, and I didn't even spend much time on it.
------------------------------Great Little War Game
nullsquared
nullsquared
I don't think it was mentioned here, but when it comes to memory, you can definitely do better than the standard stuff, at least on Windows.

For example, nedmalloc is just about the fastest allocator I know of.
Quote:

It is more than 125 times faster than the standard Win32 memory allocator, 4-10 times faster than the standard FreeBSD memory allocator and up to twice as fast as ptmalloc2, the standard Linux memory allocator. It can sustain a minimum of between 7.3m and 8.2m malloc & free pair operations per second on a 3400 (2.20Ghz) AMD Athlon64 machine.

Topic Locked

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

Sign in to reply to this topic.