how do I decrease stack usage of memchr::memmem::Finder?

[BurntSushi]

The Finder struct uses a couple hundred bytes of stack on x86-64. How can I decrease this?

Original context for this question comes from #160 (comment)

[BurntSushi]

so I have an issue that ties into this one, and solving this issue can help solve that. The SearcherKind enum is a bit too fat, especially on an avx2 supported cpu, it has two copies of the sse2 Finder along with an avx2 Finder, making the whole thing 288 bytes on x86_64, and I would benefit from having that go down to reduce memory usage.

It's not really SearcherKind itself. It's the stuff inside of it. SearcherKind is a union, and its biggest member is TwoWayWithPrefilter. And that in turn contains a PrefilterKind, which is another union, very similar to SearcherKind. And its biggest member is memchr::arch::x86_64::avx2::packedpair::Finder, at 160 bytes on my x86-64 machine. And that Finder has both an SSE2 and an AVX2 finder embedded within it. The SSE2 finder is 48 bytes and the AVX2 finder is 96 bytes. Each finder is a pair of vectors (so on AVX2, that's 64 bytes), a minimum haystack length (another 8 bytes on x86-64) and 2 bytes of metadata related to the search algorithm.

So, using memchr::arch::x86_64::avx2::packedpair::Finder directly looks like it would cut your stack usage in about a half. That still does have both an AVX2 and an SSE2 finder internally (as mentioned above), and there's no way to get an AVX2-without-SSE2 searcher. The crate doesn't expose that level of API composition and probably won't. The API is pretty sprawling as it is. (I'm also not sure if you're aware of the lower-level memchr::arch::x86_64::avx2::packedpair::Finder API, since you didn't mention what you've tried to get stack usage down.)

Now, you could instead just use memchr::arch::x86_64::sse2::packedpair::Finder. That would be SSE2-only without AVX2 optimizations. So this would technically run a slower search. But SSE2 is still quite fast, much faster than scalar code. And if stack usage is critical to you, using this directly would, I think it would get you less than a quarter of what you have now.

Of course, the easiest way to reduce stack usage is to box it. That's ultimately what I had in mind: for callers that care a lot about stack usage, they can just box the finder. This means using more heap of course, but it might be a beneficial trade-off depending.

The reason why memchr works this is in part because it needs to work in a core-only context, so memchr itself can't really use a box internally to decrease stack usage. It could do it when alloc is available and leave things unboxed when alloc isn't available, but the problem there is that it would mean a heap alloc for most searches that don't amortize Finder construction, which is kind of a bummer.

Finally, the last resort for folks that need to prioritize stack size above all else is to use memchr::arch::all::twoway::Finder directly. This won't give you accelerated searches, but a twoway::Finder is only 32 bytes big on x86-64. (I believe I could get that down to 24 bytes if I were pushed to do it.)

I overall think that memchr exposes a lot of options for controlling stack usage, but they all come with their own trade offs. There is potentially one point in the space that isn't supported, that is, an AVX2 accelerated searcher without an SSE2 fallback, but I don't think that's worth exposing given that SSE2 is quite fast all on its own. Otherwise, there are lots of different things to choose from and it really depends on what problem you're trying to solve.

[BurntSushi]

It's very hard to say what the cutover point is. My loose feeling is that vectorization will help in the 30-50 bytes range when compared to just plain twoway::Finder. But not nearly as much as it would help if you were searching kilobytes. At that haystack length, it's worth benchmarking. The other thing that plays a factor here is searcher construction. Building a twoway::Finder is probably more expensive than building one of the SIMD finders. That might matter if you can't amortize searcher construction (i.e., you only run one search for each needle).

[ambyjkl]

might be worth benchmarking rabin-karp as well then, it might outperform for one-time needles when both the needle and haystack are small

[BurntSushi]

Indeed it could. memchr uses Rabin-Karp in cases like that in its higher level searcher. The cutoffs I used were motivated by benchmarks. So you could look at the cutoffs I used in this crate for guidance. (And now you start to see the shape of the problem. You want multiple algorithms to handle different cases, and then you need to build up the infrastructure for very quickly determining which algorithm to use.)

[ambyjkl]

I was able to reduce memory usage by over 40% thanks to your advice :). It turns out, for my input, I only enter the "When haystack.len() is less than Finder::min_haystack_len" case less than 1% of the time, so I'm resorting to creating a rabinkarp finder as needed rather than caching it.

[BurntSushi]

Nice! Yeah, there's a TON you can do better when you're restricted to specific use cases. Data dependent optimizations like yours are my favorite to do. :-)