   How to effectively handle memory allocations (multicore)?
  Greets!Currently I've successfully implemented my own cross-platform task scheduler for my multithreaded 3d engine.But I think that a better performance can be archived with an own memory manager, because if two threads allocate memory at the same time one has to wait before it can continue. I thought about globally overloading new and delete and for each thread I allocate some free-lists (TLS) with power of two memory blocks ranging from 2B - 256KB.What do you think about this?I know that there various libraries out there like Intel TBBs scalable memory allocator or TCMalloc and so on. But I need something cross-platform and free for commercial use.Thanks for any help!Cheers,Mike   
  Look up tcmalloc, it's licensed under BSD, which might suit your needs.   ;  Yeah I allocate heaps for each thread so they can safely perform allocations (in most cases) on their own private heap without requiring a lock.However, the problem sneaks in that you might call delete from a different thread later, which isn't at all safe!So... I break up the execution of my frames into several "phases", which lets you rationalise about scheduling and saftey easier.For example, lets say we've got an "execution" phase and a "clean-up" phase. Every thread executes the both the "execution" phase and the "clean-up" phase, but these phases can't overlap. No thread can begin "clean-up" until all threads have finished "execution". You can mask this synch point by putting another (independent) phase between these two 'dependent' ones.In the execution phase, you can allocate memory from your own heap, and free memory from any heap -- but "freeing" an allocation actually just puts it in a thread-local queue to be released later.After the execution phase is finished, each thread runs the clean-up phase, which processes the items in the queues and actually frees the memory.struct MyHeap{  MyHeap( int numThreads ) : m_Index(ThreadIndex())  {    threadLocalFreeQueue.resize( numThreads );    for each thread threadLocalFreeQueue[thread].reserve( someGuess )  }  void* Alloc( uint size )  {    //assert we're in the execute phase    //assert m_Index == ThreadIndex()    return m_Heap.alloc( size );  }  void Free( void* p )  {    //assert we're in the execute phase    threadLocalFreeQueue[ThreadIndex()].push_back( p );  }  void Cleanup()  {    //assert we're in the clean-up phase    for each thread for each pointer in threadLocalFreeQueue[thread]   m_Heap.dealloc( pointer )  }private:  std::vector<std::vector<void*>> threadLocalFreeQueue;  ... m_Heap; //<-- insert any single-threaded allocator here};Voila, wait-free allocations and deallocations.   ;  @cache_hit: Thank you for your reply, but I already looked over this library a bit and I think that it's a little bit inflexible for me, because I also want to track all my memory allocations and integrate it nicely with all my other components (logging and so on).Isn't there an easier way to accomplish my own memory manager that gives me a little bit more allocation boost and integrates nicely in my framework?@hodgman: Wow! That sounds really interesting to me and I think that this is exactly what I'm looking for!But will you kindly tell me a bit more about these phases?AFAIK in every thread you have in your task scheduler you call Alloc() and Free() while popping tasks from your TLS stacks and whenever all threads are idle you call Cleanup() to actually deallocate the single-threaded system heap and emtpy your TLS free-queues?Am I right?So I would have two options where I can insert the Cleanup() call:1) at the end of my game loop2) integrate it nicely into my task scheduler by calling it every time all threads go idle and no tasks are currently processedThanks dude for your help! ;)[Edited by - CppCoder on June 11, 2010 1:57:53 AM];  @hodgman: Just for interest but do you already have done some performance comparision against TCMalloc or Intels TBB allocator?   ;Quote:Original post by HodgmanIn the execution phase, you can allocate memory from your own heap, and free memory from any heap -- but "freeing" an allocation actually just puts it in a thread-local queue to be released later.After the execution phase is finished, each thread runs the clean-up phase, which processes the items in the queues and actually frees the memory.*** Source Snippet Removed ***Voila, wait-free allocations and deallocations.I don't understand ... doesn't this strategy have the same problem as the original operator new, namely that it requires all your threads to synchronize with each other (i.e. WAIT)? Hmm ... ok, I can see that your threads no longer need to wait when ALLOCATING memory, but FREEING it will still require some sort of synchronization? Or am I missing something here?;  AFAIK hodgman manages some heaps (TLS specific free-lists of different block-size) for each thread and so Alloc() is a non-locking function call, because it immediately returns a preallocated block of memory. If one of the heaps doesn't have any more memory blocks of requested size, it simply allocates a new big block of memory.Free() on the other hand caches all deallocations and only a call to Cleanup() actually deallocates the memory blocks. But be aware to call Cleanup() only when all threads are idle (at the end of a frame).I hope I could explain my view of his nice solution a little bit.// EDIT:Deallocating of memory in Cleanup() can easily be solved through a threshold or time intervall and a semaphore. When this threshold or time intervall is reached, then the memory actually gets free'd. Think of it like the .NET garbage collector where the GC calls Collect() in different cycles.   ;Quote:Original post by Red AntI don't understand ... doesn't this strategy have the same problem as the original operator new, namely that it requires all your threads to synchronize with each other (i.e. WAIT)? Hmm ... ok, I can see that your threads no longer need to wait when ALLOCATING memory, but FREEING it will still require some sort of synchronization? Or am I missing something here?There's no synch on alloc or free. However, I'm assuming that the user will ensure that nobody will be calling alloc/free at the same time as clean-up.To achieve this, I categorise jobs into different "phases" or "task groups". Every task/job within phase/task-group can be executed in parallel. That is, you can just pump a whole group of tasks into a thread pool.However, some phases/task-groups can be dependent on other phases/groups. A 'dependent' group of tasks wont be pumped into the pool until all of it's dependent groups have completed 100%.There's several ways to track this. In my task pool, I don't use work stealing -- the phase/task-group is divided amongst the threads in the pool, and as each one finishes it sets a flag. If all the flags are set, then that phase is complete (and dependent phases can begin).If you are using work-stealing (or a shared job queue), then every time you submit a job for a particular phase, you could increment a "waiting for" counter, and every time you complete a job, you increment a "completed" counter. If "waiting for" is equal to "completed", then that phase is complete (and dependent phases can begin). However, these counters would need to be shared between threads, so you'd have to use something like InterlockedIncrement, which is a very lightweight synch point in itself.In this case, the "clean-up phase" is dependent on the "execute" phase.During the execute phase, each thread can call alloc from its own heap, and can call free from any heap. During the clean-up phase, each thread calls CleanUp on its own heap. This is a form of mutual exclusion (execute/clean-up don't run at the same time), but achieved via careful scheduling rather than via mutexes.Quote:Original post by CppCoder@hodgman: Just for interest but do you already have done some performance comparision against TCMalloc or Intels TBB allocator?No, sorry I don't have any stats on this :/I would assume that it could be faster than a general-purpose thread-safe allocation scheme though, because it's piggybacking off existing synch-points in the app (i.e. the end-frame synch) and doesn't require any extra locking (not even "lock free" locking). This obviously isn't suitable for general purpose use, but is great for games.Quote:Original post by CppCoderAFAIK in every thread you have in your task scheduler you call Alloc() and Free() while popping tasks from your TLS stacks and whenever all threads are idle you call Cleanup() to actually deallocate the single-threaded system heap and emtpy your TLS free-queues? Am I right?Yeah, pretty much ;)My "phases" are a task-group class like below, a list of task groups forms the schedule for the frame:struct TaskGroup{  std::vector<Task*> tasks;  std::vector<TaskGroup*> dependencies;};typedef std::vector<TaskGroup*> Schedule;Schedule s;s.push_back( executeGroup );cleanupGroup.dependencies.push_back( executeGroup );s.push_back( cleanupGroup );Each task-group is executed by all threads, and a range of the tasks in the group are assigned to each thread:When Run is called on the execute group, the thread-index and number of threads are used to determine which sub-set of the tasks to execute.When Run is called on the clean-up group, each thread has one task each -- to call CleanUp on their own heap.void CTaskGroup::Run( uint idxThread ){for( uint i=0,s=m_Prerequisites.size(); i<s; ++i )YieldThreadUntil( WaitForTaskGroup(Prerequisites) );//For each task, find out how much work this thread should do, execute that range.uint threads = m_Weights.size();//Find a every task, find non-overlapping range for this thread to executefor( uint i=0,s=m_Tasks.size(); i<s; ++i ){CTask& task = *m_Tasks;uint taskSize = task.Size();//For each thread (up until this thread), divide up the problem range deterministically//(This range calculation must produce the same results when run by each thread)TaskRange range ={-1,-1};ASSERT( idxThread < threads )for( uint iThread=0, itRange=0; iThread<threads; ++iThread ){ASSERT( itRange <= taskSize )uint begin = itRange, end;if( iThread == threads-1 || iThread==taskSize-1 )//last worker, make sure the whole range is coveredend = taskSize;elseend = std::min( taskSize,  uint(begin + taskSize*m_Weights[iThread]) );if( iThread == idxThread ){//found the answer for this thread, break out of the looprange.begin = begin;range.end = end;break;}itRange = end;}ASSERT( range.begin != -1 )//Execute the task, using the problem range for this threadif( range.begin != range.end )task.Execute( range );}//Signal this thread has completed all tasksm_IsExecuting[idxThread] = 0;}Quote:So I would have two options where I can insert the Cleanup() call:1) at the end of my game loop2) integrate it nicely into my task scheduler by calling it every time all threads go idle and no tasks are currently processedEither of those would work too ;)[Edited by - Hodgman on June 11, 2010 5:46:00 AM];  Thank you for this great detailed explanation hodgman!I think one can optimize this concept to a more general approach by implementing a GC like .NET already has. As I already mentioned one can call Cleanup() for a very basic example say all ten seconds or whenever a specific hotspot is reached an all tasks are IDLE.   