Attached patch contains LongFixedBitSet:

• Only set/get(long). No more set/fastSet and int/long variations. This class should be used only for more than 2.1B bits.

• Doesn't implement Bits/DocIdSet – again, this class should be used only for more than 2.1B bits.

• A static utility method "grows" it if needed while sharing the underlying long[] if possible.

I reviewed code which uses OpenBitSet and turns out most of this code could use a "fixed" bitset already. Some needed a Long version, but otherwise the number of bits was known in advance already. Yet all these classes used obs.set() instead of .fastSet(), which IMO shows the need for this new class and removed confusion.

There are some places in lucene/ code that still use OpenBitSet, such as TestOpenBitSet, javadoc mentions and where doc IDs are used (e.g. FieldCache). I didn't touch them since the new LongFixedBitSet is not intended to be used for doc IDs anyway.

I quickly reviewed some of the solr/ code, and looks like there too we can cutover to (Long)FixedBitSet already, since the number of bits is known in advance. I will do it after I get some feedback about the current patch.

+1, it's nice to see how many OBS's you were able to cut over.

I especially loved seeing this pre-existing comment (again):

       super(in, false); // <-- not passing false here wasted about 3 hours of my time!!!!!!!!!!!!!

Maybe if we added a FixedBitSet.ensureCapacity then we could use FBS
in Numeric/BinaryDocValuesWriter? Seems like we should decouple elasticity
and long vs int index?

I find it crazy that SloppyPhraseScorer seems to allocate a new bitset
for every .advance call?

Maybe we should rename FBS -> IntFBS?

Maybe if we added a FixedBitSet.ensureCapacity

You're right. Added FixedBitSet.ensureCapacity.

I find it crazy that SloppyPhraseScorer seems to allocate a new bitset

for every .advance call?

Me too, therefore I only added a TODO. I guess a quick fix would be to try and share a single FixedBitSet and clear() it in each advance. Also I'd optimize the scary while (bits.cardinality() > 0). Maybe in a separate issue?

Maybe we should rename FBS -> IntFBS?

We could, though it will generate a huge amount of changes, so if we want to do it, I'll do it after we're done reviewing the patch (just rote rename). But since it's public and useful API (i.e. even though it's marked internal, I believe it's used wider than just Lucene), maybe we shouldn't? It's just a rename...

BTW, I reviewed more Solr code and could use some guidance from someone who's more familiar with it. Looks like a core class of Solr that uses OBS is BitDocSet, but from what I can tell, it doesn't rely much on elasticity (e.g. it documents that the given bitset should be at least of size maxDoc()). Also, it (and other classes) sometimes use set/get and sometimes fast. So if someone can confirm it's safe to change this class to use FixedBitSet (seems like we don't even need Long here), I'll do it.

New patch:

• All lucene/ code is now cut over to (Long)FixedBitSet, including ChainedFilter. What remains is OBS, test and iterator. I think I'll extract FBS.iterator() to its own class, so that we could optimize in FBS.or() and friends.

• OpenBitSetDISI is now unused, not in lucene/ nor solr/. Should I nuke it?

• I also moved some code which used FBS copy-constructor to grow an FBS to FBS.ensureCapacity. So now nothing uses the new copy-constructor – nuke it?

I think we can cutover Solr usage of OBS in a separate commit/patch/issue, to make this issue contained.

Added a FixedBitSetIterator class and optimization in or/and etc. to do instanceof checks. Also nuked the copy-constructors - if someone wants to grow, he can use ensureCapacity. And I don't think shrinking a bitset is a good enough usecase to keep the ctor (it was anyway not entirely safe, as it didn't turn off the unused bits in the last word...).

I think this is ready. If there are no objections, I'd like to commit this tomorrow and proceed w/ cutting over Solr to FBS/LFBS as well.

Is there any way to deprecate but keep FixedBitSet while moving to IntFixedBitSet? A simple 'extends' isn't possible unless the final modifier is removed, and I think doing it any other way would lead to breakage.

I don't think we should deprecate anything. We can simply rename it - it's an internal class... If we rename it, I think we should just rename it to Int/LongBitSet. The word Fixed should not be there, I doubt if it was if we didn't have OpenBitSet. That that it's fixed is a given, and documented. I don't mind renaming it, as I said it's just a rote rename. Perhaps I should name the Long bit set LongBitSet (remove Fixed), to avoid renames in the future.

The class is definitely not internal only. Almost every filter I know of outside of Lucene uses it. I disahree with renaming it before Lucene 5.

Fair enough, I will rename the Long version to LongBitSet then, to avoid future renames.

Patch renames to LongBitSet.

Thanks,
I think the @lucene.internal on FixedBitSet is a bug, the javadoc tag should be removed. Without that class it is impossible to external users to implement their own Filter. Not even DocIdBitSet is available anymore, which could be used on top of a java.util.BitSet.

+1 to commit, the @lucene.internal problems can be solved separately!

I removed the internal annotation from LongBitSet and also FixedBitSet. I agree FBS is not internal...

Commit 1566662 from Shai Erera in branch 'dev/trunk'
[ https://svn.apache.org/r1566662 ]

LUCENE-5440: Add LongBitSet to handle large number of bits; replace usage of OpenBitSet by FixedBitSet/LongBitSet

Commit 1566670 from Shai Erera in branch 'dev/branches/branch_4x'
[ https://svn.apache.org/r1566670 ]

LUCENE-5440: Add LongBitSet to handle large number of bits; replace usage of OpenBitSet by FixedBitSet/LongBitSet

Committed this patch to trunk and 4x. I will work on the solr/ code ... at least, I'll make a best effort .

Patch moves solr/ code to use FixedBitSet instead of OpenBitSet. I ran into few issues e.g. w/ bulk operations such as or/union, where OpenBitSet grew the underlying long[]. Now it needs to grow on the outside. I think I'll add a check to FBS.or() to make sure the given bitset is not bigger than the current one.

Anyway, I still didn't run tests, just wanted to checkpoint. There are no more uses of OBS in solr/.

OpenBitSet is part of the Solr APIs in a number of places, so if we make these changes, I guess it should be trunk only?

I don't mind if we do it only in trunk. However, this affects only the Java API, which looks pretty low-level and expert to me? Given that and that migrating from OpenBitSet to FixedBitSet is trivial, wouldn't it be OK to port it to 4x as well?

I'm thinking about e.g. merging changes from trunk to 4x, which will be much easier if the two are in sync. Of course this alone doesn't justify an API break, but if it's such low-level and expert API, I wonder if we shouldn't do this in 4x as well.

Having said all that, you obviously understand Solr API better than me and know how it's used by users, so if you think we absolutely shouldn't do this in 4x, we'll do it only in trunk.

I think the @lucene.internal on FixedBitSet is a bug, the javadoc tag should be removed.

I don't think FixedBitSet should be external.

Our purpose here is to provide search APIs, not bitset utility APIs, and we should not have to commit to API back compatibility for this class or other such utility classes.

Commit 1567183 from Shai Erera in branch 'dev/trunk'
[ https://svn.apache.org/r1567183 ]

LUCENE-5440: add back elasticity assumptions

Commit 1567185 from Shai Erera in branch 'dev/branches/branch_4x'
[ https://svn.apache.org/r1567185 ]

LUCENE-5440: add back elasticity assumptions

I don't think FixedBitSet should be external. Our purpose here is to provide search APIs, not bitset utility APIs, and we should not have to commit to API back compatibility for this class or other such utility classes.

I disagree: If this is our case, we have to do more APIs internal and also hide stuff like AtomicReader, because its not useful for the end user. FixedBitSet is currently the only way for users to write own filters, unless they write their own DocIdSets. So to support filtering results, users have to implement the DocIdSet, Bits and DISI interfaces (which are public), so at least one implementation (the recommended one) should be public and stable.

I don't think FixedBitSet should be external.

+1. I mistakenly removed the @lucene.internal annotation, will add it back in the new patch. Our API isn't FixedBitSet, it's Filter/DocIdSet. And we offer DocIdBitSet (external) to use w/ Java's BitSet. It's not true that users cannot write their own Filters - they can write them using DocIdBitSet, or risk and use the internal FixedBitSet. I wouldn't want to see FBS stays w/ that name, just because once there was OpenBitSet - renaming (just as removing 'extends DocIdSet') is a trivial change to your code when you migrate...

Patch resolves an error I had w/ grouping (under Solr) and improves FBS assertions errors. I also returned the internal annotation to both FBS and LongBitSet, until we resolve that matter on LUCENE-5441. Another thing – I added an assert to FBS.or/xor if the given set.length() was bigger than current – we silently discarded bits!

All Solr tests pass now (except testDistribSearch which seem to fail constantly recently). I'd appreciate if someone can give it a second look.

I reviewed how we can perhaps not break the API. I thought first to
deprecate BitDocSet and create a new class BitsDocSet which will use
FixedBitSet. But the problem is that DocSet (the interface) commits to
OpenBitSet in its APIs: .getBits() and .setBitsOn().

I think that .setBitsOn could take a DocSet and check if it's a BitsDocSet,
call bits.or(), otherwise, iterate on the bits and call add().

As for .getBits(), it's currently used by DocSetBase's various base impls,
so I think if we made it protected (and only on DocSetBase), we could get
rid of it from the public API. BitDocSet would then override to return a
bits.clone(), whereas the others would just create a new FBS, like what
DocSetBase.getBits() does now.

It's also used by UninvertField, but it assumes the given DocSet is
BitDocSet already, so we can just add .getBits() to BitDocSet...

While this breaks the DocSet API, I think it's a good break as it allows
flexibility in the future (e.g if we rename FixedBitSet to IntBitSet, the
API doesn't break again). I'll post a patch soon.

Patch decouples DocSet from Fixed/OpenBitSet. DocSet.setBitsOn renamed to .addAllTo and takes a DocSet instead. DocSet.getBits() moved to DocSetBase as protected method and BitDocSet overrides and declares public. No code affected by these changes, outside DocSetBase.

I think it's ready to commit.

Commit 1568737 from Shai Erera in branch 'dev/trunk'
[ https://svn.apache.org/r1568737 ]

LUCENE-5440: decouple OpenBitSet from DocSet and move to use FixedBitSet

Commit 1568738 from Shai Erera in branch 'dev/branches/branch_4x'
[ https://svn.apache.org/r1568738 ]

LUCENE-5440: decouple OpenBitSet from DocSet and move to use FixedBitSet

Committed the Solr changes.

Commit 1568824 from Shai Erera in branch 'dev/trunk'
[ https://svn.apache.org/r1568824 ]

LUCENE-5440: fix bug in FacetComponent

Commit 1568825 from Shai Erera in branch 'dev/branches/branch_4x'
[ https://svn.apache.org/r1568825 ]

LUCENE-5440: fix bug in FacetComponent