{"id":106321,"date":"2022-03-08T07:00:00","date_gmt":"2022-03-08T15:00:00","guid":{"rendered":"https:\/\/devblogs.microsoft.com\/oldnewthing\/?p=106321"},"modified":"2022-03-08T10:41:15","modified_gmt":"2022-03-08T18:41:15","slug":"20220308-00","status":"publish","type":"post","link":"https:\/\/devblogs.microsoft.com\/oldnewthing\/20220308-00\/?p=106321\/","title":{"rendered":"Optimizing code to darken a bitmap, part 2"},"content":{"rendered":"

Our investigation into a simple function to darken a bitmap left off with this function:<\/p>\n

struct Pixel\r\n{\r\n    uint8_t c[4]; \/\/ four channels: red, green, blue, alpha\r\n    uint32_t v;   \/\/ full pixel value as a 32-bit integer\r\n};\r\n\r\nvoid darken(Pixel* first, Pixel* last, int darkness)\r\n{\r\n  int lightness = 256 - darkness;\r\n  for (; first < last; ++first) {\r\n    first->c[0] = (uint8_t)(first->c[0] * lightness \/ 256);\r\n    first->c[1] = (uint8_t)(first->c[1] * lightness \/ 256);\r\n    first->c[2] = (uint8_t)(first->c[2] * lightness \/ 256);\r\n  }\r\n}\r\n<\/pre>\n
There’s a lot of multiplication going on here, and multiplication tends to be one of the more expensive CPU instructions. Maybe we can collapse them into a single multiplication operation by running the calculations in parallel.<\/p>\n
The idea here is to break the 32-bit integer into the respective channels, but spread them out so they act like independent lanes of a SIMD register. (This technique goes by the name  SWAR<\/a>, short for “SIMD within a register”.) Once they’ve been spread out into lanes, we perform a single multiplication, which acts like a parallel multiplication across all the lanes, thanks to the magic of the distributive law:<\/p>\n
(100\u00b2a<\/var> + 100b<\/var> + 100c<\/var>)d<\/var> = 100\u00b2a<\/var>d<\/var> + 100b<\/var>d<\/var> + c<\/var>d<\/var><\/p>\n
If c<\/var>d<\/var> < 100, then there will be no carry into the hundreds place, and similar, if b<\/var>d<\/var> < 100, then there will be no carry into the ten thousands place. Under such conditions, you can pluck out the individual products by extracting the corresponding pairs of digits from the final product.<\/p>\n
It so happens that my program uses only three darkness values: 8, 16, and 24, corresponding to lightness factors 248, 240, and 232, respectively. The application of the lightness factor can therefore be simplified to<\/p>\n
newPixel = oldPixel * (lightness \/ 8) \/ 32;\r\n<\/pre>\n
which can be rewritten as<\/p>\n
newPixel = oldPixel - ceil(oldPixel * (darkness \/ 8) \/ 32);\r\n<\/pre>\n
The truncation toward zero in the lightness calculation becomes a ceiling calculation when viewed as darkness.<\/p>\n
Reinterpreting it as a darkness calculation is helpful because the value of darkness \/ 8<\/code> is limited to the values 1, 2, and 3. The factor is at most two bits.<\/p>\n
Multiplying an 8-bit value with a 2-bit value produces a 10-bit result. And we can squeeze three 10-bit fields inside a 32-bit integer.<\/p>\n
A quick mental check confirms that rounding up any fractional portion won’t take us into 11 bits:<\/p>\n
255 \u00d7 3 < 256 \u00d7 3 = 256 \u00d7 4 \u2212 256 < 256 \u00d7 4 \u2212 32 = 10\u00b9\u00b9 \u2212 32.<\/p>\n
The idea therefore is that we take our three channel values and arrange them inside a 32-bit integer like this:<\/p>\n\n\n\n\n
3
\n1<\/td>\n		3
\n0<\/td>\n		2
\n9<\/td>\n		2
\n8<\/td>\n		2
\n7<\/td>\n		2
\n6<\/td>\n		2
\n5<\/td>\n		2
\n4<\/td>\n		2
\n3<\/td>\n		2
\n2<\/td>\n		2
\n1<\/td>\n		2
\n0<\/td>\n		1
\n9<\/td>\n		1
\n8<\/td>\n		1
\n7<\/td>\n		1
\n6<\/td>\n		1
\n5<\/td>\n		1
\n4<\/td>\n		1
\n3<\/td>\n		1
\n2<\/td>\n		1
\n1<\/td>\n		1
\n0<\/td>\n		\n9<\/td>\n\n8<\/td>\n\n7<\/td>\n\n6<\/td>\n\n5<\/td>\n\n4<\/td>\n\n3<\/td>\n\n2<\/td>\n\n1<\/td>\n\n0<\/td>\n<\/tr>\n
\u00a0<\/td>\nb<\/td>\ng<\/td>\nr<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n
In other words,<\/p>\n
    \n
  • value[ 0: 9] = r;<\/code><\/li>\n
  • value[10:19] = g;<\/code><\/li>\n
  • value[20:29] = b;<\/code><\/li>\n
  • value[30:31]<\/code> are unused<\/li>\n<\/ul>\n
    The lanes are 10 bits wide, so multiplying the entire integer by 1, 2, or 3 will not trigger any carries across lanes.<\/p>\n
    After the multiply, we reinterpret the integer as a fixed-point value, by applying an implied scale of 32 = 2\u2075. Rounding up the fixed-point value to the next integer is the same as rounding up the original integer to the next multiple of 32.<\/p>\n
    Once the multiplication and rounding is done, we extract the integer portion of the fixed-point fields (which means we take the top five bits of each field) and subtract them from our starting value.<\/p>\n
    constexpr unsigned pack_fields(uint8_t r, uint8_t g, uint8_t b)\r\n{\r\n  return r | (g << 10) | (b << 20);\r\n}\r\n\r\nvoid darken(Pixel* first, Pixel* last, int darkness)\r\n{\r\n  int factor = darkness \/ 8;\r\n  for (; first < last; ++first) {\r\n    uint32_t fields = pack_fields(\r\n        first->c[0], first->c[1], first->c[2]);\r\n    fields *= factor;\r\n    fields += pack_fields(31, 31, 31);\r\n    first->c[0] -= (fields >>  5) & 31;\r\n    first->c[1] -= (fields >> 15) & 31;\r\n    first->c[2] -= (fields >> 25) & 31;\r\n  }\r\n}\r\n<\/pre>\n
    Unfortunately, this benchmarks at 2.9\u00d7 slower<\/i> than the non-parallel version.<\/p>\n
    Okay, so maybe it’s the byte access that is killing us. Let’s load and store entire pixels at a time.<\/p>\n
    void darken(Pixel* first, Pixel* last, int darkness)\r\n{\r\n  int factor = darkness \/ 8;\r\n  for (; first < last; ++first) {\r\n    uint32_t v = first->v;\r\n    uint32_t fields = (v & 0xFF) |\r\n                     ((v & 0xFF00) << 2) |\r\n                     ((v & 0xFF0000) << 4);<\/span>\r\n    fields *= factor;\r\n    fields += pack_fields(31, 31, 31);\r\n    uint32_t diff = ((fields >> 5) & 0x1F) |\r\n                    ((fields >> 7) & 0x1F00) |\r\n                    ((fields >> 9) & 0x1F0000) |\r\n    first->v = v - diff;<\/span>\r\n  }\r\n}\r\n<\/pre>\n
    Still 2.1\u00d7 slower than the non-parallel version. A tiny improvement but still way behind.<\/p>\n
    Some micro-tweaking here won’t help much: We waste our time building up the difference fields, when we can just subtract each of the pieces as we calculate them.<\/p>\n
    void darken(Pixel* first, Pixel* last, int darkness)\r\n{\r\n  int factor = darkness \/ 8;\r\n  for (; first < last; ++first) {\r\n    uint32_t v = first->v;\r\n    uint32_t fields = (v & 0xFF) |\r\n                     ((v & 0xFF00) << 2) |\r\n                     ((v & 0xFF0000) << 4);\r\n    fields *= factor;\r\n    fields += pack_fields(31, 31, 31);\r\n    v -= (fields >> 5) & 0x1F;\r\n    v -= (fields >> 7) & 0x1F00;\r\n    v -= (fields >> 9) & 0x1F0000;\r\n    first->v = v;<\/span>\r\n  }\r\n}\r\n<\/pre>\n
    As expected, this doesn’t really help. Still 2.1\u00d7 slower than the non-parallel version.<\/p>\n
    Part of the problem might be that I’m running the benchmarks on an x86-64 system, and the x86-64 does not have dedicated bitfield manipulation instructions, unlike other processors like PowerPC, ARM, and AArch64.<\/p>\n
    Or maybe the problem is that I’m doing a multiply. Since I know that the darkness factor is going to be 1, 2, or 3, I can strength-reduce that to an addition. We’ll look at how to do that jumplessly next time.<\/p>\n","protected":false},"excerpt":{"rendered":"
    Exploiting parallel arithmetic.<\/p>\n","protected":false},"author":1069,"featured_media":111744,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[1],"tags":[25],"class_list":["post-106321","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-oldnewthing","tag-code"],"acf":[],"blog_post_summary":"
    Exploiting parallel arithmetic.<\/p>\n","_links":{"self":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/106321","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/users\/1069"}],"replies":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/comments?post=106321"}],"version-history":[{"count":0,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/106321\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/media\/111744"}],"wp:attachment":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/media?parent=106321"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/categories?post=106321"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/tags?post=106321"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}