NextSetMany is broken and probably not a good idea.

[FlorianUekermann]

I don't have a shorter example unfortunately. This example will loop indefinitely:

import (
	"fmt"
	"math"
	"math/rand"

	"github.com/willf/bitset"
)

func main() {
	var bits = make([]uint64, 68) //(1<<30)/8)
	setRnd(bits, 4)

	fmt.Println("Checksum", batched(bits))
}

func batched(input []uint64) (checksum uint) {
	var bits = bitset.From(input)
	var buffer [256]uint
	var last, batch = bits.NextSetMany(0, buffer[:])
	fmt.Println(last, batch)
	for len(batch) > 0 {
		for _, idx := range batch {
			checksum += idx
		}
		last, batch = bits.NextSetMany(last+1, batch)
		fmt.Println(last, batch)
	}

	return checksum
}

var rnd = rand.NewSource(0).(rand.Source64)

func setRnd(bits []uint64, halfings int) {
	for i := range bits {
		bits[i] = math.MaxUint64
		for j := 0; j < halfings; j++ {
			bits[i] &= rnd.Uint64()
		}
	}
}

My benchmarks indicate that NextSetMany is conceptually a bad idea as well. The following is depending on the circumstances (bitset length and density of ones) equally fast or faster:

func good(set []uint64) (checksum uint) {
	for rep := 0; rep < numReps; rep++ {
		for wordIdx, word := range set {
			var wordIdx = uint(wordIdx * 64)
			for word != 0 {
				var bitIdx = uint(bits.TrailingZeros64(word))
				word ^= 1 << bitIdx
				// Do something with the result of the next line
				var index = wordIdx + bitIdx
			}
		}
	}
	return checksum
}

I'm sure you can turn this in an iterator without too much effort, or just take a function pointer. Any serious work to be done will dwarf the overhead of the function pointer or iterator call anyway. In particular in the case with many zeros (which where the NextSet functions are useful) the relatively naive function above is much faster.

Note that the above is a fairly naive implementation, which is nowhere close to optimal. There is at the very least a superfluous word ==0 check in bits.TrailingZeros64 which could be skipped. But I suspect there are even more gains to be had with a little effort.

[lemire]

My benchmarks indicate that NextSetMany is conceptually a bad idea as well. The following is depending on the circumstances (bitset length and density of ones) equally fast or faster:

Let us try it out... Here is your function...

func good(set []uint64) (checksum uint) {
	for wordIdx, word := range set {
		var wordIdx = uint(wordIdx * 64)
		for word != 0 {
			var bitIdx = uint(trailingZeroes64(word))
			word ^= 1 << bitIdx
			// Do something with the result of the next line
			var index = wordIdx + bitIdx
			checksum += index
		}
	}
	return checksum
}

Here is a related benchmark...

func BenchmarkFlorianUekermannIterateManyComp(b *testing.B) {
	var input = make([]uint64, 68)
	setRnd(input, 4)
	b.ResetTimer()
	var checksum = uint(0)
	for i := 0; i < b.N; i++ {
		checksum += good(input)
	}
	if checksum == 0 { // added just to fool ineffassign
		return
	}
}

Here is the version with our current API:

func BenchmarkFlorianUekermannIterateMany(b *testing.B) {
	var input = make([]uint64, 68)
	setRnd(input, 4)
	var bitmap = From(input)
	b.ResetTimer()
	var checksum = uint(0)
	for i := 0; i < b.N; i++ {
		buffer := make([]uint, 256)
		var last, batch = bitmap.NextSetMany(0, buffer)
		for len(batch) > 0 {
			for _, idx := range batch {
				checksum += idx
			}
			last, batch = bitmap.NextSetMany(last+1, batch)
		}
	}
	if checksum == 0 { // added just to fool ineffassign
		return
	}
}

Here are the result on a Linux server...

$ go version
go version go1.9 linux/amd64
dlemire@skylake:~/go/src/github.com/willf/bitset$ go test -bench=BenchmarkFlorianUekermannIterateMany
{0,1,2,3,4,5,6,7,8,9}
goos: linux
goarch: amd64
pkg: github.com/willf/bitset
BenchmarkFlorianUekermannIterateMany     	 3000000	       523 ns/op
BenchmarkFlorianUekermannIterateManyReg  	 1000000	      1738 ns/op
BenchmarkFlorianUekermannIterateManyComp 	 2000000	       618 ns/op

Here are the results on my laptop...

$ go version
$ go test -bench=BenchmarkFlorianUekermannIterateMany
{0,1,2,3,4,5,6,7,8,9}
goos: darwin
goarch: amd64
pkg: github.com/willf/bitset
BenchmarkFlorianUekermannIterateMany-8       	 3000000	       496 ns/op
BenchmarkFlorianUekermannIterateManyReg-8    	 1000000	      1684 ns/op
BenchmarkFlorianUekermannIterateManyComp-8   	 3000000	       579 ns/op

So according to these tests, your version is systematically slower.

I'm sure you can turn this in an iterator without too much effort

Pull request invited. Please also provide benchmarks showing that your code is faster.

[lemire]

Please upgrade to Version 1.1.6 the latest version.

[FlorianUekermann]

You'll want to test larger bitsets as well as lower densities. 68 and 4 were chosen because that's where the bug happens. This could be anything.

It also seems like you replaced the TrailingZeros64 function, there's something odd going on with the compiler if I do that on my machine (not sure what, didn't have time to check the generated code today).

I won't send a PR, since we aren't using this library. I just stumbled over the bug while checking the claim about batching. I'll retest with the fixed code, but I doubt it makes a big difference.

[lemire]

In the lastest version, I have added tests at various densities. When the bitset is super low-density, the bulk of the time is just spent scanning zero words (arguably it is indicative that you shouldn't be using a bitset) so all methods are pretty much equivalent.

Otherwise, the NextSetMany method is much faster than NextSet as I reported.

Surprisingly (to me), NextSetMany even beats your hand-crafted (non-iterated) approach. It may very well be that you could "turn this in an iterator without too much effort", but I don't know how to do it. I'd be very interested in a code sample.

$ go test -bench=BenchmarkFlorianUekermann
{0,1,2,3,4,5,6,7,8,9}
goos: linux
goarch: amd64
pkg: github.com/willf/bitset
BenchmarkFlorianUekermannIterateMany                     	 3000000	       516 ns/op
BenchmarkFlorianUekermannIterateManyReg                  	 1000000	      1790 ns/op
BenchmarkFlorianUekermannIterateManyComp                 	 2000000	       618 ns/op

BenchmarkFlorianUekermannLowDensityIterateMany           	    2000	   1101767 ns/op
BenchmarkFlorianUekermannLowDensityIterateManyReg        	    1000	   1239836 ns/op
BenchmarkFlorianUekermannLowDensityIterateManyComp       	    2000	   1101817 ns/op

BenchmarkFlorianUekermannMidDensityIterateMany           	     100	  12572068 ns/op
BenchmarkFlorianUekermannMidDensityIterateManyReg        	      50	  25299202 ns/op
BenchmarkFlorianUekermannMidDensityIterateManyComp       	     100	  14618127 ns/op

BenchmarkFlorianUekermannMidStrongDensityIterateMany     	      30	  40667044 ns/op
BenchmarkFlorianUekermannMidStrongDensityIterateManyReg  	      10	 104326575 ns/op
BenchmarkFlorianUekermannMidStrongDensityIterateManyComp 	      30	  51650557 ns/op