Fast Multiplication of Large Permutations for Disk, Flash Memory and RAM
Permutation multiplication (or permutation composition) is perhaps the simplest of all algorithms in computer science. Yet for large permutations, the standard algorithm is not the fastest for disk or for flash, and surprisingly, it is not even the fastest algorithm for RAM on recent multi-core CPUs. On a recent commodity eight-core machine the authors demonstrate a novel algorithm that is 50% faster than the traditional algorithm, along with strong evidence that it will be up to twice as fast on future many-core computers. For larger permutations on flash or disk, the novel algorithm is orders of magnitude faster.