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.
_______________________________________________
freebsd-hackers@freebsd.org mailing list
http://lists.freebsd.org/mailman/listinfo/freebsd-hackers
To unsubscribe, send any mail to "[EMAIL PROTECTED]"
