Memory leak

[bowenwang1996]

In get_data_decode_matrix the inverted matrix will always be added to the trie but nothing seems to every gets removed from the trie, so this can potentially consume a lot of memory. Is it expected that an instance of ReedSolomon<F> wouldn't be used too many times?

[darrenldl]

It is expected there would not be a lot of inverted matrices required for a run of the application, which may not be a valid assumption, especially after the upgrade to GF16 where the number of possible matrices may be much larger than GF8.

At the time of writing the library, most of the efforts was dedicated to making sure the code was sound, and thus this memory leak was overlooked (and also it only supported GF8 at the time).

[darrenldl]

Adding a cache eviction procedure would be ideal (obviously), but I think I'm overwhelmed by things at the moment to warrant me implementing it.

[darrenldl]

I roughly outline the changes that need to be made as follows to help the fix get started

• Either define the upper bound as a constant, or as a parameter in the ReedSolomon<F> instantiation function, and passed to the tree creation procedure
• InversionTree type in src/inversion_tree.rs needs to have at least one more field for cache eviction metadata (number of fields depends on which cache eviction algorithm we want to use)
• We need an eviction procedure to clear one spot if the tree is full, and this is to be called within insert_inverted_matrix, after the square matrix check
• The quickcheck test qc_tree_same_as_hash_map_prop in src/inversion_tree.rs will need to keep the upper bound of matrices in mind

[darrenldl]

Lastly, I definitely could have documented this memory leak, which I know from the start, better and lodged it as a backlog issue to tackle later on or for others to tackle.

At the time of porting from Klaus Post's Go implementation to Rust's, I was mostly focusing on correctness (via heavy testing) and matching the feature parity of Klaus's. Flaws carried over from Klaus's were overlooked if they didn't (directly) lead to incorrect results, such as this bug.

Sorry for the inconvenience to whomever is affected, and thanks for reporting @bowenwang1996 !

[bowenwang1996]

@darrenldl Thanks for the quick response. We have found a workaround so it is not super urgent.

[darrenldl]

@bowenwang1996 Just to get some sanity checks before I attempt to do anything: is there a cache eviction policy in mind that you think would enable best performance in, say, your company's use case?

I was thinking of just doing a simple LRU, but reckon I should check with others before too late just in case that's a terrible idea.

[bowenwang1996]

I don't have anything specific in mind. I think LRU works.

[burdges]

I suppose ReedSolomon::new gets somewhat heavy too, so maybe worth mentioning https://github.com/dermesser/memoize somewhere in the docs.

[Miezhiko]

@bowenwang1996 hello, may you please check if #83 is helping?