How to correctly simulate memory allocation behavior of applications by calibrating main memory stubs

Trapp, Peter; Meyer, Markus; Facchi, Christian Working Paper How to correctly simulate memory allocation behavior of applications by calibrating main memory stubs Arbeitsberichte - Working Papers, No. 20 Provided in Cooperation with: Technische Hochschule Ingolstadt (THI) Suggested Citation: Trapp, Peter; Meyer, Markus; Facchi, Christian (2011) : How to correctly simulate memory allocation behavior of applications by calibrating main memory stubs, Arbeitsberichte - Working Papers, No. 20, Hochschule Ingolstadt - University of Applied Sciences, Ingolstadt, https://nbn-resolving.de/urn:nbn:de:bvb:573-360 This Version is available at: https://hdl.handle.net/10419/202572 Standard-Nutzungsbedingungen: Die Dokumente auf EconStor dürfen zu eigenen wissenschaftlichen Zwecken und zum Privatgebrauch gespeichert und kopiert werden. Sie dürfen die Dokumente nicht für öffentliche oder kommerzielle Zwecke vervielfältigen, öffentlich ausstellen, öffentlich zugänglich machen, vertreiben oder anderweitig nutzen. Sofern die Verfasser die Dokumente unter Open-Content-Lizenzen (insbesondere CC-Lizenzen) zur Verfügung gestellt haben sollten, gelten abweichend von diesen Nutzungsbedingungen die in der dort genannten Lizenz gewährten Nutzungsrechte. Terms of use: Documents in EconStor may be saved and copied for your personal and scholarly purposes. You are not to copy documents for public or commercial purposes, to exhibit the documents publicly, to make them publicly available on the internet, or to distribute or otherwise use the documents in public. If the documents have been made available under an Open Content Licence (especially Creative Commons Licences), you may exercise further usage rights as specified in the indicated licence. https://creativecommons.org/licenses/by-nc-nd/3.0/de/ Working Papers Arbeitsberichte How to Correctly Simulate Memory Allocation Behavior of Applications by Calibrating Main Memory Stubs Peter Trapp, Markus Meyer and Christian Facchi How to Correctly Simulate Memory Allocation Behavior of Applications by Calibrating Main Memory Stubs Peter Trapp, Markus Meyer, and Christian Facchi University of Applied Sciences Ingolstadt Ingolstadt, Germany {trapp,meyerma,facchi}@haw-ingolstadt.de March 2011 Abstract Dynamic performance stubs provide a framework to simulate the performance behavior of software modules and functions. Hence, they can be used as an extension to software performance engineering methodologies. The methodology of dynamic performance stubs targets to gain oriented performance improvement. Other applications include the identification of “hidden” bottlenecks and the prioritization of optimization alternatives. Main memory stubs have been developed to extend the simulation possibilities of the dynamic performance stubs framework. They are able to simulate the heap and stack behavior of software modules or functions. This paper extends and improves the simulation algorithm to be able to simulate constant stack values. Moreover, it presents calibration possibilities to improve the simulation results by determining the various overhead in the algorithm. The results are furthermore used to compensate inaccuracies in the simulation. Additionally, a proof of concept is given as validation of the results. This paper shows that, main memory stubs can be used to simulate the heap, stack and timing behavior exactly when considering the parameters determined by the calibration functions. Keywords:Memory Systems; Software Performance, Evaluation and Testing; Modeling; Performance Optimization, Bounds, and Models; Case Studies 1 1 Introduction Dynamic performance stubs have been introduced in [1]. They can be used for the detection of “hidden” bottlenecks. By demonstrating the optimization potential of the detected bottleneck a cost-benefit analysis can be performed, leading to a gain-oriented approach to performance optimizations. In the past, performance increases in many system architectures have been achieved by higher CPU speeds, and more recently, by using multiple cores. Yet, the memory speed and, hence, the memory access times, did not increase to the same order as the CPUs frequencies. This has lead to a situation in which many systems are heavily memory bound and, consequently, software performance optimization studies are often targeting an improvement of the memory usage. The methodology of dynamic performance stubs can be used to optimize these memory bound systems by using main memory stubs. 1.1 Dynamic Performance Stubs The idea behind dynamic performance stubs is a combination of performance improvements [2–4] in already existing modules or functions and the stubbing mechanism from software testing [5,6]. The performance behavior of the component under study (CUS) will be determined and replaced by a dynamic performance stub. This stub can be parameterized to simulate different performance behaviors. Typically, the CUS is the part of the software under test (SUT) that has been identified as a potential performance bottleneck. The optimization expert can use dynamic performance stubs to analyze the performance of the SUT. This procedure relates to stubbing a single software unit. Hence, it will be called “local”. Therefore, a “local stub” has to be built. The dynamic performance stub can also be used to change the behavior of the complete system. A software module has to be created, which interacts “globally” in the sense of influencing the whole system instead of a single software component. This stub will be called a “global stub”. Figure 1 sketches the design and the interaction between a real system on the left and the dynamic performance stubs on the right side. The unfilled arrowhead indicates a replacement. Filled arrowheads describe the extension of a unit by this feature and the dashed block provides an additional functionality to the dynamic performance stub and will not really replace a software unit. In the context of dynamic performance stubs, the system under test is a software module or function, which includes a software performance bottleneck. The framework of the dynamic performance stub consists of the following 2 system software component (SUT) bottleneck (CUS) dynamic performance stub (local) performance simulation functions (PSF) simulated software functionality (SSF) performance measurement functions (PMF) calibration functions (CF) dynamic performance stub (global) Figure 1: Interactions of “Dynamic Performance Stubs” parts, which is presented in Figure 1: Simulated Software Functionality (SSF). The simulated software functionality is used to simulate the functional behavior of a component under study or a software performance bottleneck. This can be achieved by generating valid output values for dedicated input values without executing the original functionality. Another possibility is to simulate different states of objects inside of the component under study. Hence, the application can be executed without the original functionality as it is realized by the simulated software functionality. Performance Simulation Functions (PSF). Performance simulation functions provide the ability to simulate the performance behavior of the replaced CUS, and are divided into four categories: “CPU”, “Memory”, “I/O” and “Network”. Furthermore, memory PSF will be subdivided into the cache memory PSF and main memory PSF respectively their according stubs, i.e., cache memory - and main memory stubs. Performance Measurement Functions (PMF). To provide a basic set of evaluation possibilities the performance measurement functions can be used. They are mainly wrapper functions for the measurement functions already provided by the system. Calibration Functions (CF). In order to provide trustworthy results, the stubs have to be adjusted to a dedicated system. This can be done using the calibration functions. For more detailed information on dynamic performance stubs the reader is referred to [1]. A short introduction to CPU stubs and memory stubs is given below. 3 CPU Stubs. CPU stubs are targeting to handle CPU bound systems. Therefore, a general approach to parameterize the runtime behavior and CPU usage has been achieved as well as a possible realization has been implemented. The methodology of CPU stubs has been used to improve the performance behavior of a long term evolution (LTE) telecommunication software. Furthermore, the applicability of CPU stubs has been extended to support multi-core and parallel processing applications in [7]. Cache Memory Stubs. The cache memory stubs can be used to simulate the data cache access behavior of software modules or functions to improve suspected memory bottlenecks. The algorithm, a validation as well as an evaluation by means of a proof of concept for cache memory stubs have been published in [8]1. Main Memory Stubs. Main memory stubs simulate the stack and heap behavior of software modules or functions. They are an extension of the dynamic performance stubs framework to simulate the main memory behavior to achieve a cost-benefit oriented optimization. They are defined in [9]. 1.2 Content of the Paper The first part of this paper enhances the algorithm to simulate the memory behavior of an application, known from [9]. A closer view on the design and the execution of the algorithm is shown. An extension of the algorithm to recreate situations where the amount of allocated stack memory remains constant is introduced. Second, in [9], there are some imperfections with the simulation of the time and memory allocation behavior. This paper extends the concept of main memory stubs by evaluating calibration functions. These can be used to adjust the main memory stubs to the system. This highly improves the simulation results for the “heap”, “stack” and “timing” behavior. Additionally, a proof of concept is given. 2 Main Memory Stubs Main memory stubs are used to simulate the main memory performance behavior of a component under study in the context of dynamic performance stubs. 1Cache memory stubs are referred to this in the earlier publication as memory stubs. 4 2.1 Methodology To simulate the main memory behavior of applications the following steps have to be done. First, a main memory performance bottleneck has to be identified. Now, the bottleneck has to be evaluated, especially, the functional as well as the main memory behavior have to be determined. Afterwards, the functional behavior has to be rebuilt using the simulated software functionality. Moreover, the main memory performance simulation functions have to be recreated. This leads to a main memory stub. Now, the memory behavior of the stub can be changed according to the needs of the performance study. Hence, several possible optimization levels as well as their influences to the system can be simulated. Moreover, studying the results can identify “hidden” bottlenecks, e.g., the timing behavior of a related software function can change because of the main memory stub. So, possible results of an optimization can be simulated before the optimization has to been done. 2.2 Performance Simulation Functions In [9], performance simulation functions to simulate the main memory allocation of a SUT have been introduced. In this section, the algorithm is briefly presented. Figure 2 shows the design of the memory simulation algorithm. The recursive function, needed to simulate the stack behavior, is called “allocate()”. This function is called when the amount of stack is increasing. allocate() allocate stack (re-)allocate heap while(…) time delay (re-)allocate heap time delay represents trace point x -stack is increasing -heap may change -time is delayed -decide wether stack increases or decreases at the next trace point stack <=0 represents trace point x+1 -stack will decrease by previous allocated value when leaving recursion -heap & time are simulated stack > 0 I II III goto next trace point Figure 2: Memory Simulation Algorithm 5 Simulate Stack Allocation. In the first part of the algorithm (Part I in Figure 2), the time will be delayed as requested by the data set. Then, the stack memory is allocated by calling the alloca()-function and used with the distmemset()-function (see also [9]). Next Trace Point. In the second part (Part II), the algorithm decides whether the stack is increasing or decreasing at the following trace point. It will again reach Part I if the stack is increasing. If the stack is shrinking, the recursion has to be left, which is realized in Part III. Simulate Stack Deallocation. This is achieved in the third part (Part III). The time delay is simulated and the stack memory is automatically freed when leaving the allocate()-function. After having left the allocate()-function, the algorithm is either back in the previous function, which initially called the allocate()-function, or it is in Part II and the while(...) condition proves once more if the amount of stack is increasing at the next trace point. This construction is needed to simulate a sequence of rising and trailing edges. Simulate Heap (De-)Allocation. The heap memory can be deas well as allocated in Part I and III. As it can increase and shrink at this points nothing special has be to considered. 2.3 Simulation Data File To reduce the overhead created when running the algorithm, the measuring points used to simulate are written into a data structure within a header file that is used to compile the algorithm. 1#define NUMDATA 4 2 3struct memAlloc{ 4int time ; 5int stackAlloc ; 6int heapAlloc ; 7}memUse[NUMDATA]={ 8[ 0 ] . time =129, [ 0 ] . stackAlloc =300, [ 0 ] . heapAlloc =0, 9[ 1 ] . time =223, [ 1 ] . stackAlloc =100, [ 1 ] . heapAlloc =200, 10[ 2 ] . time =384, [ 2 ] . stackAlloc =−100, [ 2 ] . heapAlloc=−40, 11[ 3 ] . time =112, [ 3 ] . stackAlloc =−300, [ 3 ] . heapAlloc=−160 12} Listing 1: Example for a Simulation Data File 6 The different measurements show that the amount of additional stack memory allocated by the algorithm (stackoverhead) is constant for every call of the allocate()-function and, therefore, for its recursive call as well. 5 Proof of Concept In the previous sections an algorithm to simulate a program’s memory behavior has been presented and the calibration functions have been introduced. Now, both will be validated and evaluated within this proof of concept. Therefore, a defined sample for the input data is used to cover a broad variety of possible memory behaviors. 5.1 Experimental Setup This proof of concept is used evaluate to the impact of the calibration functions as well as the enhanced main memory allocation algorithm. Environment. All measurements were performed on a FSC Amilo Si3655 Notebook with an Intel Core(TM)2 Duo P8400 CPU (Intel 64 architecture). As operating system Arch Linux is used. Its kernel version is 2.6.34. The binary has been build using the gnu compiler collection (gcc) without any optimization flags to guarantee that the option “-O0” has been used. Beside of running the proof of concept, the system has been idle to avoid further influences on the execution time. Measurement Tools. To offer the possibility to evaluate the simulated behavior of the memory allocation a very precise way to measure the stack and heap allocation has to be used. For this reason, the value of allocated stack memory is measured by inline assembler calls to read the stack pointer (esp) and base pointer (ebp) registers. The value of ebp is taken at the beginning of the simulation to get a base value for the stack allocation. During the simulation the esp register has been read at every measuring point. So the offset between the starting ebp and the actual esp gives the actual total amount of allocated stack memory. To measure the value of allocated heap memory, the mallinfo structure of the malloc.h header-file is read. This structure contains all the desired information about the heap memory for this process. The measured data has to be associated with the time spent in the system. Because of this, at every measuring point a time stamp is taken using an inline assembler to read the real time clock of the system [11]. 13 5.2 Calibration Function To determine the time, heap and stack allocation offset, created by executing the simulation, the calibration functions as presented in Section 4 are used. The values for those offset depends on the system’s implementation. Hence, the calibration has to be repeated when changing any of the system’s parameters. As described in Section 4, different simulation data files have to be used to measure the various offset values of the algorithm. Time Overhead. The measurement of the basic time offset has shown to be constant in our setup. It is determined to timebasic = 126775cycles with an squared coefficient of variation (see also [12]) of 0.009, calculated for 100 test evaluations. Within this proof of concept, the time consumed by allocating stack and heap memory has been identified. The evaluation of the measurements, that were described in Section 4, leads to following results for the heap and stack allocation (ydescribes the previously allocated total memory size in the memory segment and xthe newly allocated memory in bytes). Equation 4 is used to calculate the number of page faults at a certain memory allocation value. pagefaults(x, y) = (y%pagesize) + x pagesize (4) The number of bytes, which did not cause a page fault is calculated (y%pagesize). The result plus the newly allocated memory (x) is devided by the pagesize to determine the amount of page faults for the new allocation. The result is passed to the floor function as page faults can only be a natural number. P agesize denotes the system page size in bytes. Time Influence of the Heap Simulation. The heap memory will only be reallocated. Hence, the memory value (x) is always greater or equal zero. As can be seen in Equation 5, the time spent for allocating memory heavily depends on whether a page fault is raised in the allocation function or not. Additionally, there is only one page fault in the allocation function even if more than one page is allocated. timealloc heap(x, y) = (3722cycles pagefaults(x, y)>0 94cycles pagefaults(x, y) = 0 (5) timeuse heap(x, y) = 69cycles ∗(pagefaults(x, y) + 1)+ 3252cycles ∗(pagefaults(x, y)−1pagefaults(x, y)>1 0pagefaults(x, y) = 0 (6) 14 In Equation 6, the time spent in the distmemset()-function is calculated. The equation consists of two parts. First, the time spent iterating over the memory block, i.e., 69cycles∗(pagefaults(x, y)+1) and, second, the number of page faults occurred in the function minus one as one page fault appeared within the allocation function (see also Equation 5). Time Influence of the Stack Simulation. For both times, i.e., timealloc stack(x) and timeuse stack(x), the algorithm does not take significant time to free the stack memory (x≤0). Additionally, the “freed” memory will not be used, obviously. Hence, both values are set to zero cycles. In the other case, the time needed to allocate and use the new memory can be calculated by using Equations 7 and 8. timealloc stack(x) = 48cycles (7) timeuse stack(x, y) = 61cycles+ 3358cycles ∗pagefaults(x, y) (8) The time to allocate stack memory (Equation 7) is constant as only the baseand stack pointer have to be adjusted [9]. The time spent in the distmemset()-function to initialize the stack memory (Equation 8) is the same as in Equation 6. The only difference is that the stack allocate function does not raise a page fault. All the described equations were found by determining the average time stamps of several runs in our test setup and describe the time behavior of allocating and using the heap and stack memory in sufficient accuracy. When not allocating any heap and/or stack memory at a trace point, the respective times are set to 0. In those cases, they do not have any influence on the calculation of the total time overhead for each measuring point. The equation used to determine the total time overhead timeoverhead(heap, stack) is described in Section 4. Heap and Stack Overhead. As stated in Section 4, the heap offset that is introduced when executing the algorithm has to be determined. The measurements showed that heapoverhead is constant at 32 bytes, if there is no heap memory allocated within the simulation. If there is any heap memory allocated during the simulation, the heap overhead rises to 40 bytes and also remains constant while the memory is allocated. Measuring with the given calibration trace file results in a constant increase of allocated stack per trace point. So, the call of the allocation function allocates a constant amount of stack memory. Because of this measurement, the stack offset is determined to stackoffset = 216 bytes as well as to 15 stackoverhead(x) =      64bytes x > 0 0bytes x= 0 −64bytes x < 0 . As these bytes overhead are constant for each execution, there is no need for an statistical interpretation. The values for stack, heap and time overhead is used to produce a simulation data file. This allows the simulation algorithm to perform a simulation that fit as exact as possible to the desired behavior of memory allocation. 5.3 Measurement and Evaluation After the measurements of the calibration functions, all necessary data for the simulation of the memory behavior is available. The same input data as in [9] has been used and the time, heap and stack overhead has been determined via the calibration functions. Simulation Data File. As the first step in simulating the memory behavior of a system, a valid simulation data file has to be generated. With the input data and the overhead for time delay, heap and stack allocation, the needed trace points are calculated. The output is presented as a header file, see Section 2.3, containing the data set used within the simulation algorithm. Measurement. After creating a valid header file, an executable of the simulation algorithm can be build. 4000 6000 8000 10000 12000 memory [bytes] stack input data heap input data stack simulated data heap simulated data 0 2000 4000 6000 8000 10000 12000 0 1000000 2000000 3000000 4000000 5000000 6000000 memory [bytes] time [µs] stack input data heap input data stack simulated data heap simulated data Figure 3: Comparison of Original and Simulated Memory Behavior 16 Figure 3 shows the measured stack and heap memory allocation in comparison to the desired behavior. The time in microseconds is printed at the X-axis and the total allocated amount of memory is shown at the Y-axis. The figure shows the original stack behavior, the measured stack allocation during the simulation, the original heap allocation and the measured heap behavior while simulating the memory allocation. Simulating Execution Time. When comparing the time supposed by the simulation data file, which is 4.8 seconds, and the execution time measured in the evaluation, which is 4.8000444 seconds, it can be seen that the simulation produces only a small amount of time overhead. Here, an overhead of 9 ∗10−3% in total execution time is produced. So, the total execution time is sufficiently simulated. Simulating Heap Allocation. The analyses of the heap’s allocation simulation, as shown in Figure 3, depicts that it is very accurate. There is nearly no variation to the desired behavior of heap allocation. It is possible to simulate situations where the heap is rising and falling. Fast switches of allocating and freeing heap memory are simulated exactly. The simulation algorithm works absolutely fine for simulating heap memory allocation in our example. Simulating Stack Allocation. The results of the simulation of stack memory allocation behavior also are satisfying. The allocation behavior can be reproduced exactly. Rising and trailing edges as well as constant amounts of stack are simulated in a correct way. High peaks and fast changes of allocated stack are rebuild as desired. Even slow rises of the allocated amount of stack are simulated quite well. Summary. The calibration functions that are introduced within this paper as well as the presented memory simulation algorithm fully meet the requirements to simulate the memory behavior of a system under test. Both, heap and stack memory allocation, are simulated with high accuracy and almost without an overhead in execution time. 6 Conclusion and Future Work This paper presents an algorithm to simulate the main memory behavior of applications in the context of dynamic performance stubs. There are two contributions: An extension and improvement of the simulation algorithm and the determination of the various types of overhead caused by the algorithm, e.g., time overhead caused by executing the algorithm. With the improvement of the algorithm, it is now possible to simulate constant stack behavior. Additionally, calibration functions have been intro17 duced to evaluate the overhead values caused by executing the algorithm. Considering the calibration functions leads to an almost exact simulation of the main memory behavior. This has been validated with a proof of concept. The future work will focus on an algorithm to measure the component under study as well as to generate the simulation data file. Moreover, a methodology, which applies the main memory stubs in industrial case studies, has to be defined and evaluated. It has been shown that the behavior of the stack and heap usage can be simulated without significant errors. Based on the presented algorithm, a goal oriented performance optimization regarding the memory behavior of an arbitrary application can be achieved. 7 Acknowledgments The authors would like to thank the long term evolution group in Ulm for the excellent support and contributions to this research project. For careful reading and providing valuable comments on draft versions of this paper we would like to thank Helge Janicke. We would also like to thank the Software Technology Research Laboratory (STRL) from the De Montfort University, especially Francois Siewe and Hussein Zedan for providing the appropriate environment for research. References [1] P. Trapp and C. Facchi, “Performance Improvement Using Dynamic Performance Stubs,” Fachhochschule Ingolstadt, Tech. Rep. 14, Aug. 2007. [2] R. Jain, The art of computer systems performance analysis. Wiley and sons, Inc., 1991. [3] N. H. Gunther, The Practical Performance Analyst. McGraw-Hill Education, 1998. [4] J. J. Marciniak, Encyclopedia of Software Engineering, 2nd ed. John Wiley & Sons Inc, 2002. [5] A. Bertolino and E. Marchetti, Software Engineering: The Development Process - A Brief Essay on Software Testing, 3rd ed. John Wiley & Sons, Inc., 2005, vol. 1, ch. 7, pp. 393–411. 18 [6] I. Sommerville, Software Engineering, 6th ed. Addison-Wesley, 2001, german redaction. [7] P. Trapp, M. Meyer, and C. Facchi, “Using CPU Stubs to Optimize Parallel Processing Tasks: An Application of Dynamic Performance Stubs,” in ICSEA ’10: Proceedings of the International Conference on Software Engineering Advances. IEEE Computer Society, 2010. [8] P. Trapp, C. Facchi, and S. Bittl, “The Concept of Memory Stubs as a Specialization of Dynamic Performance Stubs to Simulate Memory Access Behavior,” in CMG ’09: International Conference Proceedings. Computer Measurement Group, 2009. [9] P. Trapp and C. Facchi, “Main Memory Stubs to Simulate Heap and Stack Memory Behavior,” in CMG ’10: International Conference Proceedings. Computer Measurement Group, 2010. [10] P. Ezolt, “A study in malloc: a case of excessive minor faults,” in ALS ’01: Proceedings of the 5th annual Linux Showcase & Conference. Berkeley, CA, USA: USENIX Association, 2001, pp. 17–17. [11] Y. Etsion and D. Feitelson, “Time Stamp Counters Library - Measurements with Nano Seconds Resolution,” The Hebrew University of Jerusalem, Tech. Rep. 2000-36, 2000. [12] R. Srinivasan and O. Lubeck, “MonteSim: A Monte Carlo Performance Model for In-order Microarchitectures,” ACM SIGARCH Computer Architectur News, vol. 33, no. 5, pp. 75–80, Dec. 2005. 19