Lazy allocation and *alloc()

Recently I read somewhere that calloc() does lazy allocation, in that it doesn't allocate any real memory, but just virtual memory. Real memory pages are only allocated as writes to it are performed, and any reads performed on uninitialized memory returns 0, just like a sparse file. This made a lot of sense to me, because it seemed strange that ANSI would come up w/a whole new function to do the same thing that malloc() followed by bzero() could do, and besides, I've never found a use for calloc() in my entire career, so far. So I thought that this would be great, because if I have a method that writes a blob to a db, and if the blob column in that db can be up to 1Gb, then my method can lazily allocate a whole Gb, and even if my app only ever handles 10-byte blobs, the most memory that would be wasted is the better part of a page.

Since then I've tried to read up on this, and what I've read is that malloc() and calloc() allocate memory in the same way, and calloc() does actively initialize the memory. Furthermore, that lazy allocation I'm talking about is system-dependent, and if calloc() on a particular system does it, then so does malloc(). Can anyone confirm any of this for me? I'm mostly interested in the Linux kernel, since that seems to be all I program in these days.

Quote:

---

Originally Posted by Angus

This made a lot of sense to me, because it seemed strange that ANSI would come up w/a whole new function to do the same thing that malloc() followed by bzero() could do

---

Several ways to skin a cat. I do not think it is within the scope of the standard to define whether memory allocated should be "real" or "virtual", so unless you find an explicit statement to the contrary, that cannot be the reason for the two functions; calloc() is just a convenience.

Linux uses an optimistic memory allocation method. It works the way you described in that malloc will return a valid address, but pages will only be allocated as they are used. This allows the OS to use the memory in other applications and I/O paging while it waits for the app that allocated the memory to use it.

There are some downsides to this approach though. Mainly, you cannot ever be sure that your memory allocation succeeded since malloc returns an address before it actually allocates the memory. If you attempt to use the memory when there is no space available, the OOM killer will simply kill your application (or another one on the system).

Note that this behavior is configurable, and can be turned off by running:
# echo 2 > /proc/sys/vm/overcommit_memory
In which case memory allocations will behave the way they do on Windows.

> in that it doesn't allocate any real memory, but just virtual memory.
All modern OS's allocate virtual memory.

> Real memory pages are only allocated as writes to it are performed
The virtual pages become mapped if that's what you mean.

> This made a lot of sense to me, because it seemed strange that ANSI would come up w/a whole new function to do the same thing that malloc() followed by bzero() could do
calloc pre-dates ANSI.


> because if I have a method that writes a blob to a db, and if the blob column in that db can be up to 1Gb, then my method can lazily allocate a whole Gb,
All this presumes a particular OS (or kind of OS).

Since you mention Linux, you should be aware of the "OOM" issue. Linux will over-commit VM pages. So whilst your malloc may succeed, the kernel may subsequently fail to map a page of your allocation due to being out of memory.

So you shouldn't lazily alloc 1GB because you can't be bothered to figure out a better answer. The kernel still has to account for your request in some way, even if it doesn't immediately cause a great deal of activity (it isn't free).

Quote:

---

Originally Posted by Salem

>
So you shouldn't lazily alloc 1GB because you can't be bothered to figure out a better answer. The kernel still has to account for your request in some way, even if it doesn't immediately cause a great deal of activity (it isn't free).

---

Account for my request anymore than it would just, say, 10 bytes?

Well if you ask for 1GB, then you've used up an awful lot (of a finite number) of VM page table entries for no good reason.

If you use them, then that's fine.
But if you don't, nobody will be impressed by your code.

Quote:

---

Originally Posted by Salem

But if you don't, nobody will be impressed by your code.

---

Is that the only drawback? If I was in the racket to impress folk I probably would have chosen pop music instead.

Quote:

---

Originally Posted by Angus

Is that the only drawback? If I was in the racket to impress folk I probably would have chosen pop music instead.

---

The other drawback is that you are relying on the OS behavior instead of proper coding techniques. What happens if you ever want to port your application to a non-Linux platform? What if a Linux user has the overcommit behavior turned off?

Then

1. The use of macros and #if #endif block should cure that
2. A quick reading of /proc/sys/vm/overcommit_memory should tell me all I need to know

Quote:

---

Originally Posted by Angus

Then

1. The use of macros and #if #endif block should cure that
2. A quick reading of /proc/sys/vm/overcommit_memory should tell me all I need to know

---

Why don't you just allocate the amount of memory that you are using? This way you don't need to worry about this issue at all.

I'm done wasting effort - doesn't want to learn, stuck with a single idea and can't change it.

Quote:

---

Originally Posted by bithub

Why don't you just allocate the amount of memory that you are using? This way you don't need to worry about this issue at all.

---

Because I don't always know how much that is, and I risk calling realloc() a lot

That's a good philosophy, Salem. You should go by it more often

Quote:

---

Because I don't always know how much that is, and I risk calling realloc() a lot

---

And what's wrong with calling realloc() a lot? Calling realloc() is exactly what you want to do if your memory usage is growing over time.

Quote:

---

Originally Posted by bithub

And what's wrong with calling realloc() a lot? Calling realloc() is exactly what you want to do if your memory usage is growing over time.

---

Well, every time you call realloc() to increase the size of the block you run the risk of having to copy all the data in that block. If you can rely on lazy allocation, though, you'd only have to deal with the expense of the odd page fault.

Quote:

---

Originally Posted by Angus

Well, every time you call realloc() to increase the size of the block you run the risk of having to copy all the data in that block. If you can rely on lazy allocation, though, you'd only have to deal with the expense of the odd page fault.

---

Well if it helps you sleep better at night, the glibc implementation of realloc() on Linux uses the mremap() system call. It rarely has to copy the existing memory, and will usually just allocate new virtual pages that are contiguous with the existing memory.

Really, I don't think you have to worry about that. I don't know, but I'd imagine that if a realloc() call needs to copy its data to another location in memory, the OS would simply reused the old physical address. In other words, it would be moved in virtual memory, but that portion of virtual memory would refer to the same physical memory.

(I really don't know what I'm talking about here, but I could see that happening.) [edit] Regarding bithub's post: Wow, my guess was right! :) [/edit]

Anyway, you *really* shouldn't allocate 1GB just because you can. Re-think your algorithm, use realloc(), and only if it's too slow go with another solution.

One thing you could do is to simulate lazy allocation in your own program. Let's say you have a data structure like this:

Code:

---

struct data_t {
    char data[20];
};

---

Maybe you want a huge, spare array or matrix of that data. You could then use

Code:

---

struct data_t *lookup(struct index_t where);

---

which would look into a table of allocated pages to see if "where" exists. If it does, you return the actual pointer to it; otherwise, you return NULL or maybe allocate space for the chunk. Some sort of hash table would probably be a good idea for this.

Of course, that's really just a spare matrix in disguise, so you should read up more on how they can be implemented . . . the only type of sparse matrix implementation I've ever done was in a program of mine called planedist. You can download it here: http://dwks.theprogrammingsite.com/m...anedist.tar.gz

[I believe you need SDL and SDL_gfx to compile it, which you can get here: Simple DirectMedia Layer]

explanation.txt in that archive describes the algorithm. Anyway, you could use something like that for your own code if you wanted to. Keep in mind that I know absolutely nothing about this subject and came up with that algorithm by myself after a few hours of puzzlement. :) No idea if it's any good . . . .

I see. Usually, eh? Well, I guess there's not much point in trying to program for lazy allocation. In any case, my hopes for calloc() are shattered, because it clearly doesn't generally do the lazy allocation I thought it was for :(

Thanks