News for hackers. Stuff that matters.
Re:HighwayHash: Strong hashing at 0.3 clock cycles per byte by nkurz on Wednesday March 02, 2016 @06:42PM (#11214004)
Are there any better instructions for how to build this? I'm interested in it, but not having any luck with Bazel. First I failed with a permissions issue (https://github.com/bazelbuild/bazel/issues/739), then because I didn't have a "WORKSPACE" file, and now it gives me an unhelpful error message:

  nate@skylake:~/git/highwayhash$ bazel build :all -c opt --copt=-mavx2
  .....
  ERROR: /home/nate/git/highwayhash/BUILD:3:1: unexpected   
  keyword 'default_hdrs_check' in call to package(*, 
  default_deprecation = ?, distribs = ?, licenses = ?, 
  default_testonly = ?, default_visibility = ?, features = ?, 
  default_compatible_with = ?, default_restricted_to = ?).
  ERROR: no such package '': Package '' contains errors.
Re:HighwayHash: Strong hashing at 0.3 clock cycles per byte by amock on Wednesday March 02, 2016 @07:33PM (#11214240)
I'm guessing it was built and tested internally at Google and no one tested it with bazel. It also depends on smasher, which I believe should be declared in the WORKSPACE file. So unless you want to manually build it you'll have to wait for someone to fix the build.
Re:HighwayHash: Strong hashing at 0.3 clock cycles per byte by nkurz on Wednesday March 02, 2016 @08:48PM (#11214514)
I went ahead and created a Makefile:

  CXXFLAGS := -g -std=c++11 -Wall -O3 -march=native -Wno-sign-compare
  OBJS := highway_tree_hash.o \
  	scalar_highway_tree_hash.o \
  	scalar_sip_tree_hash.o \
  	sip_hash.o \
  	sip_tree_hash.o
  MAIN := sip_hash_main
  all: $(OBJS)
  	$(CXX) $(CXXFLAGS) $(OBJS) $(MAIN).cc -o $(MAIN)
  clean:
  	rm -f $(OBJS) $(MAIN)
Then I commented out two lines in "sip_hash_main.cc":

   // #include "smhasher.h"
   // RunAllTests(argc, argv);
Then "make" and run:

  nate@skylake:~/git/highwayhash$ ./sip_hash_main
  ScalarSipTreeHash ...	    GBps=2.44  c/b=1.44
  ScalarHighwayTreeHash ... GBps=1.16  c/b=3.02
  SipHash ...               GBps=1.54  c/b=2.27
  SipTreeHash ...           GBps=4.56  c/b=0.77
  HighwayTreeHash ...       GBps=11.49 c/b=0.30
  ...
The inner loop for HighwayTreeHash looks like this:

   0.89 │ 60:┌─→vpor   %ymm5,%ymm0,%ymm0                                                            
   4.47 │    │  vpaddq (%rcx),%ymm1,%ymm1                                                           
   6.04 │    │  add    $0x4,%rax                                                                    
   0.22 │    │  add    $0x20,%rcx                                                                   
   2.24 │    │  cmp    %rax,%rdi                                                                    
   3.13 │    │  vpsrlq $0x20,%ymm1,%ymm2                                                            
   3.36 │    │  vpmulu %ymm1,%ymm0,%ymm4                                                            
  13.20 │    │  vpshuf %ymm3,%ymm4,%ymm4                                                            
  11.19 │    │  vpmulu %ymm2,%ymm0,%ymm2                                                            
        │    │  vpaddq %ymm1,%ymm2,%ymm1                                                            
  31.32 │    │  vpaddq %ymm4,%ymm0,%ymm0                                                            
   7.61 │    └──ja     60
Re:HighwayHash: Strong hashing at 0.3 clock cycles per byte by forgotpwtomain on Thursday March 03, 2016 @11:03AM (#11217671)
Do you know if there is a reference for a comparative number of collisions anywhere e.g. (http://programmers.stackexchange.com/questions/49550/which-h...) ?
Re:HighwayHash: Strong hashing at 0.3 clock cycles per byte by janwas on Thursday March 03, 2016 @12:55PM (#11218538)
With a 64-bit hash, you shouldn't be seeing collisions at all on small datasets. A test such as smhasher can verify this.
Re:HighwayHash: Strong hashing at 0.3 clock cycles per byte by janwas on Thursday March 03, 2016 @10:54AM (#11217588)
Thanks for mentioning, I have removed the smhasher dependency. We have an enhanced version of it which cannot be yet be released due to a dependency on threading libraries.
Re:HighwayHash: Strong hashing at 0.3 clock cycles per byte by janwas on Thursday March 03, 2016 @10:52AM (#11217562)
Thank you for mentioning this. I have added a WORKSPACE file and removed the default_hdrs_check (apparently only available in Google Blaze).
Re:HighwayHash: Strong hashing at 0.3 clock cycles per byte by nkurz on Thursday March 03, 2016 @04:58PM (#11220382)
Great, the new version now works for me with Bazel. I pushed you an improved Makefile and some fixes for conversion warnings on Github. Up to you if you want to include the Makefile, but I think it would make it much easier for outsiders to test your code. Thanks for providing this!
Re:HighwayHash: Strong hashing at 0.3 clock cycles per byte by janwas on Friday March 04, 2016 @12:19PM (#11225199)
You're welcome, thank you for suggesting these :) We do need a contributor agreement click-through first, please see CONTRIBUTING.