[Feature request] Fallback storage beyond capacity

[benninkrs]

If I understand correctly, SmallVector and other collections implemented in this package have a fixed capacity, meaning it is impossible to store more than the number of items specified by the type parameter. As per this discussion on Julia discourse, a very desirable feature would be the ability to occasionally store more than this amount, while retaining stack allocation in the case that the number of items is within the specified capacity. There is even a sketch of a solution there.

Would it be very difficult to add this feature to the collection types defined here? I think we should try to avoid having another package that also implements small vectors.

[matthias314]

If I understand correctly, SmallVector and other collections implemented in this package have a fixed capacity

Yes, that's correct.

Would it be very difficult to add this feature to the collection types defined here?

I think that this is an interesting idea and possible to do. Instead of modifying existing types, I would define new ones. One would have to see how much the new feature affects performance, but it would be worth a try. That being said, I cannot promise that if I will find enough time in the near future to do this. I'm currently finishing up the addition of MutableSmallVector as well as FixedVector, SmallDict and SmallSet and their mutable counterparts.

[benninkrs]

I made a bare-bones package ShortVectors.jl that does this. It's quite simple: it is a wrapper around a Union of a standard vector and short fixed-capacity vector, and chooses one or the other at construction time based on the length of the input. I rolled my own fixed-capacity vector for this, but it is conceptually the same as your SmallVector and favba's ImmutableVector. In principle one could use either one of those as the backing type.

I've only done limited benchmarking, but so far it seems to work about as I expect. (I did run into a couple of performance gotchas that I don't fully understand, but had reasonable workarounds.)

In principle there could also be a mutable version, but it is less clear to me how to do that and whether there would be much performance gains (since I think Julia requires mutable objects to be on the heap).

[matthias314]

I believe that so far you have implemented getindex, but not other operations like addition or scalar multiplication. That's not much to get an idea of the performance of such an approach. I would also think that a mutable variant might be more interesting than an immutable one. One may start with some sort of small vector that is later extended via push! operations.

[benninkrs]

I believe that so far you have implemented getindex, but not other operations like addition or scalar multiplication. That's not much to get an idea of the performance of such an approach.

That's correct. As I said, it is bare bones. And for my immediate use case it is sufficient. Basically, I just want variable length tuples that I can store locally in homogeneous arrays and quickly iterate through. But I agree it is not super easy to benchmark that kind of workload.