Vector question

advanced
#1

Hi,

It’s not so openFrameworks related, but am programming this in OF (and it looks great!), so maybe some of you could answer this one.

I am recording a load of FFT spectrograms, big vectors of vectors, and processing these. Every now and then the program’s soundStream gets interrupted. I suspect, because the vector has run out of size and needs to reallocate memory and copy the old data across. Is there any way to check if that is indeed happening?

(supposing it is, I might then try to get round it by making circular vectors or something)

also, is there any problem in doing something like

create std::vector newVector
myBigMatrix.erase(myBigMatrix.begin())
myBigMatrix.push_back(newVector)

this would erase the first column and add to the last. Thus keeping the big matrix at constant size. But is vector the best way to implemewnt such a thing? Is the copying of all the other vectors a memory-intensive thing to do?

any help much appreciated!

Andrew

#2

Hi,

I think there’s many possible answer to your problem (I’m not a data structure expert, nor a high performance computing guy, so you should double check everything !).

So first question, do you have an idea of the size of your matrix ? If so you can reserve the space needed at runtime, and avoid what you describe.

Second, to check if you hypothesis is true, you can use a software that monitor the memory usage of a process (process explorer on windows is pretty handy for this kind of stuff, and if you’re developing on linux/mac osx you can use the comand line tool “ps” to check that) This way you can see whether there’s a big jump in the memory usage after the soundStream is interrupted.

Concerning what you suggest: here’s what the stl documentation says:

“Because vectors use an array as their underlying storage, erasing elements in positions other than the vector end causes the container to relocate all the elements after the segment erased to their new positions. This is generally an inefficient operation compared to the one performed for the same operation by other kinds of sequence containers (such as list or forward_list).”

So that doesn’t seem hyper bueno to me. As suggested, you can use a list structure instead.
If you don’t need a fast access to your data, list should be good, however if you’re relying on the contiguity of your vector (for caching purpose, pointer magic, or whatever) you might seek other alternative.

For instance, you can check boost matrix that are apparently okay.

Finally, you can build some metrics to evaluate different solution: by either measuring the time it takes to let say handle 10 000 data or counting the number of processor cycle it takes.
Something that goes in this direction:

http://lemire.me/blog/archives/2012/06/20/do-not-waste-time-with-stl-vectors/

Hope it helps,

Philippe

#3

this sounds like a job for a queue: http://www.cplusplus.com/reference/queue/queue/

untested:
create std::vector newVector
myBigMatrix.pop()
myBigMatrix.push(newVector)

#4

The matrix is being dynamically added to. I have made some headway with this, related to both your replies here.
Using myBigMatrix.capacity() you can see the memory allcoated for the vector.
I found that the capacity had jumps from 2048 to 4096 to 8192 etc, and these corresponded to the problems in the audio.

So I’ve looked to remove old elements and add new ones.
Restricting the vector to a fixed size, we could copy all elements manually. For a 512 vector, this takes ~= 15000 micros (15 msec).
By using myBigMatrix.erase(myBigMatrix.begin())
it will improve to about 11200 micros (1.2 msec).

I’ve now implemented a version that instead uses std::deque
The advantage here is that the double-ended queue can allow removal from both ends of the vector. This hasn’t required too much changing of the code (apart from making sure the data is not accessed by draw() when the removal process takes place). This now allows
myBigDequerMatrix.pop_front()
an operation not available to vectors
and takes only 6micros (0.006msec)

Also the queue also looks ideal for this. I get the impression that it will remove the oldest element when adding a new one. So a fixed sized queue would do what I’m hoping. I’ll look into that…

Thanks!
Andrew

#5

I get the impression that it will remove the oldest element when adding a new one.

not automatically afaik, you still have to pop().
fwiw, the default container type for a queue is a deque anyway, so the behaviour will be pretty similar.

I found that the capacity had jumps from 2048 to 4096 to 8192

this is the standard behaviour of vectors - if they approach/reach(?) their allocated capacity, they are re-allocated to a twice as large capacity. you can avoid this by creating the vector with a certain size, and keeping it at that size.

#6

Yes, it looks like the advantage of a deque is that you still have the [] operator, so the elements can be accessed as an array. And since this is for an FFT-style spectrogram, that’s really useful.

I found that the capacity had jumps from 2048 to 4096 to 8192

Indeed. Although here, the problem has been how to use a fixed vector of N elements but allow for new data coming in. In order to keep it at fixed size, we have to delete old data.
It does seem that the erase() method for vector is less efficient than implementing as a deque and using pop_front(), with the caveat that accessing elements can be easier for a vector as the memory is allocated as a big chunk.

being in London, I’ve implemented this as
typedef std::deque DoubleDequer
:wink:

(okay in fact a deque of DoubleVectors but I might find use for the DoubleDequer)