   multi threaded bulk terrain generation
  [edit]This thread has taken a new direction, read below for the original post[/edit]Hi,.I wanted to find out what kind of overheads there would be for the "fork and join" method of multithreading, compared to using a thread pool. I need to refine my test, it currently works OK on windows but ive had people test it on a few other platforms, and sometimes it runs into OS limits, for example, on freeBSD somebody had it throw an exception.#include <ctime>#include <boost/thread.hpp>#include <iostream>boost::mutex io_mutex;using std::cout;using std::endl;struct count{  count(int id) : id(id) { }  void operator()()  {  }  int id;};int main(int argc, char* argv[]){try{size_t num_threads = 100000;clock_t ticks = clock();for(int i = 0; i < num_threads; i++){boost::thread thrd1(count(1));}clock_t time = clock() - ticks;float seconds = (float)time / 1000.f / (float)CLOCKS_PER_SEC;cout<<"Number of seconds taken for " << num_threads << " threads:"<< seconds <<endl<<"Time taken to spawn each thread:" << ((float) seconds / (float) num_threads)<<endl;}catch(std::runtime_error& err){cout<<err.what()<<endl;}  return 0;}How can I improve this test?Im also curious, if anybody manages to run it, what your processor / compiler / os is, and what the times taken were.[Edited by - speciesUnknown on April 20, 2010 9:04:42 AM]
Quote:Original post by speciesUnknownI need to refine my test, it currently works OK on windows but ive had people test it on a few other platforms, and sometimes it runs into OS limits, for example, on freeBSD somebody had it throw an exception.For fork/join, the number of threads spawned is equal to number of idle processors. Depending on load characteristics, it can be one more or less than that.Reactor or proactor designs can use larger number of threads, somewhere up to 1000. Only n (number of cores) of them will be active at any given time, others serve as overflow bucket. If system is working properly, then n of them will be taking 95% of the time, with handful of them being active for the rest of time.If threads are non-idle, and there is enough memory (each thread commits between 4k and 1MB of memory), then the kernel scheduler will usually break at ~200 threads per core, where context switching overhead will become so large that no useful work gets done.The largest number of threads used in production system was reported for some of Google servers, which apparently run ~4000 threads, but IIRC they required kernel patches.100000 is about 10000 times too many threads.   ;  So what you;re saying is that I should only spawn the number of threads equal to the number of cores that I have?The reason I'm doing this is due to this design, for generating lots of seperate blocks of terrain:#ifdef THREADED// on call(), generate the terrain for the given area, lock the given mutex, and add the terrain block to the given block listclass TerrainGenerator{public:TerrainGenerator(float x, float y, size_t w, size_t h, float scale,boost::mutex* node_list_lock, TerrainSceneNode::block_list_t* block_list) :w(w), h(h), x(x), y(y), scale(scale),node_list_lock(node_list_lock), block_list(block_list){}// destructor does nothing, since ptr is pushed to given list~TerrainGenerator(){}void operator()(){ptr = new TerrainBlock(x, y, w, h, scale);boost::mutex::scoped_lock lock(*node_list_lock);block_list->push_back(ptr);}private:size_t w, h;float x, y;float scale;TerrainSceneNode::block_ptr_t ptr;boost::mutex* node_list_lock; TerrainSceneNode::block_list_t* block_list;};#endifTerrainSceneNode::TerrainSceneNode(Mat44f pos):SceneNode(pos){clock_t start = clock();// store threads here for joining and delete#ifdef THREADEDtypedef std::list<boost::thread * > threads_t;threads_t threads;boost::mutex node_list_lock;// spawn a bunch of threads to generate terrainfor(int x = -25; x < 25; x++)for(int z = -25; z < 25; z++){// each one will generate its terrain, lock the mutex, and append the new terrain block to this->blocksthreads.push_back( new boost::thread(TerrainGenerator (x * 32, z * 32, 32, 32, 1.f,&node_list_lock, &(this->blocks) )));}// join threads then delete themthreads_t::iterator t_it = threads.begin(), t_end = threads.end();for(t_it; t_it != t_end; ++t_it){(*t_it)->join();delete(*t_it);}#elsefor(int x = -25; x < 25; x++)for(int z = -25; z < 25; z++){blocks.push_back( new TerrainBlock(x * 32, z * 32, 32, 32, 1.f));}#endif#undef THREADEDfloat time = float(clock() - start) / (float) CLOCKS_PER_SEC;;std::cout<<"Time taken to generate terrain:" << time << std::endl;}Obviously this version will spawn at a total of 100 threads, but I was told that this would suffer overheads. However, on running it I found that the terrain was being generated orders of magnitude faster (4 seconds MT compared to around 18 seconds ST). Until i rebooted that is. Now, the results are 17 seconds (multithreaded) compared to 18 seconds(single threaded)   ;Quote:Original post by speciesUnknownThe reason I'm doing this is due to this design, for generating lots of seperate blocks of terrain:That is a sub-optimal design.std::vector<TerrainBlock> blocks(w*h); // pre-allocateparallel_for(block.begin(), blocks.end(), BlockInitializer);for (int i = 0; i < blocks.size(); i++) block_list.add(&blocks);parallel_for is obviously some version of fork/join. BlockInitializer is what initializes individual terrain block. A free function does the job, it's passed reference to block.All memory allocation is done from main thread. There are no locks, or anything similar, each block is processed in complete isolation.If some per-node operation needs to be done, such as adding to that block_list (whatever purpose that serves), it is done after the main loop completes.This approach scales reliably. Ideally, blocks would be allocated at properly aligned boundary, and number of blocks to process in parallel would be chosen in such a way as to minimize false sharing (each thread operates on full cache line).Intel's TBB is a very solid implementation for this type of tasks, but I'm not sure it's supported in BSD.   ;  I eventually figured this out using a system whcih divides the work out between teh number of cores availble.typedef std::vector<TerrainBlock *> pending_blocks_t;class TerrainGenerator{public:TerrainGenerator(pending_blocks_t& generators, size_t begin, size_t end):generators(generators), begin(begin), end(end){}void operator()(){for(size_t i = begin; i < end; i++){generators->generate();}}private:pending_blocks_t& generators;size_t begin, end;};typedef std::list<TerrainGenerator> users_t;TerrainSceneNode::TerrainSceneNode(Mat44f pos):SceneNode(pos){clock_t start = clock();// how many cores do we need to usesize_t num_cores = boost::thread::hardware_concurrency();// if we are single threaded, just do it all the easy wayif(num_cores == 1){for(int x = -25; x < 25; x++)for(int z = -25; z < 25; z++){TerrainBlock * b = new TerrainBlock(x * 32, z * 32, 32, 32, 10.f);b->generate();blocks.push_back( b );}}else{// otherwise do it the slightly harder way// generate large list of required generatorspending_blocks_t generators;for(int x = -25; x < 25; x++)for(int z = -25; z < 25; z++){generators.push_back( new TerrainBlock(x * 32, z * 32, 32, 32, 10.f) );}// divvy up the generators between the right number of generator users// how many generators in totalsize_t num_generators = generators.size();if(num_generators == 0)return;// number of generators per core (minus leftovers)size_t generators_per_core = num_generators / num_cores;// just give the leftovers to the first threadsize_t leftovers = num_generators % num_cores;// spawn one thread for each of those userstypedef std::list<boost::thread * > threads_t;threads_t threads;for(size_t i = 0; i < num_cores; i++){size_t start = i * generators_per_core;size_t end = start + generators_per_core;// first thread gets any leftoversif(i == 0)end += leftovers;threads.push_back( new boost::thread(TerrainGenerator(generators,start,end)) );}// join threads then delete themthreads_t::iterator t_it = threads.begin(), t_end = threads.end();for(t_it; t_it != t_end; ++t_it){(*t_it)->join();delete(*t_it);}// add newly generated terrain to blockspending_blocks_t::iterator it = generators.begin(), end = generators.end();for(it; it != end; ++it){blocks.push_back(*it);}}// figure out how long it tookfloat time = float(clock() - start) / (float) CLOCKS_PER_SEC;std::cout << "Time taken to generate terrain:" << time << " num cores used:" << num_cores <<std::endl;}It seems optimal, but doesnt quite give me the 4x boost I expected (typically 6.25 seconds single core compared with around 21 seconds with 4 cores given a 50x50 grid of terrain nodes, each 32x32 at a scale of 10x). I imagine this is roughly how the TBB version of parrallel_for would work (sort of)How could I improve this style further?   ;  Try benchmarking single-threaded VS multi-threaded without the if(num_cores == 1) test/block -- so that the overhead of setting up the job system is included in both benchmarks.Also, instead of creating num_cores threads, you want to create num_cores-1 threads and then make use of the existing main-thread. e.g.for(size_t i = 0; i < num_cores; i++){size_t start = i * generators_per_core;size_t end = start + generators_per_core;// first thread gets any leftoversif(i == 0)end += leftovers;if( i == num_cores-1 ){//for the last chunk of work, just use the existing threadTerrainGenerator worker(generators,start,end);worker();}elsethreads.push_back( new boost::thread(TerrainGenerator(generators,start,end)) );}[EDIT]Looking at the logic for handling leftovers, won't that cause the 1st/2nd chunks to overlap?i.e.end0 = (generators_per_core + leftovers)start1 = (generators_per_core)end0 can be >= start1Might be better off putting the leftovers on the last thread.   ;  Thanks for noticing that bug - I might not have noticed it for a while.Quote:Original post by HodgmanTry benchmarking single-threaded VS multi-threaded without the if(num_cores == 1) test/block -- so that the overhead of setting up the job system is included in both benchmarks.This is interesting from a technical perspective, however there are two flaws; 1) Doing it with only 1 core is unlikely to give me reasonable results, due to small sample size and anomolies being too high compared to a single result.2) I'm actually comparing the time taken for the multi core version with the non threaded version.Quote:Also, instead of creating num_cores threads, you want to create num_cores-1 threads and then make use of the existing main-thread. Hmm, this makes sense, what kind of speed gains will this give compared to blocking the main thread in waiting for all 4 worker threads? I cant really measure the difference given only 4 cores, espec. since windows has only a 1ms timer resolution. This particular application is targeting windows (it uses havok for example). Perhaps I should isolate the terrain generation in a cross platform way.Quote:e.g.*** Source Snippet Removed ***[EDIT]Looking at the logic for handling leftovers, won't that cause the 1st/2nd chunks to overlap?i.e.end0 = (generators_per_core + leftovers)start1 = (generators_per_core)end0 can be >= start1Might be better off putting the leftovers on the last thread.Awsome, again, thanks for noticing this mistake. It doesnt manifest with 50x50 sections since 2500 % 4 == 0. I wouldnt have noticed for some time.