Closed ksmoore17 closed 3 years ago
Thanks. Overflow triggers panic in debug
builds but wraps around in release
builds. Because of how computationally heavy this algorithm is, I always ran it in release
mode so I never triggered those panics. On similar projects in the future, I'll probably enable overflow-checks on my dev profile builds with a higher optimization level.
https://doc.rust-lang.org/cargo/reference/profiles.html#overflow-checks
https://doc.rust-lang.org/cargo/reference/profiles.html#default-profiles
With #5 merged, that shouldn't be a problem anymore. Be sure to use the release build of your Rust project with whatever you're wrapping the Python in to ensure you get the best performance. If you come across anything else, feel free to open more issues.
In the process of writing this, I realized that matrix indexing should use checked arithmetic instead of wrapping, which was more of an implementation detail/quirk inherited from the original. Changing to checked_mul/add
alters the results slightly and seems to show a bit more contrast while needing less repeats/iterations. Logically, it makes sense to me that the magnitudes in the matrices were being invalidly modified by retrieving data from the overflowing indices they were being fed. I've made this change in #6 and I'm in the process of removing more unwrap
assumptions.
Something else kinda tangential to this issue: I think it would be good to swap the Matrix for the ndarray crate as it provides a more stable and well documented implementation of the same thing. ndarray also makes it really easy to do parallel with rayon if the algorithm could benefit from that anywhere. Would you be interested in a PR for that if I can get it working?
I agree with the suggestion and I'm open to a PR for it, but I'm not sure how much effort it'd be or if it'd be worth it. Normally I wouldn't roll my own but the implementation was "simple" enough (but not without potential bugs). I'm not too familiar with ndarray and it's changed a lot since I looked at it last, it didn't have rayon support before among other things.
The quantization algorithm doesn't do a lot of direct matrix operations which matrix libraries are usually optimized for. The for loops are mainly iterating over indices and retrieving from the Matrix2d
or Matrix3d
with the computed index. I think multi-threading could help some parts like the quant::utility
functions but we'd have to make sure we're not adding more overhead or multi-threading results that depend on a sequential order. I've opened an issue to discuss this more in #8. It's very likely there are places where chunking or par_iter would be beneficial but if you look closer at parts of the code you'll see the control flow is a little gnarly.
Very good to know, thanks for the insight on release builds.
I thought about whether the undefined behavior should just be prevented, but figured maybe the negative indexing was actually how its supposed to work. If the results are better, that's a no brainer.
I'm now having a problem with how numpy ravels and how this library unravels. It's been driving me crazy, and at this point I think that reimplementing in ndarray might solve my problem quicker. Might let me a look at #1 as well.
I think this issue has run its course. With #6 merged, I'm going to close it. Feel free to open a new issue if you have any or discuss in the other relevant issues. Thanks again for reporting this.
Hi,
This package is awesome, thanks for porting it. I'm trying to wrap it in python and getting an overflow panic when using it as a lib despite no problems using the cli.
I've used the flow described in lib.rs and compared to main.rs and it seems like I'm passing the correct objects to the
spatial_color_quantization
function, but there is an overflow error caused by theutility::b_value
andmatrix::get
functions. I can't tell exactly at which place inspatial_color_quantization
this is being triggered.The problem is that
b_value
calculates indices to use in a get call to a matrix, and the indices that it calculates can sometimes be negative.https://github.com/okaneco/rscolorq/blob/8cce9488289cb81645e3f3f2a813066285d6027e/src/quant/utility.rs#L85-L94
They are converted to
usize
to index the array and if negative they wraparound. The overflow occurs when this indexi
at the max value is added to the calculation for the index in the flattened row.https://github.com/okaneco/rscolorq/blob/8cce9488289cb81645e3f3f2a813066285d6027e/src/matrix.rs#L48-L50
I've added some print statements to watch this and it seems like in the cli program, the wraparound occurs but the panic and overflow doesn't seem to. I don't know why my use of the library doesn't work.
The fix to it that I found was changing the get functions on the
Matrix
https://github.com/pierogis/rscolorq/blob/e833cb7cdb6a509361308c6b0577644a4302dbee/src/matrix.rs#L47-L55
The
wrapping
methods on the usize objects work with the overflow and the output images are the same.Something else kinda tangential to this issue: I think it would be good to swap the
Matrix
for thendarray
crate as it provides a more stable and well documented implementation of the same thing.ndarray
also makes it really easy to do parallel withrayon
if the algorithm could benefit from that anywhere. Would you be interested in a PR for that if I can get it working?