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