Bug 119077

Summary: [patch] sysinstall(8) - reading packages from index is extremely slow
Product: Base System Reporter: Michal Botka <michal.botka>
Component: binAssignee: freebsd-sysinstall (Nobody) <sysinstall>
Status: Closed Overcome By Events    
Severity: Affects Only Me    
Priority: Normal    
Version: Unspecified   
Hardware: Any   
OS: Any   
Attachments:
Description Flags
file.txt none

Description Michal Botka 2007-12-27 21:30:00 UTC 
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.

Fix: We should use some better sorting algorithm. My implementation of quick
sort is attached to this problem report.


Patch attached with submission follows:
Comment 1 Remko Lodder freebsd_committer freebsd_triage 2007-12-28 08:10:16 UTC 
Responsible Changed
From-To: freebsd-bugs->re

Dear Release engineers, I think this is something for you to 
have a look (or someone who dares touching sysinstall ;-))
Comment 2 Mark Linimon freebsd_committer freebsd_triage 2009-03-10 03:41:31 UTC 
Responsible Changed
From-To: re->freebsd-bugs

These days, we don't assign sysinstall PRs to re@.
Comment 3 Gavin Atkinson freebsd_committer freebsd_triage 2010-07-13 14:36:54 UTC 
Responsible Changed
From-To: freebsd-bugs->freebsd-sysinstall

Over to maintainer(s)
Comment 4 Garrett Cooper 2010-07-13 15:52:47 UTC 
I don't think that this algorithm is correct, because instead of
bisecting the set (like quicksort typically does), it's taking the
first element, and then doing a bubble-like sort.

Regardless of the correctness of the algorithm, if one is concerned
about using quicksort, the replacement algorithm should be using qsort
in libc (because it's more tested and most likely more correct).

Thanks,
-Garrett
Comment 5 Enji Cooper freebsd_committer freebsd_triage 2015-11-10 09:07:31 UTC 
sysinstall has been replaced by bsdinstall in FreeBSD 9.x. Closing.
Comment 6 Enji Cooper freebsd_committer freebsd_triage 2015-11-10 09:12:12 UTC 
sysinstall has been replaced by bsdinstall in FreeBSD 9.x. Closing.