From owner-freebsd-current@freebsd.org Wed Nov 23 16:28:14 2016 Return-Path: Delivered-To: freebsd-current@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 BFE9CC511FA for ; Wed, 23 Nov 2016 16:28:14 +0000 (UTC) (envelope-from ed@nuxi.nl) Received: from mail-yw0-x235.google.com (mail-yw0-x235.google.com [IPv6:2607:f8b0:4002:c05::235]) (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 86E24929 for ; Wed, 23 Nov 2016 16:28:14 +0000 (UTC) (envelope-from ed@nuxi.nl) Received: by mail-yw0-x235.google.com with SMTP id a10so15791322ywa.3 for ; Wed, 23 Nov 2016 08:28:14 -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=a4dV1UNarGyWvGAdbsieWM7u5xFfV+yfdggkgGB9VE0=; b=DSVOtHXHRuPep45Z8mMAOjYSJxHUdobXoD93Vj4CR8oso7Dxj+IpFQjg22NttxO8b0 SJdUpD8EnoaLAKi+FBK5VaHmfVhWnN7ZDo1euW45I3RhK59SGxa6cof/iGxJ8v9ExL7x 7I5QcVSjf4X9xhSTYX6XYfNE6yK5RX1IPqf+aO72hyv8prTRKuVzP+XGMrdS8f2H8IPf 50LSsmEEYZDR25yb/UTh6Dy/1n6NamkSu/W3DntByDFzXOMgTt09cV9fdP5eV6ptUPg1 Hfdx6kM6PWxFJwp3+gMeoKkJuHPN4cxxw0wdRU/9DmrwDCSJ3FEh9a/Yj4bBy1Wwvwan TWtQ== 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=a4dV1UNarGyWvGAdbsieWM7u5xFfV+yfdggkgGB9VE0=; b=D+obxhSEgR1siXREIWmcchw8Wd9jMdem+07b6ok9ZZS6mmeSVeGowVktWFp3kKIMxp oE7wanh5gGM7/ZMfacgfNNB+RlKmPGWv4w8YEnwDGPtS7x23LLbtJwV/kllzuoZClH35 aWHcpLgQXMKJ8gkvDDL6XnDJFsszq7dwkQubtm/oTGdFc+tlY6htSb/dQVoxVHuop8+F GlKieERZgNt6cT8eYe/Abt34K9QscMbtgnqsRTBEoLImJH0mpszIWxDgNS9Y7Fu5rHLt GPyd4ucFsTSQuBVJtKRYmgCdyu0NpbGdwkc5FJ9lWxYXvR9TJ39bH9GIwEvgBEzcZEdD 9iJw== X-Gm-Message-State: AKaTC03Q68dBjRHD5a1ptzvKcov/nIWiQ6KiKmUR5XZ3wAItFBAs8YV18ki5kqhcgcL6iIUy9EYKx5t86WamMg== X-Received: by 10.13.200.3 with SMTP id k3mr5012608ywd.173.1479918493472; Wed, 23 Nov 2016 08:28:13 -0800 (PST) MIME-Version: 1.0 Received: by 10.129.31.213 with HTTP; Wed, 23 Nov 2016 08:27:42 -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: Wed, 23 Nov 2016 17:27:42 +0100 Message-ID: Subject: Re: Optimising generated rules for SAT solving (5/12 are duplicates) To: Hans Petter Selasky Cc: Baptiste Daroussin , Slawa Olhovchenkov , ports@freebsd.org, FreeBSD Current Content-Type: text/plain; charset=UTF-8 X-BeenThere: freebsd-current@freebsd.org X-Mailman-Version: 2.1.23 Precedence: list List-Id: Discussions about the use of FreeBSD-current List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 23 Nov 2016 16:28:14 -0000 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? By the way, why attach a zip file with a diff? GitHub's pull requests are awesome! :-) [1] Davis-Putnam-Logemann-Loveland algorithm: https://en.wikipedia.org/wiki/DPLL_algorithm -- Ed Schouten Nuxi, 's-Hertogenbosch, the Netherlands KvK-nr.: 62051717