読者です 読者をやめる 読者になる 読者になる

qsortを撃墜し(最悪ケースを与え)てみた。

glibcのqsortをターゲットに、クイックソートの最悪ケースO(n^2)を与えてみた。

先日の記事の通り、glibcのqsortはマージソートだが、非常に大きいデータのときはクイックソートを利用するので、そのように仕向けてみた。

実行した結果、約5億バイトの配列が確保され、ソートにかかった時間は以下のようになった。

明らかに最悪ケースである。

環境は

もちろん、別のCライブラリ相手では撃墜できない可能性が高い。


qnighy's
gist: 105860 — Gist

#include <stdio.h>
#include <stdlib.h>
#include <signal.h>
#include <sys/time.h>
#include <unistd.h>
#include <err.h>
#include <errno.h>

static struct timeval starttime, endtime;
static int started = 0;
static void start_timer(void)
{
    if(!started) {
        started = 1;
        gettimeofday(&starttime, NULL);
    }
}
static void end_timer(const char *msg)
{
    if(started) {
        started = 0;
        gettimeofday(&endtime, NULL);
        printf("%s %ldmsecs.\n", msg, (endtime.tv_sec-starttime.tv_sec)*1000+(endtime.tv_usec-starttime.tv_usec)/1000);
    }
}

static int intcmp(const int *a, const int *b)
{
    return (*a == *b) ? 0 : (*a > *b) ? 1 : -1;
}

static void attack_main(size_t memsize, int does_attack)
{
    size_t arysize;
    int *ptr;

    ptr = (int*)malloc(memsize);
    if(ptr) {
        int i;
        printf("safely allocated %d bytes.\n", memsize);
        arysize = (memsize / sizeof(int)) & ~1;
        printf("generating sequences...\n");
        for(i = 0; i < arysize/2; ++i) {
            int nextsize = (i+1)*2;
            int nextmid = (nextsize-1)/2;
            int tmp;
            ptr[i*2] = i;
            ptr[i*2+1] = i;
            if(does_attack) {
                tmp = ptr[nextmid];
                ptr[nextmid] = ptr[i*2];
                ptr[i*2] = tmp;
            }
        }
        printf("sorting...\n");
        start_timer();
        qsort(ptr, arysize, sizeof(int), (int(*)(const void*, const void*))intcmp);
        end_timer("sorted.");
        printf("the first element is:%d\n", ptr[0]);
        free(ptr);
        printf("finished.\n\n");
    } else {
        err(errno,NULL);
    }
}

static void sigint_action(int signum, siginfo_t *info, void *ctx)
{

    end_timer("aborted.");
    exit(1);
}


int main(int argc, char *argv[], char *envp[])
{
    long int phys_pages;
    int pagesize;
    long long int all_memory;
    struct sigaction sa_sigint;

    sa_sigint.sa_sigaction = sigint_action;
    sa_sigint.sa_flags = SA_RESTART | SA_SIGINFO;

    if (sigaction(SIGINT, &sa_sigint, NULL) < 0) {
        err(errno, NULL);
        exit(1);
    }


    srand(2009u);

    phys_pages = sysconf(_SC_PHYS_PAGES);
    pagesize = sysconf(_SC_PAGESIZE);
    all_memory = (long long int)phys_pages*pagesize;
    printf("%ld * %d = %lld;\n", phys_pages, pagesize, all_memory);

    printf("testing phys_pages*pagesize/4 bytes (maybe merge sort in glibc)...\n");
    attack_main((size_t)(all_memory / 4), 0);
    printf("testing phys_pages*pagesize/4 bytes (maybe merge sort in glibc) with ATTACK...\n");
    attack_main((size_t)(all_memory / 4), 1);
    printf("testing phys_pages*pagesize/4 + 10000 bytes (maybe quick sort in glibc)...\n");
    attack_main((size_t)(all_memory / 4 + 10000), 0);
    printf("testing phys_pages*pagesize/4 + 10000 bytes (maybe quick sort in glibc) with ATTACK...\n");
    attack_main((size_t)(all_memory / 4 + 10000), 1);
    return 0;
}
% ./qsattack
516777 * 4096 = 2116718592;
testing phys_pages*pagesize/4 bytes (maybe merge sort in glibc)...
safely allocated 529179648 bytes.
generating sequences...
sorting...
sorted. 37126msecs.
the first element is:0
finished.

testing phys_pages*pagesize/4 bytes (maybe merge sort in glibc) with ATTACK...
safely allocated 529179648 bytes.
generating sequences...
sorting...
sorted. 46724msecs.
the first element is:0
finished.

testing phys_pages*pagesize/4 + 10000 bytes (maybe quick sort in glibc)...
safely allocated 529189648 bytes.
generating sequences...
sorting...
sorted. 39189msecs.
the first element is:0
finished.

testing phys_pages*pagesize/4 + 10000 bytes (maybe quick sort in glibc) with ATTACK...
safely allocated 529189648 bytes.
generating sequences...
sorting...
^Caborted. 507514msecs.