Memory Management of .NET List vs. PTL List64 (Video)

We continue our Parallel Template Library (PTL) video series with our “Memory Management in PTL Containers” video. The PTL Containers component for .NET and Java offers powerful data containers that have been optimized for large data sets and for parallelism to take advantage of multicore processors.

In this video, we demonstrate how PTL’s superior container architecture results in better memory management and increased performance. We compare a .NET List to a PTL List64 container. We add from 100 million to 1.1 billion elements to both containers to show how PTL uses memory much more efficiently. We also retrieve all elements from both containers to prove that random access performance was not sacrificed to implement PTL’s superior memory management scheme.

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 PTL list containers. A list (sometimes called a sequence) is a resizable container whose elements are ordered in a strict linear sequence. It allows fast random access to any element by its index and fast insertions and deletions at the end of the list.

PTL offers List32 and List64 classes that are very similar to the .NET List class. It’s important to note that PTL’s List32 and List64 are not tuned for a 32 or 64-bit OS. They only differ in their maximum size: List32’s maximum size is around 2 billion elements (Int32.MaxValue), while List64’s maximum size is around 281 trillion elements (2^48). We use the .NET List and PTL List64 containers in this demo because List64 is more complex due to its very large capacity.

In this demo, both lists contain 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).

First, we added 100 million elements one-by-one to an empty .NET List and an empty PTL List64. The Add function for the PTL List64 finished properly in 1 second, but the Add function of the .NET List failed with the following error: “the array dimensions exceeded the supported range.”

This error occurred because you can’t allocate a contiguous chunk of memory larger than 2 GB in Visual Studio 2010 or earlier versions, and the capacity of the .NET List grew to 2 GB. PTL uses a superior memory management scheme for its containers, so the PTL List64 did not exceed 2 GB.

The capacity of the .NET List grew to 2 GB due to its container resizing scheme. In order to make containers resizable, most standard libraries use the following method when the container grows beyond its current maximum size: a new container is created with a doubled maximum size, the elements are copied to this new container and the old container is destroyed. This method is used in .NET, and Java uses a similar method where the size of the new container is 1.5 times the previous size.

This method is widely adopted because of its simplicity and because it’s extremely efficient in calculating the address of any element in the container (the element index is multiplied by the number of bytes per element). However, it uses memory quite inefficiently and can decrease performance if it triggers the garbage collector when the old container is destroyed.

PTL’s resizing algorithm is much more complex but also very efficient in memory usage due to an innovative architecture on which all of PTL’s containers are based. PTL’s containers can grow efficiently in small increments to very large sizes, so they are especially useful for very large data sets. That’s why the PTL List64 didn’t fail when we added 100 million elements.

In Visual Studio 2012 or later versions, we can add the following element to the App.config file to allow allocating a contiguous chunk of memory larger than 2 GB on 64-bit platforms.

<configuration>
       <runtime>
              <gcAllowVeryLargeObjects enabled="true"/>
       </runtime>
</configuration>

In our demo, we made this change in order to fix the .NET List error and continue our execution. It’s important to note that this change isn’t needed at all for the PTL List64 due to its different architecture.

After this change, we added 600 million and 1.1 billion elements one-by-one to both a .NET List and a PTL List64 in order to show the drastic difference in memory usage between the two containers (see the chart below). The PTL List64 memory footprint is never much larger than the actual size of the container’s data. PTL’s internal container architecture can grow in small increments and doesn’t waste memory.

.NET List vs. PTL List64 - Memory Usage

The memory management scheme for the .NET List actually resulted in a large decrease in speed when we added 1.1 billion elements to the list. During the Add function’s execution, the capacity of the .NET List grew to 31.98 GB, and our system only had 32 GB of memory. Then, the speed of the addition really decreased because the operating system had to swap memory pages on the hard drive. Therefore, the Add function of the PTL List64 was 4.6 times faster than the Add function of the .NET List for 1.1 billion elements (see the chart below).

.NET List vs. PTL List64 - 1.1 Billion Elements

You may be able to use memory more efficiently by setting the Capacity property of the .NET List to a certain size. In practice, this is a burden for developers, and the same problem will occur again if the list size exceeds the new capacity. Also, when the value of Capacity is set explicitly, the internal array is reallocated to accommodate the new capacity, and all the elements are copied. PTL containers don’t implement the Capacity property because PTL handles these complexities internally to make it easier on developers.

During our demo, we also added only 600 million elements to an empty .NET List and an empty PTL List64. This allowed the .NET List to fit in memory, so we’d have a fair comparison with the PTL List64. Now, the Add function of the PTL List64 was 1.4 times faster than the Add function of the .NET List (see the chart below).

While we had the 600 million elements loaded into our .NET List and our PTL List64, we also retrieved each element in a random order using the Item property. Both the .NET List and PTL List64 retrieved all 600 million elements in only 3 seconds (see the chart below). PTL’s address calculation is much more complex than the simple multiplication used by the .NET List due to PTL’s more complex container architecture. However, the speed of the PTL List64 is still excellent and was not sacrificed to implement our superior memory management scheme.

.NET List vs. PTL List 64 - 600 Million Elements

PTL’s List classes are well designed to sustain large data sets. During this demo, we showed you how PTL’s container architecture results in better memory management and increased performance, while the .NET List is poor in memory allocation and can generate unexpected problems.

If you’re ready to take advantage of PTL’s Containers, you can download a free trial today. Also, stay tuned for more blog posts with PTL videos. 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 soon.

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>