pthreadクイックソートは放置することに

pthreadでqsortを並列化するのは、やっぱりうまく行かない。joinなしにすると微妙に結果が並びきっていないので、たぶんタイミングの問題だろうと思って、メインスレッドで以下のようにsleep(1)としてみたら、これがきちんとソートされるではないか。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#include <assert.h>
#include <stdbool.h>
#include "psort.h"

int main (int argc, char *argv[]) {
  int size;
  partition p;

/*   if (argc < 1) exit(1); */
/*   size = atoi(argv[1]); */
  size = 10;

  int x[size], i, r; 

  srand(time(NULL));
  for (i = 0; i < size; i++) {
    x[i] = rand() % size;
  }

  show_ary(x, size);
  p.ary = x;
  p.begin = 0;
  p.end = size - 1;
  myqsort(&p);
  sleep(1);
  //    qsort(x, size, sizeof(int), isLarger);
  printf("--sort--\n");
  show_ary(x, size);
}

myqsortの後にsleepがあるかどうかで結果が変わる。ということはやっぱり配列のサブセットに対してソート実行中のスレッドが終わる前にメインスレッドの処理が進んでしまっているということで、これはjoinの問題だとは分かる。

それで以下のように書いてみた。すべての親スレッドは自分が生成した子スレッドについて責任をもってjoinする。「ボス/ワーカー」モデルに対比していえば、「多重請負IT業界スレッド」モデルだ。

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

#define SWAP(type, x, y) do {type tmp = x; x = y; y = tmp;}while(0)

typedef struct {
  int *ary;
  int begin;
  int end;
} partition;

void *myqsort(void *p) {

  pthread_t thread1, thread2; 
  int ret1, ret2;

  partition *part, *pnext;
  part = (partition *)malloc(sizeof(partition));

  part = (partition *)p;

  int left = part->begin;
  int right = part->end;

  if (left >= right) {
    pthread_exit(NULL);
  }

  int pivot = part->ary[(left + right) / 2];
  
  while (1) {
    while(part->ary[left] < pivot) left++;
    while(part->ary[right] > pivot) right--;
    if (left >= right) break;

    SWAP(int, part->ary[left], part->ary[right]);
    left++; right--;
  }

  if (left - part->begin >= 2) {
    pnext = (partition *)malloc(sizeof(partition));
    pnext->ary = part->ary;
    pnext->begin = part->begin;
    pnext->end = left - 1;
    ret1 = pthread_create(&thread1, NULL, myqsort, (void *)pnext);
    if (ret1) exit(1);
  }
  if (part->end - right >= 2) {
    pnext = (partition *)malloc(sizeof(partition));
    pnext->ary = part->ary;
    pnext->begin = right + 1;
    pnext->end = part->end;
    ret2 = pthread_create(&thread2, NULL, myqsort, (void *)pnext);
    if (ret2) exit(1);
  }
  if (ret1 == 0) {
    pthread_join(thread1, NULL);
  }
  if (ret2 == 0) {
    pthread_join(thread2, NULL);
  }
  if ((ret1 == 0) || (ret2 == 0)) free(pnext);
  free(part);
}

int show_ary(int ary[], int size) {
  int i;
  for (i = 0; i < size; i++) {
    printf("%d:", ary[i]);
  }
  printf("\n");
}

しかし、SEGVで落ちる。マルチスレッドのとき、gdbのステップ実行ってどうなるんだ。

% gdb ./psort
GNU gdb 6.8-debian
Copyright (C) 2008 Free Software Foundation, Inc.
License GPLv3+: GNU GPL version 3 or later <http://gnu.org/licenses/gpl.html>
This is free software: you are free to change and redistribute it.
There is NO WARRANTY, to the extent permitted by law.  Type "show copying"
and "show warranty" for details.
This GDB was configured as "i486-linux-gnu"...
(gdb) run
Starting program: /home/ken/src/mysort/psort 
[Thread debugging using libthread_db enabled]
0:9:9:6:4:5:5:4:2:7:
[New Thread 0xb7e096b0 (LWP 12196)]
[New Thread 0xb7e08b90 (LWP 12199)]
[New Thread 0xb7607b90 (LWP 12200)]

Program received signal SIGSEGV, Segmentation fault.
[Switching to Thread 0xb7607b90 (LWP 12200)]
0xb7f60672 in pthread_join () from /lib/tls/i686/cmov/libpthread.so.0
(gdb) where
#0  0xb7f60672 in pthread_join () from /lib/tls/i686/cmov/libpthread.so.0
#1  0x080489cd in myqsort (p=0x804a0c8) at psortlib.c:59
#2  0xb7f5f4fb in start_thread () from /lib/tls/i686/cmov/libpthread.so.0
#3  0xb7ee1e5e in clone () from /lib/tls/i686/cmov/libc.so.6

なるほど、pthread_createは、実際にはLinuxのclone(2)とかを呼んでるらしいことが分かったりしたけど、なんで落ちるのか分からない。配列の要素が10個のときに3つスレッドを生成して落ちている。配列を100個にすると8個のスレッド生成後にSEGV。

しかし、そもそも分割していくたびにスレッドを生成するのは、qsortの並列化手法としてもっともストレートなやり方だとはいえ、スレッド生成のコストからすると、かなりひどいやり方という気がする（いろいろ検索してたら、スレッド生成コストはだいたい2万CPUサイクルだと言ってる人がいた）。特に配列サイズが縮んで行く最後のほうは処理対象量が少ないし。

スレッド数の上限を「プロセッサ数＋1」とかに制限して、スレッドが走っているときには新規スレッド生成ではなく再帰として処理するというようなやり方もあるんだろうか。しかし、それも何だか妙にモデルが複雑な気がする。

もう1つ素直なやり方として、ソート前にまず半分に配列を分けて、それらをパラで処理して、マージソートするという方法もある。

pthread版クイックソートは何が悪いのか分からないけど、これ以上頑張ってもしょうがなさそうなので、とりあえず放置することにした。