Bench `math::nq`

[TianyiShi2001]

The complex but stable (API unlikely to change) algorithms in math::nq seems to be good subjects of benchmarking. Benchmarks will help those who want to improve their performance.

[TianyiShi2001]

In my experience, for example, the compiler isn't always smart enough to elide the bound checks for indexing where all indexing operations are garanteed to be in-bound within a function, and using unsafe {x.get_unchecked()} can be used to improve performance, if you can tolerate unsafes in your code in exchange for perf improvement.

[fintelia]

Do we know if anyone is actually using math::nq?

[197g]

Trading performance for some well-reviewed unsafe can be okay, imageproc needs to do it as well. It is, however, not the preferred resolution. In my experience, a large part of the work is finding the cause of a particular slowdown. Here, temporarily removing some bounds checks by-hand using unsafe is a useful tool for finding missed optimization. In many cases there are alternatives. The llvm optimizer is quite powerful when given the right inputs.

For example, bounds checks on slices can often be removed by using iteration instead. Or by doing a check once at the start of a local scope then relying on llvm deducing that all indices are smaller than the initial check. When in doubt, the secure code working group or #black-magic in the community Discord can also answer some questions and propose alternative.

[197g]

We can't say that it is not used at all.

That said, the code was at some point extracted as a separate crate: color_quant.

[197g]

Which was transferred to image-rs not too long ago, by the way:
https://github.com/image-rs/color_quant

[TianyiShi2001]

Which was transferred to image-rs not too long ago, by the way:
https://github.com/image-rs/color_quant

Then, how about unifying the implementations in math::nq module with the corresponding implementations in the color_quant crate, and any benchmarks and further developments on this algorithm will happen in the color_quant crate.

[197g]

That seems useful, yeah. There probably needs to be one pass ensuring that the implementation hasn't diverged but I see you're already busy merging them 🙂

[fintelia]

My inclination would be to deprecate the math::nq module and just point people to the color_quant crate.