Strange memory allocation problem lazarus / 21-General ---------------------------------------------------------------------- jollytall · 2024-12-01 15:08 I have a difficult to debug error. My program generates points in the 3D space, using 3x8 byte records in a dynamic array. I also have some other much smaller arrays that are dynamically created, destroyed, resized, etc. Hundreds of them, but the total size is 4 bytes per point (basically I have a fixed size 3D array where in each cell there is a dynamic array, with the list of int32 values/indexes showing which points are in that cell). This way it is easy to find out where a certain point is as well as to find out what points are at a certain segment of the space. Up to about a million (depends on many things) points it works OK, but then I run out of memory. So, I have about let's say 28MB used in a system with 12GB memory. I tried to print from the heaptrc unit the GetHeapStatus.Allocated memory and it is indeed as planned. Also checked that there is no memory leak. Still if I look in top/System Monitor I see a huge and rapidly growing memory usage after a certain point. When the total memory used - as seen by Linux, not by Pascal! - reaches the system capacity then the kernel kills the process with an Out Of memory error. In dmesg I see: Code: [Select][38281.389610] [   5773]  1000  5773  2736272  2533780 22261760   193261           200 points [38281.389613] oom-kill:constraint=CONSTRAINT_NONE,nodemask=(null),cpu set=/,mems_allowed=0,global_oom,task_memcg=/user.slice/user- 1000.slice/user@1000.service/app.slice/app- org.gnome.Terminal.slice/vte-spawn-55fa8107-2a93-429a-991e- dbdda3704dfa.scope,task=points,pid=5773,uid=1000 [38281.389636] Out of memory: Killed process 5773 (points) total- vm:10945088kB, anon-rss:10135116kB, file-rss:4kB, shmem-rss:0kB, UID:1000 pgtables:21740kB oom_score_adj:200 My guess is that it is because the array is continuously resized and moved in memory leaving a lot of holes in the memory. So, I tried tricks. E.g. at the beginning I set the array size of my points to a very large number and then setting it back to the starting point (100 points to start with) where it can grow again. I thought that with this trick the array reserves the large space and when it grows it does not need to be moved around (speed, memory efficiency). Unfortunately it can be seen that the used memory jumps down, so probably it does not keep the Heap reserved. What is strange though that with this high area reserved the problems start later. For some time the memory used as seen in top is the same as seen by heaptrc and then again it suddenly starts growing. I think I have a workaround (need to rewrite the program), that I reserve and keep the array size at a very large value and use a "lastindex" property to manage how large it really is. Still it bothers me a lot. I guess it has something to do that other smaller dynamic arrays are allocated/resized. So it can be that e.g. my large array occupies at one point 100MB memory. Then a small array is created for a cell of the other array, listing the points in it. This small array is placed immediately after the large array. Then the large array has to be increased (when it gets larger than the actually reserved size - I know it is normally more than the size was last asked for) and so it blocks a new area. Then again a new small array is created (a new cell has points in it) and for some reason it is not placed e.g. in the area that has just been freed up where the large array was earlier, but again placed after the new large array. So when again the large array has to be increased it takes another "fresh" area and the next small array is again works as a separator, so at the end I will have many large holes in the heap with small blocking separators. Is it possible? Still why does linux see it as the whole area is reserved for my program. Why are the small "separator" array not created somewhere in a whole, so the large array could grow where it is? Is it something depends on linux or FPC? Is there a way to trace what is happening and to see whether my assumption is correct? Any other idea? ---------------------------------------------------------------------- jamie · 2024-12-01 15:22 if all the cells are the same array sizes, don't use Dynamic allocations for arrays like that, use static arrays within each. This way you larger chucks and less fragmentation of memory allocations. ---------------------------------------------------------------------- Martin_fr · 2024-12-01 15:24 Couple of rough workarounds /patches: - use a diff mem manager, e.g. "uses cmem;" as the very first uses in your "program foo;" file. Mem managers may allocate chunks from the OS, and redistribute. So this change can make a diff. Do not use heaptrc => as each mem alloc gets an extra chunk to save the stack trace... - You seem to be on Linux man ulimit You may be able to allow your app more memory. But the real deal may be to switch from array to list (either any existing class, or do your own). As you said over allocate the array a bit. Then keep it that size, until you know it no longer needs to grow (or of course further grow it as needed). Then: "length(Array)" is the capacity. And you need a 2nd variable "ArrayCnt:Integer" that keeps track how many elements you actually use. That may save a lot of reallocs. Mind that resizing the inner dimension of a multi-dim array (or "array of array") means that each inner array is reallocated => and hence if you are unlucky you can get a big amount of gaps. Other structures (like linked list) can be appended without re-alloc at all. But they have other downsides.... ---------------------------------------------------------------------- Martin_fr · 2024-12-01 15:26 Mind that with those amount of datas, you may also google for optimized memory layout. If you work on the data, then items that you need to work on in one go, should ideally be in a single cache line. That speeds up the processing. Not your current problem, but maybe of interest. ---------------------------------------------------------------------- jamie · 2024-12-01 15:31 I've ran into cases like this handling large amounts of small packets of data and ended making my own managed memory handler for a single instance of a large chuck of memory. Jamie ---------------------------------------------------------------------- MarkMLl · 2024-12-01 17:02 Quote from: jollytall on December 01, 2024, 04:08:59 pmMy guess is that it is because the array is continuously resized and moved in memory leaving a lot of holes in the memory. So, I tried tricks. E.g. at the beginning I set the array size of my points to a very large number and then setting it back to the starting point (100 points to start with) where it can grow again. I thought that with this trick the array reserves the large space and when it grows it does not need to be moved around (speed, memory efficiency). Unfortunately it can be seen that the used memory jumps down, so probably it does not keep the Heap reserved. BTDT, you have to allocate a "reasonable" maximum size and then keep track of how much space you're actually using. Thaddy has in the past recommended that when you hit the limit you multiply the size by the Golden Ratio, but didn't provide any rationale. There's some classic Knuth code where he implements multiple heaps, with different heaps being used for different sized allocations... I'm not sure I've got a copy but it's probably in his Magnum Opus. MarkMLl ---------------------------------------------------------------------- 440bx · 2024-12-01 17:13 Quote from: jollytall on December 01, 2024, 04:08:59 pmI think I have a workaround (need to rewrite the program), that I reserve and keep the array size at a very large value and use a "lastindex" property to manage how large it really is. Disclaimer: my knowledge of Linux internals is _zero_. However, I believe that as most (all?) O/Ss it is a demand paged O/S. if that is the case you can allocate (fully commit) a block of virtual memory that is larger than the amount of memory required by the largest array you anticipate in the worst case. In a demand paged O/S there will only be memory allocated for those blocks that contain data.  The only thing to be aware of is that virtual address space (not actual memory) is consumed in the full allocated amount.  This can occasionally be a problem in 32 bit. In Windows the allocation is done using VirtualAlloc, Linux has an equivalent function but I don't remember its name. Basically that would implement what you mentioned without using more actual memory than necessary. HTH. ---------------------------------------------------------------------- Thaddy · 2024-12-01 17:28 It is just a dead pointer and you forgot to allocate memory for it. ---------------------------------------------------------------------- LV · 2024-12-01 19:19 What you described closely resembles the functionality of Particle-in- Cell codes. This category of tasks is well-developed, particularly for parallel computing, and I assume any issues related to memory allocation have been addressed. It may be worthwhile to explore existing software implementations of these tasks. ---------------------------------------------------------------------- jollytall · 2024-12-01 21:22 Thanks, I will do the workaround and will let you know. I will do the large array as a fixed size (dynamic in the heap) one, as I know the final size in advance. The smaller ones I need to make really dynamic as reserving the maximum in each cells would be too much as most of the cells will be empty. @LV: I will definitely search for it. @Thaddy, I do not get the "dead pointer" hint. Would that be memory leak and something that is found by heaptrc? ---------------------------------------------------------------------- marcov · 2024-12-01 21:31 28MB on a system of 12GB is more than a bit heap fragmentation. I don't believe that is it. ---------------------------------------------------------------------- MarkMLl · 2024-12-02 08:01 Quote from: marcov on December 01, 2024, 10:31:23 pm28MB on a system of 12GB is more than a bit heap fragmentation. I don't believe that is it. Agreed, or it needs further elucidation. MarkMLl ---------------------------------------------------------------------- jollytall · 2024-12-02 09:00 @marcov, @MarkMLI Yes, it seems strange, but it is the case. Also thanks to everybody else for the ideas, hints. Now I made 4 test runs (in a smaller machine, with about 6GB total memory: physical + swap): The first one is just letting the main array of Points grow as normal from 100 elements. It can be seen that the 0-th element of the array is moved at every 10k cycles (my printout frequency) to a lower address. This is totally in line with the earlier hypothesis, that when I grow the array it does not fit to the place where it was and moves to a new location. Also, because I create small, sticking arrays in the Heap, it seems that such a small array is placed right next to the large array and stay there for ever, so when the large array needs to be increased again, it eats up a new fresh memory area. At the end the whole memory is cut into pieces by the small sticky arrays and when the large array needs again a large block, it cannot find and the process is killed. In the attached table it can be seen that the total allocated memory is totally in line with the expectation of 28 (+ some overhead) bytes/point, but the memory address of the 0-th element is moved in total about 6GB when it cannot move further and crashes. The second one is the same program with one line difference. At the very beginning I set the size of the large array to 10M points, but then immediately after it, as before, the program manages it the same way, i.e. sets its length to 100 (initial points) and then grow from there. It can be seen that memory usage is different. The first 20k points fit in the original space, the 0-th element is not moved. Then it moved few times (the other direction in the heap than in test one!), but between 40k and 50k it jumps a much larger step and for some while it is happy with it. At 460k it moves again this time to lower addresses, then again up at 510k, etc. This goes on till 940k, where suddenly it starts to move the array a lot, until again it cannot find a new place for it after moving the address in net 4.6GB (I did parallel runs with this one so it had somewhat less total memory, hence basically it is the same problem as with the 6GB above, where I had only one instance running). The third test is again building up the array from 100 elements upwards without a pre-sizing up-and-then-down, but switching cmem on, as the first unit of the program. Here I do not have the allocated memory as heaptrc does not give data when cmem is on. However from top I see a normal memory usage and from the address of the 0-th element it can be seen that at the beginning it also moves often as the allocated size is quickly overgrown, but later it makes big jumps (double the size every step), so it needs to reallocate much less frequently. The program could run much farther than the others. I did not wait until it crashes. The last test is a combination of the pre-allocation by simply setting again the size to 10M (my intended end number) and then back to 100, but apparently cmem (unlike in test two the normal memory management) is not polluting this memory (I guess as long as it can), so although the memory usage reported is kept low (as I see in top/System Monitor) this area is somehow "reserved" for this array and therefore it never needs to be moved (guess before reaching 10M). As a conclusion I do not need to use the workaround, the way test four is done seems perfect. Just for my curiosity: What is the benefit of the "normal" memory management over cmem? If cmem is better (this case definitely is) why is it not a default built in one? ---------------------------------------------------------------------- marcov · 2024-12-02 09:51 It raises the minimal requirements. And cmem is merely and interface that links to the system malloc, which is not the same on all systems. ---------------------------------------------------------------------- alpine · 2024-12-02 10:19 Quote from: jollytall on December 02, 2024, 10:00:17 amJust for my curiosity: What is the benefit of the "normal" memory management over cmem? If cmem is better (this case definitely is) why is it not a default built in one? It all depends on the scenario. I guess cmem have an allocation strategy that fits better to your use case. Before a year or so I had a similar case with a program (on Windows) bursting the memory seams and I did a lot of experiments and research, including writing my own FPC memory manager with static pools, etc. My doubt then was that the extensive use of containers causes a severe fragmentation and using specially designed memory manager will overcome the issues. My findings were that both "standard" and "cmem" managers are quite good and sophisticated and by no means worse than (to my surprise) my "special one". If it was up to me I would never use dynamic arrays, especially big and growing ones. I would declare a static array which is big enough and an additional length variable. Every time you grow a dynamic array you'll leave a gap which cannot satisfy the further growth without merging, you can have other small allocations that prevents free blocks from merging, etc. ---------------------------------------------------------------------- marcov · 2024-12-02 10:38 Cmem has more workarounds for bad allocation schemes (mass allocating in a thread and releasing in another thread). However the default distro linux one uses a bit more memory overhead iirc. Relying on cmem on a particular system might cause problems on the next (e.g. OS X or embedded Linux etc). It only masks problems. Better is to have some guard against reallocating for every element (e.g. once every n elements growth).  Pooling repeated large operations yourself (easy with a generic pool class)If you employ an exponential growth scheme, make sure it is capped at some top value (typically hundreds of MBs worth, and then stop growing exponentially, but 10% or so.Don't rely too much on linear container types (like tstringlist) with very high counts ---------------------------------------------------------------------- MarkMLl · 2024-12-02 10:42 Quote from: alpine on December 02, 2024, 11:19:23 amIf it was up to me I would never use dynamic arrays, especially big and growing ones. I would declare a static array which is big enough and an additional length variable. Every time you grow a dynamic array you'll leave a gap which cannot satisfy the further growth without merging, you can have other small allocations that prevents free blocks from merging, etc. And if the heap manager fragments it's reasonable to assume that it's not deeply integrated with the OS, and that it's forced to copy data around whenever it resizes. That has a significant speed penalty, plus can also leave unwiped data in RAM which is a potential security hazard (which obviously also applies to strings). MarkMLl ---------------------------------------------------------------------- marcov · 2024-12-02 12:53 Quote from: MarkMLl on December 02, 2024, 11:42:31 amAnd if the heap manager fragments it's reasonable to assume that it's not deeply integrated with the OS, and that it's forced to copy data around whenever it resizes. That has a significant speed penalty, plus can also leave unwiped data in RAM which is a potential security hazard (which obviously also applies to strings). Most do copy around afaik, since blocks won't be page aligned etc.  I think it is more a tunable, how much extra space do you allocate/leave for future expansion of a block?  Space/speed tradeoff...... In this case cmem wins, but it might use more memory overall. ---------------------------------------------------------------------- MarkMLl · 2024-12-02 13:25 Quote from: marcov on December 02, 2024, 01:53:11 pmMost do copy around afaik, since blocks won't be page aligned etc.  I think it is more a tunable, how much extra space do you allocate/leave for future expansion of a block?  Space/speed tradeoff...... If the allocation were being done at the level of a paging OS and was recognised as being e.g. more than a certain size, then in principle at least it should be possible to base it on a page boundary and to only have to copy the content of the highest page when necessary. I don't know whether that can be done by an application program without recourse to kernel facilities... which of course will vary enormously depending on the OS. Systems with multiple heaps (for small and large allocations) go back to Knuth: he either wrote one for Burroughs or borrowed their implementation for TAoCP. MarkMLl ---------------------------------------------------------------------- LV · 2024-12-02 14:11 “For any possible allocation algorithm, there exists a stream of allocation and deallocation requests that defeat the allocator and force it into severe fragmentation.” — Robson. https://github.com/pbrinkmeier/kit-lecture- notes/blob/master/betriebssysteme/14-memory-allocation.md ---------------------------------------------------------------------- MathMan · 2024-12-02 14:40 Quote from: LV on December 02, 2024, 03:11:00 pm“For any possible allocation algorithm, there exists a stream of allocation and deallocation requests that defeat the allocator and force it into severe fragmentation.” — Robson. https://github.com/pbrinkmeier/kit-lecture- notes/blob/master/betriebssysteme/14-memory-allocation.md Indeed  And that's why for memory intensive programs/applications usually a thorough memory requirements analysis should be done ... You mentioned earlier that thread starters program seems to fall into a specific category and I fully support that TS should look for secondary implementations/literature to see how his memory management may be improved.