Re: bogosort (was Re: Re: [RFC][PATCH -mm 5/6] Freezer: Use freezing timeout more efficiently)

Rafael J. Wysocki
2007-07-10T22:07:34Z

On Tuesday, 10 July 2007 23:39, Pavel Machek wrote:
> Hi!
>
> > > Task here is to sort the tasks, and freeze them in such order that
> > > freezing works, right? Yep, we do not know the dependencies
> > > explicitely... but what you invented is bogosort.
> >
> > Define, please?
>
> Uff, sorry. http://en.wikipedia.org/wiki/Bogosort .

So this thing is not bogosort, because it makes the tasks that haven't frozen
appear on the bottom. IOW, the first (failing) freezing attempt is used as
a sieve, so the process is not completely random.

This actually is important, because the things like FUSE should be taken
care of within a couple of iterations.

> > > Yes, it does increase chance that freezing succeeds, but I do not
> > > think increase of chance is worth having bogosort in tree :-).
> >
> > Well. Do you think it's better to uselessly wait for 20s?
>
> I'd prefer not to add more randomness in the process. If we have
> freezing failure in 10% cases now, 2 retries will make it 1%... that
> will be ugly to debug...

No more ugly then it's now, I'd say ...

> Hmm, if someone wants to retry... perhaps we should just return
> specific error and let the _userland_ do the retries? It can do it as
> efficiently as outer loop in freezer...

No, because _that_ would be bogosort, as defined in Wikipedia. :-)

Greetings,
Rafael

--
"Premature optimization is the root of all evil." - Donald Knuth