How do I allocate ludicrous amounts of memory in C?

Question

I'm trying to investigate the practicalities of a d-dimensional range searching algorithm which is proven to be good in the asymptotic cases, but has large constants associated with it. This means I need to be able to vary the number of points in d-dimensional space up to some very large values. Using 1<<20 (2 to the power of 20) points starts causing my mallocs to return null pointers. I'm freeing memory up as frequently as I possibly can, and I'm making what few savings I can in what few places I can, but I'd like to be able to go up to values closer to 1<<28. Is there a conventional way of handling blocks of memory of this sort of size?

Answer 1

If malloc() is beginning to fail then you may be hitting (slightly arbitrary) rlimit restrictions. You should be able to relax those somewhat (see ulimit in bash); but keep in mind that these limits are set to help keep the system stable and predictable in general-purpose usage. Also, beware of overcommit, which is where the OS may let you ask for more memory than it can possibly provide, and then kills you if you try to use it.

If you're genuinely running out of address space and you're building a 32-bit application, then switch to 64-bit.

If you're running out of address space in a 64-bit application then I would suggest that you're not making good use of your allocations. That's a lot of data to fill, and I would expect you to run out of time before you run out of address space. In this case you should probably rethink the way you're using the space.

If you do need a greater address space than is available on your system, you could create a file (or many files) and mmap() pieces of those files as you need them. This allows the OS to cache the file(s) to the best of its ability, and if it does run out of both physical memory and swap (always a risk with projects like these) then it has somewhere it can page the data out to without getting in a panic and killing your application.

Unfortunately, using mmap() this way does require that you manage your own allocation within that file.

Answer 2

2^28 = 256MB.

Should certainly be doable on 32-bit or 64-bit systems provided you have enough physical memory. To check if you do or not, get the output of cat /proc/meminfo and look for the MemFree row.

The API I would recommend is mmap() (anonymous mapping) instead of malloc()

http://man7.org/linux/man-pages/man2/mmap.2.html

mmap is a system call which asks the OS directly for memory. It's what malloc() uses underneath.

Answer 3

You say that allocating such large blocks starts to return null pointers. To me, this implies that it works for a while, that you're allocating and freeing quite a few of these over time, and that after having done some MANY times, you start getting nulls.

If that is the case, you're seeing a classic case of memory fragmentation. (Pardon the following novel if my assumption is incorrect.) In the past, I've handled such issues by writing my own memory manager that allows me to relocate objects in memory to make room for the allocation of new blocks. If your code has to be able to hold pointer into the allocated blocks, your memory manager is going to have to involve a pointer implementation that will make the moves transparent. This becomes difficult to impossible if you're relying on third party software.

You might look into preallocating a pool of each of the block sizes that you'll be using. This ensures that you'll never fragment your memory in a way that a large block will only be unavailable if you have used the entire pool of large blocks, as opposed to having plenty of free memory, but only in small fragments. Check up on a method called Slab Allocation.

My implementation of relocatable memory worked something like this: At the beginning of program execution, I allocated the largest single block of memory available. (mmap is your friend.) If I could not find a free fragment where I could satisfy an allocation request, I find some block with a chunk of free space before and after it, and move it to the location of the preceding free space. I'd plan this move so that the resulting free block would be large enough for the newly requested allocation.

This is not a good general solution. It can be very slow and I wouldn't use it in a system that required real-time performance. (Think about what happens if you have to shuffle a few dozen blocks for the sake of one allocation. Worst case, you have to copy every allocated byte for the sake of satisfying one request.) It also requires that you can tolerate the shuffling of every pointer that refers into this memory. But it does provide more efficient use of memory than a slab allocator, if it is absolutely necessary.

Answer 4

If you are running on a 32 bit processor and/or operating system or are compiling for 32 bits rather than 64 then you can't and even if you are running on a 64 bit processor and compiling for it you will need to have lots of physical memory - malloc tries for a contiguous block so swap files are no good to you. SIZE_MAX will tell you the maximum number that can try to be allocated but failures depend on the physical constraints.