Etherscan-Analyzer_2.png' alt='Matlab Windows 2011A' title='Matlab Windows 2011A' />Preallocation performance Undocumented Matlab.Array preallocation is a standard and quite well known technique for improving Matlab loop run time performance.Todays article will show that there is more than meets the eye for even such a simple coding technique.Express Helpline Get answer of your question fast from real experts.KdERhbO.jpg' alt='Matlab Windows 2011A' title='Matlab Windows 2011A' />A note of caution in the examples that follow, dont take any speedup as an expected actual value the actual value may well be different on your system.Your mileage may vary.I only mean to display the relative differences between different alternatives.The underlying problem.Memory management has a direct influence on performance.I have already shown some examples of this in past articles here.Preallocation solves a basic problem in simple program loops, where an array is iteratively enlarged with new data dynamic array growth.Unlike other programming languages such as C, C, C or Java that use static typing, Matlab uses dynamic typing.This means that it is natural and easy to modify array size dynamically during program execution.For example fibonacci 0, 1.While this may be simple to program, it is not wise with regards to performance.The reason is that whenever an array is resized typically enlarged, Matlab allocates an entirely new contiguous block of memory for the array, copying the old values from the previous block to the new, then releasing the old block for potential reuse.This operation takes time to execute.In some cases, this reallocation might require accessing virtual memory and page swaps, which would take an even longer time to execute.If the operation is done in a loop, then performance could quickly drop off a cliff.The cost of such nave array growth is theoretically quadratic.This means that multiplying the number of elements by N multiplies the execution time by about N2.The reason for this is that Matlab needs to reallocate N times more than before, and each time takes N times longer due to the larger allocation size the average block size multiplies by N, and N times more data elements to copy from the old to the new memory blocks. Software Update For Mio Gps Updates . A very interesting discussion of this phenomenon and various solutions can be found in a newsgroup thread from 2.Three main solutions were presented preallocation, selective dynamic growth allocating headroom and using cell arrays.The best solution among these in terms of ease of use and performance is preallocation.The basics of pre allocation.The basic idea of preallocation is to create a data array in the final expected size before actually starting the processing loop.This saves any reallocations within the loop, since all the data array elements are already available and can be accessed.This solution is useful when the final size is known in advance, as the following snippet illustrates Regular dynamic array growth tic.Elapsed time is. 0.Now use preallocation 5 times faster than dynamic array growth tic.Elapsed time is. 0.On pre R2. 01. 1a releases the effect of preallocation is even more pronounced I got a 3.Matlab 7. 1 R1. 4 SP3.R2. 01. 1a Matlab 7.R2. 01. 1a. Non deterministic pre allocation.Because the effect of preallocation is so dramatic on all Matlab releases, it makes sense to utilize it even in cases where the data arrays final size is not known in advance.We can do this by estimating an upper bound to the arrays size, preallocate this large size, and when were done remove any excess elements The final array size is unknown assume 1.Kx. 3K upper bound 2.MB. data zeros1. Condition.Idx some. Value. 1 num.Cols maxnum. Cols,col.Idx. row. Idx some.Value. Rows maxnum.Rows,row. Idx. datarow.Idx,col. Idx some.Other. Value. Now remove any excess elements.Cols1 end remove excess columns.Rows1 end, remove excess rows.Variants for pre allocation.It turns out that Math.Works official suggestion for preallocation, namely using the zeros function, is not the most efficient Math.Works suggested variantclear data.Elapsed time is. 0.A much faster alternative 5.Elapsed time is. 0.The reason for the second variant being so much faster is because it only allocates the memory, without worrying about the internal values they get a default of 0, false or, in case you wondered.On the other hand, zeros has to place a value in each of the allocated locations, which takes precious time.In most cases the differences are immaterial since the preallocation code would only run once in the program, and an extra 1.But in some cases we may have a need to periodically refresh our data, where the extra run time could quickly accumulate.Update October 2.As Marshall notes below, this behavior changed in R2.LXE Matlabs new execution engine replaced the previous engine.In R2. 01. 5b, the zeros function is faster than the alternative of just setting the last array element to 0.Similar changes may also have occurred to the following post content, so if you are using R2.Pre allocating non default values.When we need to preallocate a specific value into every data array element, we cannot use Variant 2.The reason is that Variant 2 only sets the very last data element, and all other array elements get assigned the default value 0, or false, depending on the arrays data type.In this case, we can use one of the following alternatives with their associated timings for a 1.Variant A 8. 7. 6.Variant B 2. 8. 6.Variant C 1. 7. 2.Variant D 1. 7. 1.Variant E 1. 6. 3.As can be seen, Variants C E are about twice as fast as Variant B, and 5 times faster than Variant A.Pre allocating non double data.Preallocating non double data.When preallocating an array of a type that is not double, we should be careful to create it using the desired type, to prevent memory andor performance inefficiencies.For example, if we need to process a large array of small integers int.Similarly, it would be inefficient to preallocate the array as a double type and then convert it to int.Instead, we should create the array as an int.Bad idea allocates 8.MB double array, then converts to 1.MB int. 8 array. data int.M elements. Elapsed time is.Better directly allocate the array as a 1.MB int. 8 array x.Elapsed time is. 0.Pre allocating cell arrays.To preallocate a cell array we can use the cell function explicit preallocation, or the maximal cell index implicit preallocation.Explicit preallocation is faster than implicit preallocation, but functionally equivalent Note this is contrary to the experience with allocation of numeric arrays and other arrays Variant 1 Explicit preallocation of a 1.Kx. 3K cell array.Elapsed time is. 0.Variant 2 Implicit preallocation x.Elapsed time is. 0.Pre allocating arrays of structs.To preallocate an array of structs or class objects, we can use the repmat function to replicate copies of a single data element explicit preallocation, or just use the maximal data index implicit preallocation.In this case, unlike the case of cell arrays, implicit preallocation is much faster than explicit preallocation, since the single element does not actually need to be copied multiple times ref Variant 1 Explicit preallocation of a 1.Elapsed time is. 0.Variant 2 Implicit preallocation x.Elapsed time is. 0.When preallocating structs, we can also use a third variant, using the built in struct feature of replicating the struct when the struct function is passed a cell array.For example, structfield.Unfortunately, this variant is slower than both of the previous variants.Pre allocating class objects.When preallocating in general, ensure that you are using the maximal expected array size.There is no point in preallocating an empty array or an array having a smaller size than the expected maximum, since dynamic memory reallocation will automatically kick in within the processing loop.For this reason, do not use the empty method of class objects to preallocate, but rather repmat as explained above.When using repmat to replicate class objects, always be careful to note whether you are replicating the object itself this happens if your class does NOT derive from handle or its reference handle which happens if you derive the class from handle.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. Archives
November 2017
Categories |