It has always been stated that reasonably justifiable departures from semantic or performance requirements can be documented if it's deemed to be the right tradeoff as compared to the alternative of not conforming to a protocol at all. That doesn't make it any less of a requirement, unless you're arguing that protocols have no semantic or performance requirements and just "expectations."
This is applicable to LazyFilterCollection, since without invoking an exception it cannot semantically both be Lazy and a Collection.
That is inapplicable here. We are not deciding between conforming to Collection with a documented exception versus not conforming to Collection at all: it is very clear that BitSet should conform to Collection. The requirements (or "expectations") of the protocol are not suggestions to be picked from when it suits, and nowhere is that license given.
Okay, if you want to call something that you don't have to do according to the documentation, and isn't done in standard library types, a “requirement” then I don't mind what word you use. To be explicit about the particular tradeoff here: making startIndex O(1) impacts the performance of other methods. In particular, if BitSet is backed by a BitArray, as it is in the proposal, then methods like remove can require linear scanning to update the stored startIndex. That might be the right tradeoff to make (it's probably fairly cheap in practice because in most cases you're already scanning the BitArray) or you might be suggesting a different implementation.
I think it can be both Lazy and a Collection. It comes with the cost that creation of a LazyFilterCollection would be O(n), but the type itself would still be a collection of lazily-filtered elements, and it would be a better-behaved Collection.
Bringing it back to this type: that means the BitSet from BitArray initializer mentioned here:
Would become linear. I think that's totally fine - just because BitSet happens to be backed by BitArray, there's no reason it can't do extra work if needed to expose a better Collection interface. startIndex is super important, and pre-calculating/storing it is worth much more than we'd gain by simplifying this initializer IMO.
This is off the current topic, but maybe nonzeroBitCount should be added. UInt8 has fast implementation of nonzeroBitCount, but we have to use bitArray.reduce(0, {$0 + ($1 ? 1 : 0)}) for BitArray. Perhaps it's not good in terms of performance. I think it's nice if nonzeroBitCount or like is included for BitArray.
Another option would be amortized O(1), by caching startIndex when it is first found, updating when it moves earlier (or anywhere within the same storage word), and either clearing or updating the cache when it moves later.
This could be a var _startIndex: Index? property on BitSet, or a var _firstTrue: Int? property on BitArray.
If you wanted to cache it when it was first found (i.e. even from a non-mutating method), it would cost a lot in terms of implementation complexity.
But just imagining we did want to do it. IMO, the best/most efficient way would be to:
Use a ManagedBuffer rather than an Array. This means implementing COW, RangeReplaceableCollection, etc.
Include the cached Index? in the ManagedBuffer's header
Read and write the cached index using atomic instructions.
The biggest problem would be point 1. It's really not an insignificant amount of code to write good quality reimplementations of Array's interface on top of a ManagedBuffer and, most importantly, to make sure it's all thoroughly tested. In my projects, I call this a ManagedArrayBuffer - basically, the layout of a ManagedBuffer with the API, bound-checking and value semantics of Array - and I think it would be great if either the standard library or swift-collections provided something like that one day.
And that's really the key point IMHO - how much code will need to be maintained? How can we be sure that it's reliable? etc. If we make the thing so complex that subtle bugs can sneak in, we'd have made it worse and less functional by chasing performance, which is not a good trade.
I think if we decide startIndex really needs to be O(1) (which IMO would need to be driven by empirical data, which so far is not pointing that direction), one easy thing to do would be to allow indices to point to positions that don't actually contain a bit and have accessing them/advancing them do the scan for the next valid location.
Ah dang you're right. I think there's probably a way of addressing that (e.g. make the canonical startIndex always 0 and have its equatable specifically check for 0-or-the-real-first), but I also still don't think this is a major concern in practice.
Hello everyone! I thought that since a good bit of responses have come in, I'd just give a comprehensive reply and see how that goes. Hopefully I touch on most everyone's concerns!
If I understood correctly, I believe that is what the BitSet is for!
I understand there are a lot of opinions on this matter. I personally wasn't sure which to side with, nor did I feel I had enough evidence or experience. Hence, for the initial PR, I just included all of them as I felt like its easier to remove some of them than it is to add or change them later .
This is a good point and:
Is my thought on it as well! I feel that my implementation can be removed unless/until a benchmark is ran that proves my implementation is faster. Thank you!
To be truthful, I'm not very familiar with encoding, but I do agree that it might work!
This was actually my thought exactly! I was very set on conforming to RRC, until a mentor of mine asked us to think of a use case for replaceSubrange(...), and we simply couldn't think of one! replaceSubrange(...), because it allows for inserting a larger range than what was deleted, was somewhat of a challenge. Hence, because we couldn't think of a use case, I decided to implement the methods that seemed necessary and omit the conformance, knowing it can easily be added later if someone from the community could come up with a reasonable use case.
It is true that my implementation is still missing a few SetAlgebra operations. However, I still feel like SetAlgebra is not an appropriate protocol for this type of Set, as counterintuitive as that sounds. Regardless of my opinion, I think this point:
is probably the more difinitive one. If the benchmarks prove that the methods without conformance perform better, I think sticking with the omission of SetAlgebra is a good choice. I have not run exhaustive benchmarks yet that compare SetAlgebra conforming methods versus the ones that don't, but thank you for bringing up this point, and I agree that it is worth checking out.
As for the debate on startIndex, I agree with this point:
If the change were to be made, I appreciate the point made by @Karl on the trade-off with the BitArray initializer and find that insightful (and worth tryig out). However I agree with @jawbroken in that it is not required. This sums it up pretty well:
This observation is correct, and is a bug. Thank you for finding it and pointing it out. The BitSet implementation so far has been made to work in a way that its underlying storage is identical for identical BitSets. There is a method in the imlementation that is not adjusting that properly. I think it is one of the remove functions, but I need to go in and check and correct it.
As for the argument regarding the excessive storage regarding the sparse data, there definitely might be some other options worth looking at, but mostly I agree with
I think there are other sets out there that better accomodate these use cases, and the point of the BitSet is to provide a set-like API for the BitArray. Hence, when it comes to my personal contribution, I prefer to leave it as is. I think this comment sums it up fairly well for me:
Hmm, thats an interesting point and I'd like to get more opinions on that if it is something concerning.
Thank you all for your insightful discussions! I hope I was able to touch on most everything!
Yeah, I think the benchmarks should really be the deciding factor here. Performance notwithstanding, I don't find the fact that insert returns memberAfterInsertthat problematic from an API standpoint: the method is marked @discardableResult anyway, and if it's not useful for BitSet then when someone does want to use the return value they will probably just do
(wasInserted, _) = bitSet.insert(someInt)
and the compiler can (hopefully) optimize away any work required for calculating memberAfterInsert (if the APIs here are intended to be inlinable?).
For update, if the objection is that it is just a potentially-less-performant version of insert, perhaps we could mark it as deprecated on BitSet to encourage any concrete uses of BitSet.update to use insert instead, while still allowing for its use in generic contexts?
Personally, I'm not as troubled as @xwu is by the tension here. The fact that the contents of these types is stored as a bitfield is a salient aspect of this type, and is why you would choose either of these types over an Array<Bool> or Set<Int>, respectively.
We could, I suppose, name these something like CompactBoolArray or BitfieldBoolArray (CompactIntSet, BitfieldIntSet) if we really wanted to avoid the bit/boolean confusion, but I'm not convinced it's necessary. It's not as though we're introducing some sort of independent Bit type with both numeric and boolean properties.
I would take a different view: if the simpler APIs make more sense for BitSet, or if benchmarks show that the protocol methods are less efficient, then that is a reason to include the simpler APIs on BitSet.
The protocol conformance stands on its own merits, irrespective of whether the nicer APIs also exist on the concrete type.
Having thought about this more, I’m not sure we want the backing storage to repeatedly expand and contract as we insert and remove values. That seems like a recipe for inefficient “thrashing” memory allocation patterns.
Perhaps it’s worth considering a “size” or “capacity” property for BitSet, so users can say, eg., “I want a set of exactly 1024 bits.” Then attempting to insert an excessively large value would fail, rather than silently allocating huge amounts of memory.
.
and I'd like to get more opinions on that if it is something concerning.