bin/119077: sysinstall - reading packages from index is extremely slow

[Michal Botka]

>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: