From owner-freebsd-announce@freebsd.org Fri Dec 6 00:09:36 2019 Return-Path: Delivered-To: freebsd-announce@mailman.nyi.freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2610:1c1:1:606c::19:1]) by mailman.nyi.freebsd.org (Postfix) with ESMTP id 470531B06E7 for ; Fri, 6 Dec 2019 00:09:36 +0000 (UTC) (envelope-from devin@shxd.cx) Received: from shxd.cx (mail.shxd.cx [64.201.244.140]) (using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits)) (Client did not present a certificate) by mx1.freebsd.org (Postfix) with ESMTPS id 47TXyR3Cdrz3Htk; Fri, 6 Dec 2019 00:09:35 +0000 (UTC) (envelope-from devin@shxd.cx) Received: from [76.77.180.168] (port=53633 helo=devins-mbp.lan) by shxd.cx with esmtpsa (TLSv1:AES256-SHA:256) (Exim 4.77 (FreeBSD)) (envelope-from ) id 1id1BX-0001LV-F4; Thu, 05 Dec 2019 16:09:27 -0800 From: Devin Teske Mime-Version: 1.0 (Mac OS X Mail 12.4 \(3445.104.11\)) Message-Id: <51AD9B50-9488-45CE-878F-EE97F6914E49@freebsd.org> Date: Thu, 5 Dec 2019 16:09:26 -0800 To: freebsd-announce@freebsd.org X-Mailer: Apple Mail (2.3445.104.11) Sender: devin@shxd.cx X-Rspamd-Queue-Id: 47TXyR3Cdrz3Htk X-Spamd-Bar: ++ Authentication-Results: mx1.freebsd.org; dkim=none; dmarc=none; spf=none (mx1.freebsd.org: domain of devin@shxd.cx has no SPF policy when checking 64.201.244.140) smtp.mailfrom=devin@shxd.cx X-Spamd-Result: default: False [2.70 / 15.00]; ARC_NA(0.00)[]; RCVD_VIA_SMTP_AUTH(0.00)[]; RCVD_TLS_ALL(0.00)[]; FROM_HAS_DN(0.00)[]; TO_DN_SOME(0.00)[]; TO_MATCH_ENVRCPT_ALL(0.00)[]; MV_CASE(0.50)[]; MIME_GOOD(-0.10)[multipart/alternative,text/plain]; DMARC_NA(0.00)[freebsd.org]; AUTH_NA(1.00)[]; NEURAL_SPAM_MEDIUM(0.34)[0.344,0]; IP_SCORE(0.10)[ip: (0.29), ipnet: 64.201.240.0/20(0.15), asn: 36734(0.12), country: US(-0.05)]; RCPT_COUNT_TWO(0.00)[2]; NEURAL_SPAM_LONG(0.55)[0.555,0]; R_SPF_NA(0.00)[]; FORGED_SENDER(0.30)[dteske@freebsd.org,devin@shxd.cx]; R_DKIM_NA(0.00)[]; MIME_TRACE(0.00)[0:+,1:+,2:~]; ASN(0.00)[asn:36734, ipnet:64.201.240.0/20, country:US]; FROM_NEQ_ENVFROM(0.00)[dteske@freebsd.org,devin@shxd.cx]; MID_RHS_MATCH_FROM(0.00)[]; RCVD_COUNT_TWO(0.00)[2] X-Mailman-Approved-At: Thu, 12 Dec 2019 06:39:19 +0000 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable X-Content-Filtered-By: Mailman/MimeDel 2.1.29 Subject: [FreeBSD-Announce] BSD-Licensed Combinatorics library/utility X-BeenThere: freebsd-announce@freebsd.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: "Project Announcements \[moderated\]" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 06 Dec 2019 00:09:36 -0000 Hello. I=E2=80=99d like to announce a new utility/library for FreeBSD base = available for review. https://reviews.freebsd.org/D16132 Preview HTML-formatted manuals: https://fraubsd.org/doc/cmb.1.html https://fraubsd.org/doc/cmb.3.html *** Combinatorics is the study of combinations. For example, calculating how many possible combinations given a set of = items and some parameters such as how many or a range of how many items = to select. Iterating over every possible combination to perform some action for = each =E2=80=94 with support for position indicators so that if you = prematurely terminate you can pick up at the last combination where you = left-off. Find combinations of numerical items that produce a particular sum, = quotient, product, or difference. *** While these problem have been solved (or partially solved) in languages = such as: Perl (Algorithm::Combinatorics) Python (itertools, numpy) R (comb) Haskell Others =E2=80=A6 my implementation is faster than all of them. =E2=80=A6 and BSD-licensed. =E2=80=A6 and written in C with bindings for Perl and Python (R and = others forthcoming). =E2=80=A6 and works on Mac OS X, Linux, Solaris, BSD, etc. with minimal = dependencies. NB: The Perl/Python bindings are not in the review for import to base. *** Q. Why add this to FreeBSD base? A. Lofty goals With a combinatorics library, we can start thinking about taking on = monumental tasks such as: * Making the =E2=80=9Cbuild option survey=E2=80=9D test all combinations = of build options Today, the build-option survey only iterates over a handful of = hand-selected build options. It does combinatorially iterate over all = possible combinations as that might prove exorbitantly expensive in = either time or resources. I will be attempting to solve the incompleteness aspect using cmb, while = dedicating several hundred cores in a private cluster to solving the = time/resource requirements. * Offer packages compiled from ports with non-standard options I don=E2=80=99t know if any other Operating System is tackling this = problem, but I think we can, if not for the entire ports tree, a subset = thereof. One of the things I imagine is adding to the ports tree, the ability to = say =E2=80=9Cmake allpkg=E2=80=9D or something which would compile every = possible combination of optional directives in the given port directory = where you say it, generating uniquely named packages with appropriately = codified MANIFEST files that enumerate which options were enabled for = each. This project too, I am not sure how many resources or time will need to = be dedicated to staying current (especially if we try and tackle the = entire ports tree), but I do happen to have quite a lot of hardware at = my disposal and HPC scheduling software providing an MPI environment to = get the job done. *** Through both of these endeavors, the missing element has been a = permissively-licensed high-performance combinatorics library. I first started working in the highly specialized area of mathematics = dealing with combinations back in 1989, wrote my first Proof-of-Concept = (using Bourne Shell of all things) back in 2001 and in the past 3 years = have made a concerted effort to provide the missing aspect to more = complex work like the above endeavors. 30 years in the making, I am excited to bring to FreeBSD base my = BSD-licensed solution. Let it be like =E2=80=9Cseq=E2=80=9D, =E2=80=9Cjot=E2=80=9D, and other = well-known utilities in base for solving a hard problem in the =E2=80=9CUN= IX Way=E2=84=A2=E2=80=9D (write a tool to do one job and do it well). =E2=80=94=20 Cheers, Devin=