Re: Optimising generated rules for SAT solving (5/12 are duplicates)

From: Hans Petter Selasky <hps_at_selasky.org>
Date: Wed, 23 Nov 2016 17:41:34 +0100
On 11/23/16 17:27, Ed Schouten wrote:
> Hi Hans,
>
> 2016-11-23 15:27 GMT+01:00 Hans Petter Selasky <hps_at_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?

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
Received on Wed Nov 23 2016 - 15:41:55 UTC

This archive was generated by hypermail 2.4.0 : Wed May 19 2021 - 11:41:08 UTC