挿入ソートの話のまとめ

gcc4.3 -O3 on Atom, N=10000の条件で挿入ソートを測った結果(ソースコードは下に)。所要時間(time)を測っただけでは振る舞いが掴めないので、cachegrindでD1キャッシュ読み回数(D1read)を数えてみた。

関数	メモリ	time	D1read
yane0	malloc	9.79	62M
wkpd0	malloc	9.82	27M
yane1	static	8.09	27M
wkpd1	static	11.35	28M

大規模なソートということでmallocで確保したメモリをソートする場合、最適化がよく効いている限り、どちらもほぼ同等の速度で動くようだ。
ただし、やね版はstaticに確保したメモリをソートする場合、Wikipedia版よりも約3割速く動いた。ほぼ本人の言っている通りの成績だ。

〆。

とはいえ、jのオフセットや番兵のありなしで20%くらい揺らぐのも事実。要素数によっても要素サイズによってもCPUによってもコンパイラによっても簡単に変わる話なので、両方実装して速度を比較しないと判断できない、といったところだろうか。
あと、iccではWikipedia版の方が速い、というより、iccではやね版が妙に遅い、という傾向がある。オプション調整で速くなるのかもしれないけれど試さない。

ソース。

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

void yaneurao_ins_sort_000(int data[], size_t const size) {
  int i, j, tmp;
  for (i = 1; i < size; ++i) {
    tmp = data[i];
    if (data[i-1] > tmp) {
      j = i;
      do {
        data[j] = data[j-1];
        --j;
      } while (j > 0 && data[j-1] > tmp);
      data[j] = tmp;
    }
  }
}

void wikipedia_ins_sort_000(int data[], size_t const size) {
  int i, j, tmp;
  for (i = 1; i < size; ++i) {
    tmp = data[i];
    for (j = i; j > 0 && data[j-1] > tmp; j--) {
      data[j] = data[j-1];
    }
    data[j] = tmp;
  }

}

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

#define MAX 100000
static int local[MAX];

void yaneurao_ins_sort_001(int const orig[], size_t const size) {
  int i, j, tmp;
  if (MAX < size) {
    return;
  }
  memcpy(local, orig, size*sizeof(int));
  for (i = 1; i < size; ++i) {
    tmp = local[i];
    if (local[i-1] > tmp) {
      j = i;
      do {
        local[j] = local[j-1];
        --j;
      } while (j > 0 && local[j-1] > tmp);
      local[j] = tmp;
    }
  }
}

void wikipedia_ins_sort_001(int const orig[], size_t const size) {
  int i, j, tmp;
  if (MAX < size) {
    return;
  }
  memcpy(local, orig, size*sizeof(int));
  for (i = 1; i < size; ++i) {
    tmp = local[i];
    for (j = i; j > 0 && local[j-1] > tmp; j--) {
      local[j] = local[j-1];
    }
    local[j] = tmp;
  }
}

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <time.h>

extern void yaneurao_ins_sort_000(int data[], size_t const size);
extern void wikipedia_ins_sort_000(int data[], size_t const size);
extern void yaneurao_ins_sort_001(int const data[], size_t const size);
extern void wikipedia_ins_sort_001(int const data[], size_t const size);

int main (int argc, char *argv[]) {
  int i, loop, size;
  clock_t start, stop;

  if (argc < 3) {
    return -1;
  }
  loop = atoi(argv[1]);
  size = atoi(argv[2]);

  int *orig = malloc(size*sizeof(int));
  int *data = malloc(size*sizeof(int));
  
  srand(0xdeadbeef);
  for (i = 0; i < size; ++i) {
    orig[i] = rand();
  }

  start = clock();
  for (i = 0; i < loop; ++i) {
    memcpy(data, orig, size*sizeof(int));
    yaneurao_ins_sort_000(data, size);
  }
  stop = clock();
  for (i = 1; i < size; ++i) {
    if (data[i] < data[i-1]) {
      puts("ERROR!");
    }
  }
  printf("%f\n", (stop-start)*1E-6);

  start = clock();
  for (i = 0; i < loop; ++i) {
    memcpy(data, orig, size*sizeof(int)); 
    wikipedia_ins_sort_000(data, size);
  }
  stop = clock();
  for (i = 1; i < size; ++i) {
    if (data[i] < data[i-1]) {
      puts("ERROR!");
    }
  }
  printf("%f\n", (stop-start)*1E-6);

  start = clock();
  for (i = 0; i < loop; ++i) {
    yaneurao_ins_sort_001(orig, size);
  }
  stop = clock();
  printf("%f\n", (stop-start)*1E-6);

  start = clock();
  for (i = 0; i < loop; ++i) {
    wikipedia_ins_sort_001(orig, size);
  }
  stop = clock();
  printf("%f\n", (stop-start)*1E-6);

  free(data);
  free(orig);

  return 0;
}

CC     = gcc
CFLAGS = -O3
#CC     = icc
#CFLAGS = -O3

all:a.out
	./a.out 100000000 10
	./a.out 1000000 100
	./a.out 10000 1000
	./a.out 100 10000
	./a.out 1 100000

cg:a.out
	valgrind --tool=cachegrind ./a.out 1000000 10
	valgrind --tool=cachegrind ./a.out 10000 100
	valgrind --tool=cachegrind ./a.out 100 1000
	valgrind --tool=cachegrind ./a.out 1 10000
	find . -name 'cachegrind.out.*' -exec cg_annotate {} \;

clean:
	${RM} *.out *.o
	${RM} cachegrind.out.*

.c.o:
	${CC} -c ${CFLAGS} $?

a.out:extern.o sort_000.o sort_001.o
	${CC} ${CFLAGS} extern.o sort_000.o sort_001.o -o $@