Date: Thu, 27 Dec 2007 21:27:53 GMT From: Michal Botka <michal.botka@seznam.cz> To: freebsd-gnats-submit@FreeBSD.org Subject: bin/119077: sysinstall - reading packages from index is extremely slow Message-ID: <200712272127.lBRLRr8h021128@www.freebsd.org> Resent-Message-ID: <200712272130.lBRLU02G004444@freefall.freebsd.org>
next in thread | raw e-mail | index | archive | help
>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:
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?200712272127.lBRLRr8h021128>