[Solved] Dynamic arrays much slower than GetMem lazarus / 62-General ---------------------------------------------------------------------- ChrisR · 2021-09-27 12:56 The attached project computes a gaussian blur on a 3D volume of dimensions kDim^3. With kDim = 256, the exact same computations are 172 times slower (Apple M1, 1394 vs 239723 ms) and 294 times slower (Ryzen 3900X, 2706 vs 796013 ms ) than using traditional arrays.  I realize that there is some overhead to calling setlength(), where the array will be initialized as zeros, but there are very few calls to setlengths(). I have used dynamic arrays extensively in my projects as they are convenient. I had always thought they incurred a small penalty, but not to this extent. Can anyone suggest modifications to the code that can improve dynamic array performance. Dynamic arrays:   TFloat32s = array of single;   setlength(img3D, n)   ...   img3D := nil; Traditional arrays:  f32ra = array [0..0] of Single;  f32p = ^f32ra; GetMem(img3D, n * 4); ... FreeMem(img3D); ---------------------------------------------------------------------- Warfley · 2021-09-27 13:31 Dynamic arrays have a few overhead factors. The first one is of course the initialization when calling SetLength. The second one is the lazy copy mechanism. Arrays are reference counted to minimize copy operations. But when you change the array it needs to be copied. So on every single write access, code is executed that checks if the reference counter is 1 and if it is greater, it will copy the array into a new memory location before performing the access To avoid this, you can use pointer access to the array: Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i var  MyArray: Array of Single;begin  SetLength(MyArray, 2);  PSingle(MyArray)[0] := 42;  PSingle(MyArray)[1] := 3.14159;end; ---------------------------------------------------------------------- Thaddy · 2021-09-27 13:40 Indeed. It is the setlengths in loops that bites you. Never do that for performance code. ---------------------------------------------------------------------- MarkMLl · 2021-09-27 13:45 Quote from: Thaddy on September 27, 2021, 03:40:07 pmIndeed. It is the setlengths in loops that bites you. Never do that for performance code. Seconded. Memory can be released/reallocated in situations where common sense would have suggested that it would have been retained and that has massive performance implications. That is NOT intended as criticism of the way the compiler and runtimes are written, I'm sure there are reasons that make it inevitable. MarkMLl ---------------------------------------------------------------------- Thaddy · 2021-09-27 14:00 Well, actually: if the resize is smaller than before, there is no relocation. That only happens when the array grows. ---------------------------------------------------------------------- ChrisR · 2021-09-27 14:24 There are very few setlength() calls, none in the inner loop. I did try Warfley's PSSingle() trick, but do not see much advantage. Testing this, I found that virtually all the difference is due to a memory copy that DOES happen inside a for loop: For the dynamic arrays I use:   tmp := copy(img, imgp, imgp + nx - 1); while for GetMemory I use   Move(img^[imgp], tmp^[0],nx*4);//src,dst I found that I could get similar performance for dynamic arrays by using   Move(img[imgp], tmp[0],nx*4);//src,dst So in my case, the culprit was copy. Are there any comments on my hack of using a move instruction? Is there any alternative to the `copy` instruction - here the length of the array never changes. ---------------------------------------------------------------------- Warfley · 2021-09-27 14:38 The reason why copy is so much slower is pretty simple: Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i MyArray := Copy(...)does the following: 1. It allocates new memory for the result of Copy 2. It calles a move operation from the old array to the newly allocated memory region 3. It releases the memory hold by MyArray Using move works "in-place" i.e. it moves directly to the memory location without creating a new array first. Generally speaking, avoid allocations and free operations. Pre allocations are always a good solution. Modern OS use virtual memory, which means that until you touch a memory page it will not be actually loaded into memory. So you can make huge pre-allocations without any punishment. So if you are writing performance oriented code, you can simply do one large allocation that allocates all the memory you could possibly need for your algorithm and don't do any new allocations afterwards ---------------------------------------------------------------------- avk · 2021-09-27 15:36 Quote from: Warfley on September 27, 2021, 03:31:07 pm... The second one is the lazy copy mechanism. Arrays are reference counted to minimize copy operations. But when you change the array it needs to be copied. So on every single write access, code is executed that checks if the reference counter is 1 and if it is greater, it will copy the array into a new memory location before performing the access ... Are you sure? What, then, will print a test like this? Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i program test_cow;{$mode objfpc}var  a, b: array of Integer;begin  a := [1, 2, 3];  b := a;  b[1] := 42;  WriteLn('a[1] = ', a[1]);end.  Quote from: Warfley on September 27, 2021, 03:31:07 pm... To avoid this, you can use pointer access to the array: Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i var  MyArray: Array of Single;begin  SetLength(MyArray, 2);  PSingle(MyArray)[0] := 42;  PSingle(MyArray)[1] := 3.14159;end; Hmm, Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i program test;{$mode objfpc}uses  SysUtils, DateUtils;var  a: array of Single;  I, J: Integer;  Start, Stop: TTime; begin  SetLength(a, 1000000);  Start := Time;  for I := 1 to 1000 do    for J := 0 to High(a) do     PSingle(a)[J] := Single(5.0);  Stop := Time;  WriteLn('PSingle: ', MillisecondsBetween(Stop, Start));  FillChar(Pointer(a)^, Length(a)*SizeOf(Single), 0);  Start := Time;  for I := 1 to 1000 do  for J := 0 to High(a) do     a[J] := Single(5.0);  Stop := Time;  WriteLn('Index: ', MillisecondsBetween(Stop, Start));   prints Code: Text  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i PSingle: 501Index: 483 ---------------------------------------------------------------------- Warfley · 2021-09-27 16:10 Looks like I confused this with Strings, strings call fpc_ansistr_unique but arrays don't: Assembly Example ---------------------------------------------------------------------- Awkward · 2021-09-27 16:38 i tried test program on my slightly ol PC and got different results 3 times: PSingle: 3496 Index: 3873 PSingle: 3834 Index: 3511 PSingle: 3562 Index: 3594 i think, it shows not too good test algorithm ---------------------------------------------------------------------- ASerge · 2021-09-27 16:40 Quote from: ChrisR on September 27, 2021, 02:56:44 pmCan anyone suggest modifications to the code that can improve dynamic array performance. For me QuoteBlur time 2618 Blur time (dynamic arrays) 2582With replace (commented out) in blurSd Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i tmp := copy(img, imgp, {imgp + nx - 1}nx); because in blurS it is Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i Move(img^[imgp], tmp^[0], nx * 4); ---------------------------------------------------------------------- Gustavo 'Gus' Carreno · 2021-09-27 16:49 Hey Y'all, Poor @GetMem, isn't he already busy enough curating OPM? Why do you have to also burden him with curating your memory? Give the poor person a break Cheers, Gus ---------------------------------------------------------------------- avk · 2021-09-27 17:02 Quote from: Awkward on September 27, 2021, 06:38:53 pmi tried test program on my slightly ol PC and got different results 3 times: PSingle: 3496 Index: 3873 PSingle: 3834 Index: 3511 PSingle: 3562 Index: 3594 i think, it shows not too good test algorithm In a desktop system, there will always be deviations due to its multitasking. Make statistics of several measurements, if interested. But I suppose if there really was some reason to take this or that approach, it would be immediately visible. ---------------------------------------------------------------------- Warfley · 2021-09-27 17:33 If you look at the assembly the Indexed access and the Pointer access generate the exact same assembly. Any differences in speed are coincidental. See: Link It's only dynamic strings that have this lazy copy mechanism on indexed access ---------------------------------------------------------------------- Awkward · 2021-09-27 17:59 slightly offtop: try to add array prefix "var" for index example and/or "const" for pointer example ^_^ THAT the optimization! ---------------------------------------------------------------------- Jonas Maebe · 2021-09-27 18:10 Quote from: ChrisR on September 27, 2021, 02:56:44 pmThe attached project computes a gaussian blur on a 3D volume of dimensions kDim^3. With kDim = 256, the exact same computations are 172 times slower (Apple M1, 1394 vs 239723 ms) and 294 times slower (Ryzen 3900X, 2706 vs 796013 ms ) than using traditional arrays.  I realize that there is some overhead to calling setlength(), where the array will be initialized as zeros, but there are very few calls to setlengths(). In case of a dynamic array, there's (on 64 bit platforms) a 16 byte header at the start of the memory block (containing the reference count and size), but I'm not sure how that could explain such a difference in speed. ---------------------------------------------------------------------- ASerge · 2021-09-27 19:08 Maybe I didn't make it clear in the previous message, but the program compares different algorithms! When I made the algorithms the same, the dynamic version became even faster. ---------------------------------------------------------------------- ChrisR · 2021-09-27 20:03 ASerge I agree that the difference in speed can be resolved by changing the dynamic array call from  tmp := copy(img, imgp, nx); to   Move(img^[imgp], tmp^[0], nx * 4); Even though the array has the same size before and after the copy(), there seems to be a big penalty. ---------------------------------------------------------------------- Kays · 2021-09-27 21:06 Quote from: ChrisR on September 27, 2021, 02:56:44 pm[…] I have used dynamic arrays extensively in my projects as they are convenient. […]Dynamic arrays are managed data types. The FPC will automagically insert try … finally frames when you use them. You can [but shouldn’t] control this with {$implicitExceptions}. For more on that topic cf. avoiding implicit try finally section in the Wiki. ---------------------------------------------------------------------- Jonas Maebe · 2021-09-28 06:41 Quote from: ChrisR on September 27, 2021, 10:03:16 pmASerge I agree that the difference in speed can be resolved by changing the dynamic array call from  tmp := copy(img, imgp, nx); to   Move(img^[imgp], tmp^[0], nx * 4); Even though the array has the same size before and after the copy(), there seems to be a big penalty. copy always allocates a new array. ---------------------------------------------------------------------- ASerge · 2021-09-28 16:27 Quote from: ChrisR on September 27, 2021, 10:03:16 pmI agree that the difference in speed can be resolved by changing the dynamic array call from  tmp := copy(img, imgp, nx); to   Move(img^[imgp], tmp^[0], nx * 4); Again, you did not understand me. The problem is that the functions with a dynamic and static array are different. That is, they do not the same thing. That is, it is useless to compare them, no matter what tricks you do with Move. They are different! In my first message, I just showed where the error is located, and pointed out that if make them logically the same, then the difference in speed disappears. Was Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i tmp := copy(img, imgp, imgp + nx - 1);After correction (this is similar to the version without a dynamic array) Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i tmp := copy(img, imgp, nx);Imagine that imgp equal 100000 to understand where the error is, and why there is such a difference in speed. ---------------------------------------------------------------------- ChrisR · 2021-09-29 11:45 ASerge is correct, my original problem was that the copy() command was copying a larger array than required. So while there copy() command may have a slight penalty versus move(), the effect is small. So this thread is largely a false alarm. It does look like dynamic array can perform reasonably as long as you minimize the use of setlength() calls (which carry some overhead and obligatorily zero arrays). My fault entirely. Thanks for the community help. By the way, how do I set a thread to being "solved" with this forum? ---------------------------------------------------------------------- dseligo · 2021-09-29 11:56 Quote from: ChrisR on September 29, 2021, 01:45:16 pmBy the way, how do I set a thread to being "solved" with this forum? Just change title of the first post to: '[SOLVED] Dynamic arrays much slower than GetMem'