Upstreaming a delta-debugging-based shrinking algorithm

[matheus23]

Hello proptest maintainers :wave:

The shrinking algorithm in the bool_vec, vec and related functions removes elements one-by-one when shrinking. This can be improved by removing a batch of values at a time. There's an existing description of such an algorithm in the academic literature, it's called the "delta debugging" algorithm. Here's the paper describing it.

I've implemented a ValueTree for a bitmap-based reduction somewhere downstream: https://github.com/adaszko/roaring-graphs/blob/master/src/delta_debugging_bitmap.rs

Would you be interested in me contributing this algorithm upstream? Or would you prefer that to be a crate of its own? Or would you like something similar to it, but adapted? E.g. not depending on RoaringBitmap, or something that's Vec based and allows for shrinking the elements within the vec as well?

[matthew-russo]

Thanks for reaching out. I'm going to read the paper to get a better understanding of what Delta Debugging is. Re: implementation strategy, my first reaction is we'd probably want to keep the same data structures rather than introducing new ones but I'm not familiar with Roaring Bitmaps so I'll do a bit of reading and get back to this

[matthiasgoergens]

If memory serves right: I think Python Hypothesis does something similar already, and it works well there.

[tzemanovic]

hello @matheus23, this is very cool! Imho a RoaringBitmap support could be a nice addition, though it would probably be better behind a feature flag that's not enabled by default to avoid pulling in extra deps for people who don't use it. As for the "delta" debugging algo, I think it could be an improvement over the current Vec strategy as it's a binary search, so it would be more efficient than the current approach of trying to delete elements one by one and hence improve shrinking

[matheus23]

The simplest first thing we can implement using my code is a better strategy for anything that implements BitSetLike. The next step would be using that shrinking algorithm within the VecValueTree on its included_elements bitset. However, this adaptation may be a bit more involved, since my original code only does bit-set shrinking, not shrinking of elements themselves, too.

I'm happy to help out here on some weekend in the future. However, I may not get to that for a while, so that shouldn't stop anyone else from trying! Happy to help out when there's questions anytime though.