私は 2007 年夏頃の MacBook Pro (x86-64) を 32KB L1 (私が思うに)、4MB L2、および 4GB RAM で使用しています。OS X 10.6.8 を実行しています。
私は C++ で標準の基数ソートを作成しています。これは、ある配列から別の配列にコピーし、ソート時に再び元に戻します (したがって、使用されるメモリは配列のサイズの 2 倍になります)。「。」を印刷して監視します。100 万件のエントリが移動しました。
アレイが最大で 750 MB の場合、これらのドットは通常非常に速く移動します。ただし、アレイが大きい場合、プロセス全体がクロールして停止します。ブロックで 512 MB を基数ソートしてから、ブロックをマージソートしようとすると、最初のブロックが高速になり、プロセスが再びクロールして停止します。つまり、私のプロセスはソートに 1.5 GB の RAM しか使用できないようです。奇妙なのは、4 GB の物理 RAM があることです。
8 GB の配列を割り当てて、各バイトを書き込んで '.' を印刷してみました。100 万バイトごと。すべてが 1.5 GB あたりで遅くなり始め、4 GB を過ぎてもその速度を維持しているように見えますが、ディスクに移動する必要があることがわかっています。そのため、OS は約 1.5 GB のページをディスクに書き込み始めます。
マシンを使用して大きな配列をソートしたいと考えています。少なくとも 3.5 GB の RAM をプロセスに与えるように OS に指示するにはどうすればよいですか? mlock() を使用してみましたが、さらに遅くなるようです。アイデア？