Strange memory allocation problem

[jollytall]

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),cpuset=/,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]

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]

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]

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]

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]

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.

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]

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.

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]

It is just a dead pointer and you forgot to allocate memory for it. <sigh>

[LV]

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]

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]

28MB on a system of 12GB is more than a bit heap fragmentation.

I don't believe that is it.

[MarkMLl]

28MB 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]

@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]

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]

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?

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.