[Date Prev][Date Next] [Thread Prev][Thread Next] [Date Index] [Thread Index]

Re: Too Many Packages [was Re: Splitting locales...]

On Thu, Oct 05, 2000 at 12:27:39PM -0400, Itai Zukerman wrote:
> > 1. The speed and memory usage of our packaging system is at points linear 
> > or worse with the number of packages.  [...]
> > 3. More packages take up more space in /var/lib/dpkg/ [...]
> Doesn't this indicate broken package management tools?  I mean, if the
> number of packages in Debian increases faster than hardware
> speed/capacity ("linear ... in the number of packages"), we'll be in
> trouble eventually anyway, right?

As I said, this can't be fixed. If you have n packages, files/directories
that have information on each package are going to be O(n) in size. Any
program (dselect, console-apt) that needs to deal with all the packages
is going to take O(n) memory for storage and O(n log n) for sorting the
packages. With brilliant programming, you could get dpkg using b-trees
and stuff to get O(b log n) (where b is the number of packages being
installed or changed), but that's going to be a lot of work with
fragile databases and you're still going to have significant parts that
are O(n). 

It's not a problem of our package tools; it's innate in the problem.
We may be in trouble sometime, but it doesn't mean we should give
up now.

David Starner - dstarner98@aasaa.ofe.org
http/ftp: dvdeug.dhis.org
And crawling, on the planet's face, some insects called the human race.
Lost in space, lost in time, and meaning.
	-- RHPS

Reply to: