Lazy allocation and *alloc()

dwks · 09-08-2009, 12:18 PM

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 . . . .

Angus · 09-08-2009, 01:01 PM

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

09-08-2009, 12:18 PM	#16
dwks Frequently Quite Prolix Join Date: Apr 2005 Location: Canada Posts: 7,629	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 . . . . __________________ dwk Seek and ye shall find. quaere et invenies.* "Simplicity does not precede complexity, but follows it." -- Alan Perlis "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra "The only real mistake is the one from which we learn nothing." -- John Powell Other boards: DaniWeb, TPS Unofficial Wiki FAQ: cpwiki.sf.net My website: http://dwks.theprogrammingsite.com/ Projects: codeform, xuni, atlantis, etc. New project: nort
dwks is offline

09-08-2009, 01:01 PM	#17
Angus Kung Fu Kitty Join Date: Oct 2008 Location: Montreal, Canada Posts: 107	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
Angus is offline

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Dynamic array Allocation	deepak_j	C Programming	3	08-17-2009 07:18 AM
dynamic allocation from 1 instead of zero	cfdprogrammer	C Programming	27	04-28-2009 08:21 AM
pointer to array with dynamic allocation	cfdprogrammer	C Programming	22	04-07-2009 09:56 AM
redundant allocation	George2	C++ Programming	22	03-06-2008 06:43 PM
Dynamic memory allocation.	HAssan	C Programming	3	09-07-2006 05:04 PM