Wakeup alarm?

[n0dalus]

On 2/11/07, dragoran <drago01 at gmail.com> wrote:
> a better solution is to speed up the depsolving process somehow.
> maybe doing it with a plugin which is written in C like the metadata
> parser would help?

One thing that would really help, regardless of programming language
(though C would be much faster), is to provide a "summary" of
dependency relationships between packages on the discs.

It would be in a small, separate file. A simple binary format would
make it very small for fitting into memory uncompressed (though it's
not necessary). To save space, packages should be referred to by an
indexing system (integer numbers) and not by name -- this could
improve efficiency in other parts of the installer too, so a
centralized lookup table should be there if it's not already.
- The first thing it would have is a pre-computed installation order
for the (very) minimal installation. For this subset of packages the
installer should be doing no dep-checking, and it should be the first
things installed (and on the first disc).
- Packages which only rely on the minimal set are then listed in the
file. The installer can now install any of these at any time without
dep-solving.
- The rest of the dependencies are then listed, in an installable
order, for every package.

For example:
The bare minimum install has the packages: A, B and C.
There are also packages: D, E, F, G, H, I, J, K and L.
Dependencies are as follows:
A < B  (this means B depends on A)
A < C
B < D
C < D
A < E
A < F
C < F
A < G
D < G
F < H
G < H
K < H
J < I
E < J
I < K

The above dependencies can now be "summarized" (note that all these
should be sets of indexes, not package names as shown here):
A,B,C (installed first and in this order -- no dep checking needed)
D,E,F (can be installed at any time without dep checking)
D < G
D,E,F,G,J,I,K < H (note order is already worked out)
E,J < I
E < J
E,J,I < K

The installer would go through and use a process something like this
(some of this could likely be futher optimized, but keeping it simple
for now).

Pseudocode:
#define n (KNOWN_PACKAGES-MIN_INSTALL_PACKAGES)
int wanted_packages[];
bool installing[n] = { false, false, ... };
int install_order[n];
int i = 0;
for(wanted_package in wanted_packages) {
  /* Gets install list from summary file
     This should offset indexes so package 0
     the first package not in min install */
  int install_list[] = get_install_list(wanted_package);
  for(package in install_list) {
    if(!installing[package]) {
      install_order[i++] = package + MIN_INSTALL_PACKAGES;
      installing[package] = true;
    }
  }
}
min_install();
install_packages(install_order);

I don't know how different this is from what the installer already
does, but I'd be interested to see how much it could be improved.

n0dalus.