Parallel Sort & Reverse Algorithms of PTL Array vs. .NET List

The next video in our Parallel Template Library (PTL) video series is our “Parallel Sort and Reverse in PTL Algorithms” video. PTL differs from the .NET standard library because its Array and Iterator Algorithms components offer parallel versions of many useful algorithms, which take advantage of multicore processors to greatly improve their performance.

In this video, we demonstrate the performance of PTL’s Sort and Reverse algorithms for large data sets (1 billion elements) using a .NET List and a PTLArray container. On a quad-core processor, PTL’s parallel Sort was 4.5 times faster than the sequential Sort of the .NET List, and PTL’s parallel Reverse was 109 times faster than the sequential Reverse of the .NET List.

We executed our demo application on a system with one Intel Core i7 processor with 4 physical cores (8 logical cores with hyperthreading) and 32 GB of memory. We also restarted the demo application after each test to run each test independently and get a fair comparison.

For this demo, we use the .NET List and PTLArray containers because they are both based on contiguous native arrays and give us a fair comparison. In our tests, both containers are filled with MapEntry values, which are (key, value) pairs. The size of a MapEntry object is 16 bytes (8 bytes for the key and 8 bytes for the value).

To fill both containers with values, we use a randomly-shuffled array of 1 billion numbers that has been stored to a file. We use this same file to load both the .NET List and PTLArray objects with MapEntry values, and we use the next random number for both the key and the value for each MapEntry element. This allows us to compare the Sort results using the exact same data and also makes it easier to verify the results.

We chose to use the Sort and Reverse operations because they are part of the .NET List implementation. The containers in the PTL Containers component only implement basic functions (such as Add, Remove, etc.). All other complex operations, such as Sort and Reverse, are implemented in the PTL Algorithms component. The functions in the PTL Algorithms component operate on a range of elements and can be used with the PTL Containers component or with custom containers that you design.

First in the demo, we load 1 billion elements into a .NET List. Then, we run the sequential Sort operation of the .NET List class. While we still have the list in memory, we run the Reverse operation of the .NET List class.

Next, we load the same 1 billion elements into a PTLArray object. PTLArray is the only PTL container that can be used with both the Iterator Algorithms and the Array Algorithms components. PTLArray has a property called Data that exposes the underlying native array, so it can be used with the Array Algorithms component for faster performance, which is what we use in this demo.

We run the sequential Sort operation from the PTL Array Algorithms component on the PTLArray object. PTL’s sequential Sort is 1.1 times faster than the sequential Sort of the .NET List (all results are shown in the chart below). While the PTL container is still in memory, we run PTL’s sequential Reverse operation. PTL’s sequential Reverse is 54 times faster than the sequential Reverse of the .NET List. The Reverse algorithm, when implemented correctly, is very fast because the algorithm itself is very cache-friendly.

PTL differs from .NET because it also offers parallel versions of many algorithms, including Sort and Reverse. Next, we run the parallel Sort operation from the PTL Array Algorithms component. It is 4.5 times faster than the sequential Sort of the .NET List on the quad-core processor used in this demo. Then, we run PTL’s parallel Reverse operation. It is 109 times faster than the sequential Reverse of the .NET List (the performance improvements in the sequential version of PTL’s Reverse algorithm also carry over into its parallel implementation).

.NET List vs. PTLArray - Sort & Reverse Algorithms

PTL’s Algorithms are well designed to process large datasets. During this demo, we show you how we carefully optimized all of PTL’s sequential algorithms first. Then, we worked hard on our parallel algorithms to obtain the best possible performance improvement over their sequential counterparts.

If you’re ready to take advantage of PTL’s Algorithms, you can download a free trial today of the Array Algorithms and Iterator Algorithms components. Also, stay tuned for more blog posts with PTL demos. In the blog or video comments, please let us know if you have any questions or what function demos or tutorials you would like to see next.

LinkedInGoogle+TwitterFacebookGoogle GmailShare

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>