Re: кто кого победит?
On Wed, Oct 14, 2009 at 01:13:47PM +0400, Иван Лох wrote:
> On Wed, Oct 14, 2009 at 05:24:41AM +0400, Prokofyev Vladislav wrote:
> > >>>>>
> > >>>>
> > >>>> http://ck.kolivas.org/patches/bfs/
> > >
> >
> > posix@callisto:~$ cat /proc/cpuinfo
> > processor : 0
> > vendor_id : AuthenticAMD
> > cpu family : 6
> > model : 10
> > model name : AMD Athlon(tm) XP 2500+
> >
> > это мой десктоп, настолько быстрый, что стыдно даже. по ссылке, которую я
> > выше указал, перейдите.
>
> BFS в принципе не может дать никаких преимуществ на одноядерном процессоре.
> Это и автор признает.
Из авторского описания я этого не вычитал, правда смотрел
по-диагонали. Там наоборот сказано, что BFS не масштабируется на
системы с большим количеством процессоров и/или большой нагрузкой.
Из исходников видно, что алгоритм сильно отличается от того, что в
майнлайн: простая O(N) глобальная очередь на выполнение; фиксированные
таймслайсы независимо от приоритета; с каждой задачей связано значение
deadline (для более приоритетных задач оно меньше и они с большей
вероятностью получают квант времени).
--
Stanislav
Reply to: