From owner-freebsd-ports@freebsd.org Thu Nov 24 14:15:39 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 97A2AC51B2B for ; Thu, 24 Nov 2016 14:15:39 +0000 (UTC) (envelope-from ed@nuxi.nl) 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 7350AB20 for ; Thu, 24 Nov 2016 14:15:39 +0000 (UTC) (envelope-from ed@nuxi.nl) Received: by mailman.ysv.freebsd.org (Postfix) id 6F992C51B29; Thu, 24 Nov 2016 14:15:39 +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 6F49EC51B28 for ; Thu, 24 Nov 2016 14:15:39 +0000 (UTC) (envelope-from ed@nuxi.nl) Received: from mail-yw0-x22c.google.com (mail-yw0-x22c.google.com [IPv6:2607:f8b0:4002:c05::22c]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (Client CN "smtp.gmail.com", Issuer "Google Internet Authority G2" (verified OK)) by mx1.freebsd.org (Postfix) with ESMTPS id 34450B1E for ; Thu, 24 Nov 2016 14:15:38 +0000 (UTC) (envelope-from ed@nuxi.nl) Received: by mail-yw0-x22c.google.com with SMTP id i145so40297822ywg.2 for ; Thu, 24 Nov 2016 06:15:38 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=nuxi-nl.20150623.gappssmtp.com; s=20150623; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc; bh=wIyWl5W1kyPHbAS3dL22waOwPPGYWpL7PIAqBZSOjL4=; b=xTTuLrw4QBBdD6+0H24pXRcjb8y8kKwZzNPbfpg9I6iXbeNtiFDRnmXDD0naUpC/J7 5UFgF0s+QQaMMY3Vyj5DXbcgMqj07Rme1qAoVjbCLivB4BRN9hIAp314who7rsF5+tu4 SxQmOcPyT5RiWwZZf5ko7ViBX+/ywt6s6YO3ybESI2iWyQVtXPJyv+jlYjPmlm4jkTW8 7BBUVR1h/BXTaBd3NHIcrQ4k3ioOdbdqfHKTy+3FNj8ihhPGHSXTwwC0kbxRLv7IVJRQ WFLZ0t6pSRc3on70l1zT+Iakm29DTNDH8WR3qk87OEa/pTIyWFOX2aMaYskVpZX01NjD P92g== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to:cc; bh=wIyWl5W1kyPHbAS3dL22waOwPPGYWpL7PIAqBZSOjL4=; b=CdCOMgIiacP1uBm/t6nl/JIPESElVunTQ/gaDBBkosDClvm3lWV4yG0joxO4LHpYR5 1+jWhWKwqYn6q9EDVK5lGkwMPWkBLUdDsYOeFhV/BMXkyaM0xQnPiPm55hXtLNyWqBOR 7SE8uq35UoUnPG+gi7sUohBJFWcHr1pqhCWPdc5GMd1opwbIyMOUH58j6KK0lVo210E1 7Evfe5ylIKfRx3j18DtIyGm5GJOSS/mJW/Ta5Endi+G+NDf/O2oCWuJ09EEO5iVPteuE oFr6ij3aTvVmLSIRTPI7m/HvsZlOJLy/P0//eaiuny4ynInY36UjBYbTNcfVlpTjP6UR d3QQ== X-Gm-Message-State: AKaTC03tDID56INbZQilfm47vrYGIlEO2wR7HDwgTngTmMHk23xAyR2igL6MdBdk9dBUsdEfOvMrduwdpCQfew== X-Received: by 10.13.196.194 with SMTP id g185mr3326291ywd.138.1479996937757; Thu, 24 Nov 2016 06:15:37 -0800 (PST) MIME-Version: 1.0 Received: by 10.129.31.213 with HTTP; Thu, 24 Nov 2016 06:15:07 -0800 (PST) In-Reply-To: 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> From: Ed Schouten Date: Thu, 24 Nov 2016 15:15:07 +0100 Message-ID: Subject: Re: Optimising generated rules for SAT solving (5/12 are duplicates) To: Vsevolod Stakhov Cc: Hans Petter Selasky , Baptiste Daroussin , Slawa Olhovchenkov , ports@freebsd.org, FreeBSD Current Content-Type: text/plain; charset=UTF-8 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 14:15:39 -0000 2016-11-24 13:13 GMT+01:00 Vsevolod Stakhov : > 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. Exactly. This is why I've stated: it affects performance linearly. Referring to Wikipedia's pseudo-code of the algorithm: the number of calls to unit-propagate() and pure-literal-assign() drops linearly, but the recursion will stay the same. -- Ed Schouten Nuxi, 's-Hertogenbosch, the Netherlands KvK-nr.: 62051717