{"id":1482,"date":"2013-02-11T12:36:14","date_gmt":"2013-02-11T10:36:14","guid":{"rendered":"http:\/\/mariusbancila.ro\/blog\/?p=1482"},"modified":"2013-02-11T12:36:14","modified_gmt":"2013-02-11T10:36:14","slug":"beware-of-parallelization","status":"publish","type":"post","link":"https:\/\/mariusbancila.ro\/blog\/2013\/02\/11\/beware-of-parallelization\/","title":{"rendered":"Beware of parallelization"},"content":{"rendered":"<p>A recent question on stackoverflow raised the problem of a fast algorithm to count the unique colors in an image (<a href=\"http:\/\/stackoverflow.com\/questions\/14769841\/faster-algorithm-to-check-the-colors-in-a-image\/\">Faster algorithm to check the colors in a image<\/a>). My answer what that this kind of problems are suited for parallelization. However, parallelization may only help when used judiciously. <\/p>\n<p>To demonstrate the point I have written a pretty simple implementation in VC++ (with C++11), that uses a std::set to store the unique colors. The size of the set is the number of the colors. The implementation simply iterates over the pixels of the image and adds them to the set. <\/p>\n<p>There are probably better solutions than the one presented in this article. The code shown here is merely for the purpose of showing how parallelization can help, though not everything that runs in parallel is faster that a sequential code.<\/p>\n<p>There are some things to note:<\/p>\n<ul>\n<li>I used CImage class to load an image from disk<\/li>\n<li>images can be 1,4,8,16,24 or 32 bit per pixel, but in the code presented here, for simplicity, I assume the image loaded from disk is 24 bits per pixel<\/li>\n<li>Windows device-independent bitmaps can be stored in memory in two ways: top-down (as you would naturally expect) or bottom-up. The processing of the image varies based on the storage. You can find details here: <a href=\"http:\/\/msdn.microsoft.com\/en-us\/library\/ms787796.aspx\">Top-Down vs. Bottom-Up DIBs<\/a>.<\/li>\n<li><a href=\"http:\/\/msdn.microsoft.com\/en-us\/library\/4sa8ea41(v=vs.80).aspx\">CImage::GetPitch<\/a> method returns the pitch of the bitmap, which is the distance in bytes between the two memory addresses representing the beginning of two consecutive lines of the bitmap. This is important because the bitmap can be stored (align) with padding bytes at the end of a line, and the pitch and the width are used to determine the number of padding bytes. If the pitch is positive, then the bitmap is stored top-down. If the pitch is negative then the image is stored bottom-up.<\/li>\n<li>the pointer returned by <a href=\"http:\/\/msdn.microsoft.com\/en-US\/library\/zx1ex9b5(v=vs.80).aspx\">CImage::GetBits<\/a> points to the beginning of the buffer if the image is top-down, and to the end of the buffer if the image is bottom-up.<\/li>\n<li>since the image data is stored in contiguous array, the position of each pixel is given by the following algorithm:\n<pre>\r\nlet ptr be the beginning of the buffer\r\nforeach row from 0 to height\r\n foreach column from 0 to width\r\n   if top-down \/\/ ptr point to the beginning of the buffer\r\n     pixel = ptr + row * pitch + column * bytesperpixel\r\n   else bottom-up \/\/ ptr points to the end of the buffer\r\n     pixel = ptr - row * pitch + column * bytesperpixel\r\n<\/pre>\n<p>Since the pitch is positive when the bitmap is stored top-down and negative when then image is stored bottom-up, the above algorithm can be simplified to:<\/p>\n<pre>\r\nlet ptr be the beginning of the buffer\r\nforeach row from 0 to height\r\n foreach column from 0 to width\r\n   pixel = ptr + row * pitch + column * bytesperpixel\r\n<\/pre>\n<\/li>\n<\/ul>\n<p>My simple implementation of the sequential algorithm looks like this:<\/p>\n<pre class=\"cpp\" name=\"code\">\r\nint CountColors24bpp(unsigned char* data, int width, int height, int pitch)\r\n{\r\n    int bytespp = 3;\r\n    std::set&lt;unsigned int&gt; colors;\r\n\r\n    int padding = abs(pitch) - width * bytespp;\r\n\r\n    for(int i = 0; i &lt; height; ++i)\r\n    {\r\n        for(int j = 0; j &lt; width; ++j)\r\n        {\r\n            unsigned char* ptr = data + i*pitch + j * bytespp;\r\n            unsigned int color = ((*ptr) &lt;&lt; 16) | (*(ptr+1) &lt;&lt; 8) | *(ptr+2);\r\n            colors.insert(color);\r\n        }\r\n    }\r\n\r\n    return colors.size();\r\n}\r\n<\/pre>\n<p>Loading the image from disk, and timing the execution looks like this:<\/p>\n<pre class=\"cpp\" name=\"code\">\r\nCImage image;\r\nimage.Load(_T(\"d:\\\\sample.bmp\"));\r\n\r\nint width = image.GetWidth();\r\nint height = image.GetHeight();\r\nint pitch = image.GetPitch();\r\nint bpp = image.GetBPP();\r\n\r\nunsigned char* data = reinterpret_cast&lt;unsigned char*&gt;(image.GetBits());\r\n\r\n{\r\n    std::chrono::time_point&lt;std::chrono::high_resolution_clock&gt; start = std::chrono::high_resolution_clock::now();\r\n\r\n    int colors = CountColors(data, width, height, bpp, pitch);\r\n\r\n    std::chrono::time_point&lt;std::chrono::high_resolution_clock&gt; end = std::chrono::high_resolution_clock::now();\r\n\r\n    auto elapsed_time = std::chrono::duration_cast&lt;std::chrono::milliseconds&gt;(end-start).count();\r\n\r\n    std::cout &lt;&lt; \"[seq] colors count: \" &lt;&lt; colors &lt;&lt; std::endl;\r\n    std::cout &lt;&lt; \"[seq] elapsed time: \" &lt;&lt; elapsed_time &lt;&lt; \"ms\" &lt;&lt; std::endl;\r\n}\r\n<\/pre>\n<p>The result on my machine (Intel Core i7 2.67GHz, 6 GB RAM) on four random bitmaps with sizes 200&#215;150, 1680&#215;1050, 3360&#215;1065 and 3360&#215;2100 look like this (obviously with small variations):<\/p>\n<pre>\r\n[seq] colors count: 513\r\n[seq] elapsed time: 1ms\r\n\r\n[seq] colors count: 10544\r\n[seq] elapsed time: 81ms\r\n\r\n[seq] colors count: 33454\r\n[seq] elapsed time: 172ms\r\n\r\n[seq] colors count: 33454\r\n[seq] elapsed time: 345ms\r\n<\/pre>\n<p>The simplest parallelization you can think of is using parallel_for from the Parallel Patterns Library. Especially, because the conversion from a sequential implementation to a parallel one is pretty trivial.<\/p>\n<pre class=\"cpp\" name=\"code\">\r\n#include &lt;mutex&gt;\r\nstd::mutex g_mutex;\r\n\r\nint CountColors24bpp_pfor(unsigned char* data, int width, int height, int pitch)\r\n{\r\n    int bytespp = 3;\r\n    std::set&lt;unsigned int&gt; colors;\r\n\r\n    int padding = abs(pitch) - width * bytespp;\r\n\r\n    parallel_for(0, height, [&amp;](int i) {\r\n        for(int j = 0; j &lt; width; ++j)\r\n        {\r\n            unsigned char* ptr = data + i*pitch + j * bytespp;\r\n            unsigned int color = ((*ptr) &lt;&lt; 16) | (*(ptr+1) &lt;&lt; 8) | *(ptr+2);\r\n            g_mutex.lock();\r\n            colors.insert(color);\r\n            g_mutex.unlock();\r\n        }\r\n    });\r\n\r\n    return colors.size();\r\n}\r\n<\/pre>\n<p>When you run this code you get some pretty surprising results.<\/p>\n<pre>\r\n[pfor] colors count: 513\r\n[pfor] elapsed time: 106ms\r\n\r\n[pfor] colors count: 10544\r\n[pfor] elapsed time: 5803ms\r\n\r\n[pfor] colors count: 33454\r\n[pfor] elapsed time: 10714ms\r\n\r\n[pfor] colors count: 33454\r\n[pfor] elapsed time: 15854ms\r\n<\/pre>\n<p>It&#8217;s not that surprising after all, if you look at how the insertion is performed. The access to the std::set is guarded with std::mutex, allowing only one thread to insert a new element into the set. Because of this synchronization it takes much more, in the order of 50-100 times, than the sequential implementation. Of course, the bigger the image is, the smaller this performance lost.<\/p>\n<p>Obviously, parallelization through the means of parallel_for is not a solution in this case. Using threads directly however, can help, if we can get rid of syncing. This is possible by using a separate std::set for each thread, and merging the results at the end.<\/p>\n<pre class=\"cpp\" name=\"code\">\r\n#include &lt;thread&gt;\r\n\r\nstruct thread_data \r\n{\r\n    unsigned char* data;\r\n    int width;\r\n    int h0;\r\n    int h1;\r\n    int pitch;\r\n};\r\n\r\nvoid CountColors24bpp_threadfunc(thread_data td, std::set&lt;unsigned int&gt;&amp; colors)\r\n{\r\n    int bytespp = 3;\r\n    int padding = abs(td.pitch) - td.width * bytespp;\r\n\r\n    for(int i = td.h0; i &lt; td.h1; ++i)\r\n    {\r\n        for(int j = 0; j &lt; td.width; ++j)\r\n        {\r\n            unsigned char* ptr = td.data + i*td.pitch + j * bytespp;\r\n            unsigned int color = ((*ptr) &lt;&lt; 16) | (*(ptr+1) &lt;&lt; 8) | *(ptr+2);\r\n            colors.insert(color);\r\n        }\r\n    }\r\n}\r\n\r\nint CountColors24bpp_threads(unsigned char* data, int width, int height, int pitch, int threadscount)\r\n{    \r\n    std::vector&lt;std::set&lt;unsigned int&gt;&gt; colors(threadscount);\r\n    std::vector&lt;std::thread&gt; threads(threadscount);\r\n\r\n    int range = height \/ threadscount;\r\n\r\n    for(int i = 0; i &lt; threadscount; ++i)\r\n    {\r\n        thread_data td;\r\n        td.data = data;\r\n        td.h0 = range * i;\r\n        td.h1 = i == (threadscount - 1) ? height : td.h0 + range;\r\n        td.width = width;\r\n        td.pitch = pitch;\r\n\r\n        std::thread t(CountColors24bpp_threadfunc, td, std::ref(colors[i]));\r\n        threads[i].swap(t);\r\n    }\r\n    \r\n    for(int i = 0; i < threadscount; ++i)\r\n        threads[i].join();\r\n\r\n    std::set&lt;unsigned int&gt; result;\r\n\r\n    for(int i = 0; i &lt; threadscount; ++i)\r\n        result.insert(colors[i].begin(), colors[i].end());\r\n\r\n    return result.size();\r\n}\r\n<\/pre>\n<p>A few considerations:<\/p>\n<ul>\n<li>the std::thread constructor does not take (yet) any number of parameters, so I had to pack the arguments in a structure<\/li>\n<li>the std::set with the colors is passed by reference, and therefore it has to be packed in a std::ref<\/li>\n<li>I create N threads, call the thread function with the arguments and then join them all<\/li>\n<li>when all threads have finished I aggregate the individual sets in a single one<\/li>\n<\/ul>\n<p>Running this code with 4 threads yields results that look like this:<\/p>\n<pre>\r\n[threads] colors count: 513\r\n[threads] elapsed time: 1ms\r\n\r\n[threads] colors count: 10544\r\n[threads] elapsed time: 28ms\r\n\r\n[threads] colors count: 33454\r\n[threads] elapsed time: 61ms\r\n\r\n[threads] colors count: 33454\r\n[threads] elapsed time: 110ms\r\n<\/pre>\n<p>As you can see the performance is better than the sequential code in each case (and implicitly far better than the parallel_for version).<\/p>\n<p>As I said at the beginning, one can imagine better algorithms (both sequential and parallel), but the straight forward conclusion is that you have to beware of parallelization, as not every parallel version of an algorithm can run faster than the sequential version. The more syncing for shared-access takes place, the more performance is affected and the results can get much worse than the sequential version.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>A recent question on stackoverflow raised the problem of a fast algorithm to count the unique colors in an image (Faster algorithm to check the colors in a image). My answer what that this kind of problems are suited for parallelization. However, parallelization may only help when used judiciously. To demonstrate the point I have &#8230; <a title=\"Beware of parallelization\" class=\"read-more\" href=\"https:\/\/mariusbancila.ro\/blog\/2013\/02\/11\/beware-of-parallelization\/\" aria-label=\"Read more about Beware of parallelization\">Read more<\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_uag_custom_page_level_css":"","advgb_blocks_editor_width":"","advgb_blocks_columns_visual_guide":"","_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_feature_clip_id":0,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":true,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2},"jetpack_post_was_ever_published":false},"categories":[7,42],"tags":[451,345,173,47,347,346],"class_list":["post-1482","post","type-post","status-publish","format-standard","hentry","category-c","category-parallel-programming","tag-c","tag-c11","tag-image","tag-parallel","tag-sync","tag-thread"],"aioseo_notices":[],"aioseo_head":"\n\t\t<!-- All in One SEO 5.0.3 - aioseo.com -->\n\t<meta name=\"description\" content=\"A case study of the pitfalls of parallelizing sequential algorithms.\" \/>\n\t<meta name=\"robots\" content=\"max-image-preview:large\" \/>\n\t<meta name=\"author\" content=\"Marius Bancila\"\/>\n\t<meta name=\"keywords\" content=\"c++,c++11,thread,parallel,image,sync\" \/>\n\t<link rel=\"canonical\" href=\"https:\/\/mariusbancila.ro\/blog\/2013\/02\/11\/beware-of-parallelization\/\" \/>\n\t\t<meta name=\"generator\" content=\"All in One SEO (AIOSEO) 5.0.3\" \/>\n\t\t<meta property=\"og:locale\" content=\"en_US\" \/>\n\t\t<meta property=\"og:site_name\" content=\"Marius Bancila&#039;s Blog | About code. Mostly on C++\" \/>\n\t\t<meta property=\"og:type\" content=\"article\" \/>\n\t\t<meta property=\"og:title\" content=\"Beware of parallelization\" \/>\n\t\t<meta property=\"og:description\" content=\"A case study of the pitfalls of parallelizing sequential algorithms.\" \/>\n\t\t<meta property=\"og:url\" content=\"https:\/\/mariusbancila.ro\/blog\/2013\/02\/11\/beware-of-parallelization\/\" \/>\n\t\t<meta property=\"article:published_time\" content=\"2013-02-11T10:36:14+00:00\" \/>\n\t\t<meta property=\"article:modified_time\" content=\"2013-02-11T10:36:14+00:00\" \/>\n\t\t<meta name=\"twitter:card\" content=\"summary\" \/>\n\t\t<meta name=\"twitter:title\" content=\"Beware of parallelization\" \/>\n\t\t<meta name=\"twitter:description\" content=\"A case study of the pitfalls of parallelizing sequential algorithms.\" \/>\n\t\t<script type=\"application\/ld+json\" class=\"aioseo-schema\">\n\t\t\t{\"@context\":\"https:\\\/\\\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/2013\\\/02\\\/11\\\/beware-of-parallelization\\\/#article\",\"name\":\"Beware of parallelization\",\"headline\":\"Beware of parallelization\",\"author\":{\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/author\\\/admin\\\/#author\"},\"publisher\":{\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/#organization\"},\"datePublished\":\"2013-02-11T12:36:14+02:00\",\"dateModified\":\"2013-02-11T12:36:14+02:00\",\"inLanguage\":\"en-US\",\"mainEntityOfPage\":{\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/2013\\\/02\\\/11\\\/beware-of-parallelization\\\/#webpage\"},\"isPartOf\":{\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/2013\\\/02\\\/11\\\/beware-of-parallelization\\\/#webpage\"},\"articleSection\":\"C++, Parallel Programming, C++, C++11, image, parallel, sync, thread\"},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/2013\\\/02\\\/11\\\/beware-of-parallelization\\\/#breadcrumblist\",\"itemListElement\":[{\"@type\":\"ListItem\",\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/#listItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/\",\"nextItem\":{\"@type\":\"ListItem\",\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/category\\\/it\\\/#listItem\",\"name\":\"IT\"}},{\"@type\":\"ListItem\",\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/category\\\/it\\\/#listItem\",\"position\":2,\"name\":\"IT\",\"item\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/category\\\/it\\\/\",\"nextItem\":{\"@type\":\"ListItem\",\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/category\\\/it\\\/software\\\/#listItem\",\"name\":\"Software\"},\"previousItem\":{\"@type\":\"ListItem\",\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/#listItem\",\"name\":\"Home\"}},{\"@type\":\"ListItem\",\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/category\\\/it\\\/software\\\/#listItem\",\"position\":3,\"name\":\"Software\",\"item\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/category\\\/it\\\/software\\\/\",\"nextItem\":{\"@type\":\"ListItem\",\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/category\\\/it\\\/software\\\/c\\\/#listItem\",\"name\":\"C++\"},\"previousItem\":{\"@type\":\"ListItem\",\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/category\\\/it\\\/#listItem\",\"name\":\"IT\"}},{\"@type\":\"ListItem\",\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/category\\\/it\\\/software\\\/c\\\/#listItem\",\"position\":4,\"name\":\"C++\",\"item\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/category\\\/it\\\/software\\\/c\\\/\",\"nextItem\":{\"@type\":\"ListItem\",\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/2013\\\/02\\\/11\\\/beware-of-parallelization\\\/#listItem\",\"name\":\"Beware of parallelization\"},\"previousItem\":{\"@type\":\"ListItem\",\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/category\\\/it\\\/software\\\/#listItem\",\"name\":\"Software\"}},{\"@type\":\"ListItem\",\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/2013\\\/02\\\/11\\\/beware-of-parallelization\\\/#listItem\",\"position\":5,\"name\":\"Beware of parallelization\",\"previousItem\":{\"@type\":\"ListItem\",\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/category\\\/it\\\/software\\\/c\\\/#listItem\",\"name\":\"C++\"}}]},{\"@type\":\"Organization\",\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/#organization\",\"name\":\"Marius Bancila's Blog\",\"description\":\"About code. Mostly on C++\",\"url\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/\"},{\"@type\":\"Person\",\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/author\\\/admin\\\/#author\",\"url\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/author\\\/admin\\\/\",\"name\":\"Marius Bancila\",\"image\":{\"@type\":\"ImageObject\",\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/2013\\\/02\\\/11\\\/beware-of-parallelization\\\/#authorImage\",\"url\":\"https:\\\/\\\/secure.gravatar.com\\\/avatar\\\/a84dd2831d955c38355ddea55df4df260809b88f36408bc14fd4eab8f7f131c9?s=96&d=mm&r=g\",\"width\":96,\"height\":96,\"caption\":\"Marius Bancila\"}},{\"@type\":\"WebPage\",\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/2013\\\/02\\\/11\\\/beware-of-parallelization\\\/#webpage\",\"url\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/2013\\\/02\\\/11\\\/beware-of-parallelization\\\/\",\"name\":\"Beware of parallelization\",\"description\":\"A case study of the pitfalls of parallelizing sequential algorithms.\",\"inLanguage\":\"en-US\",\"isPartOf\":{\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/#website\"},\"breadcrumb\":{\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/2013\\\/02\\\/11\\\/beware-of-parallelization\\\/#breadcrumblist\"},\"author\":{\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/author\\\/admin\\\/#author\"},\"creator\":{\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/author\\\/admin\\\/#author\"},\"datePublished\":\"2013-02-11T12:36:14+02:00\",\"dateModified\":\"2013-02-11T12:36:14+02:00\"},{\"@type\":\"WebSite\",\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/#website\",\"url\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/\",\"name\":\"Marius Bancila's Blog\",\"description\":\"About code. Mostly on C++\",\"inLanguage\":\"en-US\",\"publisher\":{\"@id\":\"https:\\\/\\\/mariusbancila.ro\\\/blog\\\/#organization\"}}]}\n\t\t<\/script>\n\t\t<!-- All in One SEO -->\n\n","aioseo_head_json":{"title":"Beware of parallelization","description":"A case study of the pitfalls of parallelizing sequential algorithms.","canonical_url":"https:\/\/mariusbancila.ro\/blog\/2013\/02\/11\/beware-of-parallelization\/","robots":"max-image-preview:large","keywords":"c++,c++11,thread,parallel,image,sync","webmasterTools":{"miscellaneous":""},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/mariusbancila.ro\/blog\/2013\/02\/11\/beware-of-parallelization\/#article","name":"Beware of parallelization","headline":"Beware of parallelization","author":{"@id":"https:\/\/mariusbancila.ro\/blog\/author\/admin\/#author"},"publisher":{"@id":"https:\/\/mariusbancila.ro\/blog\/#organization"},"datePublished":"2013-02-11T12:36:14+02:00","dateModified":"2013-02-11T12:36:14+02:00","inLanguage":"en-US","mainEntityOfPage":{"@id":"https:\/\/mariusbancila.ro\/blog\/2013\/02\/11\/beware-of-parallelization\/#webpage"},"isPartOf":{"@id":"https:\/\/mariusbancila.ro\/blog\/2013\/02\/11\/beware-of-parallelization\/#webpage"},"articleSection":"C++, Parallel Programming, C++, C++11, image, parallel, sync, thread"},{"@type":"BreadcrumbList","@id":"https:\/\/mariusbancila.ro\/blog\/2013\/02\/11\/beware-of-parallelization\/#breadcrumblist","itemListElement":[{"@type":"ListItem","@id":"https:\/\/mariusbancila.ro\/blog\/#listItem","position":1,"name":"Home","item":"https:\/\/mariusbancila.ro\/blog\/","nextItem":{"@type":"ListItem","@id":"https:\/\/mariusbancila.ro\/blog\/category\/it\/#listItem","name":"IT"}},{"@type":"ListItem","@id":"https:\/\/mariusbancila.ro\/blog\/category\/it\/#listItem","position":2,"name":"IT","item":"https:\/\/mariusbancila.ro\/blog\/category\/it\/","nextItem":{"@type":"ListItem","@id":"https:\/\/mariusbancila.ro\/blog\/category\/it\/software\/#listItem","name":"Software"},"previousItem":{"@type":"ListItem","@id":"https:\/\/mariusbancila.ro\/blog\/#listItem","name":"Home"}},{"@type":"ListItem","@id":"https:\/\/mariusbancila.ro\/blog\/category\/it\/software\/#listItem","position":3,"name":"Software","item":"https:\/\/mariusbancila.ro\/blog\/category\/it\/software\/","nextItem":{"@type":"ListItem","@id":"https:\/\/mariusbancila.ro\/blog\/category\/it\/software\/c\/#listItem","name":"C++"},"previousItem":{"@type":"ListItem","@id":"https:\/\/mariusbancila.ro\/blog\/category\/it\/#listItem","name":"IT"}},{"@type":"ListItem","@id":"https:\/\/mariusbancila.ro\/blog\/category\/it\/software\/c\/#listItem","position":4,"name":"C++","item":"https:\/\/mariusbancila.ro\/blog\/category\/it\/software\/c\/","nextItem":{"@type":"ListItem","@id":"https:\/\/mariusbancila.ro\/blog\/2013\/02\/11\/beware-of-parallelization\/#listItem","name":"Beware of parallelization"},"previousItem":{"@type":"ListItem","@id":"https:\/\/mariusbancila.ro\/blog\/category\/it\/software\/#listItem","name":"Software"}},{"@type":"ListItem","@id":"https:\/\/mariusbancila.ro\/blog\/2013\/02\/11\/beware-of-parallelization\/#listItem","position":5,"name":"Beware of parallelization","previousItem":{"@type":"ListItem","@id":"https:\/\/mariusbancila.ro\/blog\/category\/it\/software\/c\/#listItem","name":"C++"}}]},{"@type":"Organization","@id":"https:\/\/mariusbancila.ro\/blog\/#organization","name":"Marius Bancila's Blog","description":"About code. Mostly on C++","url":"https:\/\/mariusbancila.ro\/blog\/"},{"@type":"Person","@id":"https:\/\/mariusbancila.ro\/blog\/author\/admin\/#author","url":"https:\/\/mariusbancila.ro\/blog\/author\/admin\/","name":"Marius Bancila","image":{"@type":"ImageObject","@id":"https:\/\/mariusbancila.ro\/blog\/2013\/02\/11\/beware-of-parallelization\/#authorImage","url":"https:\/\/secure.gravatar.com\/avatar\/a84dd2831d955c38355ddea55df4df260809b88f36408bc14fd4eab8f7f131c9?s=96&d=mm&r=g","width":96,"height":96,"caption":"Marius Bancila"}},{"@type":"WebPage","@id":"https:\/\/mariusbancila.ro\/blog\/2013\/02\/11\/beware-of-parallelization\/#webpage","url":"https:\/\/mariusbancila.ro\/blog\/2013\/02\/11\/beware-of-parallelization\/","name":"Beware of parallelization","description":"A case study of the pitfalls of parallelizing sequential algorithms.","inLanguage":"en-US","isPartOf":{"@id":"https:\/\/mariusbancila.ro\/blog\/#website"},"breadcrumb":{"@id":"https:\/\/mariusbancila.ro\/blog\/2013\/02\/11\/beware-of-parallelization\/#breadcrumblist"},"author":{"@id":"https:\/\/mariusbancila.ro\/blog\/author\/admin\/#author"},"creator":{"@id":"https:\/\/mariusbancila.ro\/blog\/author\/admin\/#author"},"datePublished":"2013-02-11T12:36:14+02:00","dateModified":"2013-02-11T12:36:14+02:00"},{"@type":"WebSite","@id":"https:\/\/mariusbancila.ro\/blog\/#website","url":"https:\/\/mariusbancila.ro\/blog\/","name":"Marius Bancila's Blog","description":"About code. Mostly on C++","inLanguage":"en-US","publisher":{"@id":"https:\/\/mariusbancila.ro\/blog\/#organization"}}]},"og:locale":"en_US","og:site_name":"Marius Bancila's Blog | About code. Mostly on C++","og:type":"article","og:title":"Beware of parallelization","og:description":"A case study of the pitfalls of parallelizing sequential algorithms.","og:url":"https:\/\/mariusbancila.ro\/blog\/2013\/02\/11\/beware-of-parallelization\/","article:published_time":"2013-02-11T10:36:14+00:00","article:modified_time":"2013-02-11T10:36:14+00:00","twitter:card":"summary","twitter:title":"Beware of parallelization","twitter:description":"A case study of the pitfalls of parallelizing sequential algorithms."},"aioseo_meta_data":{"post_id":"1482","title":"Beware of parallelization","description":"A case study of the pitfalls of parallelizing sequential algorithms.","keywords":[{"label":"C++","value":"C++"},{"label":"C++11","value":"C++11"},{"label":"thread","value":"thread"},{"label":"parallel","value":"parallel"},{"label":"image","value":"image"},{"label":"sync","value":"sync"}],"keyphrases":null,"primary_term":null,"canonical_url":null,"og_title":null,"og_description":null,"og_object_type":"default","og_image_type":"default","og_image_url":null,"og_image_width":null,"og_image_height":null,"og_image_custom_url":null,"og_image_custom_fields":null,"og_video":null,"og_custom_url":null,"og_article_section":null,"og_article_tags":null,"twitter_use_og":false,"twitter_card":"default","twitter_image_type":"default","twitter_image_url":null,"twitter_image_custom_url":null,"twitter_image_custom_fields":null,"twitter_title":null,"twitter_description":null,"schema":{"blockGraphs":[],"customGraphs":[],"default":{"data":{"Article":[],"Course":[],"Dataset":[],"FAQPage":[],"Movie":[],"Person":[],"Product":[],"ProductReview":[],"Car":[],"Recipe":[],"Service":[],"SoftwareApplication":[],"WebPage":[]},"graphName":"","isEnabled":true},"graphs":[]},"schema_type":null,"schema_type_options":null,"pillar_content":false,"robots_default":true,"robots_noindex":false,"robots_noarchive":false,"robots_nosnippet":false,"robots_nofollow":false,"robots_noimageindex":false,"robots_noodp":false,"robots_notranslate":false,"robots_max_snippet":null,"robots_max_videopreview":null,"robots_max_imagepreview":"large","priority":null,"frequency":null,"location":null,"local_seo":null,"breadcrumb_settings":null,"limit_modified_date":false,"ai":null,"created":"2021-03-18 21:12:20","updated":"2025-12-12 07:39:24","seo_analyzer_scan_date":null,"focus_keyword":null,"additional_keywords":null,"truseo_locale":null},"author_meta":{"display_name":"Marius Bancila","author_link":"https:\/\/mariusbancila.ro\/blog\/author\/admin\/"},"featured_img":null,"jetpack_publicize_connections":[],"uagb_featured_image_src":{"full":false,"thumbnail":false,"medium":false,"medium_large":false,"large":false,"1536x1536":false,"2048x2048":false},"uagb_author_info":{"display_name":"Marius Bancila","author_link":"https:\/\/mariusbancila.ro\/blog\/author\/admin\/"},"uagb_comment_info":0,"uagb_excerpt":"A recent question on stackoverflow raised the problem of a fast algorithm to count the unique colors in an image (Faster algorithm to check the colors in a image). My answer what that this kind of problems are suited for parallelization. However, parallelization may only help when used judiciously. To demonstrate the point I have&hellip;","coauthors":[],"tax_additional":{"categories":{"linked":["<a href=\"https:\/\/mariusbancila.ro\/blog\/category\/it\/software\/c\/\" class=\"advgb-post-tax-term\">C++<\/a>","<a href=\"https:\/\/mariusbancila.ro\/blog\/category\/it\/software\/parallel-programming\/\" class=\"advgb-post-tax-term\">Parallel Programming<\/a>"],"unlinked":["<span class=\"advgb-post-tax-term\">C++<\/span>","<span class=\"advgb-post-tax-term\">Parallel Programming<\/span>"]},"tags":{"linked":["<a href=\"https:\/\/mariusbancila.ro\/blog\/category\/it\/software\/parallel-programming\/\" class=\"advgb-post-tax-term\">C++<\/a>","<a href=\"https:\/\/mariusbancila.ro\/blog\/category\/it\/software\/parallel-programming\/\" class=\"advgb-post-tax-term\">C++11<\/a>","<a href=\"https:\/\/mariusbancila.ro\/blog\/category\/it\/software\/parallel-programming\/\" class=\"advgb-post-tax-term\">image<\/a>","<a href=\"https:\/\/mariusbancila.ro\/blog\/category\/it\/software\/parallel-programming\/\" class=\"advgb-post-tax-term\">parallel<\/a>","<a href=\"https:\/\/mariusbancila.ro\/blog\/category\/it\/software\/parallel-programming\/\" class=\"advgb-post-tax-term\">sync<\/a>","<a href=\"https:\/\/mariusbancila.ro\/blog\/category\/it\/software\/parallel-programming\/\" class=\"advgb-post-tax-term\">thread<\/a>"],"unlinked":["<span class=\"advgb-post-tax-term\">C++<\/span>","<span class=\"advgb-post-tax-term\">C++11<\/span>","<span class=\"advgb-post-tax-term\">image<\/span>","<span class=\"advgb-post-tax-term\">parallel<\/span>","<span class=\"advgb-post-tax-term\">sync<\/span>","<span class=\"advgb-post-tax-term\">thread<\/span>"]}},"comment_count":"0","relative_dates":{"created":"Posted 14 years ago","modified":"Updated 14 years ago"},"absolute_dates":{"created":"Posted on February 11, 2013","modified":"Updated on February 11, 2013"},"absolute_dates_time":{"created":"Posted on February 11, 2013 12:36 pm","modified":"Updated on February 11, 2013 12:36 pm"},"featured_img_caption":"","series_order":"","jetpack_shortlink":"https:\/\/wp.me\/pYNdv-nU","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/mariusbancila.ro\/blog\/wp-json\/wp\/v2\/posts\/1482","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/mariusbancila.ro\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/mariusbancila.ro\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/mariusbancila.ro\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/mariusbancila.ro\/blog\/wp-json\/wp\/v2\/comments?post=1482"}],"version-history":[{"count":12,"href":"https:\/\/mariusbancila.ro\/blog\/wp-json\/wp\/v2\/posts\/1482\/revisions"}],"predecessor-version":[{"id":1494,"href":"https:\/\/mariusbancila.ro\/blog\/wp-json\/wp\/v2\/posts\/1482\/revisions\/1494"}],"wp:attachment":[{"href":"https:\/\/mariusbancila.ro\/blog\/wp-json\/wp\/v2\/media?parent=1482"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/mariusbancila.ro\/blog\/wp-json\/wp\/v2\/categories?post=1482"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/mariusbancila.ro\/blog\/wp-json\/wp\/v2\/tags?post=1482"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}