Changeset 0c1f3a6

Timestamp:

Jun 8, 2021, 4:36:55 PM (3 years ago)

Author:

m3zulfiq <m3zulfiq@…>

Branches:

ADT, ast-experimental, enum, forall-pointer-decay, jacob/cs343-translation, master, new-ast-unique-expr, pthread-emulation, qualifiedEnum

Children:

e056330

Parents:

dac16a0

Message:

added benchmarks -> performance matrices of memeory allocator -> memory overhead

File:

• doc/theses/mubeen_zulfiqar_MMath/benchmarks.tex (modified) (1 diff)

doc/theses/mubeen_zulfiqar_MMath/benchmarks.tex

@@ -34 +34 @@
 \noindent
 ====================
+
+\section Performance Matrices of Memory Allocators
+
+When it comes to memory allocators, there are no set standards of performance. Performance of a memory allocator depends highly on the usage pattern of the application. A memory allocator that is the best performer for a certain application X might be the worst for some other application which has completely different memory usage pattern compared to the application X. It is extremely difficult to make one universally best memory allocator which will outperform every other memory allocator for every usage pattern. So, there is a lack of a set of standard benchmarks that are used to evaluate a memory allocators's performance.
+
+If we breakdown the goals of a memory allocator, there are two basic matrices on which a memory allocator's performance is evaluated.
+
+1. Memory Overhead
+2. Speed
+
+        /subsection Memory Overhead
+
+        Memory overhead is the extra memory that a memory allocator takes from OS which is not requested by the application. Ideally, an allocator should get just enough memory from OS that can fulfill application's request and should return this memory to OS as soon as applications frees it. But, allocators retain more memory compared to what application has asked for which causes memory overhead. Memory overhead can happen for various reasons.
+
+                /subsubsection Fragmentation
+                Fragmentation is one of the major reasons behind memory overhead. Fragmentation happens because of situations that are either necassary for proper functioning of the allocator such as internal memory management and book-keeping or are out of allocator's control such as application's usage pattern.
+
+                        /subsubsubsection Internal Fragmentation
+                        For internal book-keeping, allocators divide raw memory given by OS into chunks, blocks, or lists that can fulfill application's requested size. Allocators use memory given by OS for creating headers, footers etc. to store information about these chunks, blocks, or lists. This increases usage of memory in-addition to the memory requested by application as the allocators need to store their book-keeping information. This extra usage of memory for allocator's own book-keeping is called Internal Fragmentation. Although it cases memory overhead but this overhead is necassary for an allocator's proper funtioning.
+
+
+*** Insert a figure of internal fragmentation with explanation
+
+                        /subsubsubsection External Fragmentation
+                        External fragmentation is the free bits of memory between or around chunks of memory that are currently in-use of the application. Segmentation in memory due to application's usage pattern causes external fragmentation. The memory which is part of external fragmentation is completely free as it is neither used by allocator's internal book-keeping nor by the application. Ideally, an allocator should return a segment of memory back to the OS as soon as application frees it. But, this is not always the case. Allocators get memory from OS in one of the two ways.
+
+                        \begin{itemize}
+                        \item
+                        MMap: an allocator can ask OS for whole pages in mmap area. Then, the allocator segments the page internally and fulfills application's request.
+                        \item
+                        Heap: an allocator can ask OS for memory in heap area using system calls such as sbrk. Heap are grows downwards and shrinks upwards.
+                        \begin{itemize}
+
+                        If an allocator uses mmap area, it can only return extra memory back to OS if the whole page is free i.e. no chunk on the page is in-use of the application. Even if one chunk on the whole page is currently in-use of the application, the allocator has to retain the whole page.
+
+                        If an allocator uses the heap area, it can only return the continous free memory at the end of the heap area that is currently in allocator's possession as heap area shrinks upwards. If there are free bits of memory in-between chunks of memory that are currently in-use of the application, the allocator can not return these free bits.
+
+*** Insert a figure of above scenrio with explanation
+
+                        Even if the entire heap area is free except one small chunk at the end of heap area that is being used by the application, the allocator cannot return the free heap area back to the OS as it is not a continous region at the end of heap area.
+
+*** Insert a figure of above scenrio with explanation
+
+                        Such scenerios cause external fragmentation but it is out of the allocator's control and depend on application's usage pattern.
+
+                /subsubsection Internal Memory Management
+                Allocators such as je-malloc (FIX ME: insert reference) pro-actively get some memory from the OS and divide it into chunks of certain sizes that can be used in-future to fulfill application's request. This causes memory overhead as these chunks are made before application's request. There is also the possibility that an application may not even request memory of these sizes during their whole life-time.
+
+*** Insert a figure of above scenrio with explanation
+
+                Allocators such as rp-malloc (FIX ME: insert reference) maintain lists or blocks of sized memory segments that is freed by the application for future use. These lists are maintained without any guarantee that application will even request these sizes again.
+
+                Such tactics are usually used to gain speed as allocator will not have to get raw memory from OS and manage it at the time of application's request but they do cause memory overhead.
+
+        Fragmentation and managed sized chunks of free memory can lead to Heap Blowup as the allocator may not be able to use the fragments or sized free chunks of free memory to fulfill application's requests of other sizes.
+
+        /subsection Speed
+