parallel quicksort boost :: thread

Question

私はクイックソートアルゴリズムのインプレース実装を書いており、それは美しく実行されました（1024要素で0.8ms）。私はboost :: threadを使って試してみたので、複数のスレッドで実装した方が速く実行できると思っていましたが、リストは完全にソートされましたが、私のシーケンシャルバージョン（1539.3ms）よりも1500倍も長くかかりました。私はさまざまな数にスレッドの数を制限しようとしましたが、何もそれは元のバージョンと同じくらい速くするように見えませんでした。これがなぜこのように思われるのでしょうか？誰かが正常にインプレースクイックソートを実装していますか？アドバイスの

Answer 1

一般作品：

• 小さなワークロードを並列化しないでください、それは動作しませんが（ちょうどあなたの8ミリ秒にそれを比較し、試してみて、どのくらいのOSは、新しいスレッドを作成するために取るん測ります）。あなたはそのコストを過小評価しています。
  • それぞれのスレッドにはまだ大きな作業負荷が必要です。そうでなければシングルスレッドに戻ってください。
• 可能であればをロックしないでください。。ロックすると、CPUに何もしない機会が与えられます。
• 異なるスレッドでデータを共有しないでください。それはありません：「クローズ」は、メモリ内のデータにアクセスしないでください
• • は、最初の書き込みのため、同じデータにアクセスしない（決して）（フォルス・シェアリング効果）
• タスク・ライブラリーを使用しますスレッドの代わりに（boost.threadpool私は好きな人がいますが、ほかにも同じように良い人がいます）。
  • 彼らは（あなたがハイパースレッディングまたは類似を持っている場合は論理プロセッサ）を使用すると、プロセッサを持っているよりも多くのスレッドを実行しないでください、より多くの仕事
• を待っている、作成されたスレッドを殺してはいけません。
• CPUアフィニティを使用して、指定されたコアのスレッドをロックします（使用するOSによって異なります）。

EDIT：1000は本当に小さなあるので、100万個の要素または何かをしてみてください。次に、スレッドごとの効率曲線と配列のサイズを描きます。