| [linuxtools-dev] Re: TMF questions |
Just moving this discussion to the mailing list./fc
From: Polzer, Franz [mailto:Franz_Polzer@xxxxxxxxxx]
Sent: October-15-09 3:14 PM
To: Francois Chouinard
Cc: Kreutzer, Manfred
Subject: AW: TMF questionHello Francois,[1] I do not assume events are of the same size, so we are on the same page :)It was just a clarification :-)[2] What I meant is that for parsing all N events on an indexed page we have to search for the first event, then for the second beginning from the first and so on. So we need N * N / 2 event skip (during event search) operations for parsing all N events in an index page. Right?Not exactly. It would be more like N/2 on average and N-1 in the worst case, N being the interval between 2 checkpoints.E.g. Assuming that we store a checkpoint at every 1000 events (i.e. N = 1000), looking for event 3025 will require:[1] Position the trace at event 3000 (the third checkpoint)[2] Read 25 times to reach event #3025We can't keep the file content in memory and we can't have an index for each event (we are talking many millions here). By playing with the page size (N) and using caches I think we can get reasonable responsive times.[3] The trace/stream underlying is a user-implemneted object. Of course a file stream (even when managing multiplle fiels) has one active location but when this is implemented in JNI the random file access can be performed really fast so I think that's not an issue.What I suggested is that the location object can also be used for storing (in addition to the page starting index) the current file offset into the stream. I C/C++ there is a concept of using thread local storage. This is a variable that is named the same for all threads, but it holds a different object depending on the thread that uses the variable. So we could archive storing the actual parse position for each thread without the need or searching for the file position by iterating the events in the index page. This would greatly enhance performance of the system i think. I have to check the documentation if something similar exists in java. Otherwise we can use it using JNI then?Humm. I'm not sure I'm following you on this one. The location object does pretty much what you said. I am not aware of thread local storage in Java, although it might exist. Nonetheless, there is only one "effective" context per reading thread and it is initialized only once. The logic goes as follows:[1] Given a timestamp (or index), find the location of the checkpointed event closest (but before) in the index table (binary search or modulo). This should be the only index search for that particular thread.[2] Given the location of the checkpointed event, perform a first seekLocation() which will position the file and return a new context that can be used for subsequent accesses.[3] Using that context, perform readNextEvent() until the requested event is reached. Each readNextEvent() eventually calls seekLocation() because the file position might have changed between 2 calls to readNextEvent(). If the file was not re-positionned by a concurrent thread, there should be practically no cost for the seek operation.[4] Agreed.[5] I'm not sure if we can hold all this data in the checkpoints. Thinking of a system that traces multiple millions of events would break any memory allocation system when we try indexing each event in the index page.As you mention, I don't think it is realistic to index every event. This is why the index table checkpoints only every Nth event and the FW uses these checkpoints to position the trace in the vicinity of the requested event (and then perform the additional read required).This is really a trade-off between memory and speed: the smaller N, the faster the access but more memory is required to hold the index table. Ergo, N is a parameter for the designer to decide :-)An alternative would be to set an upper bound for the index table size and dynamically adjust N:[1] Set N = 1 and start indexing the trace (i.e. store every Nth event loction)[2] If the table size limit is reached, purge every other checkpoint, pack the table, set N' = 2*N and continue indexing (every N' location)This way the index table would be 75% full on average.[6] Was my fault. I understood it as each parse has not only to advance the index and timestamp for each parsed event but also the location. Then I would modify the location object of the index map also because I do not get a copy but a reference to the location object.Yes - i will do :)It's getting late here in Vienna (9pm currently). So I think I will continue checking this tomorrow :)br,Franz
Von: Francois Chouinard [mailto:francois.chouinard@xxxxxxxxxxxx]
Gesendet: Do 15.10.2009 20:42
An: Polzer, Franz
Cc: Kreutzer, Manfred
Betreff: RE: TMF questionHi Franz,[1] You obviously can't assume that all events are of the same size. Furthermore, you can't even assume that there is only one stream: an LTTng trace is composed of a variable number of individual files - one per traced channel. So the concept of stream offset just doesn't work in the general case. This is why location is an Object and not just a plain integer.[2] To prevent locating an event by successive reads from the beginning of the trace, the trace is indexed (see TmfTrace): at every N events, a checkpoint (the TmfTraceContext) is saved. This ensures that, in the worst case, N-1 events will have to be read to access any event after positionning the trace at the previous chekpoint (since the events are not of fixed size, you can't just "jump" in the trace). The choice of N becomes an issue but it can be specified on the trace constructor. Furthermore, by judicioulsy using caches of size N, we can greatly mitigate that problem.[3] The location object is (supposed to be) unique for each context ergo for each thread that accesses the stream. But, the underlying trace/stream has only one current location even if it is accessed by multiple threads. The obvious solution is to ensure that positioning and reading the trace/stream is done atomically. I'm not clear on how having multiple faces for each thread solves the concurrency issue. Would you care to elaborate?[4] So far, the location object has no behaviour and does not handle location requests. I would believe that positionning a stream is a responsibility not of the location object but of the steam itself (using location as parameter).[5] The purpose of indexing is to come up with a structure that gives fast access to a particular event based on its timestamp or index (i.e. the nth event of the trace - usefull for tables). So, the checkpoint information has to hold that information somehow. Maybe the problem is that I am using context for checkpoint. But it keeps me from doing some checkpoint gymnastics (like patching the timestamp of the previous context...).[6] I'm not so sure that I modify the index map. Unless I made a mistake, I believe that the context passed to getNextEvent() was previously generated by a call to seekLocation() which should always return a brand new context (different from the one that was fed as its parameter). But I agree that there is a potential problem and that the context stored in the index map should not be accessible from outside (and be cloned before usage).Keep the comments/questions coming :-)Best Regards,/fc
From: Polzer, Franz [mailto:Franz_Polzer@xxxxxxxxxx]
Sent: October-15-09 1:00 PM
To: Francois Chouinard
Cc: Kreutzer, Manfred
Subject: AW: TMF questionHello Francois,The problem is that it's easy to use if you have an event stream where each event is equal in size and you can position it by simply setting the stream position and searching can be done by multiplication by the event size.but when the stream holds variable-sized events this solution enforces that each event within the large file has to be searched from the very beginning. Of course it would be possible to store the stream position in the location object, but for each parseEvent I would have to call seekLocation and this would then have to count the variable size events starting from the last well known stored position.I'm not sure if that's possible in Java but we can overcome the concurrency problem by using something like thread-local storage in C/C++. When the location object would have multiple faces for each thread the problem of concurrency would be solved.Maybe the location object can be a stub which will handle each of the thread location requests separately.The problem with the specification that the location has to match the returned event is that it breaks your concept of the indexing. You are making copies of the contexts for the index, but you are returning the very same location objects to parse event which will modify the location and will therefore also modify the object in the index map. Or have I overseen something?Best regards,Franz
Von: Francois Chouinard [mailto:francois.chouinard@xxxxxxxxxxxx]
Gesendet: Do 15.10.2009 17:26
An: Polzer, Franz
Cc: Kreutzer, Manfred; Francois Chouinard
Betreff: RE: TMF questionHi Franz,See my answers below.Best Regards,/fc
From: Polzer, Franz [mailto:Franz_Polzer@xxxxxxxxxx]
Sent: October-15-09 3:22 AM
To: Francois Chouinard
Cc: Kreutzer, Manfred
Subject: RE: TMF questionHello Francois,
Please correct me when I’m wrong:
- seekLocation returns a context at the given location (the context contains a user-defineable location object that might be used for fast positioning the stream)
- parseEvent returns the current event and advances the context to the next event.
Correct.
My understanding of how parseEvent works is that it takes the context, reads the event at the context’s position and advances the context to the next event to be read. The LTTng sample implementation calls seekLocation every time in the parseEvent method which should not be needed from my point of view because the context should point to the correct location in the file(s) using the user-defined location object.
Not exactly. Unfortunaltely, multiple clients (views, etc) might access the same trace concurrently but for different locations. You can see what kind of problems this can cause: it can not be guaranteed that the trace pointer has not been modified by a concurrent thread between 2 calls to parseEvent(). Therefore, within parseEvent(), the trace has to be positionned synchronously and something equivalent to a call to seekLocation() is required.
BTW, LTTng does a quick test for the current position in seekLocation() and does nothing if the steam is already at the right place. This is a quick test that could easily be migrated in the framerwork, assuming that the concrete Trace class can implement a the correct predicate (current location == requested location).
But I agree that this is not a very pretty piece of code and that uncontroled concurrency causes all kinds of bad delays when simultaneous accesses are enabled. I intended to mitigate the issues with caches but I'm not sure it will be enough :-( Another thing I'm looking into is request coalescing which should also help. If you have other ideas, they are welcome!
But I encountered that this is not possible to use parseEvent without calling seekLocation because when the framework positions the traces it makes a copy of the TmfTraceContext but it makes no copy of the user-defined location objects inside this context.
Hummm, I'm not sure of that: the TmfTraceContext copy constructor does not clone the location (which it should...) but definitely stores it (not my best idea). As you already figured out, the context is used to reposition the trace correctly before a parse/read. I might have missed something but if you found a place where the location is not set properly, please let me know (that would likelybe an error).
What does not show too much in the code comments is that the location can be a tricky thing: in the case of LTTng, the library uses the timestamp as the location while more "standard" trace/log types would use stream offset or something similar. TmfTraceContext has this constraint that its location has to correspond to the event with the given timestamp (and index...) which is delicate to handle without affecting the LTTng parsing library performance. In fact, I had to hack the code to make it work properly for LTTng and I now have to seriously revisit this part.
It would be much more efficient when the framework would also copy the user-defined location object inside the context when making a copy of the context because then no seek is needed in parse Event. The framework would set the new context using the positionTraces method and call parse event. And the context would be already positioned at the correct position that the user-implemented stream would need to read the next event. And when the event is read the parse event will also modify the user-defined location to the next event to be read. Working this way would remove a lot of unnecessary seekLocation calls during the event parsing stage.
What do you think?
It would be so much easier without concurrency :-) Unfortunately, I don't have yet a good, generic solution for this and I'm not sure I want to sacrifice UI responsiveness. But this is definitely an area that has to be worked on.
By the way – do you have any new model documentation as you mentioned last week?
Working on it...
Best regards,
Franz Polzer
SW Development Engineer
Embedded Systems Division
Mentor Graphics Corporation
www.mentor.com/embedded
From: Francois Chouinard [mailto:francois.chouinard@xxxxxxxxxxxx]
Sent: Thursday, October 08, 2009 4:05 PM
To: Polzer, Franz
Cc: Kreutzer, Manfred
Subject: RE: TMF question
Hi Franz,
You are absolutely right and this is one of the very first "improvements" that we will address as soon as we are done with the initial release of LTTng (due tomorow :-).
I expect to have something early next week. I will be happy to forward you the updated model doc for comments.
Regards,
/fc
From: Polzer, Franz [mailto:Franz_Polzer@xxxxxxxxxx]
Sent: October-08-09 5:13 AM
To: Francois Chouinard
Cc: Kreutzer, Manfred
Subject: TMF questionHello,
I’m trying to use the TMF classes.
The TmfEventContent is used to store the trace content data and the TmfEventField is used to provide the GUI representation of this content. My problem is that the TmfEventContent stores the event data content internally already as parsed string.
I wanted to know why the design was done that way. From my point of understanding I would create a TmfEventContent providing a content object that the TmfEventFormat can split up into fields. But in the current TMF implementation the TmfEventContent is calling .toString() and stores the returned string instead of the raw data. Wouldn’t it be more useful when the TmfEventContent object would store the original given content object as Java object and the TmfEventFormat will split up the data either binary or by using .toString()? This would allow more flexibility in the usage of the content/format pair and would also improve performance when no string parsing needs to be done by the TmfEventFormat object.
Best regards,
Franz Polzer
SW Development Engineer
Embedded Systems Division
Mentor Graphics Corporation
www.mentor.com/embedded