Changes in / [0bd6a14:e9c5db2]

File:

• doc/theses/mubeen_zulfiqar_MMath/performance.tex (modified) (15 diffs)

doc/theses/mubeen_zulfiqar_MMath/performance.tex

@@ -140 +140 @@
 
 All allocators did well in this micro-benchmark, except for \textsf{dl} on the ARM.
-\textsf{dl}'s performace decreases and the difference with the other allocators starts increases as the number of worker threads increase.
-\textsf{je} was the fastest, although there is not much difference between \textsf{je} and rest of the allocators.
-
 llheap is slightly slower because it uses ownership, where many of the allocations have remote frees, which requires locking.
 When llheap is compiled without ownership, its performance is the same as the other allocators (not shown).
 
+
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 %% THRASH
@@ -151 +149 @@
 
 \subsection{Cache Thrash}
-\label{sec:cache-thrash-perf}
 
 Thrash tests memory allocators for active false sharing (see \VRef{sec:benchThrashSec}).
@@ -182 +179 @@
 \end{figure}
 
-All allocators did well in this micro-benchmark, except for \textsf{dl} and \textsf{pt3}.
-\textsf{dl} uses a single heap for all threads so it is understable that it is generating so much active false-sharing.
-Requests from different threads will be dealt with sequientially by a single heap using locks which can allocate objects to different threads on the same cache line.
-\textsf{pt3} uses multiple heaps but it is not exactly per-thread heap.
-So, it is possible that multiple threads using one heap can get objects allocated on the same cache line which might be causing active false-sharing.
-Rest of the memory allocators generate little or no active false-sharing.
+All allocators did well in this micro-benchmark, except for \textsf{dl} and \textsf{pt3} on the x64.
+Either the memory allocators generate little active false-sharing or the micro-benchmark is not generating scenarios that cause active false-sharing.
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
@@ -224 +217 @@
 \end{figure}
 
-This micro-benchmark divided the allocators in 2 groups.
-First is the group of best performers \textsf{llh}, \textsf{je}, and \textsf{rp}.
-These memory alloctors generate little or no passive false-sharing and their performance difference is negligible.
-Second is the group of the low performers which includes rest of the memory allocators.
-These memory allocators seem to preserve program-induced passive false-sharing.
-\textsf{hrd}'s performance keeps getting worst as the number of threads increase.
-
-Interestingly, allocators such as \textsf{hrd} and \textsf{glc} were among the best performers in micro-benchmark cache thrash as described in section \ref{sec:cache-thrash-perf}.
-But, these allocators were among the low performers in this micro-benchmark.
-It tells us that these allocators do not actively produce false-sharing but they may preserve program-induced passive false sharing.
+All allocators did well in this micro-benchmark on the ARM.
+Allocators \textsf{llh}, \textsf{je}, and \textsf{rp} did well on the x64, while the remaining allocators experienced significant slowdowns from the false sharing.
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
@@ -289 +274 @@
 
 All allocators did well in this micro-benchmark across all allocation chains, except for \textsf{dl} and \textsf{pt3}.
-\textsf{dl} performed the lowest overall and its performce kept getting worse with increasing number of threads.
-\textsf{dl} uses a single heap with a global lock that can become a bottleneck.
-Multiple threads doing memory allocation in parallel can create contention on \textsf{dl}'s single heap.
-\textsf{pt3} which is a modification of \textsf{dl} for multi-threaded applications does not use per-thread heaps and may also have similar bottlenecks.
-
-There's a sudden increase in program completion time of chains that include \textsf{calloc} and all allocators perform relatively slower in these chains including \textsf{calloc}.
-\textsf{calloc} uses \textsf{memset} to set the allocated memory to zero.
-\textsf{memset} is a slow routine which takes a long time compared to the actual memory allocation.
-So, a major part of the time is taken for \textsf{memset} in performance of chains that include \textsf{calloc}.
-But the relative difference among the different memory allocators running the same chain of memory allocation operations still gives us an idea of theor relative performance.
 
 %speed-3-malloc.eps
@@ -527 +502 @@
 First, the differences in the shape of the curves between architectures (top ARM, bottom x64) is small, where the differences are in the amount of memory used.
 Hence, it is possible to focus on either the top or bottom graph.
-The heap curve is remains zero for 4 memory allocators: \textsf{hrd}, \textsf{je}, \textsf{pt3}, and \textsf{rp}.
-These memory allocators are not using the sbrk area, instead they only use mmap to get memory from the system.
-
-\textsf{hrd}, and \textsf{tbb} have higher memory footprint than the others as they use more total dynamic memory.
-One reason for that can be the usage of superblocks as both of these memory allocators create superblocks where each block contains objects of the same size.
-These superblocks are maintained throughout the life of the program.
-
-\textsf{pt3} is the only memory allocator for which the total dynamic memory goes down in the second half of the program lifetime when the memory is freed by the benchmark program.
-It makes pt3 the only memory allocator that gives memory back to operating system as it is freed by the program.
-
-% FOR 1 THREAD
+The heap curve It is possible glib, hoard, jemalloc, ptmalloc3, rpmalloc do not use the sbrk area => only uses mmap.
+
+hoard, tbbmalloc uses more total memory
+
+ptmalloc3 gives memory back to operating system
 
 %mem-1-prod-1-cons-100-llh.eps
@@ -544 +513 @@
     \subfigure[Algol]{ \includegraphics[width=0.95\textwidth]{evaluations/algol-perf-eps/mem-1-prod-1-cons-100-llh} }
     \subfigure[Nasus]{ \includegraphics[width=0.95\textwidth]{evaluations/nasus-perf-eps/mem-1-prod-1-cons-100-llh} }
-\caption{Memory benchmark results with Configuration-1 for llh memory allocator}
+\caption{Memory benchmark results with 1 producer for llh memory allocator}
 \label{fig:mem-1-prod-1-cons-100-llh}
+\end{figure}
+
+%mem-4-prod-4-cons-100-llh.eps
+\begin{figure}
+\centering
+    \subfigure[Algol]{ \includegraphics[width=0.95\textwidth]{evaluations/algol-perf-eps/mem-4-prod-4-cons-100-llh} }
+    \subfigure[Nasus]{ \includegraphics[width=0.95\textwidth]{evaluations/nasus-perf-eps/mem-4-prod-4-cons-100-llh} }
+\caption{Memory benchmark results with 4 producers for llh memory allocator}
+\label{fig:mem-4-prod-4-cons-100-llh}
 \end{figure}
 
@@ -553 +531 @@
     \subfigure[Algol]{ \includegraphics[width=0.95\textwidth]{evaluations/algol-perf-eps/mem-1-prod-1-cons-100-dl} }
     \subfigure[Nasus]{ \includegraphics[width=0.95\textwidth]{evaluations/nasus-perf-eps/mem-1-prod-1-cons-100-dl} }
-\caption{Memory benchmark results with Configuration-1 for dl memory allocator}
+\caption{Memory benchmark results with 1 producer for dl memory allocator}
 \label{fig:mem-1-prod-1-cons-100-dl}
+\end{figure}
+
+%mem-4-prod-4-cons-100-dl.eps
+\begin{figure}
+\centering
+    \subfigure[Algol]{ \includegraphics[width=0.95\textwidth]{evaluations/algol-perf-eps/mem-4-prod-4-cons-100-dl} }
+    \subfigure[Nasus]{ \includegraphics[width=0.95\textwidth]{evaluations/nasus-perf-eps/mem-4-prod-4-cons-100-dl} }
+\caption{Memory benchmark results with 4 producers for dl memory allocator}
+\label{fig:mem-4-prod-4-cons-100-dl}
 \end{figure}
 
@@ -562 +549 @@
     \subfigure[Algol]{ \includegraphics[width=0.95\textwidth]{evaluations/algol-perf-eps/mem-1-prod-1-cons-100-glc} }
     \subfigure[Nasus]{ \includegraphics[width=0.95\textwidth]{evaluations/nasus-perf-eps/mem-1-prod-1-cons-100-glc} }
-\caption{Memory benchmark results with Configuration-1 for glibc memory allocator}
+\caption{Memory benchmark results with 1 producer for glibc memory allocator}
 \label{fig:mem-1-prod-1-cons-100-glc}
+\end{figure}
+
+%mem-4-prod-4-cons-100-glc.eps
+\begin{figure}
+\centering
+    \subfigure[Algol]{ \includegraphics[width=0.95\textwidth]{evaluations/algol-perf-eps/mem-4-prod-4-cons-100-glc} }
+    \subfigure[Nasus]{ \includegraphics[width=0.95\textwidth]{evaluations/nasus-perf-eps/mem-4-prod-4-cons-100-glc} }
+\caption{Memory benchmark results with 4 producers for glibc memory allocator}
+\label{fig:mem-4-prod-4-cons-100-glc}
 \end{figure}
 
@@ -571 +567 @@
     \subfigure[Algol]{ \includegraphics[width=0.95\textwidth]{evaluations/algol-perf-eps/mem-1-prod-1-cons-100-hrd} }
     \subfigure[Nasus]{ \includegraphics[width=0.95\textwidth]{evaluations/nasus-perf-eps/mem-1-prod-1-cons-100-hrd} }
-\caption{Memory benchmark results with Configuration-1 for hoard memory allocator}
+\caption{Memory benchmark results with 1 producer for hoard memory allocator}
 \label{fig:mem-1-prod-1-cons-100-hrd}
+\end{figure}
+
+%mem-4-prod-4-cons-100-hrd.eps
+\begin{figure}
+\centering
+    \subfigure[Algol]{ \includegraphics[width=0.95\textwidth]{evaluations/algol-perf-eps/mem-4-prod-4-cons-100-hrd} }
+    \subfigure[Nasus]{ \includegraphics[width=0.95\textwidth]{evaluations/nasus-perf-eps/mem-4-prod-4-cons-100-hrd} }
+\caption{Memory benchmark results with 4 producers for hoard memory allocator}
+\label{fig:mem-4-prod-4-cons-100-hrd}
 \end{figure}
 
@@ -580 +585 @@
     \subfigure[Algol]{ \includegraphics[width=0.95\textwidth]{evaluations/algol-perf-eps/mem-1-prod-1-cons-100-je} }
     \subfigure[Nasus]{ \includegraphics[width=0.95\textwidth]{evaluations/nasus-perf-eps/mem-1-prod-1-cons-100-je} }
-\caption{Memory benchmark results with Configuration-1 for je memory allocator}
+\caption{Memory benchmark results with 1 producer for je memory allocator}
 \label{fig:mem-1-prod-1-cons-100-je}
+\end{figure}
+
+%mem-4-prod-4-cons-100-je.eps
+\begin{figure}
+\centering
+    \subfigure[Algol]{ \includegraphics[width=0.95\textwidth]{evaluations/algol-perf-eps/mem-4-prod-4-cons-100-je} }
+    \subfigure[Nasus]{ \includegraphics[width=0.95\textwidth]{evaluations/nasus-perf-eps/mem-4-prod-4-cons-100-je} }
+\caption{Memory benchmark results with 4 producers for je memory allocator}
+\label{fig:mem-4-prod-4-cons-100-je}
 \end{figure}
 
@@ -589 +603 @@
     \subfigure[Algol]{ \includegraphics[width=0.95\textwidth]{evaluations/algol-perf-eps/mem-1-prod-1-cons-100-pt3} }
     \subfigure[Nasus]{ \includegraphics[width=0.95\textwidth]{evaluations/nasus-perf-eps/mem-1-prod-1-cons-100-pt3} }
-\caption{Memory benchmark results with Configuration-1 for pt3 memory allocator}
+\caption{Memory benchmark results with 1 producer for pt3 memory allocator}
 \label{fig:mem-1-prod-1-cons-100-pt3}
+\end{figure}
+
+%mem-4-prod-4-cons-100-pt3.eps
+\begin{figure}
+\centering
+    \subfigure[Algol]{ \includegraphics[width=0.95\textwidth]{evaluations/algol-perf-eps/mem-4-prod-4-cons-100-pt3} }
+    \subfigure[Nasus]{ \includegraphics[width=0.95\textwidth]{evaluations/nasus-perf-eps/mem-4-prod-4-cons-100-pt3} }
+\caption{Memory benchmark results with 4 producers for pt3 memory allocator}
+\label{fig:mem-4-prod-4-cons-100-pt3}
 \end{figure}
 
@@ -598 +621 @@
     \subfigure[Algol]{ \includegraphics[width=0.95\textwidth]{evaluations/algol-perf-eps/mem-1-prod-1-cons-100-rp} }
     \subfigure[Nasus]{ \includegraphics[width=0.95\textwidth]{evaluations/nasus-perf-eps/mem-1-prod-1-cons-100-rp} }
-\caption{Memory benchmark results with Configuration-1 for rp memory allocator}
+\caption{Memory benchmark results with 1 producer for rp memory allocator}
 \label{fig:mem-1-prod-1-cons-100-rp}
+\end{figure}
+
+%mem-4-prod-4-cons-100-rp.eps
+\begin{figure}
+\centering
+    \subfigure[Algol]{ \includegraphics[width=0.95\textwidth]{evaluations/algol-perf-eps/mem-4-prod-4-cons-100-rp} }
+    \subfigure[Nasus]{ \includegraphics[width=0.95\textwidth]{evaluations/nasus-perf-eps/mem-4-prod-4-cons-100-rp} }
+\caption{Memory benchmark results with 4 producers for rp memory allocator}
+\label{fig:mem-4-prod-4-cons-100-rp}
 \end{figure}
 
@@ -607 +639 @@
     \subfigure[Algol]{ \includegraphics[width=0.95\textwidth]{evaluations/algol-perf-eps/mem-1-prod-1-cons-100-tbb} }
     \subfigure[Nasus]{ \includegraphics[width=0.95\textwidth]{evaluations/nasus-perf-eps/mem-1-prod-1-cons-100-tbb} }
-\caption{Memory benchmark results with Configuration-1 for tbb memory allocator}
+\caption{Memory benchmark results with 1 producer for tbb memory allocator}
 \label{fig:mem-1-prod-1-cons-100-tbb}
-\end{figure}
-
-% FOR 4 THREADS
-
-%mem-4-prod-4-cons-100-llh.eps
-\begin{figure}
-\centering
-    \subfigure[Algol]{ \includegraphics[width=0.95\textwidth]{evaluations/algol-perf-eps/mem-4-prod-4-cons-100-llh} }
-    \subfigure[Nasus]{ \includegraphics[width=0.95\textwidth]{evaluations/nasus-perf-eps/mem-4-prod-4-cons-100-llh} }
-\caption{Memory benchmark results with Configuration-2 for llh memory allocator}
-\label{fig:mem-4-prod-4-cons-100-llh}
-\end{figure}
-
-%mem-4-prod-4-cons-100-dl.eps
-\begin{figure}
-\centering
-    \subfigure[Algol]{ \includegraphics[width=0.95\textwidth]{evaluations/algol-perf-eps/mem-4-prod-4-cons-100-dl} }
-    \subfigure[Nasus]{ \includegraphics[width=0.95\textwidth]{evaluations/nasus-perf-eps/mem-4-prod-4-cons-100-dl} }
-\caption{Memory benchmark results with Configuration-2 for dl memory allocator}
-\label{fig:mem-4-prod-4-cons-100-dl}
-\end{figure}
-
-%mem-4-prod-4-cons-100-glc.eps
-\begin{figure}
-\centering
-    \subfigure[Algol]{ \includegraphics[width=0.95\textwidth]{evaluations/algol-perf-eps/mem-4-prod-4-cons-100-glc} }
-    \subfigure[Nasus]{ \includegraphics[width=0.95\textwidth]{evaluations/nasus-perf-eps/mem-4-prod-4-cons-100-glc} }
-\caption{Memory benchmark results with Configuration-2 for glibc memory allocator}
-\label{fig:mem-4-prod-4-cons-100-glc}
-\end{figure}
-
-%mem-4-prod-4-cons-100-hrd.eps
-\begin{figure}
-\centering
-    \subfigure[Algol]{ \includegraphics[width=0.95\textwidth]{evaluations/algol-perf-eps/mem-4-prod-4-cons-100-hrd} }
-    \subfigure[Nasus]{ \includegraphics[width=0.95\textwidth]{evaluations/nasus-perf-eps/mem-4-prod-4-cons-100-hrd} }
-\caption{Memory benchmark results with Configuration-2 for hoard memory allocator}
-\label{fig:mem-4-prod-4-cons-100-hrd}
-\end{figure}
-
-%mem-4-prod-4-cons-100-je.eps
-\begin{figure}
-\centering
-    \subfigure[Algol]{ \includegraphics[width=0.95\textwidth]{evaluations/algol-perf-eps/mem-4-prod-4-cons-100-je} }
-    \subfigure[Nasus]{ \includegraphics[width=0.95\textwidth]{evaluations/nasus-perf-eps/mem-4-prod-4-cons-100-je} }
-\caption{Memory benchmark results with Configuration-2 for je memory allocator}
-\label{fig:mem-4-prod-4-cons-100-je}
-\end{figure}
-
-%mem-4-prod-4-cons-100-pt3.eps
-\begin{figure}
-\centering
-    \subfigure[Algol]{ \includegraphics[width=0.95\textwidth]{evaluations/algol-perf-eps/mem-4-prod-4-cons-100-pt3} }
-    \subfigure[Nasus]{ \includegraphics[width=0.95\textwidth]{evaluations/nasus-perf-eps/mem-4-prod-4-cons-100-pt3} }
-\caption{Memory benchmark results with Configuration-2 for pt3 memory allocator}
-\label{fig:mem-4-prod-4-cons-100-pt3}
-\end{figure}
-
-%mem-4-prod-4-cons-100-rp.eps
-\begin{figure}
-\centering
-    \subfigure[Algol]{ \includegraphics[width=0.95\textwidth]{evaluations/algol-perf-eps/mem-4-prod-4-cons-100-rp} }
-    \subfigure[Nasus]{ \includegraphics[width=0.95\textwidth]{evaluations/nasus-perf-eps/mem-4-prod-4-cons-100-rp} }
-\caption{Memory benchmark results with Configuration-2 for rp memory allocator}
-\label{fig:mem-4-prod-4-cons-100-rp}
 \end{figure}
 
@@ -681 +648 @@
     \subfigure[Algol]{ \includegraphics[width=0.95\textwidth]{evaluations/algol-perf-eps/mem-4-prod-4-cons-100-tbb} }
     \subfigure[Nasus]{ \includegraphics[width=0.95\textwidth]{evaluations/nasus-perf-eps/mem-4-prod-4-cons-100-tbb} }
-\caption{Memory benchmark results with Configuration-2 for tbb memory allocator}
+\caption{Memory benchmark results with 4 producers for tbb memory allocator}
 \label{fig:mem-4-prod-4-cons-100-tbb}
 \end{figure}
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%% ANALYSIS
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%