How to Build Map Containers Faster with PTL for .NET

The last video in our Parallel Template Library (PTL) video series (.NET Sorted Dictionary vs. PTL Map32 – Add, Item & Remove Functions) demonstrated the performance of the insertion method of PTL’s map container for large data sets by comparing it to the equivalent .NET container. In our latest video, “How to Build Map Containers Faster with PTL for .NET,” we show how you can improve the performance even more by using pre-sorted elements when building a map.

The PTL Containers component for .NET and Java offers powerful data containers that have been optimized for parallelism and for large data sets, such as the Map containers that we demonstrate in this video. We compare the Insert and PushBack methods from PTL’s Map64 container to the equivalent Add method from the .NET SortedDictionary on a system with a quad-core processor and 32 GB of memory.

A map is a variable-sized collection of (key, value) pairs. Its primary usage is the efficient retrieval of elements (or values) based on their associated keys. It also implements the insertion and removal of elements very efficiently.

PTL offers Map32 and Map64 classes that are very similar to the .NET SortedDictionary class. PTL maps differ from the .NET SortedDictionary because they have a Boolean property called “Unique” that is set in their constructor and indicates if the map allows or disallows duplicate keys. The .NET SortedDictionary only allows elements with unique keys. It’s also important to note that PTL’s Map32 and Map64 are not tuned for a 32 or 64-bit operating system; they only differ in their maximum size.

For this demo, we use the .NET SortedDictionary and the PTL Map64 containers. 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).

Based on results from previous demos, we asked ourselves if we can build a map from scratch faster than just using insertion. We could append all of the elements to a list, sort this list and add all of the sorted elements to an empty map. In this demo, we investigate if the Map Insert method is faster when the elements are already sorted. Remember, the primary usage of a map is not to sort elements; it’s to retrieve values based on their keys.

PTL’s containers have superior memory management compared to .NET’s containers. For example, we initially choose for this demo to add 600 million pre-sorted elements to an empty .NET SortedDictionary using its Add method. At first, the insertion speed is a little over 2 million elements per second, but the average speed decreases to around 529,000 elements per second by the end. The .NET container consumes all of the system’s physical memory (32 GB), even though the actual data size is only around 9 GB (or 600 million elements times 16 bytes). This causes the insertion speed to slow down because the operating system has to swap memory pages on the hard drive.

In order to have a fair comparison for this demo, we decide to add only 500 million pre-sorted elements to an empty .NET SortedDictionary, so they will fit in memory. The insertion takes 5 minutes and 28 seconds, and its average speed is around 1.5 million elements per second. In our previous video, the average insertion speed was around 250,000 elements per second when the elements were not sorted, so we can already see a big improvement when using pre-sorted elements.

Next, we also insert 500 million pre-sorted elements into an empty PTL Map64 using its Insert method. The insertion takes only 58 seconds, which is 5.7 times faster than the .NET SortedDictionary. Its average speed is 8.6 million elements per second, which is much faster than the average speed of 900,000 elements per second from our previous video where the elements were not pre-sorted.

However, the biggest performance improvement for PTL vs. .NET is in the memory footprint of the map. The memory footprint for the PTL Map64 is much closer to the actual data size of 7.45 GB (or 500 million elements times 16 bytes) than the .NET SortedDictionary. For example, we can construct a PTL Map64 object with 1 billion MapEntry elements that consumes only about 15 GB (or half of the physical memory). A .NET SortedDictionary with 1 billion elements is impossible for this hardware configuration.

For even more performance improvement, PTL offers the PushBack method to construct a map from scratch from a sorted range one element at a time. The Insert function is quite complex because it needs to balance the current node with its neighbors when adding a new node. When we’re inserting a pre-sorted range, we shouldn’t need to do any balancing, which is why PTL offers the PushBack method for this situation.

We run the PTL Pushback method for 500 million pre-sorted elements. Its average insertion speed is around 83 million elements per second. It finishes very quickly in 6 seconds, which is 54 times faster than the Add method of the .NET SortedDictionary.

.NET SortedDictionary vs. PTL Map64

These tests demonstrate that the PTL Map classes are well designed to sustain large datasets. They manage memory much better than the .NET SortedDictionary, which allows you to build larger maps with a much smaller memory footprint than the SortedDictionary. They also provide a PushBack method in addition to an Insert method, which really improves performance when building a map from scratch using pre-sorted elements. The SortedDictionary only offers an Add method.

If you’re ready to test PTL’s containers for yourself, you can currently download our free trials for .NET or Java. Stay tuned for new PTL demos coming soon, including our first demos of the new PTL for C++.

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>