Very basic coding question about realloc
category: general [glöplog]
216: He had been using VC which is mainly a C++ and not a compliant C compiler, that is why switching is that easy. Your average demoscener, on the other hand, can continue reinventing the wheel in the fantasmic realm of C application development.
I'm with you 216, although not in this fight, as it is kind of difficult to let the point come across and it devolves into something not quite as interesting.
Anyway, texel, if you really programs in C++, use stl::vector. If you're programing in C, flat arrays with geometric allocations. (And if you want a convenient API, djb has a nice one: http://cr.yp.to/lib/array.html)
Anyway, texel, if you really programs in C++, use stl::vector. If you're programing in C, flat arrays with geometric allocations. (And if you want a convenient API, djb has a nice one: http://cr.yp.to/lib/array.html)
For some reason, people that insist on using STL when programming C++ always give me the chuckles.
Why is it not possible to simply create an array of sufficient size so that you will never have to reallocate it?
kb, well yeah it's kind of cute on its own (Also it's fun to see people trip themselves over the STL)
Thanks so much to all.
I had no idea of STL, so I'm reading about it.
I code in C (not C++). I don't really know how to code in C++, and I'm not sure if I want to learn to.
About using new(), it doesn't solve my question, since I want resizable arrays...
The geometric allocations approach looks good, thanks for that info too. Anyway, for a resize of ... let say, 512 to 513 megabytes, I would need 512 megabytes plus 1 gigabyte free for allocation... it looks too much.
I had no idea of STL, so I'm reading about it.
I code in C (not C++). I don't really know how to code in C++, and I'm not sure if I want to learn to.
About using new(), it doesn't solve my question, since I want resizable arrays...
The geometric allocations approach looks good, thanks for that info too. Anyway, for a resize of ... let say, 512 to 513 megabytes, I would need 512 megabytes plus 1 gigabyte free for allocation... it looks too much.
STL = Standard Template Library of C++, not C.
texel, ever thought about analyzing your use case and deciding upon that?
Like, what's the size of the single array elements, how many do you need at once, what's the grow pattern (linear vs exponential), etc?
A two-tiered array that has a statically defined array of pointers of "pages" of array elements doesn't sound too bad either. The first array is pretty small in size compared to the actual data, and first of all you'll never have to reallocate (as in allocate new block, copy, delete old block) but ony allocate additional pages when needed.
Especially when you're talking about reszing 512 to 513 megabytes you might want to avoid a realloc grow operation, as it always fragments your virtual memory space. The geometric allocation approach is particularly prone to this; if you use it, prepare to be "out of memory" when you're hitting 1GB on 32bit machines.
Like, what's the size of the single array elements, how many do you need at once, what's the grow pattern (linear vs exponential), etc?
A two-tiered array that has a statically defined array of pointers of "pages" of array elements doesn't sound too bad either. The first array is pretty small in size compared to the actual data, and first of all you'll never have to reallocate (as in allocate new block, copy, delete old block) but ony allocate additional pages when needed.
Especially when you're talking about reszing 512 to 513 megabytes you might want to avoid a realloc grow operation, as it always fragments your virtual memory space. The geometric allocation approach is particularly prone to this; if you use it, prepare to be "out of memory" when you're hitting 1GB on 32bit machines.
skrebbel: So if std::list isn't internally a linked list, how is it any quicker than std::vector at insertions? In Java at least, I believe List is a "naive" linked list, whereas ArrayList is this dynamic list of arrays indexed as one array. (I've never found any good description of how the STL classes are implemented.)
Adok: Because even a "very big" array is often not big enough. It's extremely short-sighted to think, "oh, my 3D engine would never possibly push more than a million vertices through in one frame anyway". So it makes for code that's both very wasteful because you have to stay below the maximum, and hard to reuse because those limitations you've imposed come back to haunt you later (they always do). Plus of course, if we're not talking about demos, you can rarely predict how your code is going to be used, so the golden rule is, write a concise, meaningful interface, completely hide the implementation behind it and make sure there are absolutely NO surprises. Writing open-ended code almost always pays off, and often (in my experience) a lot sooner than you think. And especially when you have the STL to use (and to build your own container classes on), it's not a very big investment.
texel: If you're usinig C, rename your .c sources to .cpp and you're halfway there. C++ is largely just a superset of C, and you should be able to take advantage of the STL without doing anything else to your code (apart from trivial things like the definition of main() etc.).
kb: How would that two-tiered array perform with a lot of single-element insertions in different places? Wouldn't you eventually need a lot of cleaning up to avoid fragmentation building up, anyway?
About analysing code, I found that for VC(++) CodeAnalyst by AMD is extremely easy to use. Just point it to the executable in your build directory and it'll find all the symbol information, run the exe, and ultimately list how much CPU time is spent in each function/method. You can even break it down into lines of code or CPU instructions. The results are often surprising, especially for complex projects,
Adok: Because even a "very big" array is often not big enough. It's extremely short-sighted to think, "oh, my 3D engine would never possibly push more than a million vertices through in one frame anyway". So it makes for code that's both very wasteful because you have to stay below the maximum, and hard to reuse because those limitations you've imposed come back to haunt you later (they always do). Plus of course, if we're not talking about demos, you can rarely predict how your code is going to be used, so the golden rule is, write a concise, meaningful interface, completely hide the implementation behind it and make sure there are absolutely NO surprises. Writing open-ended code almost always pays off, and often (in my experience) a lot sooner than you think. And especially when you have the STL to use (and to build your own container classes on), it's not a very big investment.
texel: If you're usinig C, rename your .c sources to .cpp and you're halfway there. C++ is largely just a superset of C, and you should be able to take advantage of the STL without doing anything else to your code (apart from trivial things like the definition of main() etc.).
kb: How would that two-tiered array perform with a lot of single-element insertions in different places? Wouldn't you eventually need a lot of cleaning up to avoid fragmentation building up, anyway?
About analysing code, I found that for VC(++) CodeAnalyst by AMD is extremely easy to use. Just point it to the executable in your build directory and it'll find all the symbol information, run the exe, and ultimately list how much CPU time is spent in each function/method. You can even break it down into lines of code or CPU instructions. The results are often surprising, especially for complex projects,
doom: random insertions are somewhat more complicated than with any other type of array (because you'll need copying between pages instead of simply coping up) but I don't see any more allocs than usual. Inserting into array ALWAYS sucks, that's what lists are for. (see my first sentence above) :)
just reserve a real hard maximum, (works better on 64bit of course :) ), put a guardpage at the end and commit as you go in a seh. heavy weight but extremly fast as your bounds check is free. if you are dealing with smaller amounts of memory stl or just re allocating with a copy is probably way fast enough and you are optimizing the wrong problem.
