Best way to store/recreate intervals? (in C++)

[scootermaster]

Short [ha!] version:

I'm running a simulation (with undetermined "runtime"). I would like to know utilization intervals for some entities (i.e. 2 cycles on, then 3 cycles off, then 1 cycle on, then 5 cycles off, etc). So I'm trying to figure out the best way to store/recreate this.

I was just thinking of a STL vector (since it has dynamic add/resize) of bits. Then at the end, iterating through it and creating "chunks" from that. Then I thought of a vector of intervals itself, since while I won't know a priori how long something will be idle, I will know once it's active, for how long it will be so (i.e. at cycle 6, I'll know it'll be active for 3 cycles, so I could store, say, <6,9> or <6,3> or something). Then after execution, iterate through again and find the gaps (if any). The problem here is that there may be things like <6,9>, <10,12>,<11,15> which in reality is just <6,15>, since there are no gaps and I don't really care about a specific execution. Which I guess isn't a problem, I guess.

So if I do either of those, what's the best way of [hopefully in line] dumping the off intervals? Like, "after 100 cycles, it was inactive for 4, 5, 10, 1 and 1 cycles". Knowing when/where those intervals happened would be nice, but not essential (although in both cases it would seem I'd have this information).

Anyway, I'm kind of anal so something about the above solutions seems inelegant, and I feel like I'm missing something. Any ideas?

 

[degibson]

If this was my simulator, my choice would depend on the number of samples. If you're trying to recreate the utilization profile over a short interval (say, < 10K samples), use a vector<Interval>, where Interval is your own class, probably class Interval { uint64 m_start; uint64 m_stop; }; Size the vector at startup to MAX_SAMPLES, rather than use incremental addition (for better performance).

If you want a smaller, harder-to-parse log, you can just log the times at which the activity state changes, or time since the last change, e.g., a vector consisting of 2 3 4 5 would mean on at 2, off at 5, on at 9, off at 14, etc.

If you want to consider longer intervals (e.g., > 10K samples), I recommend you log directly to file so you don't futz with the rest of your simulation.

You could combine these techniques -- log MAX_SAMPLES at a time into your vector, when the vector fills, dump the whole thing to a file and keep on loggin'

 

[scootermaster]

If this was my simulator, my choice would depend on the number of samples. If you're trying to recreate the utilization profile over a short interval (say, < 10K samples), use a vector<Interval>, where Interval is your own class, probably class Interval { uint64 m_start; uint64 m_stop; }; Size the vector at startup to MAX_SAMPLES, rather than use incremental addition (for better performance).

If you want a smaller, harder-to-parse log, you can just log the times at which the activity state changes, or time since the last change, e.g., a vector consisting of 2 3 4 5 would mean on at 2, off at 5, on at 9, off at 14, etc.

If you want to consider longer intervals (e.g., > 10K samples), I recommend you log directly to file so you don't futz with the rest of your simulation.

You could combine these techniques -- log MAX_SAMPLES at a time into your vector, when the vector fills, dump the whole thing to a file and keep on loggin'

Aite. I don't imagine anything will take much longer than, oh, 500 "cycles" or so. At least, if it did, it'd take my system foreeeeever to process it. So I'll go with something like that.

 

[Schmide]

What degibson said except store negative time values for off. That way you can jump to any sample and know if it's an on or off event.

 

[scootermaster]

Recreating the intervals themselves was harder than I thought. I should have used a recursive solution, but instead used an iterative solution and it was tricky to get it right. Still not sure how I'm going to encode the information meaningfully, but at least for now I can output each "chunk" (i.e. ON 1-4, OFF 4-5, ON 6-10, etc).

 

[Net]

Recreating the intervals themselves was harder than I thought. I should have used a recursive solution, but instead used an iterative solution and it was tricky to get it right. Still not sure how I'm going to encode the information meaningfully, but at least for now I can output each "chunk" (i.e. ON 1-4, OFF 4-5, ON 6-10, etc).

iterative was a good idea. recursion will get ugly for large runs. two main problems for very large recursive calls, running out of stack space and slowing down your calculation.

 

[Schmide]

Whatever you're measuring, just log a time event when it starts processing and when it stops processing. My idea was to use negative time to distinguish the stop processing event type.

So your even list

ON 1-4, OFF 4-5, ON 6-10, etc

Would end up

1 -4 6 -10 etc