CVS commit: pkgsrc/math/djbsort

["Amitai Schleier" <schmonz%netbsd.org@localhost>]

Module Name:    pkgsrc
Committed By:   schmonz
Date:           Tue Jul 31 06:34:11 UTC 2018

Modified Files:
        pkgsrc/math/djbsort: Makefile distinfo pseudo-PLIST

Log Message:
Update to 20180729. From the changelog:

Algorithm

Rewrite of the core int32/avx2 implementation for (1) higher speed and
(2) reduced memory consumption. Stack allocation is now at most a few
kilobytes, even for gigantic arrays.

Internally, the sorting algorithm is now mostly bitonic to simplify
indexing, although odd-even speedups are still applied when
convenient. Lanes are complemented to take the down-up decision out of
the inner loops.

As in previous djbsort versions, data is sorted first in vector lanes
and then transposed for final merges, reducing the overall number of
vector permutations. Unlike previous versions, transposition is done
in-place. The transposition in this version is bit-reversal on the outer
6 bits (bottom 3 bits and the top 3 bits), but leaves intermediate bits
alone. Non-power-of-2 array sizes are handled by an extra, more
traditional, merge step.

Sizes 2, 3, 4, 5, 6, 7, 8, 16, 32 are now special-cased. Non-power-of-2
sizes below 256 are padded to the next power of 2.

Portable implementations: The out-of-place int32/portable1 and
int32/portable2 implementations are now gone; the in-place
int32/portable3 and int32/portable4 implementations remain.

C API

float32_sort is now supported. The arithmetic in the reduction from
float32 to int32 is int32 31-bit right shift, uint32 1-bit right shift,
xor; this is slightly more efficient than the reduction from float32 to
uint32 from 2001 Herf.

Compiling

Tests now have more variation (without much slowdown): the uint32 test
cases now deviate from int32 in more than the sign; float32 uses
floating-point numbers that aren't integers; int32 does more loops for
small cases, and some larger cases.

Internals

API for 2-input sorting is now MINMAX macro operating on two
inputs in place.

Better inline assembly from Jason Donenfeld for 2-input sorting: more
flexibility in compiler's register allocation.

The package version number is now automatically copied to version.c as
the implementation version number for implementations that don't provide
version.c.

Verification

minmax now supports more peephole optimizations for complemented bitonic
sorting and for padding: xor(s,xor(s,t)) ⇒ t; xor(-1,s) ⇒ invert(s);
Reverse(Reverse(s)) ⇒ s; signedmin(invert(s),invert(t)) ⇒
invert(signedmax(s,t)); signedmax(invert(s),invert(t)) ⇒
invert(signedmin(s,t)); invert(s)[high:low] ⇒ invert(s[high:low]);
s[bits-1:0] ⇒ s; s[high:low][high2:low2] ⇒ s[high2+low:low2+low];
Concat(...)[high:low] ⇒ ...[high-pos:low-pos] when possible;
Reverse(s)[high:low] ⇒ Reverse(s[...]) when possible; eliminate
signedmin/signedmax when one input is the minimum or maximum constant.

verifymany now includes the implementation version number on
verified lines.


To generate a diff of this commit:
cvs rdiff -u -r1.3 -r1.4 pkgsrc/math/djbsort/Makefile
cvs rdiff -u -r1.2 -r1.3 pkgsrc/math/djbsort/distinfo
cvs rdiff -u -r1.1 -r1.2 pkgsrc/math/djbsort/pseudo-PLIST

Please note that diffs are not public domain; they are subject to the
copyright notices on the relevant files.

Modified files:

Index: pkgsrc/math/djbsort/Makefile
diff -u pkgsrc/math/djbsort/Makefile:1.3 pkgsrc/math/djbsort/Makefile:1.4
--- pkgsrc/math/djbsort/Makefile:1.3    Tue Jul 31 06:24:57 2018
+++ pkgsrc/math/djbsort/Makefile        Tue Jul 31 06:34:11 2018
@@ -1,7 +1,6 @@
-# $NetBSD: Makefile,v 1.3 2018/07/31 06:24:57 schmonz Exp $
+# $NetBSD: Makefile,v 1.4 2018/07/31 06:34:11 schmonz Exp $
 
-DISTNAME=              djbsort-20180717
-PKGREVISION=           1
+DISTNAME=              djbsort-20180729
 CATEGORIES=            math
 MASTER_SITES=          ${HOMEPAGE}
 

Index: pkgsrc/math/djbsort/distinfo
diff -u pkgsrc/math/djbsort/distinfo:1.2 pkgsrc/math/djbsort/distinfo:1.3
--- pkgsrc/math/djbsort/distinfo:1.2    Tue Jul 31 05:38:56 2018
+++ pkgsrc/math/djbsort/distinfo        Tue Jul 31 06:34:11 2018
@@ -1,9 +1,9 @@
-$NetBSD: distinfo,v 1.2 2018/07/31 05:38:56 schmonz Exp $
+$NetBSD: distinfo,v 1.3 2018/07/31 06:34:11 schmonz Exp $
 
-SHA1 (djbsort-20180717.tar.gz) = 8f6efd8f66aa23707d54c083b9fb28371a409c55
-RMD160 (djbsort-20180717.tar.gz) = 64d92cccf13d8a997ea25ee77491f54b6a6b3ce1
-SHA512 (djbsort-20180717.tar.gz) = c26a871c46006580343b2876203264c8de0db613ee90ba5dd050f46a71a346d9340ecd06220dc1c0a46a6c1cd910af4bd2cb3fcd39588a62cc2a4a996fc9113e
-Size (djbsort-20180717.tar.gz) = 25055 bytes
+SHA1 (djbsort-20180729.tar.gz) = 7b64b9c5b3c6428cb6bc16638876f57ffff3c58b
+RMD160 (djbsort-20180729.tar.gz) = 65455661524b5d2cdd21c1c329a9065cfc9b3b0d
+SHA512 (djbsort-20180729.tar.gz) = b46c36514ce0c2c1716421d4da216d2e7ddb80e8e9a1b97b274ab0b3fe7271ea946a65485e81d4dc76c080658b41ef1e2fa64a225594532f1be98dc29535b2a6
+Size (djbsort-20180729.tar.gz) = 29347 bytes
 SHA1 (patch-build) = 0f1ae219495cc63fc301aa1f9ae1c1655da3aaa3
 SHA1 (patch-test) = b5ba29b15d7baa896bf9e47a1522e88e73df4c9e
 SHA1 (patch-upgrade) = 2bec25c36e1ed28c67e4967ac929780d28bb2e68

Index: pkgsrc/math/djbsort/pseudo-PLIST
diff -u pkgsrc/math/djbsort/pseudo-PLIST:1.1 pkgsrc/math/djbsort/pseudo-PLIST:1.2
--- pkgsrc/math/djbsort/pseudo-PLIST:1.1        Tue Jul 31 05:38:56 2018
+++ pkgsrc/math/djbsort/pseudo-PLIST    Tue Jul 31 06:34:11 2018
@@ -1,4 +1,5 @@
 include/djbsort_cpucycles.h
+include/float32_sort.h
 include/int32_sort.h
 include/uint32_sort.h
 lib/libdjbsort.a