ChromeOS color extraction - only look at a maximum of 10k pixels in the

ui/gfx/color_analysis.cc

Index: ui/gfx/color_analysis.cc
diff --git a/ui/gfx/color_analysis.cc b/ui/gfx/color_analysis.cc
index 301b6b9fae1ab78f1154fd78ef81d5b0834f7c2d..d3e8998266dc654e5162ba1d4cef7031861becfa 100644
--- a/ui/gfx/color_analysis.cc
+++ b/ui/gfx/color_analysis.cc
@@ -368,15 +368,16 @@ SkColor CalculateProminentColor(const SkBitmap& bitmap,
   const uint32_t* pixels = static_cast<uint32_t*>(bitmap.getPixels());
   const int pixel_count = bitmap.width() * bitmap.height();
 
-  // We don't know exactly how many distinct colors there will be, so just
-  // reserve enough space to keep the maximum number of table resizes low.
-  // In our testing set, 2/3 of wallpapers have <200k unique colors and 1/4
-  // have <100k. Thus 200k is picked as a number that usually amounts to zero
-  // resizes but usually doesn't waste a lot of space.
-  std::unordered_map<SkColor, int> color_counts(200000);
+  // For better performance, only consider at most 10k pixels (evenly
+  // distributed throughout the image). This has a very minor impact on the
+  // outcome but improves runtime substantially for large images. 10,007 is a
+  // prime number to reduce the chance of picking an unrepresentative sample.

[James Cook, 2017/04/07 14:05:47]

Good idea.

[Nico, 2017/04/07 15:33:22]

I'm too dense to understand why the divisor being a prime number helps here. Can
you expand on this? My take would've been that if you walk the image with a
fixed stride, you can always end up with an unrepresentative sample (put red
pixels on the pixels you hit, make all other pixels white, and your thing will
always pick red even if the image is mostly white). This might be good enough in
practice, but I don't see how the prime helps.

(If you want to not have this kind of error, you could pick 10000 numbers
between 0 and pixel_count at random, then sort them so you don't thrash the
cache when you walk them, and collect those randomly-chosen pixels.)

+  constexpr int kMaxConsideredPixels = 10007;
+  const int pixel_increment = std::max(1, pixel_count / kMaxConsideredPixels);
+  std::unordered_map<SkColor, int> color_counts(kMaxConsideredPixels);
 
   // First extract all colors into counts.
-  for (int i = 0; i < pixel_count; ++i) {
+  for (int i = 0; i < pixel_count; i += pixel_increment) {
     // SkBitmap uses pre-multiplied alpha but the prominent color algorithm
     // needs non-pre-multiplied alpha.
     const SkColor pixel = SkUnPreMultiply::PMColorToColor(pixels[i]);