ALT Linux Team development discussions
 help / color / mirror / Atom feed
From: Alexey Tourbin <at@altlinux.ru>
To: ALT Linux Team development discussions <devel@lists.altlinux.org>
Subject: Re: [devel] robots VS sisyphus
Date: Tue, 27 Dec 2011 22:53:25 +0400
Message-ID: <20111227185324.GA24119@altlinux.org> (raw)
In-Reply-To: <20111225115528.GA6894@mail.truecrux.org>

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) ядро глючит.


  reply	other threads:[~2011-12-27 18:53 UTC|newest]

Thread overview: 25+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2011-12-23 21:15 Денис Смирнов
2011-12-23 23:17 ` [devel] масштабируемость репозитория Dmitry V. Levin
2011-12-23 23:40   ` Paul Wolneykien
2011-12-24 10:21   ` Денис Смирнов
2011-12-24 13:22     ` Alexei Takaseev
2011-12-24 10:33   ` Igor Vlasenko
2011-12-24 10:41   ` thecrux
2011-12-24 15:08   ` thecrux
2011-12-25 15:03   ` Денис Смирнов
2011-12-26 12:02   ` Michael Shigorin
2011-12-25  4:47 ` [devel] robots VS sisyphus Alexey Tourbin
2011-12-25 11:55   ` thecrux
2011-12-27 18:53     ` Alexey Tourbin [this message]
2011-12-25 14:53   ` Денис Смирнов
2011-12-27 19:29     ` Alexey Tourbin
2011-12-28 16:02       ` [devel] [JT] " Igor Vlasenko
2011-12-26 11:16   ` [devel] " Sergei Epiphanov
2011-12-27 20:09     ` Alexey Tourbin
2011-12-28  7:27       ` Sergei Epiphanov
2011-12-28  7:50         ` [devel] apt performance (was: robots VS sisyphus) Michael Shigorin
2011-12-28  8:43           ` Sergei Epiphanov
2011-12-26 16:42   ` [devel] robots VS sisyphus Dmitry V. Levin
2011-12-27 18:59     ` Alexey Tourbin
2011-12-27 20:55     ` Alexey Tourbin
2011-12-27 23:57       ` Dmitry V. Levin

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=20111227185324.GA24119@altlinux.org \
    --to=at@altlinux.ru \
    --cc=devel@lists.altlinux.org \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link

ALT Linux Team development discussions

This inbox may be cloned and mirrored by anyone:

	git clone --mirror http://lore.altlinux.org/devel/0 devel/git/0.git

	# If you have public-inbox 1.1+ installed, you may
	# initialize and index your mirror using the following commands:
	public-inbox-init -V2 devel devel/ http://lore.altlinux.org/devel \
		devel@altlinux.org devel@altlinux.ru devel@lists.altlinux.org devel@lists.altlinux.ru devel@linux.iplabs.ru mandrake-russian@linuxteam.iplabs.ru sisyphus@linuxteam.iplabs.ru
	public-inbox-index devel

Example config snippet for mirrors.
Newsgroup available over NNTP:
	nntp://lore.altlinux.org/org.altlinux.lists.devel


AGPL code for this site: git clone https://public-inbox.org/public-inbox.git