From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.1 (2015-04-28) on sa.local.altlinux.org X-Spam-Level: X-Spam-Status: No, score=-2.0 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FROM autolearn=ham autolearn_force=no version=3.4.1 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=date:from:to:subject:message-id:mime-version:content-disposition :content-transfer-encoding:user-agent; bh=iPpNct3W0hSNJEMbkBKT2haX0txxidRSt5Hj7HGI2k4=; b=eL9mbTfUbgZT4Z52iIchWGKMYvKk4W9N3DpoBLvrnJSTcU3kZc/WnRCB8XmQ4o5/os DDr/OdVgiAnvBXTs2SovGZr2qlxWo5IpbeobeAWtBE0ZQwk2vDcypAgaVLybgRPwZkJD ZX6/eHGB0JLtKyGAZDmMpZyQfcR27Vivwh2jTinMMUFqDYkpSJyuEvYrreFVa1N2cdNH eDau526DUuWersPzOuv+nu3VELeUvxOMt1PmJxvbKre5dxjU6+bSjEcjyTHJOOpD0PHX 1YjZOTu5jBzj6L1+JBP1IWi/h5qzUxxEim4BjkNagV/uMZ0S0quH2PhoWrkT8PiL+phR 58FQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:date:from:to:subject:message-id:mime-version :content-disposition:content-transfer-encoding:user-agent; bh=iPpNct3W0hSNJEMbkBKT2haX0txxidRSt5Hj7HGI2k4=; b=oYwyfFFQUHiLZAZPHe/I9b0jw4QkAY80cYJaHmDuwgz3PH7DbMxvztZI6/f7YkCfpT DBi8IAMkbStvz0trZsQFMLTntOSLr9NbiyvlAuHVu8amvdypgE5vVBjrXk4ai36TYggt 7ZANPplSi8t+FjyfMsTda/OE/hh04cUP9qiG6LY/g79lWm2Trghmd1o3yH0tOy9ujMJ4 Vutr1yTLzK0Kqs3e3u+d/Flvm9fPM/heB57iNbzI93wUKv7FQuPdEOogbsrahrjPKSPc vNDxcuJ9EYHTOS8r5LfW5lS8ckJXzK70iPjONS9avMpXbSCH2V8T9YxaqOKf+dPJLpjy V6RQ== X-Gm-Message-State: AODbwcD1q/YJSNHp7/ZXVCvMAqIBh49BrFt8RdvyfR1fyOSiHFFd8L2N zWWNLPwmEXwZXGjm X-Received: by 10.25.19.169 with SMTP id 41mr5690614lft.65.1496140291243; Tue, 30 May 2017 03:31:31 -0700 (PDT) Date: Tue, 30 May 2017 13:31:28 +0300 From: Alexey Tourbin To: devel@lists.altlinux.org Message-ID: <20170530103128.GA27102@celery> MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Disposition: inline Content-Transfer-Encoding: 8bit User-Agent: Mutt/1.6 (2015-08-30) X-Mailman-Approved-At: Tue, 30 May 2017 13:46:20 +0300 Subject: [devel] =?utf-8?b?0YPQtNCy0L7Qu9C10YLQstC+0YDQtdC90LjQtSDQt9Cw?= =?utf-8?b?0LLQuNGB0LjQvNC+0YHRgtC10LkgLSBwa2dsaXN0LXVubWV0cyB2MC4xICgr?= =?utf-8?q?rpmdsCompare_sucks=29?= 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, 30 May 2017 10:31:35 -0000 Archived-At: List-Archive: List-Post: Уважаемые мужчины, жители Энрофа! Я написал новую программу обнаружения неудволетворенных зависимостей. https://github.com/svpv/pkglist-unmets/blob/master/unmets.c Старую программу /usr/bin/unmets написал тоже я, а было это, ох, еще 12 лет назад. Поскольку deepsolver, ваш отечественный менеджер пакетов, не взлетел, а разработчик его перешел на apt, то вот и у меня зачесалось перетряхнуть некоторые вещи, связанные с аптом. Итак, старая программа просто создавала отдельное от системного состояние апта (с помощью /usr/bin/mkaptbox), запускала на нем "apt-cache unmet" и немного переформатировала вывод (чтобы выводилось по одной зависимости на строчку). Новая программа написана на Си, никак не связана с аптом, и делает всё сама. $ cat /var/lib/apt/lists/*pkglist.* |/usr/bin/time ./pkglist-unmets 2.41user 0.11system 0:02.54elapsed 99%CPU (0avgtext+0avgdata 55344maxresident)k Программа получает на вход поток rpm-хедеров, строит внутри какие-то таблицы, и ничего не выводит (потому что неудволетворенных зависимостей нет). Требует это около 2.5 секунд и 55 Мб памяти. При этом подключен полный комплект репозиториев: $ du -hsc /var/lib/apt/lists/*pkglist.* 48M ..._Sisyphus_noarch_base_pkglist.classic 53M ..._Sisyphus_x86%5f64-i586_base_pkglist.classic 91M ..._Sisyphus_x86%5f64_base_pkglist.classic 44M ..._Sisyphus_x86%5f64_base_pkglist.debuginfo 234M total Для сравнения, повторный запуск "apt-cache unmet" (на максимально "горячем" состоянии) занимает около 2 секунд и 124 Мб памяти: $ apt-cache unmet >/dev/null && /usr/bin/time apt-cache unmet >/dev/null 1.93user 0.03system 0:01.97elapsed 99%CPU (0avgtext+0avgdata 124764maxresident)k Если же создавать отдельное состояние, то получается 12 секунд user time и минимум 187 Мб памяти (максимум среди всех процессов), а общее время не имеет значения, поскольку здесь у меня идет скачивание по сети: $ /usr/bin/time unmets -s /etc/apt/sources.list.d/alt.list 11.66user 1.23system 0:28.40elapsed 45%CPU (0avgtext+0avgdata 187372maxresident)k На самом деле потребление памяти в смысле нагрузки на подсистему виртуальной памяти ядра здесь намного больше, поскольку apt распаковывает pkglist.classic.xz и хранит их в разжатом виде. Так что можно смело добавлять "234M total". Интересно также оценить, сколько из этих 12 секунд уходит на распаковку xz. $ time xz -dc Sisyphus/{x86_64-i586,noarch}/base/pkglist.classic.xz Sisyphus/x86_64/base/pkglist.{classic,debuginfo}.xz >/dev/null 3.38s user На распаковку уходит существенно меньше половины, апт делает еще много всякой лишней работы - например, вычисляет md5 и sha1 как сжатых, так и разжатых файлов, а это то же не шибко быстро происходит: $ xz -dc Sisyphus/{x86_64-i586,noarch}/base/pkglist.classic.xz Sisyphus/x86_64/base/pkglist.{classic,debuginfo}.xz |time md5sum 0.54s user В общем, новая программа обходится с ресурсами намного экономнее. Предлагаю ее использовать в сборочной системе. У меня есть еще некоторые идеи, как ее доработать, и может быть тогда. При использовании же в сборочной системе, как уже видно, на распаковку xz будет уходить больше времени, чем на pkglist-unmets. $ time xz -dc Sisyphus/{x86_64,noarch}/base/pkglist.classic.xz |./pkglist-unmets xz 2.02s user ./pkglist-unmets 1.65s user Поэтому есть еще идея параллельно с pkglist.classic.xz генерировать pkglist.classic.zst. Это будет полезно и в ряде других случаев; напишу об этом в следующий раз. С другой стороны, программа получилась сравнительно сложной - около 20 Кб кода на Си. Если бы вопрос стоял узко, в смысле разумной необходимости, то, пожалуй, писать новую программу на замену старой и не стоило бы. Но у меня вопрос стоял более широко - мне было интересно отработать определенную технику быстрой обработки больших данных внутри памяти. Эта техника может быть полезна и в других случаях, например при обработке ELF-символов, где выигрыш может быть уже гораздо более значительным. Поэтому расскажу немного, как программа устроена. Из каждого rpm-хедера программа берет Requires и Provides. Далее надо отсортировать их по имени, однако зависимости представлены в виде трех связанных массивов: names[], versions[] и flags[]. Как отсортировать три связанных массива? Ну, можно соединить их в один массив записей struct { name, version, flags } и отсортировать. :-) С другой стороны, абстрактному алгоритму сортировки какая разница что сортировать? Ему можно дать сортировать просто индексы 0..N-1, а весь доступ к реальным данным могут взять на себя примитивы LESS (или CMP) и SWAP. В общем, на третий день Зоркий Глаз понял, что тут всё сходится, и реализовал макрос QSORT(N, LESS, SWAP). Далее задача состоит в том, чтобы избежать глобальной сортировки массива Requires и Provides, а понемножку сливать их алгоритмом слияния. При этом слияние должно быть сбалансированным, чтобы обеспечить оптимальную асимптотику. То есть нужно сливать зависимости 1+1, далее 2+2 пакетов и т.п. (Конечно при слиянии 1+1 у одного из пакетов зависимостей может оказаться намного больше, но на следующих уровнях усреднение происходит очень быстро.) Чтобы реализовать такое слияние, проще всего устроить стек, класть на стек очередной пакет и пытаться провернуть сверху вниз серию слияний. В какой-то момент на стеке окажутся пакеты в таком количестве: top -> 1 2 4 8 ... n После того, как на стек положат очередной пакет, запустится каскад слияний 1+1=>2, 2+2=>4, 4+4=>8, ..., n+n=2n, после чего стек окажется в состоянии top -> 2n Когда все rpm-хедеры загружены, стек досливается принудительно, уже не в оптимальной пропорции n+n, а как получится - x+n, x= set:bMxyz, то не понятно, сменился ли soname, или же, напротив, не хватает символов.) Если же по имени найдено совпадение, то надо сравнивать версии. Здесь начинается самый ад и трешак. Я имею в виду интерфейс rpmdsCompare(). Не знаю конечно, скольким подписчикам могут быть интересны такие детали, но все-таки я хочу довести до вашего сведения масштаб разрухи в головах. /** \ingroup rpmds * Compare two versioned dependency ranges, looking for overlap. * @param A 1st dependency * @param B 2nd dependency * @return 1 if dependencies overlap, 0 otherwise */ int rpmdsCompare(const rpmds A, const rpmds B); Вину за интерфейс rpmdsCompare() оба апстрима делят пополам. Джефф неправильно назвал функцию: compare подразумевает "больше, меньше или равно", а здесь функция возвращает 0 или 1 (1 - если зависимость удовлетворена). Но неверная аналогия со сравнением прилипает/пристает и дальше направляет неверный ход мыслей: кажется, что сравнение должно быть симметричным (т.е. давать такой же результат при перестановке местами A и B). И действительно, реализация функции rpmdsCompare является симметричной относительно перестановки A и B, что приводит к ошибке: Requires с версией удовлетворяется Provides без версии (я писал об этом в прошлом письме). Однако же rpmdsCompare вызывает функцию rpmdsCompareEVR(); несмотря на свой симметричный прототип, эта функция уже не является симметричной (что делает и функцию rpmdsCompare несимметричной). Вообще, и сама аналогия "перекрытия диапазонов" (overlap) является неверной. Перекрытие симметрично, а разрешение Requires относительно Provides несимметрично! Почему? Потому что версии структурированы более сложно, они могут иметь или не иметь релиза; релиз привносит понятие специфичности, которое разрушает симметрию. Казалось бы, почему бы не экспортировать какой-нибудь интерфейс в терминах предметной области, а не ложных аналогий? Например: // Try to satisfy R with P. bool rpmSatisfy(const char *R, int flagsR, const char *P, int flagsP); Но нет, людям очень нравятся математические аналогии. Так оно как-то ближе к идеальным платоновским сущностям. С таким же успехом солнце можно объявить додекаэдром, и обсуждать применительно к солнцу группы вращения додекаэдра! А почему бы солнце могло быть додекаэдром? Ну, читайте Тимея, может поймете. Это отсекает большую часть оппонентов, хотя абсурдность утверждения от этого никак не меняется. Вторая часть вины лежит на Пану М., на большом специалисте по структурам данных, который не знает, какого цвета учебник. Он изобрел rpmstrPool - структуру данных, которая вроде пытается экономить память за счет плотной упаковки строк, но в реальности она делает глупости (вроде хеширования строк one-at-a-time, по одному байту на итерацию), что приводит к неимоверному пожиранию процессора. Может, это и работает ничего на коротких версиях типа "1.0-alt1", но на set-версиях прожорливость сразу набегает секундами. В общем, основное правило для тех, кто хочет использовать эти интерфейсы: стараться по максимуму вообще не трогать rpmds и rpmstrPool. Кстати, я видел, что в апте Глеб с Легионом сделали один глобальный пул, чтобы не создавать пул при каждой проверке зависимостей. Секунд так набегает меньше, но в результате в пуле хранятся все сравниваемые строки. Т.е. "apt-cache unmet" впустую жрет примерно на 20 Мб больше памяти, чем мог бы. Интересно, что в реализации pkglist-unmet мне удалось проторить, как это говорится, to tread the middle path: по максимуму избегать rpmds и rpmstrPool, а иначе создавать пулы не слишком часто, и в то же время накапливать в них строк не слишком много. В общем, когда я пишу, что rpm является наслоением глупостей, причем новый rpm - в большей степени, чем старый, то это не является преувеличением: всё это вживую вас мучает при написании и профилировании кода. Отпрофилировав код первые несколько раз, я вспомнил бессмертную цитату из Бивиса и Баттхеда: "This sucks more than anything that has ever sucked before." Таковы апстримы rpm. Кстати, в pkglist-unmets я реализовал и своеобразный строковый пул. Строковый пул может работать очень быстро, если ставить целью обнаружение не всех дублирующихся строк, а только большей их части. Тогда для каждой строки достаточно хешировать два средних байта, а для каждого хеша делать хеш-цепь фиксированной длины, а именно длины 2.