Re: Multiple profiles with Guix Home

[zimoun]

On Thu, 05 May 2022 at 21:08, Liliana Marie Prikler <liliana.prikler@gmail.com> 
wrote:
> Am Donnerstag, dem 05.05.2022 um 20:00 +0200 schrieb Maxime Devos:
>
>> That's one method for faster builds, but you'll get even faster
>> builds by also making union-build O(n lg n) instead of O(n²), and the
>> latter optimisation will help everyone and not only Guix Home users.
>
> If that's what you want then go ahead and improve union-build.  Unless
> you add some serious waste that eats up thousands of cycles if supplied
> with no more than three packages, I doubt it has any serious effect on
> my analysis that small n = better.
>
> As for the complexity of the actual implementation, I'm pretty sure
> you'll find it to be n log n in most cases, but I also fear that there
> might be degenerate cases in which the fact that we're reporting errors
> at all leads to a worst case lower bound of O(n²). 
>
>> And the O(n)=O(1) doesn't seem quite right here to me -- individual
>> profiles will be smaller and hence faster, but there will also be
>> _more_ profiles.  Maybe if you sum over the profiles, you'll get to
>> O(n) instead of O(n²) (where n = number of store items in the
>> profiles)
> Again, k(n log n) <= nk log nk, for k >= 1.

Well, I am not sure I understand all the debate here.

Again, without concrete timings, the discussion is purely theoretical.
And from my experience, the update of several profiles at once is
usually much faster that an unique big profile update.  For sure, the
situation is improving with recent work, but still.

Maxime, assuming the user has {n_i} packages for i in {1,..,k} profiles,
i.e., a total of N = sum n_i packages.  If the installation, update or
any other operation on one profile has the cost f(n) for n package in
this very same profile, then the comparison becomes

    sum f(n_i)
vs
    f(sum n_i)

and thus –except special cases for the ’f’ cost– considering the most
probable non-linear shapes of ’f’, multi-profile is always better.

(Note that this ’f’ probably depends on the set of packages, so it is
even more complicated, IMHO)


Now, assume the user has, in average, n packages per profile.
Therefore, it becomes,

    k f(n)
vs
    f(k n)

and if f(n) = n log n, then it becomes,

    k n log n
vs
    k n (log n + log k)

and thus, Liliana, in this very specific case of complexity – probably
not the real one –, the pragmatical question is ’n’ vs ’k’ vs the hidden
constant (for all the IO).



Again, I miss the debate. :-)


Cheers,
simon