high peak memory consumption of WaveletMatrix::from_ints

[KonradHoeffner]

Building a 205 MB wavelet matrix using WaveletMatrix::from_ints temporarily consumes 3.9 GB memory, which may be too much for small VMs.
Is there a way to reduce memory consumption while constructing a wavelet matrix?

[kampersanda]

@KonradHoeffner

In v0.5.0, there is no approach to reduce the memory consumption. The large memory is due to that WaveletMatrixBuilder always maintains input values in Vec<usize>. Using sucds::CompactVector instead of Vec<usize> can achieve memory reduction when the input alphabet size is small.

The large memory consumption is inconvenient, so we'll improve the implementation in v0.5.1. Thank you for the report!

[kampersanda]

@hirosassa I'd like to do this. No problem? Or, have you already started coding?

[hirosassa]

@kampersanda Not yet. Please go ahead!

[kampersanda]

@KonradHoeffner #45 added an option to specify the minimum number of bits to store an input integer in wavelet matrix construction. From v0.6.0, you will be able to reduce memory consumption through WaveletMatrixBuilder::with_width() (see the example usage). For example, this experiment shows memory reduction to 25%.

[KonradHoeffner]

Wow, thanks for the quick implementation!
I am trying it out right now, but I noticed that WaveletMatrixBuilder::push panics if the value doesn't fit instead of producing a Result, is that intended for purposes of faster execution?

[KonradHoeffner]

Tested it, works perfectly, thanks!

[kampersanda]

@KonradHoeffner

I am trying it out right now, but I noticed that WaveletMatrixBuilder::push panics if the value doesn't fit instead of producing a Result, is that intended for purposes of faster execution?

Oops! As one of the primitive operations such as vec[i], I naturally defined it as Panicable; however it should return Result. I'll modified the API. Thank you for the meaningful question!