Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

[PATCH 4/11] perl_hash_crc32: use HW hasher as default with SSE4.2 #14583

Open
p5pRT opened this issue Mar 14, 2015 · 28 comments
Open

[PATCH 4/11] perl_hash_crc32: use HW hasher as default with SSE4.2 #14583

p5pRT opened this issue Mar 14, 2015 · 28 comments

Comments

@p5pRT
Copy link

p5pRT commented Mar 14, 2015

Migrated from rt.perl.org#124064 (status was 'open')

Searchable as RT124064$

@p5pRT
Copy link
Author

p5pRT commented Mar 14, 2015

From @rurban

This is a bug report for perl from rurban@​cpanel.net,
generated with the help of perlbug 1.40 running under perl 5.21.9.


perl_hash_crc32​: use HW hasher as default with SSE4.2
 
can be enabled with the following ccflags​:
  -march=native or -mcrc32 or -msse42
 
also with untested AARCH64_FL_CRC support
https://gcc.gnu.org/ml/gcc-patches/2014-01/msg01012.html
 
See https://github.com/rurban/perl-hash-stats#perl-hash-stats for the
analysis. iSCSI CRC32-C is by far the fastest hash function tested, and
produces on average the least collisions, so is also the best for the
average case.
  collisions cycles/hash
  CRC32 1.066 29.78
  ONE_AT_A_TIME_HARD 1.092 83.75
 
See https://github.com/rurban/smhasher#smhasher for a more detailled
analysis on the hash function qualities. 'doc/crc32_hw' is by far better
than the current 'doc/JenkinsOOAT'
 
Worst-case​:

You cannot trust any of these fast hash functions for security at all.
Collision complexity attacks need to be secured in other ways. It's trivial
to generate such attacks without our randomized hash seeds and iterators on
all these hash functions. Without those measures CRC32 is even more trivial
to attack than siphash, city, jenkins or murmur.
 
Eventually we will need to switch to a better hash table scheme, which will
be faster (more cache-friendly), has better key checks, and avoids
complexity attacks against our linear linked lists at all. Sorted buckets,
double-hashing, universal hashing or adding a sleep with >10 collisions are
all better schemes that I am working on.

Perl Info
-----------------------------------------------------------------
---
Flags:
category=core
severity=medium
Type=Patch
PatchStatus=HasPatch
---
Site configuration information for perl 5.21.9:

Configured by rurban at Sun Feb 22 17:14:55 CET 2015.

Summary of my perl5 (revision 5 version 21 subversion 9) configuration:

Platform:
osname=linux, osvers=3.16.0-4-amd64, archname=x86_64-linux-debug
uname='linux reini 3.16.0-4-amd64 #1 smp debian 3.16.7-ckt2-1 (2014-12-08) x86_64 gnulinux '
config_args='-de -Dusedevel -Uversiononly -Dinstallman1dir=none -Dinstallman3dir=none -Dinstallsiteman1dir=none -Dinstallsiteman3dir=none -DEBUGGING -Doptimize='-g3' -Uuseithreads -D'cc=gcc-5.0' -Accflags=''-msse4.2'' -Accflags=''-march=corei7'' -Dcf_email=''rurban@cpanel.net'' -Dperladmin=''rurban@cpanel.net'''
hint=recommended, useposix=true, d_sigaction=define
useithreads=undef, usemultiplicity=undef
use64bitint=define, use64bitall=define, uselongdouble=undef
usemymalloc=n, bincompat5005=undef
Compiler:
cc='gcc-5.0', ccflags ='-msse4.2 -march=corei7 -fwrapv -DDEBUGGING -fno-strict-aliasing -pipe -fstack-protector-strong -I/usr/local/include -D_LARGEFILE_SOURCE -D_FILE_OFFSET_BITS=64',
optimize='-g3',
cppflags='-msse4.2 -march=corei7 -fwrapv -DDEBUGGING -fno-strict-aliasing -pipe -fstack-protector-strong -I/usr/local/include'
ccversion='', gccversion='5.0.0 20150103 (experimental)', gccosandvers=''
intsize=4, longsize=8, ptrsize=8, doublesize=8, byteorder=12345678, doublekind=3
d_longlong=define, longlongsize=8, d_longdbl=define, longdblsize=16, longdblkind=3
ivtype='long', ivsize=8, nvtype='double', nvsize=8, Off_t='off_t', lseeksize=8
alignbytes=8, prototype=define
Linker and Libraries:
ld='gcc-5.0', ldflags =' -fstack-protector-strong -L/usr/local/lib'
libpth=/usr/local/lib /usr/local/lib/gcc/x86_64-unknown-linux-gnu/5.0.0/include-fixed /usr/include/x86_64-linux-gnu /usr/lib /lib/x86_64-linux-gnu /lib/../lib /usr/lib/x86_64-linux-gnu /usr/lib/../lib /lib /lib64 /usr/lib64 /usr/local/lib64
libs=-lpthread -lnsl -lgdbm -ldb -ldl -lm -lcrypt -lutil -lc -lgdbm_compat
perllibs=-lpthread -lnsl -ldl -lm -lcrypt -lutil -lc
libc=libc-2.19.so, so=so, useshrplib=false, libperl=libperl.a
gnulibc_version='2.19'
Dynamic Linking:
dlsrc=dl_dlopen.xs, dlext=so, d_dlsymun=undef, ccdlflags='-Wl,-E'
cccdlflags='-fPIC', lddlflags='-shared -g3 -L/usr/local/lib -fstack-protector-strong'

Locally applied patches:
Devel::PatchPerl 1.30

---
@INC for perl 5.21.9:
/usr/local/lib/perl5/site_perl/5.21.9/x86_64-linux-debug
/usr/local/lib/perl5/site_perl/5.21.9
/usr/local/lib/perl5/5.21.9/x86_64-linux-debug
/usr/local/lib/perl5/5.21.9
/usr/local/lib/perl5/site_perl/5.21.8
/usr/local/lib/perl5/site_perl/5.21.7
/usr/local/lib/perl5/site_perl/5.21.4
/usr/local/lib/perl5/site_perl/5.21.3
/usr/local/lib/perl5/site_perl/5.21.2
/usr/local/lib/perl5/site_perl/5.21.1
/usr/local/lib/perl5/site_perl/5.21.0
/usr/local/lib/perl5/site_perl/5.20.1
/usr/local/lib/perl5/site_perl/5.20.0
/usr/local/lib/perl5/site_perl/5.19.11
/usr/local/lib/perl5/site_perl/5.19.10
/usr/local/lib/perl5/site_perl/5.19.9
/usr/local/lib/perl5/site_perl/5.19.8
/usr/local/lib/perl5/site_perl/5.19.7
/usr/local/lib/perl5/site_perl/5.19.6
/usr/local/lib/perl5/site_perl/5.19.5
/usr/local/lib/perl5/site_perl/5.19.4
/usr/local/lib/perl5/site_perl/5.19.3
/usr/local/lib/perl5/site_perl/5.19.2
/usr/local/lib/perl5/site_perl/5.19.1
/usr/local/lib/perl5/site_perl/5.19.0
/usr/local/lib/perl5/site_perl/5.18.4
/usr/local/lib/perl5/site_perl/5.18.2
/usr/local/lib/perl5/site_perl/5.18.1
/usr/local/lib/perl5/site_perl/5.18.0
/usr/local/lib/perl5/site_perl/5.17.11
/usr/local/lib/perl5/site_perl/5.17.10
/usr/local/lib/perl5/site_perl/5.17.8
/usr/local/lib/perl5/site_perl/5.17.7
/usr/local/lib/perl5/site_perl/5.17.6
/usr/local/lib/perl5/site_perl/5.17.5
/usr/local/lib/perl5/site_perl/5.17.4
/usr/local/lib/perl5/site_perl/5.17.3
/usr/local/lib/perl5/site_perl/5.17.2
/usr/local/lib/perl5/site_perl/5.17.1
/usr/local/lib/perl5/site_perl/5.17.0
/usr/local/lib/perl5/site_perl/5.17
/usr/local/lib/perl5/site_perl/5.16.3
/usr/local/lib/perl5/site_perl/5.16.2
/usr/local/lib/perl5/site_perl/5.16.1
/usr/local/lib/perl5/site_perl/5.16.0
/usr/local/lib/perl5/site_perl/5.15.9
/usr/local/lib/perl5/site_perl/5.15.8
/usr/local/lib/perl5/site_perl/5.15.7
/usr/local/lib/perl5/site_perl/5.15.6
/usr/local/lib/perl5/site_perl/5.15.5
/usr/local/lib/perl5/site_perl/5.15.4
/usr/local/lib/perl5/site_perl/5.15.3
/usr/local/lib/perl5/site_perl/5.15.2
/usr/local/lib/perl5/site_perl/5.14.4
/usr/local/lib/perl5/site_perl/5.14.3
/usr/local/lib/perl5/site_perl/5.14.2
/usr/local/lib/perl5/site_perl/5.14.1
/usr/local/lib/perl5/site_perl/5.12.5
/usr/local/lib/perl5/site_perl/5.12.4
/usr/local/lib/perl5/site_perl/5.10.1
/usr/local/lib/perl5/site_perl/5.8.9
/usr/local/lib/perl5/site_perl/5.8.8
/usr/local/lib/perl5/site_perl/5.8.7
/usr/local/lib/perl5/site_perl/5.8.6
/usr/local/lib/perl5/site_perl/5.8.5
/usr/local/lib/perl5/site_perl/5.8.4
/usr/local/lib/perl5/site_perl/5.8.3
/usr/local/lib/perl5/site_perl/5.8.2
/usr/local/lib/perl5/site_perl/5.8.1
/usr/local/lib/perl5/site_perl/5.6.2
/usr/local/lib/perl5/site_perl
.

---
Environment for perl 5.21.9:
HOME=/home/rurban
LANG=en_US.utf8
LANGUAGE (unset)
LD_LIBRARY_PATH (unset)
LOGDIR (unset)
PATH=/home/rurban/bin:/usr/local/bin:/usr/bin:/bin:/usr/local/games:/usr/games
PERL_BADLANG (unset)
SHELL=/bin/bash

@p5pRT
Copy link
Author

p5pRT commented Mar 14, 2015

From @rurban

0001-perl_hash_crc32-use-HW-hasher-as-default-with-SSE4.2.patch
From 57fd1b00ed72266d1f18de751c9c0a793e136bba Mon Sep 17 00:00:00 2001
From: Reini Urban <rurban@x-ray.at>
Date: Mon, 14 Apr 2014 17:18:51 -0500
Subject: [PATCH] perl_hash_crc32: use HW hasher as default with SSE4.2

can be enabled with the following ccflags:
  -march=native or -mcrc32 or -msse42

also with untested AARCH64_FL_CRC support
https://gcc.gnu.org/ml/gcc-patches/2014-01/msg01012.html

See https://github.com/rurban/perl-hash-stats#perl-hash-stats for the analysis.
iSCSI CRC32-C is by far the fastest hash function tested, and produces on average
the least collisions, so is also the best for the average case.
                     collisions  cycles/hash
CRC32                1.066       29.78
ONE_AT_A_TIME_HARD   1.092       83.75

See https://github.com/rurban/smhasher#smhasher for a more detailled analysis on the hash
function qualities. 'doc/crc32_hw' is by far better than the current 'doc/JenkinsOOAT'

Worst-case:
You cannot trust any of these fast hash functions for security at all. Collision complexity
attacks need to be secured in other ways. It's trivial to generate such attacks without
our randomized hash seeds and iterators on all these hash functions.
Without those measures CRC32 is even more trivial to attack than siphash, city, jenkins
or murmur.

Eventually we will need to switch to a better hash table scheme, which will be faster
(more cache-friendly), has better key checks, and avoids complexity attacks against our
linear linked lists at all. Sorted buckets, double-hashing, universal hashing or adding
a sleep with >10 collisions are all better schemes that I am working on.
---
 hv_func.h | 78 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++----
 1 file changed, 74 insertions(+), 4 deletions(-)

diff --git hv_func.h hv_func.h
index 24ebf56..6a25014 100644
--- hv_func.h
+++ hv_func.h
@@ -23,9 +23,14 @@
         || defined(PERL_HASH_FUNC_ONE_AT_A_TIME_OLD) \
         || defined(PERL_HASH_FUNC_MURMUR_HASH_64A) \
         || defined(PERL_HASH_FUNC_MURMUR_HASH_64B) \
+        || defined(PERL_HASH_FUNC_CRC32) \
     )
+#if (defined(__SSE4_2__) || defined(AARCH64_FL_CRC))
+#define PERL_HASH_FUNC_CRC32
+#else
 #define PERL_HASH_FUNC_ONE_AT_A_TIME_HARD
 #endif
+#endif
 
 #if defined(PERL_HASH_FUNC_SIPHASH)
 #   define PERL_HASH_FUNC "SIPHASH_2_4"
@@ -67,6 +72,14 @@
 #   define PERL_HASH_FUNC "MURMUR_HASH_64B"
 #   define PERL_HASH_SEED_BYTES 8
 #   define PERL_HASH_WITH_SEED(seed,hash,str,len) (hash)= S_perl_hash_murmur_hash_64b((seed),(U8*)(str),(len))
+#elif defined(PERL_HASH_FUNC_CRC32)
+#   define PERL_HASH_FUNC "CRC32"
+#   define PERL_HASH_SEED_BYTES 4
+#   define PERL_HASH_WITH_SEED(seed,hash,str,len) (hash)= S_perl_hash_crc32((seed),(U8*)(str),(len))
+#elif defined(PERL_HASH_FUNC_CITY)
+#   define PERL_HASH_FUNC "CITY"
+#   define PERL_HASH_SEED_BYTES 4
+#   define PERL_HASH_WITH_SEED(seed,hash,str,len) (hash)= S_perl_hash_city((seed),(U8*)(str),(len))
 #endif
 
 #ifndef PERL_HASH_WITH_SEED
@@ -93,6 +106,8 @@
 
 #define PERL_HASH(hash,str,len) PERL_HASH_WITH_SEED(PERL_HASH_SEED,hash,str,len)
 
+#include <assert.h>
+
 /*-----------------------------------------------------------------------------
  * Endianess, misalignment capabilities and util macros
  *
@@ -274,6 +289,7 @@ S_perl_hash_superfast(const unsigned char * const seed, const unsigned char *str
     int rem= len & 3;
     len >>= 2;
 
+    assert(hash);
     for (;len > 0; len--) {
         hash  += U8TO16_LE (str);
         tmp    = (U8TO16_LE (str+2) << 11) ^ hash;
@@ -468,8 +484,10 @@ PERL_STATIC_INLINE U32
 S_perl_hash_djb2(const unsigned char * const seed, const unsigned char *str, const STRLEN len) {
     const unsigned char * const end = (const unsigned char *)str + len;
     U32 hash = *((U32*)seed) + (U32)len;
+    assert(hash);
     while (str < end) {
-        hash = ((hash << 5) + hash) + *str++;
+        hash = ((hash << 5) + hash) + *str;
+        str++;
     }
     return hash;
 }
@@ -478,8 +496,10 @@ PERL_STATIC_INLINE U32
 S_perl_hash_sdbm(const unsigned char * const seed, const unsigned char *str, const STRLEN len) {
     const unsigned char * const end = (const unsigned char *)str + len;
     U32 hash = *((U32*)seed) + (U32)len;
+    assert(hash);
     while (str < end) {
-        hash = (hash << 6) + (hash << 16) - hash + *str++;
+        hash = (hash << 6) + (hash << 16) - hash + *str;
+        str++;
     }
     return hash;
 }
@@ -504,6 +524,7 @@ PERL_STATIC_INLINE U32
 S_perl_hash_one_at_a_time(const unsigned char * const seed, const unsigned char *str, const STRLEN len) {
     const unsigned char * const end = (const unsigned char *)str + len;
     U32 hash = *((U32*)seed) + (U32)len;
+    assert(hash);
     while (str < end) {
         hash += *str++;
         hash += (hash << 10);
@@ -519,7 +540,7 @@ PERL_STATIC_INLINE U32
 S_perl_hash_one_at_a_time_hard(const unsigned char * const seed, const unsigned char *str, const STRLEN len) {
     const unsigned char * const end = (const unsigned char *)str + len;
     U32 hash = *((U32*)seed) + (U32)len;
-    
+    assert(hash);
     while (str < end) {
         hash += (hash << 10);
         hash ^= (hash >> 6);
@@ -554,6 +575,7 @@ PERL_STATIC_INLINE U32
 S_perl_hash_old_one_at_a_time(const unsigned char * const seed, const unsigned char *str, const STRLEN len) {
     const unsigned char * const end = (const unsigned char *)str + len;
     U32 hash = *((U32*)seed);
+    assert(hash);
     while (str < end) {
         hash += *str++;
         hash += (hash << 10);
@@ -628,7 +650,7 @@ S_perl_hash_murmur_hash_64a (const unsigned char * const seed, const unsigned ch
    a 32 bit value
 
    Note uses unaligned 32 bit loads - will NOT work on machines with
-   strict alginment requirements.
+   strict alignment requirements.
 
    Also this code may not be suitable for big-endian machines.
 */
@@ -692,6 +714,54 @@ S_perl_hash_murmur_hash_64b (const unsigned char * const seed, const unsigned ch
 }
 #endif
 
+
+#if defined(PERL_HASH_FUNC_CRC32) && (defined(__SSE4_2__) || defined(AARCH64_FL_CRC))
+#include <smmintrin.h>
+
+/* Byte-boundary alignment issues */
+#define ALIGN_SIZE      0x08UL
+#define ALIGN_MASK      (ALIGN_SIZE - 1)
+#define CALC_CRC(op, crc, type, buf, len)                               \
+  do {                                                                  \
+    for (; (len) >= sizeof (type); (len) -= sizeof(type), buf += sizeof (type)) { \
+      (crc) = op((crc), *(type *) (buf));                               \
+    }                                                                   \
+  } while(0)
+
+PERL_STATIC_INLINE U32
+S_perl_hash_crc32(const unsigned char * const seed, const unsigned char *str, STRLEN len) {
+    const char* buf = (const char*)str;
+    U32 hash = *((U32*)seed); /* tested nok + len in variant .1 much higher collision costs */
+
+    /* Align the input to the word boundary */
+    for (; (len > 0) && ((size_t)buf & ALIGN_MASK); len--, buf++) {
+        hash = _mm_crc32_u8(hash, *buf);
+    }
+
+#ifdef __x86_64__
+    CALC_CRC(_mm_crc32_u64, hash, uint64_t, buf, len);
+#endif
+    CALC_CRC(_mm_crc32_u32, hash, uint32_t, buf, len);
+    CALC_CRC(_mm_crc32_u16, hash, uint16_t, buf, len);
+    CALC_CRC(_mm_crc32_u8, hash, uint8_t, buf, len);
+
+    return hash;
+}
+#endif
+
+#if 0
+/* Should be the best on non-x86 CPUs. NYI */
+PERL_STATIC_INLINE U32
+S_perl_hash_city(const unsigned char * const seed, const unsigned char *str, const STRLEN len) {
+    U32 hash = *((U32*)seed);
+#define k2 0x9ae16a3b2f90404fULL
+    return HashLen16(CityHash64(str, len) - k2, hash);
+#undef k2
+    return (hash ^ 0xFFFFFFFF);
+}
+#endif
+
+
 /* legacy - only mod_perl should be doing this.  */
 #ifdef PERL_HASH_INTERNAL_ACCESS
 #define PERL_HASH_INTERNAL(hash,str,len) PERL_HASH(hash,str,len)
-- 
2.1.4

@p5pRT
Copy link
Author

p5pRT commented Mar 16, 2015

From @bulk88

To whatever committer will review this, there are also a couple more hash algos, including hardware AES hash on an abandoned/stalled branch http​://perl5.git.perl.org/perl.git/shortlog/refs/heads/yves/hash_wip_lastet specifically commit http​://perl5.git.perl.org/perl.git/commitdiff/694bbdcff696678ca9df69c15dea62a6e6e0df2a Notice rurban's patch is hardware CRC hash. Hardware CRC and hardware AES did not come out together in Intel CPUs, so the wont share the exact same CPP macros controlling their usage, but there might need to be some thought given (maybe in Configure, IDK), on how to support hardware specific code in the Perl core, and of both of these patches are using the "right" macros to control their availability. I am not expecting rurban to write such an infrastructure, but someone else (maybe a committer) wants to, they should.

--
bulk88 ~ bulk88 at hotmail.com

@p5pRT
Copy link
Author

p5pRT commented Mar 16, 2015

The RT System itself - Status changed from 'new' to 'open'

@p5pRT
Copy link
Author

p5pRT commented Mar 17, 2015

From @rurban

On 2nd thought I wont feel comfortable enough to have this now enabled as default.
Just make it available as selectable option.

I'm rewriting the hash tables soon, and will not need HW CRC32-C. I'd rather prefer glibc double hashing (hsearch) with their short hashers, or even universal hashers for maximum security (ie. 2 random hash functions).

And I haven't worked on security with the new hash table using CRC32-C, which is known to be easily attacked.

@p5pRT
Copy link
Author

p5pRT commented Mar 17, 2015

From @kentfredric

On 16 March 2015 at 23​:38, bulk88 via RT <perlbug-followup@​perl.org> wrote​:

but there might need to be some thought given (maybe in Configure, IDK),
on how to support hardware specific code in the Perl core

+1. Hardware specific codepaths indeed need to be configurable and not 100%
automagical, for crossdev scenarios mostly.

If it can be expressed in terms of a specific CPUFlag oriented toggle, not
a feature specific toggle, then that would be desirable.

  --with-cpu-avx

For instance.

--
Kent

*KENTNL* - https://metacpan.org/author/KENTNL

@p5pRT
Copy link
Author

p5pRT commented Mar 20, 2015

From @rurban

On 03/17/2015 06​:04 PM, Kent Fredric via RT wrote​:

On 16 March 2015 at 23​:38, bulk88 via RT <perlbug-followup@​perl.org> wrote​:

but there might need to be some thought given (maybe in Configure, IDK),
on how to support hardware specific code in the Perl core

+1. Hardware specific codepaths indeed need to be configurable and not 100%
automagical, for crossdev scenarios mostly.

If it can be expressed in terms of a specific CPUFlag oriented toggle, not
a feature specific toggle, then that would be desirable.

--with-cpu-avx

IMHO not needed.
The current hardware specific toggle to check for __SSE4_2__ at
compile-time would be the same as a hardware specific check in Configure.

The only theoretical problem is with packagers who compile i386 with
-mcrc32 or -msse42, and then when the target machine is a real i386, and
not a i586 it will fail.
But this is entirely a packaging bug we cannot prevent.

For cross-compilation it is current practice that the target config.sh
is properly filled out.

A run-time check for sse4.2/aarch64 cpu features is only needed in a jit.

@p5pRT
Copy link
Author

p5pRT commented Mar 30, 2015

From @tonycoz

On Sat Mar 14 03​:50​:13 2015, rurban@​cpanel.net wrote​:

perl_hash_crc32​: use HW hasher as default with SSE4.2

can be enabled with the following ccflags​:
-march=native or -mcrc32 or -msse42

I think these assertions​:

@​@​ -504,6 +524,7 @​@​ PERL_STATIC_INLINE U32
S_perl_hash_one_at_a_time(const unsigned char * const seed, const unsigned char *str, const STRLEN len) {
  const unsigned char * const end = (const unsigned char *)str + len;
  U32 hash = *((U32*)seed) + (U32)len;
+ assert(hash);
  while (str < end) {
  hash += *str++;
  hash += (hash << 10);

are just plain wrong.

What happens when (U32)(*seed + len) just happen to be zero?

I don't think crc32 has enough hash seed length to be the default hashing algorithm.

Tony

@p5pRT
Copy link
Author

p5pRT commented Apr 3, 2015

From @rurban

On 03/30/2015 02​:37 AM, Tony Cook via RT wrote​:

On Sat Mar 14 03​:50​:13 2015, rurban@​cpanel.net wrote​:

perl_hash_crc32​: use HW hasher as default with SSE4.2

can be enabled with the following ccflags​:
-march=native or -mcrc32 or -msse42

I think these assertions​:

@​@​ -504,6 +524,7 @​@​ PERL_STATIC_INLINE U32
S_perl_hash_one_at_a_time(const unsigned char * const seed, const unsigned char *str, const STRLEN len) {
const unsigned char * const end = (const unsigned char *)str + len;
U32 hash = *((U32*)seed) + (U32)len;
+ assert(hash);
while (str < end) {
hash += *str++;
hash += (hash << 10);

are just plain wrong.

What happens when (U32)(*seed + len) just happen to be zero?

Yes, this was only there for debugging to catch the common zero-collapse
problem. It should be #ifdef DEBUGGING

I don't think crc32 has enough hash seed length to be the default hashing algorithm.

hash seed length? This is a global for all hash functions. What do you mean?

Having calculated the statistical average case your sentiment is wrong.
It is not only the fastest, it is also statistically the best.

You can argue about the security by known attacks on the CRC scheme.
Talking about security via hash functions only, only the slower siphash
makes sense.

@p5pRT
Copy link
Author

p5pRT commented Aug 3, 2015

From @tonycoz

On Fri Apr 03 02​:50​:43 2015, rurban@​cpanel.net wrote​:

On 03/30/2015 02​:37 AM, Tony Cook via RT wrote​:

On Sat Mar 14 03​:50​:13 2015, rurban@​cpanel.net wrote​:

perl_hash_crc32​: use HW hasher as default with SSE4.2

can be enabled with the following ccflags​:
-march=native or -mcrc32 or -msse42

I think these assertions​:

@​@​ -504,6 +524,7 @​@​ PERL_STATIC_INLINE U32
S_perl_hash_one_at_a_time(const unsigned char * const seed, const
unsigned char *str, const STRLEN len) {
const unsigned char * const end = (const unsigned char *)str +
len;
U32 hash = *((U32*)seed) + (U32)len;
+ assert(hash);
while (str < end) {
hash += *str++;
hash += (hash << 10);

are just plain wrong.

What happens when (U32)(*seed + len) just happen to be zero?

Yes, this was only there for debugging to catch the common zero-
collapse
problem. It should be #ifdef DEBUGGING

No, the problem is that (U32)(seed+len) will be zero in 1 in 2**32 cases[1] (consider a seed of 0xFFFFFF0 and len = 0x10), so the assert() shouldn't be there at all.

assert() is only tested under -DDEBUGGING by default anyway.

I don't think crc32 has enough hash seed length to be the default
hashing algorithm.

hash seed length? This is a global for all hash functions. What do you
mean?

Having calculated the statistical average case your sentiment is
wrong.
It is not only the fastest, it is also statistically the best.

You can argue about the security by known attacks on the CRC scheme.
Talking about security via hash functions only, only the slower
siphash
makes sense.

The problem is, even with hash order randomization, I expect a 32-bit seed to be fairly cheap to brute-force[2]

I'm not claiming that ONE_AT_A_TIME_HARD is crytographically strong, but the 64-bit seed does provide some protection against more casual attackers.

I'd have no problem accepting a patch that added CRC32 hashes as an option, which will make it simpler for you to build your own perls with that hash.

I won't accept a patch that makes CRC32 the default hash algorithm.

Tony

[1] complicated by the distribution of len values, which tend to be short, but seed should be fairly evenly distrubuted.

[2] the original 32-bit seeds were easily brute-forced on an Intel Q9660.

@p5pRT
Copy link
Author

p5pRT commented Aug 25, 2015

From @rurban

On Sun Aug 02 17​:56​:25 2015, tonyc wrote​:

On Fri Apr 03 02​:50​:43 2015, rurban@​cpanel.net wrote​:

On 03/30/2015 02​:37 AM, Tony Cook via RT wrote​:

On Sat Mar 14 03​:50​:13 2015, rurban@​cpanel.net wrote​:

perl_hash_crc32​: use HW hasher as default with SSE4.2

can be enabled with the following ccflags​:
-march=native or -mcrc32 or -msse42

I think these assertions​:

@​@​ -504,6 +524,7 @​@​ PERL_STATIC_INLINE U32
S_perl_hash_one_at_a_time(const unsigned char * const seed, const
unsigned char *str, const STRLEN len) {
const unsigned char * const end = (const unsigned char *)str +
len;
U32 hash = *((U32*)seed) + (U32)len;
+ assert(hash);
while (str < end) {
hash += *str++;
hash += (hash << 10);

are just plain wrong.

What happens when (U32)(*seed + len) just happen to be zero?

Yes, this was only there for debugging to catch the common zero-
collapse
problem. It should be #ifdef DEBUGGING

No, the problem is that (U32)(seed+len) will be zero in 1 in 2**32
cases[1] (consider a seed of 0xFFFFFF0 and len = 0x10), so the
assert() shouldn't be there at all.

I preferred zero hashes to assert, as they are invariant against \0 attacks.
As you found out, this assert is only during debugging.

assert() is only tested under -DDEBUGGING by default anyway.

I don't think crc32 has enough hash seed length to be the default
hashing algorithm.

hash seed length? This is a global for all hash functions. What do
you
mean?

Having calculated the statistical average case your sentiment is
wrong.
It is not only the fastest, it is also statistically the best.

You can argue about the security by known attacks on the CRC scheme.
Talking about security via hash functions only, only the slower
siphash
makes sense.

The problem is, even with hash order randomization, I expect a 32-bit
seed to be fairly cheap to brute-force[2]

I wrote a brute-forcer, and the faster the hash, the faster the brute-forcer.
32-bit is done <4s.

I'm not claiming that ONE_AT_A_TIME_HARD is crytographically strong,
but the 64-bit seed does provide some protection against more casual
attackers.

I see. 64bit seeds are trivial to add to all hash funcs.

I'd have no problem accepting a patch that added CRC32 hashes as an
option, which will make it simpler for you to build your own perls
with that hash.

I made it much simplier for me to use different hashes with a
Configure -Dhash_func=name option, so this argument is bogus.

But I switched to FNV1A now, which makes the fastest HT, and doesn't have
the security problems of CRC. Explained at https://github.com/rurban/smhasher and
https://github.com/rurban/perl-hash-stats
This patch was written a year ago, and is long outdated since.

I won't accept a patch that makes CRC32 the default hash algorithm.

Because? It creates the best distribution? It is the fastest?
You need to work on your argumentation a bit.
You are still using one of the worst default hash functions of all tested.
Slow *and* bad. Only DJB2 and OOAT is worse, but 8 others are better.

[1] complicated by the distribution of len values, which tend to be
short, but seed should be fairly evenly distrubuted.

[2] the original 32-bit seeds were easily brute-forced on an Intel
Q9660.

Exactly. That's why the whole security theatre is bogus.
--
Reini Urban

@p5pRT
Copy link
Author

p5pRT commented Aug 25, 2015

From @tonycoz

On Tue Aug 25 07​:41​:42 2015, rurban wrote​:

On Sun Aug 02 17​:56​:25 2015, tonyc wrote​:

On Fri Apr 03 02​:50​:43 2015, rurban@​cpanel.net wrote​:

On 03/30/2015 02​:37 AM, Tony Cook via RT wrote​:

On Sat Mar 14 03​:50​:13 2015, rurban@​cpanel.net wrote​:

perl_hash_crc32​: use HW hasher as default with SSE4.2

can be enabled with the following ccflags​:
-march=native or -mcrc32 or -msse42

I think these assertions​:

@​@​ -504,6 +524,7 @​@​ PERL_STATIC_INLINE U32
S_perl_hash_one_at_a_time(const unsigned char * const seed,
const
unsigned char *str, const STRLEN len) {
const unsigned char * const end = (const unsigned char *)str
+
len;
U32 hash = *((U32*)seed) + (U32)len;
+ assert(hash);
while (str < end) {
hash += *str++;
hash += (hash << 10);

are just plain wrong.

What happens when (U32)(*seed + len) just happen to be zero?

Yes, this was only there for debugging to catch the common zero-
collapse
problem. It should be #ifdef DEBUGGING

No, the problem is that (U32)(seed+len) will be zero in 1 in 2**32
cases[1] (consider a seed of 0xFFFFFF0 and len = 0x10), so the
assert() shouldn't be there at all.

I preferred zero hashes to assert, as they are invariant against \0
attacks.
As you found out, this assert is only during debugging.

asserts should only trigger when the code is in error. Since a zero (seed+len) can occur during normal operation the asserts are inappropriate.

assert() is only tested under -DDEBUGGING by default anyway.

I don't think crc32 has enough hash seed length to be the default
hashing algorithm.

hash seed length? This is a global for all hash functions. What do
you
mean?

Having calculated the statistical average case your sentiment is
wrong.
It is not only the fastest, it is also statistically the best.

You can argue about the security by known attacks on the CRC
scheme.
Talking about security via hash functions only, only the slower
siphash
makes sense.

The problem is, even with hash order randomization, I expect a 32-bit
seed to be fairly cheap to brute-force[2]

I wrote a brute-forcer, and the faster the hash, the faster the brute-
forcer.
32-bit is done <4s.

I'm not claiming that ONE_AT_A_TIME_HARD is crytographically strong,
but the 64-bit seed does provide some protection against more casual
attackers.

I see. 64bit seeds are trivial to add to all hash funcs.

I'd have no problem accepting a patch that added CRC32 hashes as an
option, which will make it simpler for you to build your own perls
with that hash.

I made it much simplier for me to use different hashes with a
Configure -Dhash_func=name option, so this argument is bogus.

But I switched to FNV1A now, which makes the fastest HT, and doesn't
have
the security problems of CRC. Explained at
https://github.com/rurban/smhasher and
https://github.com/rurban/perl-hash-stats
This patch was written a year ago, and is long outdated since.

I won't accept a patch that makes CRC32 the default hash algorithm.

Because? It creates the best distribution? It is the fastest?
You need to work on your argumentation a bit.
You are still using one of the worst default hash functions of all
tested.
Slow *and* bad. Only DJB2 and OOAT is worse, but 8 others are better.

Because it has only a 32-bit seed space, which makes it trivial to brute-force, as you confirmed above.

[1] complicated by the distribution of len values, which tend to be
short, but seed should be fairly evenly distrubuted.

[2] the original 32-bit seeds were easily brute-forced on an Intel
Q9660.

Exactly. That's why the whole security theatre is bogus.

We use a 64-bit seed to make such brute-forcing harder (not impossible).

Tony

@p5pRT
Copy link
Author

p5pRT commented Mar 16, 2017

From @demerphq

On 26 August 2015 at 01​:58, Tony Cook via RT <perlbug-followup@​perl.org> wrote​:

On Tue Aug 25 07​:41​:42 2015, rurban wrote​:

On Sun Aug 02 17​:56​:25 2015, tonyc wrote​:

On Fri Apr 03 02​:50​:43 2015, rurban@​cpanel.net wrote​:

On 03/30/2015 02​:37 AM, Tony Cook via RT wrote​:

On Sat Mar 14 03​:50​:13 2015, rurban@​cpanel.net wrote​:

perl_hash_crc32​: use HW hasher as default with SSE4.2

can be enabled with the following ccflags​:
-march=native or -mcrc32 or -msse42

I think these assertions​:

@​@​ -504,6 +524,7 @​@​ PERL_STATIC_INLINE U32
S_perl_hash_one_at_a_time(const unsigned char * const seed,
const
unsigned char *str, const STRLEN len) {
const unsigned char * const end = (const unsigned char *)str
+
len;
U32 hash = *((U32*)seed) + (U32)len;
+ assert(hash);
while (str < end) {
hash += *str++;
hash += (hash << 10);

are just plain wrong.

What happens when (U32)(*seed + len) just happen to be zero?

Yes, this was only there for debugging to catch the common zero-
collapse
problem. It should be #ifdef DEBUGGING

No, the problem is that (U32)(seed+len) will be zero in 1 in 2**32
cases[1] (consider a seed of 0xFFFFFF0 and len = 0x10), so the
assert() shouldn't be there at all.

I preferred zero hashes to assert, as they are invariant against \0
attacks.
As you found out, this assert is only during debugging.

asserts should only trigger when the code is in error. Since a zero (seed+len) can occur during normal operation the asserts are inappropriate.

assert() is only tested under -DDEBUGGING by default anyway.

I don't think crc32 has enough hash seed length to be the default
hashing algorithm.

hash seed length? This is a global for all hash functions. What do
you
mean?

Having calculated the statistical average case your sentiment is
wrong.
It is not only the fastest, it is also statistically the best.

You can argue about the security by known attacks on the CRC
scheme.
Talking about security via hash functions only, only the slower
siphash
makes sense.

The problem is, even with hash order randomization, I expect a 32-bit
seed to be fairly cheap to brute-force[2]

I wrote a brute-forcer, and the faster the hash, the faster the brute-
forcer.
32-bit is done <4s.

I'm not claiming that ONE_AT_A_TIME_HARD is crytographically strong,
but the 64-bit seed does provide some protection against more casual
attackers.

I see. 64bit seeds are trivial to add to all hash funcs.

I'd have no problem accepting a patch that added CRC32 hashes as an
option, which will make it simpler for you to build your own perls
with that hash.

I made it much simplier for me to use different hashes with a
Configure -Dhash_func=name option, so this argument is bogus.

But I switched to FNV1A now, which makes the fastest HT, and doesn't
have
the security problems of CRC. Explained at
https://github.com/rurban/smhasher and
https://github.com/rurban/perl-hash-stats
This patch was written a year ago, and is long outdated since.

I won't accept a patch that makes CRC32 the default hash algorithm.

Because? It creates the best distribution? It is the fastest?
You need to work on your argumentation a bit.
You are still using one of the worst default hash functions of all
tested.
Slow *and* bad. Only DJB2 and OOAT is worse, but 8 others are better.

Because it has only a 32-bit seed space, which makes it trivial to brute-force, as you confirmed above.

[1] complicated by the distribution of len values, which tend to be
short, but seed should be fairly evenly distrubuted.

[2] the original 32-bit seeds were easily brute-forced on an Intel
Q9660.

Exactly. That's why the whole security theatre is bogus.

We use a 64-bit seed to make such brute-forcing harder (not impossible).

It is not just that. The hash Reini was advocating has a trivial
multi-collision attack. I have implemented a test for the
multi-collision attack in my version of smhasher. It proves that you
can break pretty much any hash based on Intel CRC intrinsics without
knowing how they work, or what seed they are using. CRC is an
incredibly bad base unit of processing for hashes, the exact
properties that make it so desirable as a CRC make it incredibly
undesirable as a hash. Using it via the Intel intrinsic
__mm_crc32_u64() is especially irresponsible. That operation takes an
64 bit value and calculates a 32 bit CRC from it. That guarantees
2**32 possible collisions per block. You only need to look at about
160K random blocks before you find a collision. Writing the code to
CRC 160k random blocks, sorting it to find the dupes, etc, takes a
developer like me about 10 minutes. Once you have that CRC block
collision, you take the two blocks and treat them as the bits 0 and 1,
and then expand out an integer bit for block, and presto, you have the
ability to create an aribitrary set of collisions that will break any
naive use of CRC, which is what most will be if they are using it for
speed.

So the same set of blocks breaks all of the following functions​:

crc32_hw 32 32 32 FAILED 45 of 129 tests. Differential​:
17-18,23,29,31-33,39, Cyclic​: 46,48,50, TwoBytes​: 52-54,61,
CRC-MultiCollision​: 79-88, Lowbits​: 90-91, Highbits​: 93-94, Highbits2​:
96-97, HighBit​: 99-100, LowBit​: 102-103, Hi-Lo​: 105-106, Text​:
108,110-113, Seed​: 119-125
crc32_hw1 32 32 32 FAILED 68 of 173 tests. Differential​:
17-41, Cyclic​: 48,50,52, TwoBytes​: 54-56,63, Crc-MultiCollision​:
81-90, Murmur2-MultiCollision​: 94-95,97-100, Lowbits​: 132-133,
Highbits​: 135-136, Highbits2​: 138-139, HiBit-Null​: 141-142,
LowBit-Null​: 144-145, Hi-Lo​: 147-148, Text​: 150-152,154-155, Seed​:
161-162,167
crc64_hw 64 64 64 FAILED 105 of 131 tests.
Differential​: 17-41, Cyclic​: 42-52, TwoBytes​: 53-63, Sparse​: 64-80,
CRC-MultiCollision​: 81-90, Lowbits​: 92-93, Highbits​: 95-96, Highbits2​:
98-99, HighBit​: 101-102, LowBit​: 104-105, Hi-Lo​: 106-108, Text​:
110-112,114-115, Zeroes​: 117-118, Seed​: 119-127, Effs​: 129-130
metrohash128crc_1 64 64 128 FAILED 20 of 129 tests. Differential​:
17-24,39, CRC-MultiCollision​: 79-88
metrohash128crc_2 64 64 128 FAILED 21 of 133 tests. Differential​:
17-24,38,41, CRC-MultiCollision​: 81-90
metrohash64crc_1 64 64 64 FAILED 17 of 131 tests. Differential​:
17,19,21,41, Cyclic​: 42,52, CRC-MultiCollision​: 81-90
metrohash64crc_2 64 64 64 FAILED 17 of 131 tests. Differential​:
17,19,21,41, Cyclic​: 42,52, CRC-MultiCollision​: 81-90
t1ha_crc 64 64 64 FAILED 36 of 133 tests. Differential​:
17-41, CRC-MultiCollision​: 81-90

The only hash functions that use CRC that do not get tripped up by
this use CRC to perturb internal random state, not on input data.

You can see detailed test reports, summaries, graphs, etc at

https://github.com/demerphq/smhasher

cheers,
Yves

--
perl -Mre=debug -e "/just|another|perl|hacker/"

@p5pRT
Copy link
Author

p5pRT commented Mar 16, 2017

From @kentfredric

On 16 March 2017 at 21​:02, demerphq <demerphq@​gmail.com> wrote​:

CRC is an
incredibly bad base unit of processing for hashes, the exact
properties that make it so desirable as a CRC make it incredibly
undesirable as a hash. Using it via the Intel intrinsic
__mm_crc32_u64() is especially irresponsible. That operation takes an
64 bit value and calculates a 32 bit CRC from it. That guarantees
2**32 possible collisions per block. You only need to look at about
160K random blocks before you find a collision

Can we expect to see -DPERL_HASH_FUNC_CRC in the future anyway, with sufficient
warnings around its use in this regard?

Obviously this is a security risk if your Perl instance is exposed on
a public interface.

But I'm very much not concerned about that threat with no public
interface, I just want my Perl
to run fast.

How likely is it I'm going to run 160k blocks locally in a non-threat
scenario by accident?

How bad are the side effects of that going to be realistically?

To the extent if it were feasible, I'd champion adding 2 top level
configure arguments that picked specific defaults

-Dprofile=fast-but-insecure ( no taint support maybe, a fast hash
implementation , no stack protectors etc, )
-Dprofile=secure-but-slow ( expensive enhancements to taint support,
massively slow but impenetrable hash function , etc )

( where the default would be neither of those things and would give
the current P5P balance-of-compromises )

Cos Its frustrating the on-going conflict we have between speed and
security, where maintainership
ends up picking which of those things people will end up getting.

We don't have to force everyone to compromise, surely?!

NB​: Currently using PERL_HASH_FUNC_SDBM because I /do not care/ , but
its the fastest hash on my hardware.

--
Kent

KENTNL - https://metacpan.org/author/KENTNL

@p5pRT
Copy link
Author

p5pRT commented Mar 16, 2017

From @demerphq

On 16 March 2017 at 19​:48, Kent Fredric <kentfredric@​gmail.com> wrote​:

On 16 March 2017 at 21​:02, demerphq <demerphq@​gmail.com> wrote​:

CRC is an
incredibly bad base unit of processing for hashes, the exact
properties that make it so desirable as a CRC make it incredibly
undesirable as a hash. Using it via the Intel intrinsic
__mm_crc32_u64() is especially irresponsible. That operation takes an
64 bit value and calculates a 32 bit CRC from it. That guarantees
2**32 possible collisions per block. You only need to look at about
160K random blocks before you find a collision

Can we expect to see -DPERL_HASH_FUNC_CRC in the future anyway, with sufficient
warnings around its use in this regard?

Er, no. I don't think so.

Obviously this is a security risk if your Perl instance is exposed on
a public interface.

But I'm very much not concerned about that threat with no public
interface, I just want my Perl
to run fast.

How likely is it I'm going to run 160k blocks locally in a non-threat
scenario by accident?

I don't think you understood the point. An attacker need only look at
160K blocks, on their own time, in his own space, to generate *two*
blocks. They then produce keys of the same length, with different
mixtures of the two blocks IOW, expand an integer of a certain bit
size, such that each bit 0 is represented by block 0, bit 1 is
represented by block 1. If you want 2**10 collision you need to
produce keys that are 10 blocks long.

How bad are the side effects of that going to be realistically?

Excessive collisions will noticable affect performance.

To the extent if it were feasible, I'd champion adding 2 top level
configure arguments that picked specific defaults

-Dprofile=fast-but-insecure ( no taint support maybe, a fast hash
implementation , no stack protectors etc, )
-Dprofile=secure-but-slow ( expensive enhancements to taint support,
massively slow but impenetrable hash function , etc )

( where the default would be neither of those things and would give
the current P5P balance-of-compromises )

Currently you can select the hash function you want to build with.

Cos Its frustrating the on-going conflict we have between speed and
security, where maintainership
ends up picking which of those things people will end up getting.

And where we lean towards secure over fast. I understand your concern.

We don't have to force everyone to compromise, surely?!

NB​: Currently using PERL_HASH_FUNC_SDBM because I /do not care/ , but
its the fastest hash on my hardware.

I find that quite surprising. Also unfortunate, I removed support for
sdbm recently. sdbm is a "one-at-a-time" hash with terrible
properties. I would be really surprised if one of the modern block
oriented alternatives is not markedly faster. Actually I wouldnt be
surprised if *SipHash13* was faster.

I hope to provide some better alternatives soon.

Yves

--
perl -Mre=debug -e "/just|another|perl|hacker/"

@p5pRT
Copy link
Author

p5pRT commented Mar 16, 2017

From @kentfredric

On 17 March 2017 at 09​:20, demerphq <demerphq@​gmail.com> wrote​:

. An attacker

The question is​: How does this attacker mount their attack against my code.

If they're relying on some other exploit that allows executing
arbitrary perl locally, then I already have a problem much graver than
denial of service through memory exhaustion.

The only path I can think of here would be a malicious user shipping
CPAN code which used a handful of known bad hash key values,
and then inspiring me to run them.

But I'm not running any services or software that deals with 3rd
parties, so I'm at a loss to what this attack surface looks like in
reality.

I understand the theoretical problem, I just can't find any place it
would be applied.

And where we lean towards secure over fast. I understand your concern.

To be clear, its not a "leaning" for me, its a "usecase".

For local-access only on developmental-only tasks, fast is preferable,
because I have the security angle handled by other things surrounding
the other parts of my system that touch the exploit paths. I deal
predominantly with things where startup time and fast execution is
important, because nothing is long lived.

But if I *was* building a web service that wanted external access,
you can bet I'd be opting for slow things, maybe things as slow as
hash key tainting, because in that scenario, Perl is "The front line",
and thus needs to have the security beefed up. And things like startup
performance is less of a concern here because it gets ameliorated over
the long life.

Just the tools at my disposal to take this to these extremes is a
little underwhelming.

Hash Key taint support is something nobody can presently opt in to,
because the argument keeps being they're too slow for general use.

But on the other side, fast-but-insecure hash algorithms aren't
supported either, because they're too insecure.

Why can't it just be "give us both of these things and then fence them
off so people can make decisions about it instead?" while making
neither default and making sure you document how to / how not to use
them.

You could very much argue if I wanted those things I could spend time
and try to work out how to hack P5P myself, and then publish a fork
for other people who cared about these things... I just don't see that
line of progress being helpful to anyone, and the maximum utility is
that this stuff be in P5P surrounded by black and yellow stripes.

--
Kent

KENTNL - https://metacpan.org/author/KENTNL

@p5pRT
Copy link
Author

p5pRT commented Mar 17, 2017

From @demerphq

On 16 March 2017 at 21​:34, Kent Fredric <kentfredric@​gmail.com> wrote​:

On 17 March 2017 at 09​:20, demerphq <demerphq@​gmail.com> wrote​:

. An attacker

The question is​: How does this attacker mount their attack against my code.

By getting you to hash something causes degenerate behavior in your code.

CPAN code which used a handful of known bad hash key values,
and then inspiring me to run them.

Yes, I get you.

But I'm not running any services or software that deals with 3rd
parties, so I'm at a loss to what this attack surface looks like in
reality.

I understand, in many ways the *security* aspect only applies to
scenarios where there might actually be an attacker.

I understand the theoretical problem, I just can't find any place it
would be applied.

Well, I can definitely think of many use cases where "attack" is not
an issue, and I understand a user would want the option to choose
speed over any security risk.

And where we lean towards secure over fast. I understand your concern.

To be clear, its not a "leaning" for me, its a "usecase".

I am not sure we are on the same page here. What I mean is that Perl
is a *general purpose programming language*. General use implies
suitability to process untrusted data. Therefore given the balance of
concerns such as performance, portability, security, etc, for the
default we will probably always be inclined towards giving a bit more
security if it doesnt cost too much performance.

Having said that, I think there are some different issues here that
require some untangling.

First off, we want to find a happy medium between "secure enough", and
"fast". We also have to consider portability, architecture
(in)dependence, and things like that.

Another thing is that you seem to think that the trade off is "speed"
versus "security". IMO it really is not that simple. A good hash is
both fast AND reasonably secure.

Also just for the record, there is a distinction in my mind and usage
between "secure" and "cryptographic grade". IMO "secure" implies that
the hash function suitably hides the seed, that it is free from
obvious or known multi-collision attacks.

Also, I think its worth considering that there is a relationship
between "secure enough" and "good general purpose hashing function".
Both demand that the hash behave like a random function. A hash that
is insecure basically is just a hash that doesn't hash very well for
some input set, ergo not a good general purpose hash function. So for
me, it doesn't make sense in a general purpose context like a
programming language to expose a hash function that hashes incredibly
poorly for a given use case.

For local-access only on developmental-only tasks, fast is preferable,
because I have the security angle handled by other things surrounding
the other parts of my system that touch the exploit paths.

Playing devils advocate here, how can you say that when you already
said you don't know how an exploit would work?

I deal
predominantly with things where startup time and fast execution is
important, because nothing is long lived.

Well if speed is your concern then IMO using sdbm is a poor choice
unless you are predominently hashing strings under 3 characters long.
Also, sdbm is really not a very good hash function. It does not mix
the last bytes of the key properly, very few bits of the key actually
affect the hash result. I would assume that for many tasks you are
getting more collisions than you should.

But if I *was* building a web service that wanted external access,
you can bet I'd be opting for slow things, maybe things as slow as
hash key tainting, because in that scenario, Perl is "The front line",
and thus needs to have the security beefed up. And things like startup
performance is less of a concern here because it gets ameliorated over
the long life.

The front line can be something as simple rpm, or a sysadmin
management tool that looks for duplicate files, or something that
hashes a dictionary, or whatever. There are far far too many ways to
trick someone into hashing keys that you control to achieve a
degradation of service.

Just the tools at my disposal to take this to these extremes is a
little underwhelming.

Hash Key taint support is something nobody can presently opt in to,
because the argument keeps being they're too slow for general use.

But on the other side, fast-but-insecure hash algorithms aren't
supported either, because they're too insecure.

Well, no. Fast but insecure hash algorithms are rejected because
insecure == bad at hashing general use case data. As the old saw goes,
its easy to be fast if you don't have to be correct.

Why can't it just be "give us both of these things and then fence them
off so people can make decisions about it instead?" while making
neither default and making sure you document how to / how not to use
them.

That is what I have always been trying to do, however I would not put
it in such black and white terms. I believe that we should offer a
number of options along the spectrum of secure and fast. But I also
believe that the options we provide should /be good hashes/. I dont
believe that a hash with a multicollision attack is a good hash. There
will be some user out there who *accidentally* stumbles into the
degenerate hashing mode.

I mean, if you consider something much less controversial than
hashing, consider our policies on sorting. We don't by default expose
a sort algorithm with degenerate behaviour modes. We trade off being
slightly faster in the common case in return for not having terrible
worse cases. IMO we should take the same strategy with our hash
function. We should not expose hash functions which have a terrible
worse case. And hashes with known-multicollision attacks have a
provably terrible worse case, ergo they are rejected out of hand.

Anway, my feeling is that we should provide three options (compounded
somewhat by having to support 32 bit and 64 bit).

We should provide a "believed to be really secure" hash function.
SipHash24 is that. We should have a "good and fast" option, and we
should have a middle ground, which I believe that SipHash13 is. I
believe that there are some quality candidates for good and fast, and
I hope to get patches adding them to perl sometime sooner than later.

But really, I wonder at choosing sdbm. From what I know, pretty much
any block oriented hash function is going to outperform a
one-at-a-time once the string gets more than a few characters. Even
Siphash24 outperforms sdbm once you get to 13/14 byte strings. Other
block oriented hashes cross sdbm's line much sooner, at 4 or 5 bytes.
How comprehensive was your testing? How thorough was it?

Yves

--
perl -Mre=debug -e "/just|another|perl|hacker/"

@p5pRT
Copy link
Author

p5pRT commented Mar 17, 2017

From @kentfredric

On 17 March 2017 at 21​:28, demerphq <demerphq@​gmail.com> wrote​:

But really, I wonder at choosing sdbm. From what I know, pretty much
any block oriented hash function is going to outperform a
one-at-a-time once the string gets more than a few characters. Even
Siphash24 outperforms sdbm once you get to 13/14 byte strings. Other
block oriented hashes cross sdbm's line much sooner, at 4 or 5 bytes.
How comprehensive was your testing? How thorough was it?

Its been a long time now, so its hard to say

I recall I used Benchmark​::Perl​::CoreHashes at some point and recall
seeing it tell me one of the siphash would be faster, but then I built
a gaggle of perls with different hash functions and then compared how
well they loaded Dist​::Zilla ( reams and reams of Moose stuff )

SDBM was substantially quicker at that use case for me, so I just used that one.

I'll clearly have to re-evaluate though because apparently, now that
I'm setting the -D flag for it still, I expect its silently doing
nothing?. https://rt.cpan.org/Public/Bug/Display.html?id=119566 .
INSTALL still mentions SDBM being a thing, but
236a702 says SDBM, DJB2 SUPERFAST
MURMUR3's and a few OAAT hashes are gone.

( I suspect that's a perk of reinis's approach to configure is that it
can tell you easily about invalid arguments )

--
Kent

KENTNL - https://metacpan.org/author/KENTNL

@p5pRT
Copy link
Author

p5pRT commented Mar 17, 2017

From @demerphq

On 17 March 2017 at 10​:28, Kent Fredric <kentfredric@​gmail.com> wrote​:

On 17 March 2017 at 21​:28, demerphq <demerphq@​gmail.com> wrote​:

But really, I wonder at choosing sdbm. From what I know, pretty much
any block oriented hash function is going to outperform a
one-at-a-time once the string gets more than a few characters. Even
Siphash24 outperforms sdbm once you get to 13/14 byte strings. Other
block oriented hashes cross sdbm's line much sooner, at 4 or 5 bytes.
How comprehensive was your testing? How thorough was it?

Its been a long time now, so its hard to say

I recall I used Benchmark​::Perl​::CoreHashes at some point and recall
seeing it tell me one of the siphash would be faster, but then I built
a gaggle of perls with different hash functions and then compared how
well they loaded Dist​::Zilla ( reams and reams of Moose stuff )

SDBM was substantially quicker at that use case for me, so I just used that one.

Interesting. It's a pity you dont have a record of better numbers.

I'll clearly have to re-evaluate though because apparently, now that
I'm setting the -D flag for it still, I expect its silently doing
nothing?. https://rt.cpan.org/Public/Bug/Display.html?id=119566 .
INSTALL still mentions SDBM being a thing, but
236a702 says SDBM, DJB2 SUPERFAST
MURMUR3's and a few OAAT hashes are gone.

I will review INSTALL. I removed a bunch of the hashes as maintaining
hv_func was getting out of hand.

( I suspect that's a perk of reinis's approach to configure is that it
can tell you easily about invalid arguments )

Nod.

Yves

--
perl -Mre=debug -e "/just|another|perl|hacker/"

@p5pRT
Copy link
Author

p5pRT commented Mar 17, 2017

From @kentfredric

On 17 March 2017 at 23​:07, demerphq <demerphq@​gmail.com> wrote​:

Interesting. It's a pity you dont have a record of better numbers.

The really odd thing now is how this happens​: I updated the patches of
Benchmark​::Perl​::CoreHashes to map to the current hashes in 5.25.11

# time for PERL_HASH_FUNC_SIPHASH is 4.51946496963501
# time for PERL_HASH_FUNC_ONE_AT_A_TIME_HARD is 2.94429302215576
# time for PERL_HASH_FUNC_SIPHASH13 is 3.59934282302856
# time for PERL_HASH_FUNC_HYBRID_OAATHU_SIPHASH13 is 3.2349910736084

^ These are "time taken for 5 runs of some loop entirely in C" and
their times are very stable ( especially how they compare to each
other is a seemingly constant ordering and difference )

I believe these say of the hash algos in core, for the test case it
provided, OAATH is the fastest.

Granted, this benchmark is _not_ factoring in for collision cost, its
just measuring raw op-time of the hashes, so a bad hash algorithm that
just returned "4" every time would fare incredibly well in this test.

But the good news is I did record the outcome of a previous run in an
RT ticket somewhere :D

# time for PERL_HASH_FUNC_SIPHASH is 12.3072559833527
<-- gosh what happened here.
# time for PERL_HASH_FUNC_SDBM is 1.7642650604248
<--- ha, maybe I remembered this wrong.
# time for PERL_HASH_FUNC_DJB2 is 2.15215301513672
# time for PERL_HASH_FUNC_SUPERFAST is 3.48679804801941
# time for PERL_HASH_FUNC_MURMUR3 is 5.11463499069214
# time for PERL_HASH_FUNC_ONE_AT_A_TIME is 4.16085195541382
# time for PERL_HASH_FUNC_ONE_AT_A_TIME_HARD is 7.88369512557983
# time for PERL_HASH_FUNC_ONE_AT_A_TIME_OLD is 3.99120020866394
# time for PERL_HASH_FUNC_MURMUR_HASH_64A is 3.86607193946838
# time for PERL_HASH_FUNC_MURMUR_HASH_64B is 2.71661996841431

Maybe I'm just gambling on most hashes not having even as many as 20
keys and so hoping that the odds of collisions are low enough to
justify a weak hash.

I mean... a hash algorithm that always returns 4 is fine if your hash
table never needs to handle more than one key right? :P
( not entirely serious there )

Its really weird how much the baseline speed has changed though in the
last so-long. Maybe that's a stack-protected build or something, or
maybe my compiler got better. Can't think of many things that would
radically change hash performance of a single algorithm.

--
Kent

KENTNL - https://metacpan.org/author/KENTNL

@p5pRT
Copy link
Author

p5pRT commented Mar 18, 2017

From @demerphq

On 17 March 2017 at 11​:22, Kent Fredric <kentfredric@​gmail.com> wrote​:

On 17 March 2017 at 23​:07, demerphq <demerphq@​gmail.com> wrote​:

Interesting. It's a pity you dont have a record of better numbers.

The really odd thing now is how this happens​: I updated the patches of
Benchmark​::Perl​::CoreHashes to map to the current hashes in 5.25.11

# time for PERL_HASH_FUNC_SIPHASH is 4.51946496963501
# time for PERL_HASH_FUNC_ONE_AT_A_TIME_HARD is 2.94429302215576
# time for PERL_HASH_FUNC_SIPHASH13 is 3.59934282302856
# time for PERL_HASH_FUNC_HYBRID_OAATHU_SIPHASH13 is 3.2349910736084

^ These are "time taken for 5 runs of some loop entirely in C" and
their times are very stable ( especially how they compare to each
other is a seemingly constant ordering and difference )

I believe these say of the hash algos in core, for the test case it
provided, OAATH is the fastest.

I have no idea what those benchmarks say beyond that they are such a
gross simplification of the issues at hand that they are nearly
worthless.

You can't reduce a complex discussion about performance to a single
benchmark done in artificial conditions. That hashes a list of about
20 odd strings, none of which are longer than 6 bytes.

The performance of a hash function is dependent on the length of the
keys being hashed. So effectively this benchmark says that when
hashing short keys OAATH still wins.

This is not a new observation. We know that. Its why we have the
SIPHASH13_OAATHU thing.

On the other hand, it can be ameliorated somewhat. I have the
following benchmark data (done IMO "properly" compared to the
benchmark you are doing)

# JenkinsOAATH 0 byte keys 11.000 c/h
# JenkinsOAATH 1 byte keys 32.000 c/h 32.000
c/b 0.031 b/c
# JenkinsOAATH 2 byte keys 37.000 c/h 18.500
c/b 0.054 b/c
# JenkinsOAATH 3 byte keys 42.000 c/h 14.000
c/b 0.071 b/c
# JenkinsOAATH 4 byte keys 47.000 c/h 11.750
c/b 0.085 b/c
# JenkinsOAATH 5 byte keys 52.000 c/h 10.400
c/b 0.096 b/c
# JenkinsOAATH 6 byte keys 57.000 c/h 9.500
c/b 0.105 b/c
# JenkinsOAATH 7 byte keys 62.000 c/h 8.857
c/b 0.113 b/c
# JenkinsOAATH 8 byte keys 67.739 c/h 8.467
c/b 0.118 b/c
# JenkinsOAATH 9 byte keys 72.000 c/h 8.000
c/b 0.125 b/c
# JenkinsOAATH 10 byte keys 77.331 c/h 7.733
c/b 0.129 b/c
# JenkinsOAATH 11 byte keys 82.000 c/h 7.455
c/b 0.134 b/c
# JenkinsOAATH 12 byte keys 87.000 c/h 7.250
c/b 0.138 b/c
# JenkinsOAATH 13 byte keys 92.560 c/h 7.120
c/b 0.140 b/c
# JenkinsOAATH 14 byte keys 97.000 c/h 6.929
c/b 0.144 b/c
# JenkinsOAATH 15 byte keys 102.000 c/h 6.800
c/b 0.147 b/c
# JenkinsOAATH 16 byte keys 107.402 c/h 6.713
c/b 0.149 b/c

# SipHash13 0 byte keys 20.000 c/h
# SipHash13 1 byte keys 24.000 c/h 24.000
c/b 0.042 b/c
# SipHash13 2 byte keys 27.000 c/h 13.500
c/b 0.074 b/c
# SipHash13 3 byte keys 28.000 c/h 9.333
c/b 0.107 b/c
# SipHash13 4 byte keys 29.882 c/h 7.471
c/b 0.134 b/c
# SipHash13 5 byte keys 30.000 c/h 6.000
c/b 0.167 b/c
# SipHash13 6 byte keys 31.171 c/h 5.195
c/b 0.192 b/c
# SipHash13 7 byte keys 32.000 c/h 4.571
c/b 0.219 b/c
# SipHash13 8 byte keys 28.802 c/h 3.600
c/b 0.278 b/c
# SipHash13 9 byte keys 28.000 c/h 3.111
c/b 0.321 b/c
# SipHash13 10 byte keys 29.000 c/h 2.900
c/b 0.345 b/c
# SipHash13 11 byte keys 28.993 c/h 2.636
c/b 0.379 b/c
# SipHash13 12 byte keys 29.969 c/h 2.497
c/b 0.400 b/c
# SipHash13 13 byte keys 30.000 c/h 2.308
c/b 0.433 b/c
# SipHash13 14 byte keys 30.999 c/h 2.214
c/b 0.452 b/c
# SipHash13 15 byte keys 31.189 c/h 2.079
c/b 0.481 b/c
# SipHash13 16 byte keys 33.471 c/h 2.092
c/b 0.478 b/c

So SipHash13 *should* be beating JenkinsOAATH already, however I
suspect it is not linking in SipHash quite as intelligently as it
could.

Granted, this benchmark is _not_ factoring in for collision cost, its
just measuring raw op-time of the hashes, so a bad hash algorithm that
just returned "4" every time would fare incredibly well in this test.

Yes. A benchmark like this is fraught with issues. That being one of them.

But the good news is I did record the outcome of a previous run in an
RT ticket somewhere :D

# time for PERL_HASH_FUNC_SIPHASH is 12.3072559833527
<-- gosh what happened here.
# time for PERL_HASH_FUNC_SDBM is 1.7642650604248
<--- ha, maybe I remembered this wrong.
# time for PERL_HASH_FUNC_DJB2 is 2.15215301513672
# time for PERL_HASH_FUNC_SUPERFAST is 3.48679804801941
# time for PERL_HASH_FUNC_MURMUR3 is 5.11463499069214
# time for PERL_HASH_FUNC_ONE_AT_A_TIME is 4.16085195541382
# time for PERL_HASH_FUNC_ONE_AT_A_TIME_HARD is 7.88369512557983
# time for PERL_HASH_FUNC_ONE_AT_A_TIME_OLD is 3.99120020866394
# time for PERL_HASH_FUNC_MURMUR_HASH_64A is 3.86607193946838
# time for PERL_HASH_FUNC_MURMUR_HASH_64B is 2.71661996841431

Maybe I'm just gambling on most hashes not having even as many as 20
keys and so hoping that the odds of collisions are low enough to
justify a weak hash.

In the limited testing I have done hash keys are in the 6-24 byte lengths.

I mean... a hash algorithm that always returns 4 is fine if your hash
table never needs to handle more than one key right? :P
( not entirely serious there )

Its really weird how much the baseline speed has changed though in the
last so-long. Maybe that's a stack-protected build or something, or
maybe my compiler got better. Can't think of many things that would
radically change hash performance of a single algorithm.

I really wouldnt put much stock in this benchmark. Our hash functions
are not run in tight loops. Our hash functions dont need to be seeded
every time we hash, we can do it once per process.

When we decided to accept the latest hash function choices it was
after running trace level monitoring of actually how many instructions
were executed, and then chose the ones that executed the least opts,
keeping in mind the bias towards short keys.

If you want to do some benchmarks then do some real benchmarks, build
some real software with different hash functions and see how it
performs. If you cant see a performance difference IMO pick the one
with better security. If you can see a performance difference then
pick the one that suits your needs.

But relying on *that* benchmark alone to decide which hash function
you use is not the right thing to do.

I have lots of performance data and graphs in my version of smhasher.
You might want to review some of them​:

https://github.com/demerphq/smhasher/tree/master/doc/graph
https://github.com/demerphq/smhasher/tree/master/doc

cheers,
Yves

--
perl -Mre=debug -e "/just|another|perl|hacker/"

@p5pRT
Copy link
Author

p5pRT commented Mar 18, 2017

From @kentfredric

On 18 March 2017 at 21​:52, demerphq <demerphq@​gmail.com> wrote​:

But relying on *that* benchmark alone to decide which hash function
you use is not the right thing to do.

I have lots of performance data and graphs in my version of smhasher.
You might want to review some of them​:

Yeah, The point is I wasn't. It was just an interesting data point for
comparison.

These benchmarks represent a limit, because they demonstrate the
/maximum/ performance a given algorithm can have on the given
platform.

All the other stuff on top of that will only slow the algorithm down
further ( collisions )

Its interesting in the "for X iterations of a data set with average
lengths at ~6 bytes, the throughput cannot exceed X"

Throughput in reality _WILL_ be lower than all of the stated rates.

But if you look at this​:

# PERL_HASH_FUNC_SDBM is 1.7642650604248
# PERL_HASH_FUNC_ONE_AT_A_TIME_HARD is 7.88369512557983

^ that says to me that for the given sample, I can afford to have
quite a few collisions before the costs of the collision outweigh the
inferior algorithm.

Its not something to base a final decision on, but its still
interesting enough for exploratory guidance.

--
Kent

KENTNL - https://metacpan.org/author/KENTNL

@p5pRT
Copy link
Author

p5pRT commented Mar 18, 2017

From @demerphq

On 18 March 2017 at 10​:18, Kent Fredric <kentfredric@​gmail.com> wrote​:

On 18 March 2017 at 21​:52, demerphq <demerphq@​gmail.com> wrote​:

But relying on *that* benchmark alone to decide which hash function
you use is not the right thing to do.

I have lots of performance data and graphs in my version of smhasher.
You might want to review some of them​:

Yeah, The point is I wasn't. It was just an interesting data point for
comparison.

No, it is not interesting, it is misleading to the point of being
counter productive.

These benchmarks represent a limit, because they demonstrate the
/maximum/ performance a given algorithm can have on the given
platform.

You keep talking about "maximum performance". To the extent that there
is such a thing the maximum performance of most hash function is
reached at string lengths much longer than that benchmark exercises.
For instance a hash like CityHash can reach 5 bytes a cycle, where a
hash like sdbm never goes above .350 bytes a cycle, and something like
JenkinsOAAT never goes above .150 bytes a cycle.

You keep trying to reduce the comparison of two linear equations down
to the comparison of their position at one point on the line. That
doesnt make sense.

Either you say, "I have sampled a large number of keys, and this is
the relative frequency of the various string lengths occuring, and
this benchmark simulates that distribution and gives me a summary view
of the performance I can expect", or you go the simple route that
smhasher does and you time each length for many lengths, and then you
graph that.

The benchmark you keep quoting does neither. The keys it hashes are
not representative of the lengths of keys as they occur in the wild.
And it does not systematically time hashing strings of different
lengths. It is also subject to parallelism optimisations that would
easily make a small hash function like OAAT appear faster.

Add some long string to the benchmark. Make the benchmark update the
keys each time with the hash of the previous key, so it has to do them
in serial. Etc, and you will see the numbers wildly change.

That benchmark is literally not worth the paper it is written on.
Using it as a decision making basis for anything is the height of
folly.

Further, if you are going to quote benchmarks the way you are you
should make sure you are clear about what hardware and build options
you are using for the test. Are you on 64 bit? Windows or Linux?
Debugging or non? For instance one of the timings you quoted looked to
me like it could be the result of us using a macro to load 64 bits
worth of data into a register which under DEBUGGING would turn siphash
into a one-at-a-time, but under -O3 would be optimised into a single
instruction.

Cheers,
Yves


perl -Mre=debug -e "/just|another|perl|hacker/"

@p5pRT
Copy link
Author

p5pRT commented Mar 19, 2017

From @kentfredric

On 19 March 2017 at 01​:22, demerphq <demerphq@​gmail.com> wrote​:

Further, if you are going to quote benchmarks the way you are you
should make sure you are clear about what hardware and build options
you are using for the test. Are you on 64 bit? Windows or Linux?
Debugging or non? For instance one of the timings you quoted looked to
me like it could be the result of us using a macro to load 64 bits
worth of data into a register which under DEBUGGING would turn siphash
into a one-at-a-time, but under -O3 would be optimised into a single
instruction.

So I built a few Perl's just to compare their test run times, as that
should be interesting. ( Even though not comprehensive )

5.25.10 Siphash 13
self-test​: Files=2557, Tests=1231311, 752 wallclock secs (302.66 usr
45.41 sys + 1440.63 cusr 209.55 csys = 1998.25 CPU)

5.25.10 Siphash 13-Hybrid
self-test​: Files=2557, Tests=1231383, 702 wallclock secs (307.18 usr
45.35 sys + 1435.14 cusr 206.05 csys = 1993.72 CPU)

5.25.10 OAAT
self-test​: Files=2557, Tests=1231310, 745 wallclock secs (314.44 usr
47.48 sys + 1488.43 cusr 211.39 csys = 2061.74 CPU)

5.24.1 SDBM
self-test​: Files=2410, Tests=851196, 399 wallclock secs (179.73 usr
29.91 sys + 1037.96 cusr 150.77 csys = 1398.37 CPU)

5.24.1 OAAT
self-test​: Files=2410, Tests=851085, 434 wallclock secs (197.12 usr
32.36 sys + 1114.02 cusr 160.08 csys = 1503.58 CPU)

A difference of 105 CPU Seconds is nothing to sneeze at :) and I
believe this comparison may have been the one that sealed the deal for
me.

CFLAGS​: -fstack-protector-strong -fno-stack-protector -O3
-march=native -mtune=native

The first two of those is just the only way to actually disable the
stack protector without configure helpfully turning it back on again.

Non-debugging non-threaded perl.

The only other things I do that are slightly interesting is turning on
-DPERL_DISABLE_PMC and disabling man page generation ... but I'd hate
to think they're relevant.
Configuration for all above builds were identical sans HASH
implementation, including passing -Udefault_inc_excludes_dot to
configure despite none of the perl's needing it. ( just part of my
build script )

x86-64 Linux on Intel(R) Core(TM) i5-2410M CPU @​ 2.30GHz

gcc version 5.4.0 (Gentoo 5.4.0-r3 p1.3, pie-0.6.5)

--
Kent

KENTNL - https://metacpan.org/author/KENTNL

@p5pRT
Copy link
Author

p5pRT commented Mar 19, 2017

From @kentfredric

On 19 March 2017 at 23​:00, Kent Fredric <kentfredric@​gmail.com> wrote​:

So I built a few Perl's just to compare their test run times, as that
should be interesting. ( Even though not comprehensive )

I've now run 5x runs of Moose's test suite on all of the target perls,
and a few apparent trends appear.

Graph comparing times in user-seconds​: http​://i.imgur.com/jRs4EBZ.png
Data​: https://gist.github.com/kentfredric/d52a9dc8f9a21587102eb73545815f9c

I can only really afford to do so many runs, 5 targets * 5 runs * 2
minutes per run -> there's my computer out of use for an hour.

--
Kent

KENTNL - https://metacpan.org/author/KENTNL

@p5pRT
Copy link
Author

p5pRT commented Mar 19, 2017

From @kentfredric

On 20 March 2017 at 01​:02, Kent Fredric <kentfredric@​gmail.com> wrote​:

On 19 March 2017 at 23​:00, Kent Fredric <kentfredric@​gmail.com> wrote​:

So I built a few Perl's just to compare their test run times, as that
should be interesting. ( Even though not comprehensive )

I've now run 5x runs of Moose's test suite on all of the target perls,
and a few apparent trends appear.

Graph comparing times in user-seconds​: http​://i.imgur.com/jRs4EBZ.png
Data​: https://gist.github.com/kentfredric/d52a9dc8f9a21587102eb73545815f9c

I can only really afford to do so many runs, 5 targets * 5 runs * 2
minutes per run -> there's my computer out of use for an hour.

Test Times for Dzil are inconclusive, mostly because you've got 2
other factors to contend with really​:

- 5.25.10 has newer Test​::More ( slower )
- 5.25.10 has context stack reworks ( Faster )

Graph​: http​://i.imgur.com/Mow6oyt.png
Data​: https://gist.github.com/kentfredric/cab5287dbecc4fd980b6624d08fcf474

However, dzil *build* times get the Test​::More slowdown out of the mix
and give some really interesting data, because you can explain the
differences in OAAT speeds exclusively in terms of 5.25-optimisations.

This reveals Siphash13 to be promising in this scenario, but
hybrid_siphash to be underwhelming.

It also demonstrates SDBM hash to be faster than OAATH for this usecase.

Graph​: http​://i.imgur.com/ghMCFB5.png
Data​: https://gist.github.com/kentfredric/fd9ee4ff55351f3e16122f62d663c26b

The only curiosity would be how SDBM compares to SIPHASH13 with all
the other 5.25 optimizations in.

( which is why I double-accounted OAATH everywhere because it was the
only way I could get a relative metric )

So if SDBM aint' returning, I'll be switching to SIPHASH13

25% off `dzil build`? Yes please :)

--
Kent

KENTNL - https://metacpan.org/author/KENTNL

@toddr
Copy link
Member

toddr commented Jan 31, 2020

@demerphq is there any further action to take on this ticket?

@demerphq
Copy link
Collaborator

demerphq commented Jan 31, 2020 via email

@xenu xenu removed the Severity Low label Dec 29, 2021
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

4 participants