   Time for allocating via OS or manually
  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 :DAllocating 1024 blocks of 1mb each (1gb):new: 1.692 secmalloc: 1.602 secmy heap: 2.457 secAllocating 10,000 blocks of 1k each (1gb):new: 0.086 secmalloc: 0.086 secmy heap: 2.211 secAllocating 100,000 blocks of 100 bytes each:new: 0.563 secmalloc: 0.540 secmy heap: ... got tired of waitingAllocating 1,048,576 blocks of 1k each (~1.1gb):new: 10.016 secmalloc: 9.988 secmy heap: ... i got tired of waitingI'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?   
  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.   ;  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?   ;  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?   ;  new/malloc doesn't allocate directly from OS. new/malloc uses custom memory allocators from C/C++ runtime library.If you want to allocate directly from OS, then on Windows you can use functions from this page: http://msdn.microsoft.com/en-us/library/aa366781.aspx.   ;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#.   ;  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)?   ;  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.   ;Quote:Original post by japroWhat 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 allocatorAnd 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.;  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.