bin/119077: sysinstall - reading packages from index is extremely
slow
Michal Botka
michal.botka at seznam.cz
Thu Dec 27 13:30:01 PST 2007
>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:
More information about the freebsd-bugs
mailing list