From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Date: Tue, 27 Dec 2011 22:53:25 +0400 From: Alexey Tourbin To: ALT Linux Team development discussions Message-ID: <20111227185324.GA24119@altlinux.org> References: <20111223211515.GA916@t60p.mithraen.ru> <20111225044735.GA21576@altlinux.org> <20111225115528.GA6894@mail.truecrux.org> Mime-Version: 1.0 Content-Type: text/plain; charset=koi8-r Content-Disposition: inline Content-Transfer-Encoding: 8bit In-Reply-To: <20111225115528.GA6894@mail.truecrux.org> Subject: Re: [devel] robots VS sisyphus X-BeenThere: devel@lists.altlinux.org X-Mailman-Version: 2.1.12 Precedence: list Reply-To: ALT Linux Team development discussions List-Id: ALT Linux Team development discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 27 Dec 2011 18:53:25 -0000 Archived-At: List-Archive: List-Post: 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) ядро глючит.