Benchmark common::Frame::from_rgba_speed

[okaneco]

In #110, support was added to bypass the NeuQuant algorithm when the color count was <= 256 so that it could fit in a palette without quantization. The implementation is very straightforward and clear but there may be possible performance improvements. It'd be good to have a benchmark to test changes in this function since it's in the main path for encoding Frames.

The following are preliminary thoughts on the topic. They may not be faster than the current implementation.

At the cost of making the logic more complex, there may be a way to reduce allocation and hash calculations in palette creation. A HashSet is used, collected into a Vec, and then the Vec is built into a HashMap. The HashMap and palette indexing could be built from the start but manual bookkeeping would need to be introduced for indexing.

image-gif/src/common.rs

Lines 220 to 255 in 5410cb3

	// Attempt to build a palette of all colors. If we go over 256 colors,
	// switch to the NeuQuant algorithm.
	let mut colors: HashSet<(u8, u8, u8, u8)> = HashSet::new();
	for pixel in pixels.chunks_exact(4) {
	if colors.insert((pixel[0], pixel[1], pixel[2], pixel[3])) && colors.len() > 256 {
	// > 256 colours, let's use NeuQuant.
	let nq = color_quant::NeuQuant::new(speed, 256, pixels);
	return Frame {
	width,
	height,
	buffer: Cow::Owned(pixels.chunks_exact(4).map(|pix| nq.index_of(pix) as u8).collect()),
	palette: Some(nq.color_map_rgb()),
	transparent: transparent.map(|t| nq.index_of(&t) as u8),
	..Frame::default()
	};
	}
	}
	// Palette size <= 256 elements, we can build an exact palette.
	let mut colors_vec: Vec<(u8, u8, u8, u8)> = colors.into_iter().collect();
	colors_vec.sort();
	let palette = colors_vec.iter().map(|&(r, g, b, _a)| vec![r, g, b]).flatten().collect();
	let colors_lookup: HashMap<(u8, u8, u8, u8), u8> = colors_vec.into_iter().zip(0..=255).collect();
	let index_of = | pixel: &[u8] |
	*colors_lookup.get(&(pixel[0], pixel[1], pixel[2], pixel[3])).unwrap();
	return Frame {
	width,
	height,
	buffer: Cow::Owned(pixels.chunks_exact(4).map(|pix| index_of(pix)).collect()),
	palette: Some(palette),
	transparent: transparent.map(|t| index_of(&t)),
	..Frame::default()
	}

It's not clear if this sort is necessary. Maybe it can be made into a sort_unstable or removed altogether.

image-gif/src/common.rs

Lines 239 to 243 in 5410cb3

	// Palette size <= 256 elements, we can build an exact palette.
	let mut colors_vec: Vec<(u8, u8, u8, u8)> = colors.into_iter().collect();
	colors_vec.sort();
	let palette = colors_vec.iter().map(|&(r, g, b, _a)| vec![r, g, b]).flatten().collect();
	let colors_lookup: HashMap<(u8, u8, u8, u8), u8> = colors_vec.into_iter().zip(0..=255).collect();

Original discussion started in #111 (comment)

[foopub]

I've been working on a personal project using gif, and wanted to bench a different algo I implemented amongst other things, so I'm currently working on this. I can guarantee the quality of my code as I'm fairly new to rust, but I'll be happy to contribute if it's deemed up to par.

This is what I have so far for benching - it just uses PNGs in the samples directory for the input.
https://github.com/foopub/gif_caption/blob/master/benches/rgb_frame_bench.rs
I'll be adding more tests soon, and some better sample images.