Skip site navigation (1)Skip section navigation (2) 
Date:      Tue, 25 Dec 2007 17:47:47 +0100
From:      Michal Botka <michal.botka@seznam.cz>
To:        freebsd-hackers@freebsd.org
Subject:   sysinstall - index_sort
Message-ID:  <47713433.2010303@seznam.cz>
next in thread | raw e-mail | index | archive | help 
Hello,
I downloaded 6.2-RELEASE-i386-bootonly.iso and installed FreeBSD from 
FTP server. After then I tried install some packages by sysinstall, but 
reading package data from index was extremely slow. It took more then 6 
minutes on my computer (Pentium II 350MHz, 128MB RAM).

I downloaded sysinstall source, in file index.c, on line 418 there is 
following code:

/* Use a disgustingly simplistic bubble sort to put our lists in order */
void
index_sort(PkgNodePtr top)
{
    PkgNodePtr p, q;

    /* Sort everything at the top level */
    for (p = top->kids; p; p = p->next) {
    for (q = top->kids; q; q = q->next) {
        if (q->next && strcmp(q->name, q->next->name) > 0)
        swap_nodes(q, q->next);
    }
    }

    /* Now sub-sort everything n levels down */   
    for (p = top->kids; p; p = p->next) {
    if (p->kids)
        index_sort(p);
    }
}


There is about 15000 packages in index, so it's clear why it was so 
slow. I implemented quick sort algorithm and after then it took only 
about 6 seconds. My code (new function index_list_qsort and modified 
function index_sort):

/* Quick sort algorithm */
void
index_list_qsort(PkgNodePtr first, PkgNodePtr stop)
{
    // empty or one-item list is already sorted
    if (first == stop || first->next == stop)
        return;
   
    // quick sort
    PkgNodePtr i, p;
    char* pivotName = first->name;
    int size1 = 0;
    int size2 = 0;
    for (p=first, i=p->next; i!=stop; i=i->next) {
        if (strcmp(i->name, pivotName)<0) {
            p = p->next;
            swap_nodes(p,i);
            size1++;
        } else {
            size1++;
        }
    }
    swap_nodes(first,p);
   
    // we handle the shorter part before the longer
    // recursion depth never exceeds logarithm of the total list length
    if (size1 <= size2) {
        index_list_qsort(first,p);
        index_list_qsort(p->next,stop);
    } else {
        index_list_qsort(p->next,stop);
        index_list_qsort(first,p);
    }
}

/* Use a quick sort to put our lists in order */
void
index_sort(PkgNodePtr top)
{
    PkgNodePtr p, q;

    /* Sort everything at the top level */
    index_list_qsort(top->kids, NULL);

    /* Now sub-sort everything n levels down */   
    for (p = top->kids; p; p = p->next) {
    if (p->kids)
        index_sort(p);
    }
}


I'm just a newbie and know nothing about FreeBSD, but I will be glad if 
my code will be helpful.

Yours sincerely,
Michal Botka.

Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?47713433.2010303>