From owner-freebsd-hackers@FreeBSD.ORG  Tue Dec 25 17:02:38 2007
Return-Path: <owner-freebsd-hackers@FreeBSD.ORG>
Delivered-To: freebsd-hackers@freebsd.org
Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:4f8:fff6::34])
	by hub.freebsd.org (Postfix) with ESMTP id DED2F16A419
	for <freebsd-hackers@freebsd.org>; Tue, 25 Dec 2007 17:02:38 +0000 (UTC)
	(envelope-from michal.botka@seznam.cz)
Received: from surf.interdata.cz (surf.interdata.cz [84.244.124.1])
	by mx1.freebsd.org (Postfix) with ESMTP id 6478813C457
	for <freebsd-hackers@freebsd.org>; Tue, 25 Dec 2007 17:02:38 +0000 (UTC)
	(envelope-from michal.botka@seznam.cz)
Received: from [192.168.1.5] (wcbotkova.interdata.cz [84.244.125.178])
	by surf.interdata.cz (8.12.9/8.12.9) with ESMTP id lBPGlkbU023584
	for <freebsd-hackers@freebsd.org>; Tue, 25 Dec 2007 17:47:47 +0100
Message-ID: <47713433.2010303@seznam.cz>
Date: Tue, 25 Dec 2007 17:47:47 +0100
From: Michal Botka <michal.botka@seznam.cz>
User-Agent: Thunderbird 2.0.0.6 (X11/20071022)
MIME-Version: 1.0
To: freebsd-hackers@freebsd.org
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
Subject: sysinstall - index_sort
X-BeenThere: freebsd-hackers@freebsd.org
X-Mailman-Version: 2.1.5
Precedence: list
List-Id: Technical Discussions relating to FreeBSD
	<freebsd-hackers.freebsd.org>
List-Unsubscribe: <http://lists.freebsd.org/mailman/listinfo/freebsd-hackers>, 
	<mailto:freebsd-hackers-request@freebsd.org?subject=unsubscribe>
List-Archive: <http://lists.freebsd.org/pipermail/freebsd-hackers>
List-Post: <mailto:freebsd-hackers@freebsd.org>
List-Help: <mailto:freebsd-hackers-request@freebsd.org?subject=help>
List-Subscribe: <http://lists.freebsd.org/mailman/listinfo/freebsd-hackers>,
	<mailto:freebsd-hackers-request@freebsd.org?subject=subscribe>
X-List-Received-Date: Tue, 25 Dec 2007 17:02:39 -0000

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.