From owner-freebsd-ports@freebsd.org Wed Nov 23 16:28:14 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 E63F3C511FF for ; Wed, 23 Nov 2016 16:28:14 +0000 (UTC) (envelope-from ed@nuxi.nl) Received: from mailman.ysv.freebsd.org (unknown [127.0.1.3]) by mx1.freebsd.org (Postfix) with ESMTP id C3FE692C for ; Wed, 23 Nov 2016 16:28:14 +0000 (UTC) (envelope-from ed@nuxi.nl) Received: by mailman.ysv.freebsd.org (Postfix) id C04FCC511FC; Wed, 23 Nov 2016 16:28:14 +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 BFEC6C511FB for ; Wed, 23 Nov 2016 16:28:14 +0000 (UTC) (envelope-from ed@nuxi.nl) Received: from mail-yw0-x229.google.com (mail-yw0-x229.google.com [IPv6:2607:f8b0:4002:c05::229]) (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 86E5A92A for ; Wed, 23 Nov 2016 16:28:14 +0000 (UTC) (envelope-from ed@nuxi.nl) Received: by mail-yw0-x229.google.com with SMTP id i145so15909298ywg.2 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=jKiZqgTZF/EDdOyxnYI9JJH7ALBeilRTfaq7w4CO7w/9lFW0nP/q7VQjjBsu5mY/iv rTEdh6frGMJ5LMIm+BJv3KC46QEFNPpkbMqxbwZnQpG/WHKewzpVLFpD8+HABChsY+lG ercRmHZ/TUVOijiApnozT0kYnlfUk5m7Y6ck43dCn9UYH+c9eTYoFcW4f3LZHbB+OU9E tNiAado1zudO5BqhUUYpmHFNJH8RmPsmYDrv+FEnQFQZJlxa6AfMGMwX6lcEpVWnSaS6 bGIXWXWJNlFbbG5ZoXBchPU4oWUiHJILacXT/ookNzdiZagSzY2oybiw4y9F5K0aKlGU rz/w== X-Gm-Message-State: AKaTC01J1hp5yVLdPNr/n05WgFnAinyCufHdjpzW57v2FTmH0LXy2u5EfYx20z8kY91qJraOu14AwX7e/DJHHw== 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-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:28:15 -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