Statistics for perl hash tables

crc.patch

Just trying performance and quality of the Intel HW CRC32
In real code this should be checked in perl_init for CPU features.

I guess the hash function is not quite kosher yet, but gives a
rough estimate for the data I'm looking for: performance and
number of collisions.

diff --git hv_func.h hv_func.h
index 191912a..38134bc 100644
--- hv_func.h
+++ hv_func.h
@@ -21,6 +21,7 @@
         || defined(PERL_HASH_FUNC_ONE_AT_A_TIME) \
         || defined(PERL_HASH_FUNC_ONE_AT_A_TIME_HARD) \
         || defined(PERL_HASH_FUNC_ONE_AT_A_TIME_OLD) \
+        || defined(PERL_HASH_FUNC_CRC32) \
     )
 #define PERL_HASH_FUNC_ONE_AT_A_TIME_HARD
 #endif
@@ -57,6 +58,10 @@
 #   define PERL_HASH_FUNC "ONE_AT_A_TIME_OLD"
 #   define PERL_HASH_SEED_BYTES 4
 #   define PERL_HASH(hash,str,len) (hash)= S_perl_hash_old_one_at_a_time(PERL_HASH_SEED,(U8*)(str),(len))
+#elif defined(PERL_HASH_FUNC_CRC32)
+#   define PERL_HASH_FUNC "CRC32"
+#   define PERL_HASH_SEED_BYTES 4
+#   define PERL_HASH(hash,str,len) (hash)= S_perl_hash_crc32(PERL_HASH_SEED,(U8*)(str),(len))
 #endif
 
 #ifndef PERL_HASH
@@ -552,6 +557,48 @@ S_perl_hash_old_one_at_a_time(const unsigned char * const seed, const unsigned c
     return (hash + (hash << 15));
 }
 
+#ifdef __SSE4_2__
+#include <smmintrin.h>
+#endif
+
+/* 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, const STRLEN inlen) {
+    U32 hash = *((U32*)seed + inlen);
+    const char* buf = (const char*)str;
+    STRLEN len = inlen;
+
+#ifdef __SSE4_2__
+    /* 32 bit only */
+    hash ^= 0xFFFFFFFF;
+    /* 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);
+#else
+    #error SW crc32 not good. Need Intel SSE4 processor for PERL_HASH_FUNC_CRC32
+#endif
+
+    /* 32 bit only */
+    return (hash ^ 0xFFFFFFFF);
+}
+
 /* 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)

hash-result.pl

#!/usr/bin/perl -an
# test -DH hash collisions (recorded only to STDERR for easier p5 patch)

# Usage:
#   apply -DH patch at https://github.com/rurban/perl/commit/b975d736cfe40a9cf51ec0a44aaba0322fd04347
#   define PERL_HASH_FUNC_ONE_AT_A_TIME in config.h
# make test 2> log.hash.ONE_AT_A_TIME
#   kill perl hanging at cpan/Test-Simple/t/utf8.t and ext/PerlIO-encoding/t/nolooping.t
# ./hash-result.pl log.hash.ONE_AT_A_TIME | tee hash.result.ONE_AT_A_TIME

# skip non-conformant lines
# STDERR might get garbled by tests and we dont try to fix around this
# we will not print to a special filehandle just for -DH
next unless ($F[0] =~ /^\d+$/
             and $F[1] =~ /^\d+$/
             and $F[2] =~ /^\d+$/
             and (@F == 3 or (@F == 4 and $F[3] !~ /^\d+$/)));

$F{0}{$F[0]}++;
$F{1}{$F[1]}++;
$F{2}{$F[2]}++;
$F{3}{$F[3]}++ if $F[3];
$n++;

END{
  my %i = (
    0 => 'keys',
    1 => 'size',
    2 => 'coll',
    3 => 'op',
    );
  for $i (0..3) {
    print "$i $i{$i}:\n";
    for $k (sort {$a<=>$b} keys $F{$i}) {
      print "\t",$k,"\t",$F{$i}{$k},"x\n";
    }
    print "\n";
  }
  my $cost = 0;
  for $k (sort {$a<=>$b} keys $F{2}) {
    $cost += $F{2}{$k} * $k;
  }
  print "collision cost: $cost / # lines: $n\n";
  print sprintf("ratio: %0.03f\n", $cost / $n);
}

hash.stats

Counting the collisions with perl hash tables per function.
(linear chaining in a linked list, subject to collision attacks)

                        collisions (less is better)
CRC32			1.078
ONE_AT_A_TIME_HARD	1.092
SIPHASH			1.091
ONE_AT_A_TIME		1.098
ONE_AT_A_TIME_OLD	
SDBM			
SUPERFAST		
DJB2			
MURMUR3			1.105

See http://blogs.perl.org/users/rurban/2014/04/statistics-for-perl-hash-tables.html
and https://gist.github.com/rurban/10439033
 
$ tail -n20 hash.result.CRC32
2 coll:
        0       26895000x
        1       98179685x
        2       25832401x
        3       5582369x
        4       660175x
        5       53429x
        6       5726x
        7       157x
        8       5x
 
3 op:
        DEL+    2371595x
        DEL-    63408x
        -       41471245x
        DELpl   6x
 
collision cost: 169534934 / # lines: 157208947
ratio: 1.078
 
$ tail -n20 hash.result.ONE_AT_A_TIME_HARD
 
2 coll:
        0       19075964x
        1       76051725x
        2       19869990x
        3       4091870x
        4       577088x
        5       46416x
        6       16933x
        7       346x
        8       23x
 
3 op:
        DEL-    47556x
        -       30553435x
        DEL+    1521038x
        DELpl   6x
 
collision cost: 130711951 / # lines: 119730355
ratio: 1.092
 
$ tail -n20 hash.result.MURMUR3 
 
2 coll:
	0	24821274x
	1	99735474x
	2	26327227x
	3	6066529x
	4	862574x
	5	76627x
	6	6877x
	7	276x
	8	20x
 
3 op:
	DEL-	65262x
	DEL+	2379381x
	-	41634279x
	DELpl	6x
 
collision cost: 174466300 / # lines: 157896878
ratio: 1.105

$ tail -n20 hash.result.SIPHASH

2 coll:
	0	26314186x
	1	99114872x
	2	25655322x
	3	5749479x
	4	888039x
	5	205159x
	6	3449x
	7	399x
	8	46x
	9	16x

3 op:
	DEL-	65445x
	DELpl	6x
	DEL+	2379395x
	-	41638164x

collision cost: 172275903 / # lines: 157930967
ratio: 1.091

$ tail -n20 hash.result.ONE_AT_A_TIME
2 coll:
	0	25867206x
	1	98008406x
	2	27351918x
	3	5588012x
	4	836805x
	5	68047x
	6	6104x
	7	203x
	8	10x
	9	1x
	10	53x

3 op:
	DELpl	6x
	-	41623366x
	DEL+	2378959x
	DEL-	65074x

collision cost: 173202397 / # lines: 157726765
ratio: 1.098