Skip to content

ClearBits with AndNot #480

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom
Merged
merged 3 commits into from
Aug 7, 2025
Merged

ClearBits with AndNot #480

merged 3 commits into from
Aug 7, 2025

Conversation

ofpiyush
Copy link
Contributor

@ofpiyush ofpiyush commented Aug 7, 2025

I am not entirely sure why we had the iterator set up.

Clearing bits with AndNot feels correct.

Let me know if there's some case that I've missed here.

Did not remove the ClearBits functions as they're exported public API.

@guymolinari
Copy link
Contributor

guymolinari commented Aug 7, 2025 via email

@ofpiyush
Copy link
Contributor Author

ofpiyush commented Aug 7, 2025

The intention of ClearBits() is to perform "bulk deletes" of values.

Did you mean ClearValues there?

Wouldn't AndNot do that and perform better than the iteration?

@guymolinari
Copy link
Contributor

guymolinari commented Aug 7, 2025 via email

@ofpiyush
Copy link
Contributor Author

ofpiyush commented Aug 7, 2025

Why I believe that to be the case.

The Remove would need to binary search for the container and clear it one value at a time.

With AndNot, we should be searching for the container once per container of the foundset.

The bitmap containers would be even faster as we can perform bit operation on the entire uint64 with 1 operation.

I can add a benchmark later today in case it helps.

@guymolinari
Copy link
Contributor

guymolinari commented Aug 7, 2025 via email

@lemire
Copy link
Member

lemire commented Aug 7, 2025

a merge is almost guaranteed ;-)

Correct. It is a a community-based project. A PR that improves the performance is almost certain to be merged.

@guymolinari
Copy link
Contributor

guymolinari commented Aug 7, 2025 via email

@ofpiyush
Copy link
Contributor Author

ofpiyush commented Aug 7, 2025

Benchmark results on my machine. Given the nature of the change, it should translate to linux servers as well.

goos: darwin
goarch: arm64
pkg: github.com/RoaringBitmap/roaring/v2/BitSliceIndexing
cpu: Apple M4 Max
               │ bench_old.txt │            bench_new.txt             │
               │    sec/op     │    sec/op     vs base                │
ClearValues-14    18.224m ± 2%   3.968m ± 23%  -78.23% (p=0.000 n=10)

               │ bench_old.txt │            bench_new.txt             │
               │     B/op      │     B/op      vs base                │
ClearValues-14    9.536Ki ± 1%   8.536Ki ± 0%  -10.49% (p=0.000 n=10)

               │ bench_old.txt │           bench_new.txt            │
               │   allocs/op   │ allocs/op   vs base                │
ClearValues-14      29.00 ± 0%   20.00 ± 0%  -31.03% (p=0.000 n=10)

goos: darwin
goarch: arm64
pkg: github.com/RoaringBitmap/roaring/v2/roaring64
cpu: Apple M4 Max
               │ bench_old.txt │            bench_new.txt            │
               │    sec/op     │   sec/op     vs base                │
ClearValues-14    24.845m ± 2%   5.019m ± 1%  -79.80% (p=0.000 n=10)

               │ bench_old.txt │            bench_new.txt            │
               │     B/op      │     B/op      vs base               │
ClearValues-14    25.54Ki ± 1%   24.55Ki ± 0%  -3.85% (p=0.000 n=10)

               │ bench_old.txt │           bench_new.txt            │
               │   allocs/op   │ allocs/op   vs base                │
ClearValues-14      33.00 ± 0%   24.00 ± 0%  -27.27% (p=0.000 n=10)
Commands and raw outputs

With old code calling ClearBits with the iterator

go test -bench='^BenchmarkClearValues$' -run='^$' -benchmem -count=10 > bench_old.txt

With AndNot

go test -bench='^BenchmarkClearValues$' -run='^$' -benchmem -count=10 > bench_new.txt

then benchstat

benchstat bench_old.txt bench_new.txt

Raw data:

cat BitSliceIndexing/bench_old.txt

goos: darwin
goarch: arm64
pkg: github.com/RoaringBitmap/roaring/v2/BitSliceIndexing
cpu: Apple M4 Max
BenchmarkClearValues-14    	      66	  17949452 ns/op	   10301 B/op	      30 allocs/op
BenchmarkClearValues-14    	      63	  17658084 ns/op	    9762 B/op	      29 allocs/op
BenchmarkClearValues-14    	      67	  17995859 ns/op	    9768 B/op	      29 allocs/op
BenchmarkClearValues-14    	      67	  17879762 ns/op	    9767 B/op	      29 allocs/op
BenchmarkClearValues-14    	      66	  18207193 ns/op	    9762 B/op	      29 allocs/op
BenchmarkClearValues-14    	      66	  18267813 ns/op	    9756 B/op	      29 allocs/op
BenchmarkClearValues-14    	      63	  18239941 ns/op	    9756 B/op	      29 allocs/op
BenchmarkClearValues-14    	      66	  18322739 ns/op	    9763 B/op	      29 allocs/op
BenchmarkClearValues-14    	      66	  18874647 ns/op	    9770 B/op	      29 allocs/op
BenchmarkClearValues-14    	      64	  18279068 ns/op	    9828 B/op	      29 allocs/op
PASS
ok  	github.com/RoaringBitmap/roaring/v2/BitSliceIndexing	40.108s

cat BitSliceIndexing/bench_new.txt

goos: darwin
goarch: arm64
pkg: github.com/RoaringBitmap/roaring/v2/BitSliceIndexing
cpu: Apple M4 Max
BenchmarkClearValues-14    	     310	   3849987 ns/op	    8760 B/op	      20 allocs/op
BenchmarkClearValues-14    	     266	   3964120 ns/op	    8763 B/op	      20 allocs/op
BenchmarkClearValues-14    	     226	   4588439 ns/op	    8729 B/op	      20 allocs/op
BenchmarkClearValues-14    	     300	   4688459 ns/op	    8730 B/op	      20 allocs/op
BenchmarkClearValues-14    	     307	   5119839 ns/op	    8740 B/op	      20 allocs/op
BenchmarkClearValues-14    	     306	   3971695 ns/op	    8756 B/op	      20 allocs/op
BenchmarkClearValues-14    	     267	   3880223 ns/op	    8741 B/op	      20 allocs/op
BenchmarkClearValues-14    	     259	   3918312 ns/op	    8766 B/op	      20 allocs/op
BenchmarkClearValues-14    	     226	   4866790 ns/op	    8733 B/op	      20 allocs/op
BenchmarkClearValues-14    	     309	   3942959 ns/op	    8741 B/op	      20 allocs/op
PASS
ok  	github.com/RoaringBitmap/roaring/v2/BitSliceIndexing	145.173s

cat roaring64/bench_old.txt

goos: darwin
goarch: arm64
pkg: github.com/RoaringBitmap/roaring/v2/roaring64
cpu: Apple M4 Max
BenchmarkClearValues-14    	      48	  24764023 ns/op	   26910 B/op	      34 allocs/op
BenchmarkClearValues-14    	      49	  24731279 ns/op	   26526 B/op	      33 allocs/op
BenchmarkClearValues-14    	      49	  24926856 ns/op	   26152 B/op	      33 allocs/op
BenchmarkClearValues-14    	      48	  24809299 ns/op	   26152 B/op	      33 allocs/op
BenchmarkClearValues-14    	      49	  24738934 ns/op	   26152 B/op	      33 allocs/op
BenchmarkClearValues-14    	      49	  24838062 ns/op	   26152 B/op	      33 allocs/op
BenchmarkClearValues-14    	      49	  24850997 ns/op	   26280 B/op	      33 allocs/op
BenchmarkClearValues-14    	      48	  25561292 ns/op	   26152 B/op	      33 allocs/op
BenchmarkClearValues-14    	      48	  24999984 ns/op	   26152 B/op	      33 allocs/op
BenchmarkClearValues-14    	      48	  25454627 ns/op	   26152 B/op	      33 allocs/op
PASS
ok  	github.com/RoaringBitmap/roaring/v2/roaring64	29.255s

cat roaring64/bench_new.txt

goos: darwin
goarch: arm64
pkg: github.com/RoaringBitmap/roaring/v2/roaring64
cpu: Apple M4 Max
BenchmarkClearValues-14    	     249	   4945412 ns/op	   25144 B/op	      24 allocs/op
BenchmarkClearValues-14    	     243	   4952487 ns/op	   25162 B/op	      24 allocs/op
BenchmarkClearValues-14    	     235	   5081436 ns/op	   25144 B/op	      24 allocs/op
BenchmarkClearValues-14    	     228	   5017723 ns/op	   25144 B/op	      24 allocs/op
BenchmarkClearValues-14    	     237	   5150613 ns/op	   25151 B/op	      24 allocs/op
BenchmarkClearValues-14    	     238	   5021206 ns/op	   25144 B/op	      24 allocs/op
BenchmarkClearValues-14    	     237	   5026184 ns/op	   25144 B/op	      24 allocs/op
BenchmarkClearValues-14    	     238	   5079279 ns/op	   25144 B/op	      24 allocs/op
BenchmarkClearValues-14    	     238	   5000500 ns/op	   25144 B/op	      24 allocs/op
BenchmarkClearValues-14    	     238	   4998973 ns/op	   25144 B/op	      24 allocs/op
PASS
ok  	github.com/RoaringBitmap/roaring/v2/roaring64	67.009s

@lemire lemire merged commit 51c006d into RoaringBitmap:master Aug 7, 2025
8 checks passed
@ofpiyush ofpiyush deleted the clear_bits branch August 8, 2025 07:00
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Reviewers
No reviews
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

Successfully merging this pull request may close these issues.
3 participants
@ofpiyush @guymolinari @lemire