{"action":"created","issue":{"url":"https://api.github.com/repos/jcupitt/libvips/issues/392","repository_url":"https://api.github.com/repos/jcupitt/libvips","labels_url":"https://api.github.com/repos/jcupitt/libvips/issues/392/labels{/name}","comments_url":"https://api.github.com/repos/jcupitt/libvips/issues/392/comments","events_url":"https://api.github.com/repos/jcupitt/libvips/issues/392/events","html_url":"https://github.com/jcupitt/libvips/pull/392","id":135847815,"number":392,"title":"vips_hist_find: ~30% performance improvement for 1-4 band uchar","user":{"login":"lovell","id":210965,"avatar_url":"https://avatars.githubusercontent.com/u/210965?v=3","gravatar_id":"","url":"https://api.github.com/users/lovell","html_url":"https://github.com/lovell","followers_url":"https://api.github.com/users/lovell/followers","following_url":"https://api.github.com/users/lovell/following{/other_user}","gists_url":"https://api.github.com/users/lovell/gists{/gist_id}","starred_url":"https://api.github.com/users/lovell/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/lovell/subscriptions","organizations_url":"https://api.github.com/users/lovell/orgs","repos_url":"https://api.github.com/users/lovell/repos","events_url":"https://api.github.com/users/lovell/events{/privacy}","received_events_url":"https://api.github.com/users/lovell/received_events","type":"User","site_admin":false},"labels":[],"state":"closed","locked":false,"assignee":null,"milestone":null,"comments":2,"created_at":"2016-02-23T19:58:15Z","updated_at":"2016-02-28T12:10:08Z","closed_at":"2016-02-28T11:29:14Z","pull_request":{"url":"https://api.github.com/repos/jcupitt/libvips/pulls/392","html_url":"https://github.com/jcupitt/libvips/pull/392","diff_url":"https://github.com/jcupitt/libvips/pull/392.diff","patch_url":"https://github.com/jcupitt/libvips/pull/392.patch"},"body":"Hi John, \r\n\r\nI hope to use `vips_hist_entropy` for a couple of shiny new features in sharp so took the liberty of perusing libvips' histogram code.\r\n\r\nAs the original comment in `vips_hist_find_uchar_scan` rightly suggested, the inner loop of the histogram builder can't be auto-vectorized by the compiler.\r\n\r\nHowever, by manually unrolling this loop for the common cases of 1-4 band uchar images, I see a 3x reduction in instruction count and a 5x reduction in branch count for the `vips_hist_find_uchar_scan` function, resulting in an overall improvement for `vips_hist_find` of around 30%.\r\n\r\nAs always, feedback on a more elegant way to achieve this or correction of duff maths is welcome :)\r\n\r\nBelow are some timings and callgrind stats for a 10000x10000 3 band uncompressed VIPS image.\r\n\r\nBefore:\r\n\r\n```sh\r\n$ time vips hist_find 10000x10000.v hist.v\r\n\r\nreal    0m0.166s\r\nuser    0m0.469s\r\nsys     0m0.102s\r\n\r\n$ valgrind --tool=callgrind --branch-sim=yes vips hist_find 10000x10000.v hist.v\r\n\r\n--------------------------------------------------------------------------------\r\n           Ir          Bc    Bcm      Bi     Bim  file:function\r\n--------------------------------------------------------------------------------\r\n2,900,140,000 500,010,000 10,047       .       .  ???:vips_hist_find_uchar_scan [/usr/local/lib/libvips.so.42.4.0]\r\n   35,812,971   2,910,201 44,650 786,433       1  ???:vips_col_scRGB2sRGB_8 [/usr/local/lib/libvips.so.42.4.0]\r\n```\r\n\r\nAfter:\r\n\r\n```sh\r\n$ time vips hist_find 10000x10000.v hist.v\r\n\r\nreal    0m0.119s\r\nuser    0m0.312s\r\nsys     0m0.070s\r\n\r\n$ valgrind --tool=callgrind --branch-sim=yes vips hist_find 10000x10000.v hist.v\r\n\r\n--------------------------------------------------------------------------------\r\n         Ir          Bc    Bcm      Bi     Bim  file:function\r\n--------------------------------------------------------------------------------\r\n900,240,000 100,040,000 10,026       .       .  ???:vips_hist_find_uchar_scan [/usr/local/lib/libvips.so.42.4.0]\r\n 35,812,971   2,910,201 44,643 786,433       1  ???:vips_col_scRGB2sRGB_8 [/usr/local/lib/libvips.so.42.4.0]\r\n```\r\n"},"comment":{"url":"https://api.github.com/repos/jcupitt/libvips/issues/comments/189853996","html_url":"https://github.com/jcupitt/libvips/pull/392#issuecomment-189853996","issue_url":"https://api.github.com/repos/jcupitt/libvips/issues/392","id":189853996,"user":{"login":"jcupitt","id":580843,"avatar_url":"https://avatars.githubusercontent.com/u/580843?v=3","gravatar_id":"","url":"https://api.github.com/users/jcupitt","html_url":"https://github.com/jcupitt","followers_url":"https://api.github.com/users/jcupitt/followers","following_url":"https://api.github.com/users/jcupitt/following{/other_user}","gists_url":"https://api.github.com/users/jcupitt/gists{/gist_id}","starred_url":"https://api.github.com/users/jcupitt/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/jcupitt/subscriptions","organizations_url":"https://api.github.com/users/jcupitt/orgs","repos_url":"https://api.github.com/users/jcupitt/repos","events_url":"https://api.github.com/users/jcupitt/events{/privacy}","received_events_url":"https://api.github.com/users/jcupitt/received_events","type":"User","site_admin":false},"created_at":"2016-02-28T12:10:08Z","updated_at":"2016-02-28T12:10:08Z","body":"I made it slightly faster again:\r\n\r\nhttps://github.com/jcupitt/libvips/commit/e582f13d13e67522f7b00d2a9d536687356a46f3\r\n\r\n`p[constant]` is faster than `p[variable]`, so you can get a speedup by incrementing the input pointer outside the inner loop."}}