From owner-freebsd-ports@freebsd.org Wed Nov 23 16:41:55 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 6A64BC516F7 for ; Wed, 23 Nov 2016 16:41:55 +0000 (UTC) (envelope-from hps@selasky.org) Received: from mailman.ysv.freebsd.org (unknown [127.0.1.3]) by mx1.freebsd.org (Postfix) with ESMTP id 542371452 for ; Wed, 23 Nov 2016 16:41:55 +0000 (UTC) (envelope-from hps@selasky.org) Received: by mailman.ysv.freebsd.org (Postfix) id 538ACC516F6; Wed, 23 Nov 2016 16:41:55 +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 53176C516F5; Wed, 23 Nov 2016 16:41:55 +0000 (UTC) (envelope-from hps@selasky.org) Received: from mail.turbocat.net (mail.turbocat.net [IPv6:2a01:4f8:d16:4514::2]) (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 1522D1451; Wed, 23 Nov 2016 16:41:55 +0000 (UTC) (envelope-from hps@selasky.org) Received: from hps2016.home.selasky.org (unknown [62.141.129.119]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by mail.turbocat.net (Postfix) with ESMTPSA id 473061FE024; Wed, 23 Nov 2016 17:41:52 +0100 (CET) Subject: Re: Optimising generated rules for SAT solving (5/12 are duplicates) To: 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> Cc: Baptiste Daroussin , Slawa Olhovchenkov , ports@freebsd.org, FreeBSD Current From: Hans Petter Selasky Message-ID: Date: Wed, 23 Nov 2016 17:41:34 +0100 User-Agent: Mozilla/5.0 (X11; FreeBSD amd64; rv:45.0) Gecko/20100101 Thunderbird/45.4.0 MIME-Version: 1.0 In-Reply-To: Content-Type: text/plain; charset=windows-1252; format=flowed Content-Transfer-Encoding: 7bit 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: Wed, 23 Nov 2016 16:41:55 -0000 On 11/23/16 17: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? Hi Ed, I tried measuring with "time", but figured out that it was doing a lot of other stuff too. Isolating this piece of code was not so easy. > 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? > > By the way, why attach a zip file with a diff? GitHub's pull requests > are awesome! :-) GitHub wouldn't allow me to make a .diff attachment. > > [1] Davis-Putnam-Logemann-Loveland algorithm: > https://en.wikipedia.org/wiki/DPLL_algorithm > --HPS