rtutil_test.go

Documentation: github.com/dgraph-io/ristretto/z

     1  package z
     2  
     3  import (
     4  	"hash/fnv"
     5  	"math/rand"
     6  	"sync/atomic"
     7  	"testing"
     8  	"time"
     9  
    10  	"github.com/dgryski/go-farm"
    11  )
    12  
    13  func BenchmarkMemHash(b *testing.B) {
    14  	buf := make([]byte, 64)
    15  	rand.Read(buf)
    16  
    17  	b.ReportAllocs()
    18  	b.ResetTimer()
    19  	for i := 0; i < b.N; i++ {
    20  		_ = MemHash(buf)
    21  	}
    22  	b.SetBytes(int64(len(buf)))
    23  }
    24  
    25  func BenchmarkMemHashString(b *testing.B) {
    26  	s := "Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua."
    27  
    28  	b.ReportAllocs()
    29  	b.ResetTimer()
    30  	for i := 0; i < b.N; i++ {
    31  		_ = MemHashString(s)
    32  	}
    33  	b.SetBytes(int64(len(s)))
    34  }
    35  
    36  func BenchmarkSip(b *testing.B) {
    37  	buf := make([]byte, 64)
    38  	rand.Read(buf)
    39  	for i := 0; i < b.N; i++ {
    40  		SipHash(buf)
    41  	}
    42  }
    43  
    44  func BenchmarkFarm(b *testing.B) {
    45  	buf := make([]byte, 64)
    46  	rand.Read(buf)
    47  	for i := 0; i < b.N; i++ {
    48  		farm.Fingerprint64(buf)
    49  	}
    50  }
    51  
    52  func BenchmarkFnv(b *testing.B) {
    53  	buf := make([]byte, 64)
    54  	rand.Read(buf)
    55  	f := fnv.New64a()
    56  	for i := 0; i < b.N; i++ {
    57  		f.Write(buf)
    58  		f.Sum64()
    59  		f.Reset()
    60  	}
    61  }
    62  
    63  func SipHash(p []byte) (l, h uint64) {
    64  	// Initialization.
    65  	v0 := uint64(8317987320269560794) // k0 ^ 0x736f6d6570736575
    66  	v1 := uint64(7237128889637516672) // k1 ^ 0x646f72616e646f6d
    67  	v2 := uint64(7816392314733513934) // k0 ^ 0x6c7967656e657261
    68  	v3 := uint64(8387220255325274014) // k1 ^ 0x7465646279746573
    69  	t := uint64(len(p)) << 56
    70  
    71  	// Compression.
    72  	for len(p) >= 8 {
    73  		m := uint64(p[0]) | uint64(p[1])<<8 | uint64(p[2])<<16 | uint64(p[3])<<24 |
    74  			uint64(p[4])<<32 | uint64(p[5])<<40 | uint64(p[6])<<48 | uint64(p[7])<<56
    75  
    76  		v3 ^= m
    77  
    78  		// Round 1.
    79  		v0 += v1
    80  		v1 = v1<<13 | v1>>51
    81  		v1 ^= v0
    82  		v0 = v0<<32 | v0>>32
    83  
    84  		v2 += v3
    85  		v3 = v3<<16 | v3>>48
    86  		v3 ^= v2
    87  
    88  		v0 += v3
    89  		v3 = v3<<21 | v3>>43
    90  		v3 ^= v0
    91  
    92  		v2 += v1
    93  		v1 = v1<<17 | v1>>47
    94  		v1 ^= v2
    95  		v2 = v2<<32 | v2>>32
    96  
    97  		// Round 2.
    98  		v0 += v1
    99  		v1 = v1<<13 | v1>>51
   100  		v1 ^= v0
   101  		v0 = v0<<32 | v0>>32
   102  
   103  		v2 += v3
   104  		v3 = v3<<16 | v3>>48
   105  		v3 ^= v2
   106  
   107  		v0 += v3
   108  		v3 = v3<<21 | v3>>43
   109  		v3 ^= v0
   110  
   111  		v2 += v1
   112  		v1 = v1<<17 | v1>>47
   113  		v1 ^= v2
   114  		v2 = v2<<32 | v2>>32
   115  
   116  		v0 ^= m
   117  		p = p[8:]
   118  	}
   119  
   120  	// Compress last block.
   121  	switch len(p) {
   122  	case 7:
   123  		t |= uint64(p[6]) << 48
   124  		fallthrough
   125  	case 6:
   126  		t |= uint64(p[5]) << 40
   127  		fallthrough
   128  	case 5:
   129  		t |= uint64(p[4]) << 32
   130  		fallthrough
   131  	case 4:
   132  		t |= uint64(p[3]) << 24
   133  		fallthrough
   134  	case 3:
   135  		t |= uint64(p[2]) << 16
   136  		fallthrough
   137  	case 2:
   138  		t |= uint64(p[1]) << 8
   139  		fallthrough
   140  	case 1:
   141  		t |= uint64(p[0])
   142  	}
   143  
   144  	v3 ^= t
   145  
   146  	// Round 1.
   147  	v0 += v1
   148  	v1 = v1<<13 | v1>>51
   149  	v1 ^= v0
   150  	v0 = v0<<32 | v0>>32
   151  
   152  	v2 += v3
   153  	v3 = v3<<16 | v3>>48
   154  	v3 ^= v2
   155  
   156  	v0 += v3
   157  	v3 = v3<<21 | v3>>43
   158  	v3 ^= v0
   159  
   160  	v2 += v1
   161  	v1 = v1<<17 | v1>>47
   162  	v1 ^= v2
   163  	v2 = v2<<32 | v2>>32
   164  
   165  	// Round 2.
   166  	v0 += v1
   167  	v1 = v1<<13 | v1>>51
   168  	v1 ^= v0
   169  	v0 = v0<<32 | v0>>32
   170  
   171  	v2 += v3
   172  	v3 = v3<<16 | v3>>48
   173  	v3 ^= v2
   174  
   175  	v0 += v3
   176  	v3 = v3<<21 | v3>>43
   177  	v3 ^= v0
   178  
   179  	v2 += v1
   180  	v1 = v1<<17 | v1>>47
   181  	v1 ^= v2
   182  	v2 = v2<<32 | v2>>32
   183  
   184  	v0 ^= t
   185  
   186  	// Finalization.
   187  	v2 ^= 0xff
   188  
   189  	// Round 1.
   190  	v0 += v1
   191  	v1 = v1<<13 | v1>>51
   192  	v1 ^= v0
   193  	v0 = v0<<32 | v0>>32
   194  
   195  	v2 += v3
   196  	v3 = v3<<16 | v3>>48
   197  	v3 ^= v2
   198  
   199  	v0 += v3
   200  	v3 = v3<<21 | v3>>43
   201  	v3 ^= v0
   202  
   203  	v2 += v1
   204  	v1 = v1<<17 | v1>>47
   205  	v1 ^= v2
   206  	v2 = v2<<32 | v2>>32
   207  
   208  	// Round 2.
   209  	v0 += v1
   210  	v1 = v1<<13 | v1>>51
   211  	v1 ^= v0
   212  	v0 = v0<<32 | v0>>32
   213  
   214  	v2 += v3
   215  	v3 = v3<<16 | v3>>48
   216  	v3 ^= v2
   217  
   218  	v0 += v3
   219  	v3 = v3<<21 | v3>>43
   220  	v3 ^= v0
   221  
   222  	v2 += v1
   223  	v1 = v1<<17 | v1>>47
   224  	v1 ^= v2
   225  	v2 = v2<<32 | v2>>32
   226  
   227  	// Round 3.
   228  	v0 += v1
   229  	v1 = v1<<13 | v1>>51
   230  	v1 ^= v0
   231  	v0 = v0<<32 | v0>>32
   232  
   233  	v2 += v3
   234  	v3 = v3<<16 | v3>>48
   235  	v3 ^= v2
   236  
   237  	v0 += v3
   238  	v3 = v3<<21 | v3>>43
   239  	v3 ^= v0
   240  
   241  	v2 += v1
   242  	v1 = v1<<17 | v1>>47
   243  	v1 ^= v2
   244  	v2 = v2<<32 | v2>>32
   245  
   246  	// Round 4.
   247  	v0 += v1
   248  	v1 = v1<<13 | v1>>51
   249  	v1 ^= v0
   250  	v0 = v0<<32 | v0>>32
   251  
   252  	v2 += v3
   253  	v3 = v3<<16 | v3>>48
   254  	v3 ^= v2
   255  
   256  	v0 += v3
   257  	v3 = v3<<21 | v3>>43
   258  	v3 ^= v0
   259  
   260  	v2 += v1
   261  	v1 = v1<<17 | v1>>47
   262  	v1 ^= v2
   263  	v2 = v2<<32 | v2>>32
   264  
   265  	// return v0 ^ v1 ^ v2 ^ v3
   266  
   267  	hash := v0 ^ v1 ^ v2 ^ v3
   268  	h = hash >> 1
   269  	l = hash << 1 >> 1
   270  	return l, h
   271  }
   272  
   273  func BenchmarkNanoTime(b *testing.B) {
   274  	for i := 0; i < b.N; i++ {
   275  		NanoTime()
   276  	}
   277  }
   278  
   279  func BenchmarkCPUTicks(b *testing.B) {
   280  	for i := 0; i < b.N; i++ {
   281  		CPUTicks()
   282  	}
   283  }
   284  
   285  // goos: linux
   286  // goarch: amd64
   287  // pkg: github.com/dgraph-io/ristretto/z
   288  // BenchmarkFastRand-16      	1000000000	         0.292 ns/op
   289  // BenchmarkRandSource-16    	1000000000	         0.747 ns/op
   290  // BenchmarkRandGlobal-16    	 6822332	       176 ns/op
   291  // BenchmarkRandAtomic-16    	77950322	        15.4 ns/op
   292  // PASS
   293  // ok  	github.com/dgraph-io/ristretto/z	4.808s
   294  func benchmarkRand(b *testing.B, fab func() func() uint32) {
   295  	b.RunParallel(func(pb *testing.PB) {
   296  		gen := fab()
   297  		for pb.Next() {
   298  			gen()
   299  		}
   300  	})
   301  }
   302  
   303  func BenchmarkFastRand(b *testing.B) {
   304  	benchmarkRand(b, func() func() uint32 {
   305  		return FastRand
   306  	})
   307  }
   308  
   309  func BenchmarkRandSource(b *testing.B) {
   310  	benchmarkRand(b, func() func() uint32 {
   311  		s := rand.New(rand.NewSource(time.Now().Unix()))
   312  		return func() uint32 { return s.Uint32() }
   313  	})
   314  }
   315  
   316  func BenchmarkRandGlobal(b *testing.B) {
   317  	benchmarkRand(b, func() func() uint32 {
   318  		return func() uint32 { return rand.Uint32() }
   319  	})
   320  }
   321  
   322  func BenchmarkRandAtomic(b *testing.B) {
   323  	var x uint32
   324  	benchmarkRand(b, func() func() uint32 {
   325  		return func() uint32 { return uint32(atomic.AddUint32(&x, 1)) }
   326  	})
   327  }
   328
View as plain text