Skip to main content
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index] [List Home]
Re: [tracecompass-dev] Segmentstore intersection (inclusive or exclusive)
If you do a query 9:30-10:00, then yes I think latencies starting at 10:00 should be counted in. Just like the ones ending at 9:30 would be.
I'm not sure I understand the use case of wanting to do another query for 10:00-10:30 immediately after. That would be a new separate queries, and latency events ending at 10:00 would be included.
Also, even if you offset a border by one time unit, this only applies to segment that end/begin on that particular time. All the other segments that overlap the two time ranges will be "duplicates" here too.
For your lost events example, I assume you would like to store the lost event ranges in a segment store, and have the histogram read that to display the lost events? In that case I would suggest you just read the whole data structure sequentially (the default ordering is by ascending order of start times). If you try to go by doing separate requests with getIntersectingElements(), you will have an unending amount of "duplicates", no matter what the situation at the borders is. 

Cheers,
Alex

On 2015-07-03 04:43 PM, Matthew Khouzam wrote:

Thanks Alex!

About dupes, we want the model to store duplicates, so that we can have
two segments with the same time range, but I want to clarify, we may not
want duplicates while performing queries sequentially.

the whole inclusive thing makes more sense when we are dealing with the
state system since it is ensured to be contiguous in the states, if we
count the null states as states, which they are. :)

Here we have a funny sparse tree. I would like to give another use case
for it. Lost event ranges. Would you want the histogram to query at
9:30-10:00 then 10:00 to 10:30 or 9:30-9:59:59.999 then 10:00 to
10:29:59.999.

from a code pov this makes
if(delta < 1 ) throw new YoureDoingItWrongException(this);
for (int time = 0; time < timeMax; time += delta) {
     doThing(query(time, time + delta));
}

or
if(delta < 1 ) throw new YoureDoingItWrongException(this);
for (int time = 0; time < timeMax; time += delta) {
     doThing(query(time, time + delta - 1));
}

I am not a fan of the second pattern.

That's the main reason I like inclusive exclusive.

The secondary reason is quite simply, while designing the tests with
France, we discussed it, and while drawing out the boundary tests, it
really made more sense like that while drawing it out on a whiteboard
(which is continuous)

Cheers,

Matthew




On 15-07-03 03:59 PM, Alexandre Montplaisir wrote:

Hi,

Just to give a bit of context, the "segment store" is the new data
structure interface that will be used for example for latency
analysis. Like being able for instance to say "give me all the system
calls that cross the given timestamp". Or a given time range.

So the question here is, if given a time range, should latency events
that start or end at the borders of the time range be counted in?


Imo, it should be symmetrical. Inclusive at the start but exclusive at
the end does not work very well with discrete values. (With continuous
values it could make a bit more sense though.)
On the other hand, the state system is inclusive/exclusive, because
when a state ends, a new one beings. But the segment store doesn't
have to be wrt time. It could be read in one direction or another.
Which is why I think asymmetrical feels weird.



[...]
So if your only interface to the segment store is the intersection
function, you'll have to manually filter out the results of each
iteration to avoid duplications, and then you can decide if you want
to include or exclude the end bound.

It might depend on the use case, but for the latency analysis, you
want the duplicates (hence why the current implementation uses
TreeMultimap's, not just TreeMap's). If you have two latency events
that happen to start and end at the same time, you want both in the
returned results.

Cheers,
Alex


Patrick

On Fri, Jul 3, 2015 at 1:54 PM, Matthew Khouzam
<matthew.khouzam@xxxxxxxxxxxx <mailto:matthew.khouzam@xxxxxxxxxxxx>>
wrote:

      Hi all, I want to discuss a bit the design or the statesystem
segement
      store.


      Right now the get intersection is inclusive/inclusive, I would
propose
      that it should be inclusive/exclusive.

      So here are some test cases


      philosophical test cases
      query range,  segment, included?

      infinity, infinity, yes
      finite, infinity, no
      infinity, finite, yes

      specific test cases
      query range,  segment, included?

      (0,2) , (-1,-1), no
      (0,2) , (-1,0), yes
      (0,2) , (-1,2), yes
      (0,2) , (-1,2), yes
      (0,2) , (-1,3), no
      (0,2) , (0,0), yes
      (0,2) , (0,1), yes
      (0,2) , (0,2), yes
      (0,2) , (0,3), yes
      (0,2) , (1,1), yes
      (0,2) , (1,2), yes
      (0,2) , (1,3), yes
      (0,2) , (2,2), yes*
      (0,2) , (2,3), yes*
      (0,2) , (3,3), no
      (0,2) , (3,4), no

      The results noted with a star (*) are the ones I would propose
      changing.
      The reasoning, being that it will make iteration much simpler.
It is
      much more intuitive to say for example, give me everything
between t1
      and t2, now t2 and t3...

      The patch is easy to do, but I want to make sure we are on the
      same page
      for this.

      Why would this be important? We will use the segment store to show
      cumulative information too, so it we query between 0 and 5 and the
      number of segments is different from querying from 0 to 1, 1 to 2,
      2 to
      3, and 3 to 4. As we can have two identical segments in a store
(not
      impossible) this will be much harder to manage than using an
inclusive
      exclusive scheme. This pattern will allow iterating over the
segment's
      dimension, e.g. time.

      On a final note, one of my colleagues asked a really good
      question, does
      Game of Thrones play from 9:00 to 10:00 or 9:00 to 9:59:59.999?
I vote
      for 9:00 to 10:00.

      Thoughts?

      Matthew

Back to the top