Support 1.23 iterator in a backward-compatible way #475

amikai · 2025-06-01T15:44:20Z

Resolve #471

Provide two new functions:

Values: An iterator in normal order
Backward: An iterator in reverse order

Unit test:

iter123_test.go: Test the 1.23 iterator by for-range
iter_test.go: Test the iterator by call function way

Design consideration

I used a naming method similar to slices.Values and slices.Backward to make it easier to use.
It is compatible to use Values and Backward before version 1.23 without for-range function syntax, which means we don't need to update the go.mod version.
For version 1.23 or later, we can use the for-range function syntax, and these two functions are also compatible with the iterator type in the iter package.

Hi @lemire,
The unit test I wrote uses a similar approach to the one for testing Bitmap.ReverseIterator and Bitmap.Iterator. However, I am not confident that the test case is robust enough. Could you please review it? If you find the implementation acceptable, I will proceed with writing the Go doc comments and add examples to it.

lemire · 2025-06-02T00:33:12Z

Can you add benchmarks ? See

roaring/benchmark_test.go

Line 18 in fb67118

func BenchmarkIteratorAlloc(b *testing.B) {

amikai · 2025-06-02T14:10:40Z

Hi @lemire
The benchmark is added in df9d672

lemire · 2025-06-05T13:44:07Z

@amikai Can you share your benchmark results ? E.g., on your own machine ?

lemire · 2025-06-05T13:54:27Z

iter123_test.go

+
+	t.Run("#6", func(t *testing.T) {
+		b := New()
+		b.AddInt(MaxUint32)


An int might be a signed 32-bit integer, so MaxUint32 can't be represented.

But when it works, you might be allocating 512 MB of memory. Please don't do this as part of our routine tests.

lemire · 2025-06-05T13:55:08Z

iter_test.go

+
+func TestBackward(t *testing.T) {
+	t.Run("#1", func(t *testing.T) {
+		values := []uint32{0, 2, 15, 16, 31, 32, 33, 9999, MaxUint16, MaxUint32}


This will allocate hundreds of megabytes. Please don't do this in tests.

In fact, I just wrote a similar test of the TestReverseIterator to make sure the behavior is same as before. How about I change it to values := []uint32{0, 2, 15, 16, 31, 32, 33, 9999, MaxUint16}? Is that okay with you?

roaring/roaring_test.go

Lines 2428 to 2449 in b705c37

t.Run("#1", func(t *testing.T) {

values := []uint32{0, 2, 15, 16, 31, 32, 33, 9999, MaxUint16, MaxUint32}

bm := New()

for n := 0; n < len(values); n++ {

bm.Add(values[n])

}

i := bm.ReverseIterator()

n := len(values) - 1

for i.HasNext() {

assert.EqualValues(t, i.Next(), values[n])

n--

}

// HasNext() was terminating early - add test

i = bm.ReverseIterator()

n = len(values) - 1

for ; n >= 0; n-- {

assert.EqualValues(t, i.Next(), values[n])

assert.False(t, n > 0 && !i.HasNext())

}

})

lemire · 2025-06-05T13:55:22Z

iter_test.go

+
+	t.Run("#6", func(t *testing.T) {
+		b := New()
+		b.AddInt(MaxUint32)


This will allocate hundreds of megabytes. Please don't do this in tests.

Same as before, I just wrote a similar test to make sure the behavior same as before. Will delete this test.

roaring/roaring_test.go

Lines 2488 to 2496 in b705c37

t.Run("#6", func(t *testing.T) {

bm := New()

bm.Add(MaxUint32)

i := bm.ReverseIterator()

assert.True(t, i.HasNext())

assert.EqualValues(t, uint32(MaxUint32), i.Next())

assert.False(t, i.HasNext())

})

@amikai It is entirely possible that it was pre-existing. it is still a terrible idea. :-)

To be clear, we do not have AddInt(MaxUint32) in the code base because that does not work....

MaxUint32 may not fit in an int.

Sorry, I didn't see clearly.

amikai · 2025-06-05T17:31:54Z

Hi @lemire, here is the benchmark on my computer:

goos: darwin
goarch: arm64
pkg: github.com/RoaringBitmap/roaring/v2
cpu: Apple M2
BenchmarkIterator123/simple_iteration_with_alloc-8                 24210             48902 ns/op             112 B/op          1 allocs/op
BenchmarkIterator123/simple_iteration-8                            25024             47947 ns/op               0 B/op          0 allocs/op
BenchmarkIterator123/values_iteration-8                            23919             49615 ns/op             112 B/op          1 allocs/op
BenchmarkIterator123/reverse_iteration_with_alloc-8                22402             54250 ns/op             112 B/op          1 allocs/op
BenchmarkIterator123/reverse_iteration-8                           25252             47785 ns/op               0 B/op          0 allocs/op
BenchmarkIterator123/backward_iteration-8                          22621             52362 ns/op             112 B/op          1 allocs/op
BenchmarkIterator123/many_iteration_with_alloc-8                   57945             20636 ns/op            4224 B/op          2 allocs/op
BenchmarkIterator123/many_iteration-8                              59941             20383 ns/op               0 B/op          0 allocs/op
BenchmarkIterator123/values_iteration_1.23-8                       24662             49834 ns/op             112 B/op          1 allocs/op
BenchmarkIterator123/backward_iteration_1.23-8                     23325             51611 ns/op             112 B/op          1 allocs/op
BenchmarkIteratorAlloc/simple_iteration_with_alloc-8               24333             48729 ns/op             112 B/op          1 allocs/op
BenchmarkIteratorAlloc/simple_iteration-8                          24201             50280 ns/op               0 B/op          0 allocs/op
BenchmarkIteratorAlloc/values_iteration-8                          24680             49221 ns/op             112 B/op          1 allocs/op
BenchmarkIteratorAlloc/reverse_iteration_with_alloc-8              23397             51549 ns/op             112 B/op          1 allocs/op
BenchmarkIteratorAlloc/reverse_iteration-8                         26040             45923 ns/op               0 B/op          0 allocs/op
BenchmarkIteratorAlloc/backward_iteration-8                        23385             51324 ns/op             112 B/op          1 allocs/op
BenchmarkIteratorAlloc/many_iteration_with_alloc-8                 57744             20754 ns/op            4224 B/op          2 allocs/op
BenchmarkIteratorAlloc/many_iteration-8                            57397             19987 ns/op               0 B/op          0 allocs/op

lemire · 2025-06-05T18:57:38Z

@amikai The performance is ok.

Can you just tweak the small things I flagged ? We will be able to merge.

amikai · 2025-06-06T01:56:45Z

Hi @lemire, I have tweaked the test.

lemire · 2025-06-06T13:14:38Z

Great. I am running the CI tests, if it passes, we shall merge and release !!!

amikai · 2025-07-10T11:57:52Z

Hi @lemire, If there any concerns to merge the PR and release?

lemire · 2025-07-10T12:00:34Z

Merging!

This builds on the previous work in RoaringBitmap#475.

Support 1.23 iterator in a backward-compatible way

251b10c

amikai force-pushed the go-1.23-iterator branch from 5294909 to 251b10c Compare June 1, 2025 15:45

amikai marked this pull request as ready for review June 1, 2025 16:00

amikai force-pushed the go-1.23-iterator branch from ee65d37 to e0a3765 Compare June 2, 2025 14:09

amikai added 2 commits June 2, 2025 22:09

Avoid pointer escape

a6af0ed

Add benchmark for 1.23 and current version

df9d672

amikai force-pushed the go-1.23-iterator branch from e0a3765 to df9d672 Compare June 2, 2025 14:09

Fix the test of Backward

6e1cecf

amikai force-pushed the go-1.23-iterator branch from 6f79ad4 to 6e1cecf Compare June 2, 2025 14:20

lemire reviewed Jun 5, 2025

View reviewed changes

Tweak the test

69146ec

lemire merged commit 2893d51 into RoaringBitmap:master Jul 10, 2025
8 checks passed

happygiraffe added a commit to happygiraffe/roaring that referenced this pull request Jul 14, 2025

Clone Go 1.23 iterator support for roaring64.

bf70bef

This builds on the previous work in RoaringBitmap#475.

happygiraffe mentioned this pull request Jul 14, 2025

Clone Go 1.23 iterator support for roaring64. #478

Merged

amikai mentioned this pull request Jul 23, 2025

docs: add godoc for Values and Backward #479

Merged

	t.Run("#1", func(t *testing.T) {
	values := []uint32{0, 2, 15, 16, 31, 32, 33, 9999, MaxUint16, MaxUint32}
	bm := New()
	for n := 0; n < len(values); n++ {
	bm.Add(values[n])
	}
	i := bm.ReverseIterator()
	n := len(values) - 1

	for i.HasNext() {
	assert.EqualValues(t, i.Next(), values[n])
	n--
	}

	// HasNext() was terminating early - add test
	i = bm.ReverseIterator()
	n = len(values) - 1
	for ; n >= 0; n-- {
	assert.EqualValues(t, i.Next(), values[n])
	assert.False(t, n > 0 && !i.HasNext())
	}
	})

	t.Run("#6", func(t *testing.T) {
	bm := New()
	bm.Add(MaxUint32)
	i := bm.ReverseIterator()

	assert.True(t, i.HasNext())
	assert.EqualValues(t, uint32(MaxUint32), i.Next())
	assert.False(t, i.HasNext())
	})

Support 1.23 iterator in a backward-compatible way #475

Support 1.23 iterator in a backward-compatible way #475

Uh oh!

Conversation

amikai commented Jun 1, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Design consideration

Uh oh!

lemire commented Jun 2, 2025

Uh oh!

amikai commented Jun 2, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

lemire commented Jun 5, 2025

Uh oh!

lemire Jun 5, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

lemire Jun 5, 2025

Choose a reason for hiding this comment

Uh oh!

amikai Jun 5, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

lemire Jun 5, 2025

Choose a reason for hiding this comment

Uh oh!

lemire Jun 5, 2025

Choose a reason for hiding this comment

Uh oh!

amikai Jun 5, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

lemire Jun 5, 2025

Choose a reason for hiding this comment

Uh oh!

lemire Jun 5, 2025

Choose a reason for hiding this comment

Uh oh!

amikai Jun 6, 2025

Choose a reason for hiding this comment

Uh oh!

amikai commented Jun 5, 2025

Uh oh!

lemire commented Jun 5, 2025

Uh oh!

amikai commented Jun 6, 2025

Uh oh!

lemire commented Jun 6, 2025

Uh oh!

amikai commented Jul 10, 2025

Uh oh!

lemire commented Jul 10, 2025

Uh oh!

Uh oh!

Uh oh!

amikai commented Jun 1, 2025 •

edited

Loading

amikai commented Jun 2, 2025 •

edited

Loading

lemire Jun 5, 2025 •

edited

Loading

amikai Jun 5, 2025 •

edited

Loading

amikai Jun 5, 2025 •

edited

Loading