3 ms·
Nice writeup overall. Tiny nitpick however - in your Rust generation of the diff image, you go by column instead of by row, making it quite a lot slower than it
by vorachose 7y ago
Nice writeup overall. Tiny nitpick however - in your Rust generation of the diff image, you go by column instead of by row, making it quite a lot slower than it should be (probably because of cache locality, I ain't no expert).
Switching from
for x in 0..w {
for y in 0..h {
let mut rgba = [0; 4];
[...]
to
let mut rgba = [0; 4];
for y in 0..h {
for x in 0..w {
[...]
cuts down runtime by between 35 and 50% on my side.
EDIT : moving the call to get_pixel outside the inner loop take off another ~10%, bringing it to sub 0.145 from ~0.290.
let mut rgba = [0; 4];
for y in 0..h {
for x in 0..w {
let pix1 = image1.get_pixel(x, y);
let pix2 = image2.get_pixel(x, y);
for c in 0..4 {
rgba[c] = abs_diff(
pix1.data[c],
pix2.data[c],
);
}
let new_pix = image::Pixel::from_slice(&rgba);
diff.put_pixel(x, y, *new_pix);
}
}
- diroussel 7y agoThe optimal cache usage would be to not use staright nested for loops, but to segment the whole image recursively. So take the whole imahe, then take each quarter, then proceeds each quarter again. At least that is my understanding of how to implement a cache oblivious algorithm. See https://en.wikipedia.org/wiki/Cache-oblivious_algorithm https://en.wikipedia.org/wiki/Cache-oblivious_algorithm Used that approach once when computing a large cross product and it gave a good speed up.