[devel] robots VS sisyphus

[Alexey Tourbin]

On Sun, Dec 25, 2011 at 03:55:28PM +0400, thecrux на gmail.com wrote:
> On Sun, Dec 25, 2011 at 08:47:36AM +0400, Alexey Tourbin wrote:
> > On Sat, Dec 24, 2011 at 01:15:15AM +0400, Денис Смирнов wrote:
> > > В итоге единственное чем _мешает_ массовый импорт из федоры
> > > пользователям/мантейнерам -- то что наш apt плохо масштабируется. И чем
> > > больше пакетов, тем он тормознее.
> > 
> > Apt масштабируется как O(n), где n - количество пакетов.
> > Кроме того, константа масштабирования очень хорошая: на сервере с 24G RAM
> > все операции апта выполняются менее чем за секунду.  То есть нет такого,
> > что сожрали CPU user time и никакого ответа не дали - дескать подождите ещё.
> 
> Объём памяти большого значения не имеет, а вот потребление CPU user time
> бывает очень серьёзным. Практически на все операции apt потребляет 99%CPU
> 
> $ /usr/bin/time apt-cache search abc > /dev/null 
> 4.54user 1.02system 0:05.57elapsed 99%CPU (0avgtext+0avgdata 291152maxresident)k
> 0inputs+0outputs (0major+7556minor)pagefaults 0swaps

apt-cache search рыскает pkglist файлы в каталоге /var/lib/apt/lists.
Сканирует их в цикле.  Этот поиск заведомо не относится к эффективным.

Алгоритмы разрешения зависимостей, которые выполняются на основной
структуре данных - /var/cache/apt/pkgcache.bin - работают гораздо быстрее.

> Можно даже спалить процессор запустив:
> 
> $ apt-cache search $(perl -e 'print "a "x1025') > /dev/null
> 
> Можно собрать apt с флагом CXXFLAGS=-pg и увидеть, что любимая операция
> apt это сортировка. Кстати, хороший алгоритм сортировки даёт O(n log n)
> в худших случаях, поэтому мне кажется малореалистичной оценка
> масштабируемости apt, как O(n).

Сортировка выполняется только раз (при пересборке кеша), а логарифм растёт
очень медленно.  Физики говоря, что логарифм в первом приближении можно
считать константой.  Вообще, логарифм асимптотически меньше любой степени;
например, O(n log n) < O(n^{1.1}).

Если отвлечься от теории, то нету примера, что апт непропорционально жрёт CPU
user time.  Он иногда жрёт system time, но это потому что у вас 1) большой
репозиторий и 2) ядро глючит.