Re: [tracecompass-dev] Segmentstore intersection (inclusive or exclusive

[Matthew Khouzam <matthew.khouzam@xxxxxxxxxxxx>]

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
>>>    
>