c++ - Parallelized quicksort in C++11 randomly crashes -
i writing quicksort in c++ , works fine, when try make use multiple threads (with c++11 threading) randomly crashes. says "terminate called without active exception" or "pure virtual method called" or crashes without error message. more threads use more crashes.
could tell me did wrong? using mingw x64-4.8.1-release-posix-seh-rev5 -ofast optimization flag.
template<class t> t partition(t begin, t end, t pivot){ t result_pivot; std::swap(*pivot, *(end - 1)); /* puts pivot end */ pivot = end - 1; t it_right = end - 1; /* starts searching item left bigger pivot */ for(t it_left = begin; it_left < it_right; ++it_left){ if(*pivot <= *it_left){ while(*(--it_right) > *pivot && it_right != it_left) /* empty - searches item smallar pivot right */ ; if(it_right != it_left){ /* if such item found , pointers not meet swap them */ std::swap(*it_right, *it_left); } else break; /* if pointers meet, stop */ } } /* puts pivot , returns pivot */ std::swap(*pivot, *it_right); return it_right; } struct running_threads { int max_threads = 8;//std::thread::hardware_concurrency(); std::mutex mutex; int num_of_threads = 1; void operator++(){ mutex.lock(); ++num_of_threads; mutex.unlock(); } void operator--(){ mutex.lock(); --num_of_threads; mutex.unlock(); } } thr; template<class t> void swap_quick_sort(t begin, t end){ size_t size = end - begin; /* stopping criteria */ if(size <= 3){ if(size == 3) order3(begin[0], begin[1], begin[2]); else if(size == 2 && begin[0] > begin[1]) std::swap(begin[0], begin[1]); return; } /* pivot median of first, middle , last item */ t pivot = median(begin, begin + size/2, begin + size - 1); t result_pivot = partition(begin, end, pivot); /* since creating/joining threads slow, create new thread when array big enough */ if(size > 30000 && thr.num_of_threads < thr.max_threads){ std::thread a(swap_quick_sort<t>, begin, result_pivot); ++thr; swap_quick_sort(result_pivot + 1, end); a.join(); --thr; } else { swap_quick_sort(begin, result_pivot); swap_quick_sort(result_pivot + 1, end); } } template<class t> void order3(t& a, t& b, t& c){ if (a <= b && <= c){ if (b > c) std::swap(c, b); } else if(b <= && b <= c) if (a <= c) std::swap(a, b); else { std::swap(a, b); std::swap(b, c); } else if (a <= b){ std::swap(a, c); std::swap(b, c); } else std::swap(a, c); } template<class t> t median(t a, t b, t c){ if (*a <= *b && *a <= *c){ if (*b <= *c) return b; else return c; } else if(*b <= *a && *b <= *c){ if (*a <= *c) return a; else return c; } else if(*a <= *b) return a; else return b; }
in main function call vector of random elements.
Comments
Post a Comment