pouët.net

I need something that works as an array but runtime resizable. I mean:

- The faster random access to the elements by index as in an array
- A fast way to resize it to add more elements

Until now, I've used directly an array with a predefined maximum elements. I suppose it is the faster execution time way to do it, but you know the problems: memory inneficient and size limited.

So, I've thought in realloc, but how fast is it? I've read that if there is not enough space to realloc, it mallocs again and copy the content, so it looks slow and also it would require a lot of free memory for that.

Is there any kind of structure where the access is random and fast? I'm really confused since this looks as a basic coding question, but I've never had the same problem and I have no idea of how to deal with it...

Maybe cutting the array in blocks, but then again I would have to mantain a fixed array of pointers to the blocks?

Try STL's vector and have a look at reserve(), it could be enough for what you need.

If you're willing to waste memory the traditional way is a linear array that reallocs it's memory by growing in a geometric series.

You ask for 5 elements, it grows to cover 8 possible ones. You ask for 9 it will allocate 16 and so on and so forth. This way you progressively reduce the number of reallocs as the array grows.

At work some of our software runs 4x faster on Linux than on Windows (same machine). We found that the reason was realloc. So at least under Windows you might want to minimize the use of realloc.

STL vector is what you need.

As much as a fish needs a bicycle.

another problem with realloc() is that it´s not thread safe, so if your threads are reallocating you are in trouble.

you can try the (very ugly) "nedmalloc" library. We got around 50 times faster reallocation that with windows default realloc(), and it´s thread safe. It´s a really ugly library, but depending for what you want it, it might help you.

if you code a demo, you most probably know the final size of the array. So allocate the max size once and have speed. Thanks to paging, an os only use RAM for those parts of an array you actually use (as long as you dont allocate it on the stack)

Now for something completely different...

I've been toying around a bit with SDL on Windows XP lately and have some stuff I like to show in a sequence. For timing I've taken the easy route and used a counter that decrease every time I do a screen update. The question now is, will this be equally fast on differently speedy CPU's or is the double buffer + flip thing somewhat consistent time-wise on different machines?

try STL vectors

El Topo, there was a thread on scene.se about using timers in windows demos which could be helpful

texel, why not just use a list (such as STL list)? i didn't see anything about needing O(1) index access. afaik the only advantage of vector over list is exactly that, and a little bit of extra memory. MSDN has a pretty nice page somewhere in its STL docs about "which container is good for me".

oh and there's really no reason not to use STL except if you're worried about code size or are developing a huge project with hours of compile time.

El Topo: Wouldn't it change with what the refresh rate happens to be? Or is that what you're after?

hollowman: Ok thanks, I'll check that one out...

Command Cyborg: Well, I'd rather have it be somewhat equally fast on all machines.

skrebbel: Why would you want the overhead of a list, though? Especially for demo purposes I'd say chasing pointers and constantly allocating list elements is a big no-no, however it looks in big O notation. Or?

El Topo: V-sync timing isn't even close to equally fast on all machines, as refresh rates vary a lot (typically 60-100 Hz or something). You can use system timers, or if you're using a music player library that'll probably provide a timer of some sort, too. An easier way is the performance counter which is very precise and high-resolution, but I've been told it can act a little strange on multi-core/CPU systems. That may not be a real issue, though.

Unless of course he's developing in C instead of C++ (*) but most democoders probably don't even know there's a difference.
*) which wasn't mentioned but why would a C++ programmer even know about such a thing when there's this magnificent and all-capable operator 'new'?

If you're using FMOD, please ignore this otherwise helpful advice. Otherwise it's ok, eg. DirectSound's GetPosition call (given that the sound system sets the GETPOSITION2 flag) is quite accurate.

Otherwise, QueryPerfomanceCounter/QueryPerformanceFrequency or timeGetTime/timeBeginPeriod/timeEndPeriod are your friends, yes.

El Topo, as kb says. Additionally you could combine the music system's timer with QueryPerf... but resyncing your timer to the music's timer (which has bad granularity but stays stable) every X milliseconds.

People suggesting std::vector; do you know how it works under the hood - is it just using a naive realloc? Or would it vary between implementations?

skrebbel: he says he wants random indexed access. Tracing from begin to head is faster with vectors also.

doom: STL list is mostly not about pointers and allocation. Push and pop operations are enough for many tasks, in between insertions are handled with pseudopointers (iterators), still you don't need to worry about allocating stuff.

216: If he's using C, his best option is still renaming his source file extensions and including vector (and probably fixing some dirty implicit pointer casts). That is if texel is still coding for PC.

parapete: Implementations can vary but all use new (instead of malloc kind) by default. Programmers can change the allocation model (allocators).

optanes, ahyes, he does. i misread. doom, what optanes said - there's no chasing nothing with STL list, and the slowdown is often irrelevant. sure, i wouldnt put my vertices in a list, but for many other purposes it's more efficient (quick insertions/deletions, etc). but yeah, i misread texels post and he wants random access.

parcelshit, afaik most vector implementations indeed merely wrap a simple c array with malloc and stuff. at least, i've been using the assumption that i can cast the address of the first element into a pointer and use the list accordingly, and it didn't break (msvc). i don't know if there are vector implementations that allow spreading an array over multiple memory areas.

kb: you meant, of course, "don't use FMOD".

oh and i didn't mean that std::vector always uses malloc and not new; i don't really know or care. what i meant is that the implementations i've used store everything in one line in memory, just like a malloc would.

That's an excellent example of what I meant when I said something about average demosceners' knowledge.