UnsetIterator is very slow on densely populated bitsets

[rogpeppe]

I wrote this test:

func TestUnsetIterator(t *testing.T) {
	r := rand.New(rand.NewSource(0))
	s := NewBitmap()
	sz := 150000
	initsize := 65000
	for i := 0; i < initsize; i++ {
		s.Add(uint32(r.Int31n(int32(sz))))
	}
	wantCount := s.GetCardinality()
	s.Flip(0, 0x100000000)
	i := s.UnsetIterator(0, 0xffffffff)
	gotCount := uint64(0)
	for i.HasNext() {
		i.Next()
		gotCount++
	}
	assert.Equal(t, wantCount, gotCount)
}

This test passes but takes about 30 seconds to run on my machine.

It seems like UnsetIterator is doing work proportional to the number of set bits
rather than the number of unset bits.

That seems rather unfortunate, and doesn't seem inevitable, given that running
Flip and then Iterator takes a fraction of the time.

[lemire]

@rogpeppe It will iterate over all the set bits in order to produce the unset bits.

A pull request is invited to improve the performance.

[rogpeppe]

@lemire How do you feel about something like this? #493

I confess that I got Claude Code to do it for me, but it looks fairly plausible to me
(but I'm not familiar with the code base so it may well be way off base!)

[rogpeppe]

A simpler approach that would still help matters considerably might be to check the cardinality. If it's >0x80000000, make a temporary copy with flipped bits and use a regular iterator over that. I guess it might be possible to use a fast approximation of the cardinality to make the decision: when the number of set bits is similar to the number of unset bits, the overhead of iterating through all those bits is going to dwarf the overhead of flipping anyway.

[lemire]

@rogpeppe Yes. 493 looks pretty good. We should stress test it and benchmark it.

If you submit it formally, I can probably review it line by line, but at a glance it looks fine.

The reason why Claude can do it is that it is conceptually simple. We are not trying to solve a very challenging problem. It is just a lot of boilerplate/routine code. So yeah...

[rogpeppe]

The reason why Claude can do it is that it is conceptually simple. We are not trying to solve a very challenging problem. It is just a lot of boilerplate/routine code. So yeah...

Yeah, that was my feeling too. Lots of stuff that would have taken me forever to work out, but same level of abstraction as everything else - it's great at following existing patterns! I'll work it up into a better PR and add some stress/property tests that should give decent confidence.

[rogpeppe]

Proposed #501