pipeline？

最近の CPU で Bubble Sort をする場合、ランダムな配列より逆順に並んだ配列のソートの方が早いという話を聞いたので試したみた。

#include <iostream>
#include <limits>
#include <utility>
#include <vector>
#include <algorithm>
#include <boost/random/mersenne_twister.hpp>
#include <boost/random/uniform_int.hpp>

#include <ctime>

template<typename T>
void bubble_sort(T begin, T end)
{
    typedef typename std::iterator_traits<T>::difference_type size_type;
    size_type size = std::distance(begin, end);
    T a = begin;

    for (size_type i = 0; i < size - 1; ++i) {
        for (size_type j = 0; j < size - i - 1; j++) {
            if (a[j] > a[j + 1]) std::swap(a[j], a[j + 1]);
        }
    }
}

template<typename T>
void measure(T begin, T end)
{
    clock_t t1 = clock();
    bubble_sort(begin, end);
    clock_t t2 = clock();

    std::cout << static_cast<double>(t2 - t1) / CLOCKS_PER_SEC << std::endl;
}

#define ARRAY_SIZE 20000

int main()
{
    std::vector<int> a(ARRAY_SIZE);
    std::vector<int> b(ARRAY_SIZE);
    boost::uniform_int<int> r(std::numeric_limits<int>::min(), std::numeric_limits<int>::max());
    boost::mt19937 mt(0);

    typedef std::vector<int>::iterator iterator;

    for (iterator it = a.begin(), end = a.end(); it != end; ++it) {
        *it = r(mt);
    }

    std::copy(a.begin(), a.end(), b.begin());
    std::sort(b.begin(), b.end(), std::greater<int>());

    measure(a.begin(), a.end());
    measure(b.begin(), b.end());

    return 0;
}

Pentium 4 2.4GHz で実行。

% g++ -W -Wall -O3 bubble_sort.cpp -o bubble_sort

% ./bubble_sort
1.35
0.61

おぉ、本当だ。逆順に整列した配列の方が交換回数が多いはずだが、そんなのを吹き飛ばすぐらい投機実行が効いているということか？
どうせなので Java でもやってみる。

import java.util.Arrays;
import java.util.Random;

public class BubbleSort {
    public static final void bubbleSort(int[] a) {
        int length = a.length;
        for (int i = 0; i < length - 1; i++) {
            for (int j = 0; j < length - i - 1; j++) {
                if (a[j] > a[j + 1]) {
                    int tmp = a[j];
                    a[j] = a[j+1];
                    a[j+1] = tmp;
                }
            }
        }
    }

    public static final void measure(int[] a) {
        long start = System.currentTimeMillis();
        bubbleSort(a);
        long end = System.currentTimeMillis();
        System.out.println(end - start);
    }

    public static void main(String[] args) {
        final int ARRAY_SIZE = 20000;
        Random random = new Random();

        int[] a = new int[ARRAY_SIZE];
        int[] b = new int[ARRAY_SIZE];
        for (int i = 0; i < ARRAY_SIZE; i++) {
            a[i] = random.nextInt();
        }

        System.arraycopy(a, 0, b, 0, ARRAY_SIZE);
        Arrays.sort(b);
        b = reverse(b);

        measure(a);
        measure(b);
    }

    private static int[] reverse(int[] a) {
        int[] b = new int[a.length];
        for (int i = 0; i < a.length; i++) {
            b[b.length - i - 1] = a[i];
        }
        return b;
    }
}

% java -version
java version "1.5.0_06"
Java(TM) 2 Runtime Environment, Standard Edition (build 1.5.0_06-b05)
Java HotSpot(TM) Client VM (build 1.5.0_06-b05, mixed mode, sharing)

% javac -O BubbleSort.java

% java -server BubbleSort
1451
439

% java -client BubbleSort
1959
1589

Server VM ならかなり差がでる。関係ないけど、Server VM の方は C++ と遜色ない速度が出ている。実験もせずに Java が遅いとかいっているやつは腹を(ry
スクリプト言語は大差はつかないと思うが、一応 Perl も。

use strict;
use warnings;
use Benchmark;

sub bubble_sort {
    my ($a) = @_;

    for my $i ( 0 ... ( @$a - 2 ) ) {
        for my $j ( 0 ... ( @$a - $i - 2 ) ) {
            if ( $a->[$j] > $a->[ $j + 1 ] ) {
                my $tmp = $a->[$j];
                $a->[$j] = $a->[ $j + 1 ];
                $a->[ $j + 1 ] = $tmp;
            }
        }
    }
}


my $size = 5000;
my @a;
for ( 0 ... $size ) {
    push @a, rand;
}

my @b = reverse sort @a;

timethese(1, {
    random => sub { bubble_sort(\@a) },
    reverse_sorted => sub { bubble_sort(\@b) }
});

% perl bubble_sort.pl
Benchmark: timing 1 iterations of random, reverse_sorted...
sorted
    random:  7 wallclock secs ( 6.70 usr +  0.00 sys =  6.70 CPU) @  0.15/s (n=1)
            (warning: too few iterations for a reliable count)
sorted
reverse_sorted:  7 wallclock secs ( 6.71 usr +  0.00 sys =  6.71 CPU) @  0.15/s (n=1)
            (warning: too few iterations for a reliable count)

やっぱ変わんないね。
凡ミスしてた。こっちが本来の結果。

% perl bubble_sort.pl
Benchmark: timing 1 iterations of random, reverse_sorted...
    random: 16 wallclock secs (16.18 usr +  0.00 sys = 16.18 CPU) @  0.06/s (n=1)
            (warning: too few iterations for a reliable count)
reverse_sorted: 26 wallclock secs (25.25 usr +  0.00 sys = 25.25 CPU) @  0.04/s (n=1)
            (warning: too few iterations for a reliable count)

スクリプト言語なら単純に交換回数が多いほうが不利。