BitSet next

hej
ostatnio w pracy pojawił się pewien problem z operacjami nextSetBit na javowych bitSetach, mianowicie musimy się sporo iterować przez cały bitset (najgorszy przykład, ustawiony bit 0 i 1 000 000) i takie operacje są wykonywane często.
Mam rozwiązanie które zawsze ma złożoność log64(max_bit_set) dla wysztkich operacji (add, remove, next, tak naprawdę ten log64 to koszt zamortyzowany, nie zawsze potrzebuję log64 operacji), narzut pamięciowy jest minimalny, a biorąc pod uwagę przyśpieszenie dla iteratora to nawet fajny kod.
Świat javy i tablice o rozmiarach Integer.Max_Value to ten logarytm jest prawie liczbą stałą (jakoś 6 w najgorszym przypadku)

Stąd pytanie czy znacie jakieś implementacje bitsetów, które mają fajne czasowo wyniki dla iteratora w przypadku BitSet?
Bardziej chciałbym sobie porównać moje wypociny z tym co ktoś już zrobił. Osobiście nie mogę znaleźć nic co wygląda lepiej niż kod javopodobny

Serio - nie rozumiem nic z tego co napisałeś

Na ślepo po słowach kluczowych powiem tylko że przerabiałem kiedyś bibliotekę zxing do czytania kodów kreskowych - tam często i gęsto są wykonywane operacje na bitach (setki milionów razy na sekundę - jest skanowany obraz z aparatu na smartfonie z androidem, zamieniany na macierz bitową analizowaną pod wieloma kątami) - klasa jest bardzo prosta i wygląda tak https://github.com/zxing/zxing/blob/master/core/src/main/java/com/google/zxing/common/BitArray.java

A zawsze są takie rzadkie te wasze bit sety? Jeśli tak, to może po prostu zastąpić to innym rodzajem zbioru? Np. Treeset?

Z drugiej strony liniowo skanując bitset, zera można szybko pomijać całymi grupami, np. porównując całe longi z zerem. Albo nawet grupy longów. Jak to dobrze zaimplementować to na AVX pewnie dałoby się 512 bitów na jeden może dwa cykle CPU pomijać.

Wyszukiwanie binarne ma niby lepszą złożoność, ale skacze mocno po RAMie więc nie musi być wcale lepsze.

różnie, wszystko zależy co tam się dzieje i często trzeba szukać pierwszego wolnego lub pierwszego ustawionego w zależności co chcemy zrobić.
W apce takich setów jest bardzo dużo stąd nie uśmiecha się nam używać "normalnych" drzew.

Na razie mamy coś w stylu specyficznej implementacji drzewa nałożonego na wektor bitowy i działa jak opisałem w pierwszym poście. Załatwia to sprawę, ale po prostu zastanawiam się czy to coś fajnego czy poszło 3 tygodnie kodowania na coś co można załatwić biblioteką, która może będzie działać jeszcze lepiej.