From owner-freebsd-ports@freebsd.org Thu Nov 24 13:11:46 2016 Return-Path: Delivered-To: freebsd-ports@mailman.ysv.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:1900:2254:206a::19:1]) by mailman.ysv.freebsd.org (Postfix) with ESMTP id 59A9DC51B3C for ; Thu, 24 Nov 2016 13:11:46 +0000 (UTC) (envelope-from vsevolod@highsecure.ru) Received: from mailman.ysv.freebsd.org (mailman.ysv.freebsd.org [IPv6:2001:1900:2254:206a::50:5]) by mx1.freebsd.org (Postfix) with ESMTP id 3BEF7BCC for ; Thu, 24 Nov 2016 13:11:46 +0000 (UTC) (envelope-from vsevolod@highsecure.ru) Received: by mailman.ysv.freebsd.org (Postfix) id 3AF08C51B39; Thu, 24 Nov 2016 13:11:46 +0000 (UTC) Delivered-To: ports@mailman.ysv.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:1900:2254:206a::19:1]) by mailman.ysv.freebsd.org (Postfix) with ESMTP id 3A6C8C51B37; Thu, 24 Nov 2016 13:11:46 +0000 (UTC) (envelope-from vsevolod@highsecure.ru) Received: from mail.highsecure.ru (mail6.highsecure.ru [IPv6:2a01:4f8:190:43b5::99]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (Client did not present a certificate) by mx1.freebsd.org (Postfix) with ESMTPS id C2F81BCB; Thu, 24 Nov 2016 13:11:45 +0000 (UTC) (envelope-from vsevolod@highsecure.ru) Received: from secret-bunker.localdomain (unknown [81.145.134.172]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) (Authenticated sender: vsevolod@highsecure.ru) by mail.highsecure.ru (Postfix) with ESMTPSA id 7C6BF30068F; Thu, 24 Nov 2016 14:11:43 +0100 (CET) Received: from [127.0.0.1] (localhost [127.0.0.1]) by secret-bunker.localdomain (Postfix) with ESMTP id 97A9B2D12A2C; Thu, 24 Nov 2016 13:11:42 +0000 (GMT) Subject: Re: Optimising generated rules for SAT solving (5/12 are duplicates) To: Hans Petter Selasky , Ed Schouten References: <20150414200459.GE39658@ivaldir.etoilebsd.net> <20150421103454.GR1394@zxy.spb.ru> <5593D0AE.2010205@selasky.org> <416359ce-1dcd-1160-5c56-f120a0f6358f@selasky.org> <20160627115533.gqvdsmtzwnvrrfuo@ivaldir.etoilebsd.net> <0671148b-d7cd-f8ad-906d-a0baa1b98cf5@selasky.org> <9b0469bb-ab2b-4992-1d40-de748163f2c8@selasky.org> Cc: Baptiste Daroussin , Slawa Olhovchenkov , ports@freebsd.org, FreeBSD Current From: Vsevolod Stakhov Message-ID: <8c5cb2ea-54ab-c91b-5859-b6a73a2a7005@highsecure.ru> Date: Thu, 24 Nov 2016 13:11:42 +0000 User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.11; rv:45.0) Gecko/20100101 Thunderbird/45.5.0 MIME-Version: 1.0 In-Reply-To: <9b0469bb-ab2b-4992-1d40-de748163f2c8@selasky.org> Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 7bit DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=highsecure.ru; s=dkim; t=1479993103; bh=WJ0yP2AOr+gEFsfnG8Coy/NwLjJZAMZQtUTMAVxEIzA=; h=Subject:To:References:Cc:From:Message-ID:Date:MIME-Version:In-Reply-To:Content-Type:Content-Transfer-Encoding; b=ZvlDSmo9y7ivwX/0voW+uqpGQILpy1U91mP2GR6/UYDJVmVH4CWP9/BjSh0BBqMsyNNnL7HEwqpIELbUC2plkkVBmb8VS+RBQgj0EQDWpIQFj4szp7oMY1JdWllobjd1+2uumxRfGPyaBbNx/NbpRKWdXczBF0RLdgWspuUZLmE= X-BeenThere: freebsd-ports@freebsd.org X-Mailman-Version: 2.1.23 Precedence: list List-Id: Porting software to FreeBSD List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 24 Nov 2016 13:11:46 -0000 On 24/11/2016 13:05, Hans Petter Selasky wrote: > On 11/24/16 13:13, Vsevolod Stakhov wrote: >> On 23/11/2016 16:27, Ed Schouten wrote: >>> Hi Hans, >>> >>> 2016-11-23 15:27 GMT+01:00 Hans Petter Selasky : >>>> I've made a patch to hopefully optimise SAT solving in our pkg utility. >>> >>> Nice! Do you by any chance have any numbers that show the performance >>> improvements made by this change? Assuming that the SAT solver of >>> pkg(1) uses an algorithm similar to DPLL[1], a change like this would >>> affect performance linearly. My guess is therefore that the running >>> time is reduced by approximately 5/12. Is this correct? >> >> There won't be any improvement if you just remove duplicates from SAT >> formula. This situation is handled by picosat internally and even for >> naive DPLL there is no significant influence of duplicate KNF clauses: >> once you've assumed all vars in some clause, you automatically resolve >> all duplicates. >> >> Is there any real improvement of SAT solver speed with this patch? From >> my experiences, SAT solving is negligible in terms of CPU time comparing >> to other tasks performed by pkg. > > Hi, > > I added some code to measure the time for SAT solving. During my test > run I'm seeing values in the range 8-10ms for both versions, so I > consider that neglible. However, the unpatched version wants to > reinstall 185 packages while the non-patched version wants to reinstall > 1 package. That has a huge time influential. I'm not that familar with > PKG that I can draw any conclusions from this. > > # Test1: > echo "n" | /xxx/pkg/src/pkg-static upgrade --no-repo-update > b.txt > > # Test2: > echo "n" | env PKG_NO_SORT=YES /xxx/pkg/src/pkg-static upgrade > --no-repo-update > a.txt > Then I don't understand how your patch should affect the solving procedure. If pkg tries to reinstall something without *reason* it is a good sign of bug in pkg itself and/or your database/repo and not in SAT solver. I'll try to review your issue but I'll likely need your local packages database for this test. -- Vsevolod Stakhov