Changeset 1bb633b


Ignore:
Timestamp:
Jun 10, 2021, 5:41:09 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:
2fc2262
Parents:
1c54958
Message:

added benchmarks -> performance matrices of memeory allocator -> speed

File:
1 edited

Legend:

Unmodified
Added
Removed

  • doc/theses/mubeen_zulfiqar_MMath/benchmarks.tex

    r1c54958 r1bb633b  
    4545
    4646        /subsection Memory Overhead
    47 
    4847        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.
    4948
    … …  
    5554
    5655
    57 *** Insert a figure of internal fragmentation with explanation
     56*** FIX ME: Insert a figure of internal fragmentation with explanation
    5857
    5958                        /subsubsubsection External Fragmentation
    … …  
    7170                        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.
    7271
    73 *** Insert a figure of above scenrio with explanation
     72*** FIX ME: Insert a figure of above scenrio with explanation
    7473
    7574                        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.
    7675
    77 *** Insert a figure of above scenrio with explanation
     76*** FIX ME: Insert a figure of above scenrio with explanation
    7877
    7978                        Such scenerios cause external fragmentation but it is out of the allocator's control and depend on application's usage pattern.
    … …  
    8281                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.
    8382
    84 *** Insert a figure of above scenrio with explanation
     83*** FIX ME: Insert a figure of above scenrio with explanation
    8584
    8685                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.
    … …  
    9190
    9291        /subsection Speed
     92        When it comes to performance evaluation of any piece of software, its runtime is usually the first thing that is evaluated. The same is true for memory allocators but, in case of memory allocators, speed does not only mean the runtime of memory allocator's routines but there are other factors too.
    9393
     94                /subsubsection Runtime Speed
     95                Low runtime is the main goal of a memory allocator when it comes it proving its speed. Runtime is the time that it takes for a routine of memory allocator to complete its execution. As mentioned in (FIX ME: refernce to routines' list), there four basic routines that are used in memory allocation. Ideally, each routine of a memory allocator should be fast. Some memory allocator designs use pro-active measures (FIX ME: local refernce) to gain speed when allocating some memory to the application. Some memory allocators do memory allocation faster than memory freeing (FIX ME: graph refernce) while others show similar speed whether memory is allocated or freed.
     96
     97                /subsubsection Memory Access Speed
     98                Runtime speed is not the only speed matrix in memory allocators. The memory that a memory allocator has allocated to the application also needs to be accessible as quick as possible. The application should be able to read/write allocated memory quickly. The allocation method of a memory allocator may introduce some delays when it comes to memory access speed, which is specially important in concurrent applications. Ideally, a memory allocator should allocate all memory on a cache-line to only one thread and no cache-line should be shared among multiple threads. If a memory allocator allocates memory to multple threads on a same cache line, then cache may get invalidated more frequesntly when two different threads running on two different processes will try to read/write the same memory region. On the other hand, if one cache-line is used by only one thread then the cache may get invalidated less frequently. This sharing of one cache-line among multiple threads is called false sharing (FIX ME: cite wasik).
     99
     100                        /subsubsubsection Active False Sharing
     101                        Active false sharing is the sharing of one cache-line among multiple threads that is caused by memory allocator. It happens when two threads request memory from memory allocator and the allocator allocates memory to both of them on the same cache-line. After that, if the threads are running on different processes who have their own caches and both threads start reading/writing the allocated memory simultanously, their caches will start getting invalidated every time the other thread writes something to the memory. This will cause the application to slow down as the process has to load cache much more frequently.
     102
     103*** FIX ME: Insert a figure of above scenrio with explanation
     104
     105                        /subsubsubsection Passive False Sharing
     106                        Passive false sharing is the kind of false sharing which is caused by the application and not the memory allocator. The memory allocator may preservce passive false sharing in future instead of eradicating it. But, passive false sharing is initiated by the application.
     107
     108                                /subsubsubsubsection Program Induced Passive False Sharing
     109                                Program induced false sharing is completely out of memory allocator's control and is purely caused by the application. When a thread in the application creates multiple objects in the dynamic area and allocator allocates memory for these objects on the same cache-line as the objects are created by the same thread. Passive false sharing will occur if this thread passes one of these objects to another thread but it retains the rest of these objects or it passes some/all of the remaining objects to some third thread(s). Now, one cache-line is shared among multiple threads but it is caused by the application and not the allocator. It is out of allocator's control and has the similar performance impact as Active False Sharing (FIX ME: cite local) if these threads, who are sharing the same cache-line, start reading/writing the given objects simultanously.
     110
     111*** FIX ME: Insert a figure of above scenrio 1 with explanation
     112
     113*** FIX ME: Insert a figure of above scenrio 2 with explanation
     114
     115                                /subsubsubsubsection Program Induced Allocator Preserved Passive False Sharing
     116                                Program induced allocator preserved passive false sharing is another interesting case of passive false sharing. Both the application and the allocator are partially responsible for it. It starts the same as Program Induced False Sharing (FIX ME: cite local). Once, an application thread has created multiple dynamic objects on the same cache-line and ditributed these objects among multiple threads causing sharing of one cache-line among multiple threads (Program Induced Passive False Sharing). This kind of false sharing occurs when one of these threads, which got the object on the shared cache-line, frees the passed object then re-allocates another object but the allocator returns the same object (on the shared cache-line) that this thread just freed. Although, the application caused the false sharing to happen in the frst place however, to prevent furthur false sharing, the allocator should have returned the new object on some other cache-line which is only shared by the allocating thread. When it comes to performnce impact, this passive false sharing will slow down the application just like any other kind of false sharing if the threads sharing the cache-line start reading/writing the objects simultanously.
     117
     118*** FIX ME: Insert a figure of above scenrio with explanation
Note: See TracChangeset for help on using the changeset viewer.