I would do if amount >= length / 20 so that there is no risk of overflow (a possibilitiy on 32 bit systems... maybe).

On that note, one might think there is a tradeoff here between speed and memory usage. Let's actually look at it a bit.

The memory usage of inplace is sizeof<usize>() * length

The memory usage of cache is a bit more complicated. It is:

(sizeof<usize>() * amount)  # Vec return value
    # HashTable usage:
    # - size of the stored "hash" value
    # - size of the stored key/value pair
    + (sizeof<usize>() + sizeof<usize>() * 2) * amount 

Which is obviously just

sizeof<usize>() * 4 * amount

This is not accounting for how much the capacitiy's length is less than the allocated space.

So from a memory usage perspective you might want to do

if amount * 4 >= length 

But there is always a tradeoff. Basically at amount >= length / 20 you will be using around 5x more memory than the cache implementation would. If that is acceptible (which I honestly think it is) then go for it!

So long as that much memory is available, I think it should be used. Unfortunately knowing how much is available is another problem, so the crude approximation of amount >= length / N seems reasonable IMO, for some N between 4 and 20 it seems. Probably optimising for execution time is more important.

Another thing that occurs to me is that (a) the length is specified as a usize due to common use (container indices), but this gives the function different capabilities on 32- and 64-bit platforms; at the same time (b) using smaller integer sizes should help significantly and (c) if length >= 2.pow(32) then the user is dealing with very big numbers (unusual) and the inplace version of the function is almost certainly not applicable. So do you think sample_indices should accept u64 arguments, test whether they are within u32 range, and sample_indices_inplace should always use u32 numbers? Potentially it could even be worth having a version of sample_indices_inplace using smaller ints (u16), but probably not worth it. Not sure whether sample_indices_cache should use usize or u64 in this case, or possibly both u32 and u64 impls.

If you see any utility in my suggestions above, might be better if you make a separate PR and I remove the changes to seq from this one.

I actually considered doing something like you suggest: splitting the method up by the maximum size to conserve on memory/overhead, but left that as a future improvement. The problem is that sample_indicies would then have to copy that data over to a new Vec<usize> which is an annoying cost.

Ideally sample_indices would be fully generic and would just use sizeof<T> to make the correct choices. sample_slice could then call the correct one based on amount or length.

However, I was not sure how to make something generic over any integers, it looks like I might have to use the num crate?

I think this PR stands on it's own and making things generic isn't going to change this cutoff -- I would make the cache version generic too and the hashmap should reap (roughtly) the same benefits.

I don't think thinking TOO hard about absurdly large numbers of indicies is too useful at this stage... if someone's usecase is sampling 1/20th of their total memory (as indicies!) then they should probably consider rolling their own code (specifically they might want to consider a more memory-packed hashmap implementation, etc).

I'm not familiar with test --benches -- does this automatically build in release?

or does it just "run the benches once", i.e. treat them as tests.

Yes, that's it. I don't see any value in running the actual benchmarks on CI hardware. No idea whether it builds in debug/release/hybrid mode and don't really care.

Agreed. I didn't know about that flag, it's pretty cool! 😄