Source file src/github.com/bits-and-blooms/bitset/bitset_benchmark_test.go

Documentation: github.com/bits-and-blooms/bitset

     1  // Copyright 2014 Will Fitzgerald. All rights reserved.
     2  // Use of this source code is governed by a BSD-style
     3  // license that can be found in the LICENSE file.
     4  
     5  // This file tests bit sets
     6  
     7  package bitset
     8  
     9  import (
    10  	"math/rand"
    11  	"testing"
    12  )
    13  
    14  func BenchmarkSet(b *testing.B) {
    15  	b.StopTimer()
    16  	r := rand.New(rand.NewSource(0))
    17  	sz := 100000
    18  	s := New(uint(sz))
    19  	b.StartTimer()
    20  	for i := 0; i < b.N; i++ {
    21  		s.Set(uint(r.Int31n(int32(sz))))
    22  	}
    23  }
    24  
    25  func BenchmarkGetTest(b *testing.B) {
    26  	b.StopTimer()
    27  	r := rand.New(rand.NewSource(0))
    28  	sz := 100000
    29  	s := New(uint(sz))
    30  	b.StartTimer()
    31  	for i := 0; i < b.N; i++ {
    32  		s.Test(uint(r.Int31n(int32(sz))))
    33  	}
    34  }
    35  
    36  func BenchmarkSetExpand(b *testing.B) {
    37  	b.StopTimer()
    38  	sz := uint(100000)
    39  	b.StartTimer()
    40  	for i := 0; i < b.N; i++ {
    41  		var s BitSet
    42  		s.Set(sz)
    43  	}
    44  }
    45  
    46  // go test -bench=Count
    47  func BenchmarkCount(b *testing.B) {
    48  	b.StopTimer()
    49  	s := New(100000)
    50  	for i := 0; i < 100000; i += 100 {
    51  		s.Set(uint(i))
    52  	}
    53  	b.StartTimer()
    54  	for i := 0; i < b.N; i++ {
    55  		s.Count()
    56  	}
    57  }
    58  
    59  // go test -bench=Iterate
    60  func BenchmarkIterate(b *testing.B) {
    61  	b.StopTimer()
    62  	s := New(10000)
    63  	for i := 0; i < 10000; i += 3 {
    64  		s.Set(uint(i))
    65  	}
    66  	b.StartTimer()
    67  	for j := 0; j < b.N; j++ {
    68  		c := uint(0)
    69  		for i, e := s.NextSet(0); e; i, e = s.NextSet(i + 1) {
    70  			c++
    71  		}
    72  	}
    73  }
    74  
    75  // go test -bench=SparseIterate
    76  func BenchmarkSparseIterate(b *testing.B) {
    77  	b.StopTimer()
    78  	s := New(100000)
    79  	for i := 0; i < 100000; i += 30 {
    80  		s.Set(uint(i))
    81  	}
    82  	b.StartTimer()
    83  	for j := 0; j < b.N; j++ {
    84  		c := uint(0)
    85  		for i, e := s.NextSet(0); e; i, e = s.NextSet(i + 1) {
    86  			c++
    87  		}
    88  	}
    89  }
    90  
    91  // go test -bench=LemireCreate
    92  // see http://lemire.me/blog/2016/09/22/swift-versus-java-the-bitset-performance-test/
    93  func BenchmarkLemireCreate(b *testing.B) {
    94  	for i := 0; i < b.N; i++ {
    95  		bitmap := New(0) // we force dynamic memory allocation
    96  		for v := uint(0); v <= 100000000; v += 100 {
    97  			bitmap.Set(v)
    98  		}
    99  	}
   100  }
   101  
   102  // go test -bench=LemireCount
   103  // see http://lemire.me/blog/2016/09/22/swift-versus-java-the-bitset-performance-test/
   104  func BenchmarkLemireCount(b *testing.B) {
   105  	bitmap := New(100000000)
   106  	for v := uint(0); v <= 100000000; v += 100 {
   107  		bitmap.Set(v)
   108  	}
   109  	b.ResetTimer()
   110  	sum := uint(0)
   111  	for i := 0; i < b.N; i++ {
   112  		sum += bitmap.Count()
   113  	}
   114  	if sum == 0 { // added just to fool ineffassign
   115  		return
   116  	}
   117  }
   118  
   119  // go test -bench=LemireIterate
   120  // see http://lemire.me/blog/2016/09/22/swift-versus-java-the-bitset-performance-test/
   121  func BenchmarkLemireIterate(b *testing.B) {
   122  	bitmap := New(100000000)
   123  	for v := uint(0); v <= 100000000; v += 100 {
   124  		bitmap.Set(v)
   125  	}
   126  	b.ResetTimer()
   127  	sum := uint(0)
   128  	for i := 0; i < b.N; i++ {
   129  		for j, e := bitmap.NextSet(0); e; j, e = bitmap.NextSet(j + 1) {
   130  			sum++
   131  		}
   132  	}
   133  	if sum == 0 { // added just to fool ineffassign
   134  		return
   135  	}
   136  }
   137  
   138  // go test -bench=LemireIterateb
   139  // see http://lemire.me/blog/2016/09/22/swift-versus-java-the-bitset-performance-test/
   140  func BenchmarkLemireIterateb(b *testing.B) {
   141  	bitmap := New(100000000)
   142  	for v := uint(0); v <= 100000000; v += 100 {
   143  		bitmap.Set(v)
   144  	}
   145  	b.ResetTimer()
   146  	sum := uint(0)
   147  	for i := 0; i < b.N; i++ {
   148  		for j, e := bitmap.NextSet(0); e; j, e = bitmap.NextSet(j + 1) {
   149  			sum += j
   150  		}
   151  	}
   152  
   153  	if sum == 0 { // added just to fool ineffassign
   154  		return
   155  	}
   156  }
   157  
   158  // go test -bench=BenchmarkLemireIterateManyb
   159  // see http://lemire.me/blog/2016/09/22/swift-versus-java-the-bitset-performance-test/
   160  func BenchmarkLemireIterateManyb(b *testing.B) {
   161  	bitmap := New(100000000)
   162  	for v := uint(0); v <= 100000000; v += 100 {
   163  		bitmap.Set(v)
   164  	}
   165  	buffer := make([]uint, 256)
   166  	b.ResetTimer()
   167  	sum := uint(0)
   168  	for i := 0; i < b.N; i++ {
   169  		j := uint(0)
   170  		j, buffer = bitmap.NextSetMany(j, buffer)
   171  		for ; len(buffer) > 0; j, buffer = bitmap.NextSetMany(j, buffer) {
   172  			for k := range buffer {
   173  				sum += buffer[k]
   174  			}
   175  			j++
   176  		}
   177  	}
   178  
   179  	if sum == 0 { // added just to fool ineffassign
   180  		return
   181  	}
   182  }
   183  
   184  func setRnd(bits []uint64, halfings int) {
   185  	var rnd = rand.NewSource(0).(rand.Source64)
   186  	for i := range bits {
   187  		bits[i] = 0xFFFFFFFFFFFFFFFF
   188  		for j := 0; j < halfings; j++ {
   189  			bits[i] &= rnd.Uint64()
   190  		}
   191  	}
   192  }
   193  
   194  // go test -bench=BenchmarkFlorianUekermannIterateMany
   195  func BenchmarkFlorianUekermannIterateMany(b *testing.B) {
   196  	var input = make([]uint64, 68)
   197  	setRnd(input, 4)
   198  	var bitmap = From(input)
   199  	buffer := make([]uint, 256)
   200  	b.ResetTimer()
   201  	var checksum = uint(0)
   202  	for i := 0; i < b.N; i++ {
   203  		var last, batch = bitmap.NextSetMany(0, buffer)
   204  		for len(batch) > 0 {
   205  			for _, idx := range batch {
   206  				checksum += idx
   207  			}
   208  			last, batch = bitmap.NextSetMany(last+1, batch)
   209  		}
   210  	}
   211  	if checksum == 0 { // added just to fool ineffassign
   212  		return
   213  	}
   214  }
   215  
   216  func BenchmarkFlorianUekermannIterateManyReg(b *testing.B) {
   217  	var input = make([]uint64, 68)
   218  	setRnd(input, 4)
   219  	var bitmap = From(input)
   220  	b.ResetTimer()
   221  	var checksum = uint(0)
   222  	for i := 0; i < b.N; i++ {
   223  		for j, e := bitmap.NextSet(0); e; j, e = bitmap.NextSet(j + 1) {
   224  			checksum += j
   225  		}
   226  	}
   227  	if checksum == 0 { // added just to fool ineffassign
   228  		return
   229  	}
   230  }
   231  
   232  // function provided by FlorianUekermann
   233  func good(set []uint64) (checksum uint) {
   234  	for wordIdx, word := range set {
   235  		var wordIdx = uint(wordIdx * 64)
   236  		for word != 0 {
   237  			var bitIdx = uint(trailingZeroes64(word))
   238  			word ^= 1 << bitIdx
   239  			var index = wordIdx + bitIdx
   240  			checksum += index
   241  		}
   242  	}
   243  	return checksum
   244  }
   245  
   246  func BenchmarkFlorianUekermannIterateManyComp(b *testing.B) {
   247  	var input = make([]uint64, 68)
   248  	setRnd(input, 4)
   249  	b.ResetTimer()
   250  	var checksum = uint(0)
   251  	for i := 0; i < b.N; i++ {
   252  		checksum += good(input)
   253  	}
   254  	if checksum == 0 { // added just to fool ineffassign
   255  		return
   256  	}
   257  }
   258  
   259  /////// Mid density
   260  
   261  // go test -bench=BenchmarkFlorianUekermannLowDensityIterateMany
   262  func BenchmarkFlorianUekermannLowDensityIterateMany(b *testing.B) {
   263  	var input = make([]uint64, 1000000)
   264  	var rnd = rand.NewSource(0).(rand.Source64)
   265  	for i := 0; i < 50000; i++ {
   266  		input[rnd.Uint64()%1000000] = 1
   267  	}
   268  	var bitmap = From(input)
   269  	buffer := make([]uint, 256)
   270  	b.ResetTimer()
   271  	var sum = uint(0)
   272  	for i := 0; i < b.N; i++ {
   273  		j := uint(0)
   274  		j, buffer = bitmap.NextSetMany(j, buffer)
   275  		for ; len(buffer) > 0; j, buffer = bitmap.NextSetMany(j, buffer) {
   276  			for k := range buffer {
   277  				sum += buffer[k]
   278  			}
   279  			j++
   280  		}
   281  	}
   282  	if sum == 0 { // added just to fool ineffassign
   283  		return
   284  	}
   285  }
   286  
   287  func BenchmarkFlorianUekermannLowDensityIterateManyReg(b *testing.B) {
   288  	var input = make([]uint64, 1000000)
   289  	var rnd = rand.NewSource(0).(rand.Source64)
   290  	for i := 0; i < 50000; i++ {
   291  		input[rnd.Uint64()%1000000] = 1
   292  	}
   293  	var bitmap = From(input)
   294  	b.ResetTimer()
   295  	var checksum = uint(0)
   296  	for i := 0; i < b.N; i++ {
   297  		for j, e := bitmap.NextSet(0); e; j, e = bitmap.NextSet(j + 1) {
   298  			checksum += j
   299  		}
   300  	}
   301  	if checksum == 0 { // added just to fool ineffassign
   302  		return
   303  	}
   304  }
   305  
   306  func BenchmarkFlorianUekermannLowDensityIterateManyComp(b *testing.B) {
   307  	var input = make([]uint64, 1000000)
   308  	var rnd = rand.NewSource(0).(rand.Source64)
   309  	for i := 0; i < 50000; i++ {
   310  		input[rnd.Uint64()%1000000] = 1
   311  	}
   312  	b.ResetTimer()
   313  	var checksum = uint(0)
   314  	for i := 0; i < b.N; i++ {
   315  		checksum += good(input)
   316  	}
   317  	if checksum == 0 { // added just to fool ineffassign
   318  		return
   319  	}
   320  }
   321  
   322  /////// Mid density
   323  
   324  // go test -bench=BenchmarkFlorianUekermannMidDensityIterateMany
   325  func BenchmarkFlorianUekermannMidDensityIterateMany(b *testing.B) {
   326  	var input = make([]uint64, 1000000)
   327  	var rnd = rand.NewSource(0).(rand.Source64)
   328  	for i := 0; i < 3000000; i++ {
   329  		input[rnd.Uint64()%1000000] |= uint64(1) << (rnd.Uint64() % 64)
   330  	}
   331  	var bitmap = From(input)
   332  	buffer := make([]uint, 256)
   333  	b.ResetTimer()
   334  	sum := uint(0)
   335  	for i := 0; i < b.N; i++ {
   336  		j := uint(0)
   337  		j, buffer = bitmap.NextSetMany(j, buffer)
   338  		for ; len(buffer) > 0; j, buffer = bitmap.NextSetMany(j, buffer) {
   339  			for k := range buffer {
   340  				sum += buffer[k]
   341  			}
   342  			j++
   343  		}
   344  	}
   345  
   346  	if sum == 0 { // added just to fool ineffassign
   347  		return
   348  	}
   349  }
   350  
   351  func BenchmarkFlorianUekermannMidDensityIterateManyReg(b *testing.B) {
   352  	var input = make([]uint64, 1000000)
   353  	var rnd = rand.NewSource(0).(rand.Source64)
   354  	for i := 0; i < 3000000; i++ {
   355  		input[rnd.Uint64()%1000000] |= uint64(1) << (rnd.Uint64() % 64)
   356  	}
   357  	var bitmap = From(input)
   358  	b.ResetTimer()
   359  	var checksum = uint(0)
   360  	for i := 0; i < b.N; i++ {
   361  		for j, e := bitmap.NextSet(0); e; j, e = bitmap.NextSet(j + 1) {
   362  			checksum += j
   363  		}
   364  	}
   365  	if checksum == 0 { // added just to fool ineffassign
   366  		return
   367  	}
   368  }
   369  
   370  func BenchmarkFlorianUekermannMidDensityIterateManyComp(b *testing.B) {
   371  	var input = make([]uint64, 1000000)
   372  	var rnd = rand.NewSource(0).(rand.Source64)
   373  	for i := 0; i < 3000000; i++ {
   374  		input[rnd.Uint64()%1000000] |= uint64(1) << (rnd.Uint64() % 64)
   375  	}
   376  	b.ResetTimer()
   377  	var checksum = uint(0)
   378  	for i := 0; i < b.N; i++ {
   379  		checksum += good(input)
   380  	}
   381  	if checksum == 0 { // added just to fool ineffassign
   382  		return
   383  	}
   384  }
   385  
   386  ////////// High density
   387  
   388  func BenchmarkFlorianUekermannMidStrongDensityIterateMany(b *testing.B) {
   389  	var input = make([]uint64, 1000000)
   390  	var rnd = rand.NewSource(0).(rand.Source64)
   391  	for i := 0; i < 20000000; i++ {
   392  		input[rnd.Uint64()%1000000] |= uint64(1) << (rnd.Uint64() % 64)
   393  	}
   394  	var bitmap = From(input)
   395  	buffer := make([]uint, 256)
   396  	b.ResetTimer()
   397  	sum := uint(0)
   398  	for i := 0; i < b.N; i++ {
   399  		j := uint(0)
   400  		j, buffer = bitmap.NextSetMany(j, buffer)
   401  		for ; len(buffer) > 0; j, buffer = bitmap.NextSetMany(j, buffer) {
   402  			for k := range buffer {
   403  				sum += buffer[k]
   404  			}
   405  			j++
   406  		}
   407  	}
   408  
   409  	if sum == 0 { // added just to fool ineffassign
   410  		return
   411  	}
   412  }
   413  
   414  func BenchmarkFlorianUekermannMidStrongDensityIterateManyReg(b *testing.B) {
   415  	var input = make([]uint64, 1000000)
   416  	var rnd = rand.NewSource(0).(rand.Source64)
   417  	for i := 0; i < 20000000; i++ {
   418  		input[rnd.Uint64()%1000000] |= uint64(1) << (rnd.Uint64() % 64)
   419  	}
   420  	var bitmap = From(input)
   421  	b.ResetTimer()
   422  	var checksum = uint(0)
   423  	for i := 0; i < b.N; i++ {
   424  		for j, e := bitmap.NextSet(0); e; j, e = bitmap.NextSet(j + 1) {
   425  			checksum += j
   426  		}
   427  	}
   428  	if checksum == 0 { // added just to fool ineffassign
   429  		return
   430  	}
   431  }
   432  
   433  func BenchmarkFlorianUekermannMidStrongDensityIterateManyComp(b *testing.B) {
   434  	var input = make([]uint64, 1000000)
   435  	var rnd = rand.NewSource(0).(rand.Source64)
   436  	for i := 0; i < 20000000; i++ {
   437  		input[rnd.Uint64()%1000000] |= uint64(1) << (rnd.Uint64() % 64)
   438  	}
   439  	b.ResetTimer()
   440  	var checksum = uint(0)
   441  	for i := 0; i < b.N; i++ {
   442  		checksum += good(input)
   443  	}
   444  	if checksum == 0 { // added just to fool ineffassign
   445  		return
   446  	}
   447  }
   448  

View as plain text