Date: Thu, 24 Nov 2016 15:15:07 +0100 From: Ed Schouten <ed@nuxi.nl> To: Vsevolod Stakhov <vsevolod@highsecure.ru> Cc: Hans Petter Selasky <hps@selasky.org>, Baptiste Daroussin <bapt@freebsd.org>, Slawa Olhovchenkov <slw@zxy.spb.ru>, ports@freebsd.org, FreeBSD Current <freebsd-current@freebsd.org> Subject: Re: Optimising generated rules for SAT solving (5/12 are duplicates) Message-ID: <CABh_MKkt-8JReEHxE4J3kfC0L1PuxE7sTw0ipnJLLfZGxg=TuA@mail.gmail.com> In-Reply-To: <d786cde5-89af-cb14-c42e-cc649cb32bdb@highsecure.ru> 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> <cbc964a7-5f90-6ea1-630d-414de68867b1@selasky.org> <CABh_MKm7LAtQzp9KEBpaRZWQQHnsUtNFiKVSVF70-wj4GmytuA@mail.gmail.com> <d786cde5-89af-cb14-c42e-cc649cb32bdb@highsecure.ru>
next in thread | previous in thread | raw e-mail | index | archive | help
2016-11-24 13:13 GMT+01:00 Vsevolod Stakhov <vsevolod@highsecure.ru>: > On 23/11/2016 16:27, Ed Schouten wrote: >> Hi Hans, >> >> 2016-11-23 15:27 GMT+01:00 Hans Petter Selasky <hps@selasky.org>: >>> 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 <ed@nuxi.nl> Nuxi, 's-Hertogenbosch, the Netherlands KvK-nr.: 62051717
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?CABh_MKkt-8JReEHxE4J3kfC0L1PuxE7sTw0ipnJLLfZGxg=TuA>