Standard Parallel Algorithms Have Arrived

Parallel algorithms are here! Parallel algorithms are now standard, accessible in VisualStudio 2017 (version 15.8). According to a wonderful Microsoft blog C++17 parallel algorithms are no longer experimental. Algorithms such as sort, for_each, reduce, equal, count, and many more. This give us a standard and portable way to use all of the cores in a multi-core processor.

These algorithms work with many different kinds of standard C++ containers, such as arrays, vectors, and others, while providing good acceleration by using multiple cores.

Let’s see how well parallel sorting performs.

Performance

Benchmarks were ran on a quad-core laptop (i5-6300HQ), using an array filled with random floating-point values. Benchmarks are of standard C++ serial sort, standard C++ parallel sort, and my Parallel Merge Sort.

Testing with 1000000 doubles...
Serial: Lowest: 2347 Highest: 4.29496e+09 Time: 120.499663ms
Serial: Lowest: 2347 Highest: 4.29496e+09 Time: 121.635664ms
Serial: Lowest: 2347 Highest: 4.29496e+09 Time: 117.235660ms
Serial: Lowest: 2347 Highest: 4.29496e+09 Time: 117.451216ms
Serial: Lowest: 2347 Highest: 4.29496e+09 Time: 118.211661ms
Parallel: Lowest: 2347 Highest: 4.29496e+09 Time: 37.851144ms
Parallel: Lowest: 2347 Highest: 4.29496e+09 Time: 43.169372ms
Parallel: Lowest: 2347 Highest: 4.29496e+09 Time: 37.050255ms
Parallel: Lowest: 2347 Highest: 4.29496e+09 Time: 37.505367ms
Parallel: Lowest: 2347 Highest: 4.29496e+09 Time: 37.612923ms

Benchmarking Parallel Merge Sort Hybrid with 1000000 doubles...
Parallel Merge Sort: Lowest: 2347 Highest: 4.29496e+09 Time: 32.424918ms
Parallel Merge Sort: Lowest: 2347 Highest: 4.29496e+09 Time: 31.051583ms
Parallel Merge Sort: Lowest: 2347 Highest: 4.29496e+09 Time: 33.692030ms
Parallel Merge Sort: Lowest: 2347 Highest: 4.29496e+09 Time: 31.068028ms
Parallel Merge Sort: Lowest: 2347 Highest: 4.29496e+09 Time: 30.304027ms

Parallel sort runs about 3X faster on a quad-core processor. Parallel Merge sort is about 20% faster than C++17 standard sort. However, currently it only works on C++ arrays of any data type, but does not yet support vector and other standard containers.

The same benchmark was run on a six-core Xeon E5-1630 v3:

Testing with 1000000 doubles...
Serial: Lowest: 23131 Highest: 4.29496e+09 Time: 120.422200ms
Serial: Lowest: 23131 Highest: 4.29496e+09 Time: 139.577000ms
Serial: Lowest: 23131 Highest: 4.29496e+09 Time: 131.653900ms
Serial: Lowest: 23131 Highest: 4.29496e+09 Time: 133.844600ms
Serial: Lowest: 23131 Highest: 4.29496e+09 Time: 127.753400ms
Parallel: Lowest: 23131 Highest: 4.29496e+09 Time: 30.881100ms
Parallel: Lowest: 23131 Highest: 4.29496e+09 Time: 31.424800ms
Parallel: Lowest: 23131 Highest: 4.29496e+09 Time: 33.881600ms
Parallel: Lowest: 23131 Highest: 4.29496e+09 Time: 27.058000ms
Parallel: Lowest: 23131 Highest: 4.29496e+09 Time: 23.983100ms

Benchmarking Parallel Merge Sort Hybrid with 1000000 doubles...
Parallel Merge Sort: Lowest: 23131 Highest: 4.29496e+09 Time: 21.461700ms
Parallel Merge Sort: Lowest: 23131 Highest: 4.29496e+09 Time: 20.749000ms
Parallel Merge Sort: Lowest: 23131 Highest: 4.29496e+09 Time: 26.031400ms
Parallel Merge Sort: Lowest: 23131 Highest: 4.29496e+09 Time: 20.169000ms
Parallel Merge Sort: Lowest: 23131 Highest: 4.29496e+09 Time: 24.965300ms

Parallel sort speeds up by about 4X over serial sort on a six-core processor. Parallel Merge Sort is the fastest algorithm on both computers. Six-core is nearly 50% faster than quad-core.

Source Code

All of the code that generated the above benchmarks is available in a GitHub repo. Included is a complete VisualStudio 2017 solution, which has C++17 parallel sorting example, and all of the source code for the Parallel Merge Sort (see blog) and Parallel Merge Sort (see blog).

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s