From owner-freebsd-bugs@FreeBSD.ORG Thu Dec 27 21:30:01 2007 Return-Path: Delivered-To: freebsd-bugs@hub.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:4f8:fff6::34]) by hub.freebsd.org (Postfix) with ESMTP id 0F6AA16A41B for ; Thu, 27 Dec 2007 21:30:01 +0000 (UTC) (envelope-from gnats@FreeBSD.org) Received: from freefall.freebsd.org (freefall.freebsd.org [IPv6:2001:4f8:fff6::28]) by mx1.freebsd.org (Postfix) with ESMTP id E9B4313C4D5 for ; Thu, 27 Dec 2007 21:30:00 +0000 (UTC) (envelope-from gnats@FreeBSD.org) Received: from freefall.freebsd.org (gnats@localhost [127.0.0.1]) by freefall.freebsd.org (8.14.2/8.14.2) with ESMTP id lBRLU0iK004449 for ; Thu, 27 Dec 2007 21:30:00 GMT (envelope-from gnats@freefall.freebsd.org) Received: (from gnats@localhost) by freefall.freebsd.org (8.14.2/8.14.1/Submit) id lBRLU02G004444; Thu, 27 Dec 2007 21:30:00 GMT (envelope-from gnats) Resent-Date: Thu, 27 Dec 2007 21:30:00 GMT Resent-Message-Id: <200712272130.lBRLU02G004444@freefall.freebsd.org> Resent-From: FreeBSD-gnats-submit@FreeBSD.org (GNATS Filer) Resent-To: freebsd-bugs@FreeBSD.org Resent-Reply-To: FreeBSD-gnats-submit@FreeBSD.org, Michal Botka Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:4f8:fff6::34]) by hub.freebsd.org (Postfix) with ESMTP id 508B416A421 for ; Thu, 27 Dec 2007 21:28:31 +0000 (UTC) (envelope-from nobody@FreeBSD.org) Received: from www.freebsd.org (www.freebsd.org [IPv6:2001:4f8:fff6::21]) by mx1.freebsd.org (Postfix) with ESMTP id 4976613C465 for ; Thu, 27 Dec 2007 21:28:31 +0000 (UTC) (envelope-from nobody@FreeBSD.org) Received: from www.freebsd.org (localhost [127.0.0.1]) by www.freebsd.org (8.14.2/8.14.2) with ESMTP id lBRLRrp3021129 for ; Thu, 27 Dec 2007 21:27:53 GMT (envelope-from nobody@www.freebsd.org) Received: (from nobody@localhost) by www.freebsd.org (8.14.2/8.14.1/Submit) id lBRLRr8h021128; Thu, 27 Dec 2007 21:27:53 GMT (envelope-from nobody) Message-Id: <200712272127.lBRLRr8h021128@www.freebsd.org> Date: Thu, 27 Dec 2007 21:27:53 GMT From: Michal Botka To: freebsd-gnats-submit@FreeBSD.org X-Send-Pr-Version: www-3.1 Cc: Subject: bin/119077: sysinstall - reading packages from index is extremely slow X-BeenThere: freebsd-bugs@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Bug reports List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 27 Dec 2007 21:30:01 -0000 >Number: 119077 >Category: bin >Synopsis: sysinstall - reading packages from index is extremely slow >Confidential: no >Severity: non-critical >Priority: low >Responsible: freebsd-bugs >State: open >Quarter: >Keywords: >Date-Required: >Class: sw-bug >Submitter-Id: current-users >Arrival-Date: Thu Dec 27 21:30:00 UTC 2007 >Closed-Date: >Last-Modified: >Originator: Michal Botka >Release: 6.2 >Organization: >Environment: >Description: I installed FreeBSD from bootonly cd and then I tried to install some packages by sysinstall from FTP mirror. It took about 6 minutes to read index on my computer (Pentium II 350Mhz, 128MB). There is about 15.000 packages and used sorting algorithm - bubble sort - is ineffective. See function index_sort in file usr.sbin/sysinstall/index.c. >How-To-Repeat: >Fix: We should use some better sorting algorithm. My implementation of quick sort is attached to this problem report. Patch attached with submission follows: 418c418,456 < /* Use a disgustingly simplistic bubble sort to put our lists in order */ --- > /* 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; > int size1, size2; > char* pivotName; > > size1 = 0; > size2 = 0; > pivotName = first->name; > 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 { > size2++; > } > } > 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 */ 425,430c463 < 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); < } < } --- > index_list_qsort(top->kids, NULL); 434,435c467,469 < if (p->kids) < index_sort(p); --- > if (p->kids) { > index_sort(p); > } >Release-Note: >Audit-Trail: >Unformatted: