[devel] robots VS sisyphus

[thecrux на gmail.com]

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 $(perl -e 'print "a "x1025') > /dev/null

Можно собрать apt с флагом CXXFLAGS=-pg и увидеть, что любимая операция
apt это сортировка. Кстати, хороший алгоритм сортировки даёт O(n log n)
в худших случаях, поэтому мне кажется малореалистичной оценка
масштабируемости apt, как O(n).

-- 
Vladimir Lettiev aka crux ✉ theCrux на gmail.com