Large references

[marcelm]

Here is my to-do list for making strobealign work with references with more than $2^{32}$ strobemers. This will resolve #277 and #285.

• [x] Counters (unique strobemers, total no. of strobemers etc.) need to be bumped from unsigned to uint64_t. This can be done unconditionally as it’s not a memory or performance issue when these are just always 64 bit.
• [x] Audit types: search for int and unsigned and check whether they need to be replace with bucket_index_t, size_t, uint64_t
• [x] Switch the bucket_index_t typedef to uint64_t
• [x] Test whether this modified versions works with large references.
• [ ] Extract the hash table part of StrobemerIndex into a separate class (let’s call it Hashtable here)
• [ ] Make bucket_index_t a template parameter of that class
• [ ] Decide at runtime whether to use a Hashtable<uint32_t> or Hashtable<uint64_t> (use a virtual function or a function pointer).

Much of the above is done already and the question for me is whether we perhaps want to release a strobealign version now that unconditionally uses 64 bit bucket start indices because I see that it is a bit of work to switch to dynamically deciding which size of indices to use.

For CHM13, the index vector currently needs 1 GiB ($2^{28}$ entries times 4 bytes per entry). That size would double with 64-bit indices, so 2 GiB. Overall memory usage would increase from 13 GiB to 14 GiB. But then, memory usage was 22 GiB before merging #278, so the savings are still huge.

[ksahlin]

I think its a great idea to unconditionally set it to use 64 bit bucket start indices for now and make a release so that https://github.com/ksahlin/strobealign/issues/277 and https://github.com/ksahlin/strobealign/issues/285 gets resolved. Let's do that!

As you say, going from 1gb to 2gb in human or 2gb to 4gb in rye) is negligible compared to flat vector memory.

[marcelm]

When we met yesterday, we decided to close this issue for now as we think it is quite some work to dynamically switch between 32 and 64 bit indices. Always using 64 bits is good enough. Also, we are considering some further memory reduction, which are no longer possible if the index vector only uses 32 bits.