Repository navigation
Should we accelerate min/max/median filter with clever autovectorizing kernels? #10044
Description
I don't see any directly related questions. I have some ideas about how to implement the rank filters faster. There's a lot of repeated work currently b/c of the use of quick select on a sliding window. There's three ideas I have:
- For very small windows, 3x3, maybe 5x5, rewrite the min/max/median finding code to avoid data dependencies so that the compiler autovectorizes to SIMD instructions that can establish min/max/median of several separate windows at once.
- For larger windows, there might be a win to maintaining a sorted buffer and removing/inserting the boundaries as we slide the window. I'm a little less certain of this, but it seems a shame to do a fresh quick select when only O(N) values changed out of an O(N^2) block of values.
- Maybe cache-friendly tiling? Haven't thought about this as much.
My main reservation is that I'm benchmark hacking here. Are you generally open to changes like this? Can you give me a sense of your tolerance for complex code relative to throughput? Maybe just a few PRs you accepted/rejected is enough.
For example, I think the 3x3 and 5x5 windows will need to have specialized kernels that are compiled and then dispatched to at runtime. That's probably a fair bit of (rote) code.
Thanks again for holding up the foundations of Python image processing!
Best,
Dan
Activity
[-]should we accelerate min/max/median filter with clever autovectorizing kernels?[/-][+]Should we accelerate min/max/median filter with clever autovectorizing kernels?[/+]radarhere commentedon Sep 24, 2026
I personally value code simplicity more highly than minor performance gains - but there have been a number of performance PRs that have gone in lately, so I'm probably the wrong person to ask. There's also an unusually high level of activity lately, so no guarantees about when a PR will be fully reviewed.
For a PR that was approved, #10044 might most closely match what you're describing. For one that was closed, see #9976.
You mentioned SIMD, so you should also be aware of https://github.com/uploadcare/pillow-simd and #8209
akx commentedon Sep 24, 2026
As noted in #10045 (comment), I experimented with slapping the http://ndevilla.free.fr/median/median/src/optmed.c sort networks into place, and they're very fast (no quickselect at all). The patch is of course some 100 lines of cryptic-looking sort statements, but it could be explained as "trust me, this works"...
EDIT: TBH,
min/maxshouldn't even use quickselect 😄 By the looks of it, RankFilter is essentially the same as when it was originally implemented in 2003. I prototyped special-casing min/max so they just do, well, a naive min/max over the window, and they're already literally 100x faster thanmain...EDIT 2: The min/max special case was simple enough: 4455785
danking commentedon Sep 24, 2026
Thank you both for your replies! I'll read through the pillow-simd project and #8209!
Ah yes @akx, this is essentially what I had in mind! I think there's some small integer wins still available in the blurs and resizes too, but yeah the median filter was the big one.
To be clear, I don't want to check any SIMD instructions into Pillow! I think, as the optmed.c circuits demonstrate, there's pretty big wins from just restructuring code so the compiler can see the vectorization opportunities.
thanks again both!