Description

template<class T, class IndexTag = TraceMapIndexTag>
class Sawyer::Container::Trace< T, IndexTag >

Records and replays traces.

This class is able to record a trace and replay it later. A trace is an ordered list of labels of type T, where a label can be any type whose members have an ordering relationship (integers, strings, pointers, certain kinds of iterators, etc.). Some examples where a Trace could be used:

To record a traversal through a tree-like data structure where the nodes of the tree have string labels.
To record a traversal through a Sawyer::Container::Graph whose vertices are numbered.
To record the states executed by a DFA

Of course, a container traversal or DFA execution could also be replayed by re-traversing or re-executing, but that's not always convenient due to data modification during the traversal, the size of the associated data, or the runtime expense. Furthermore, a Trace can also answer queries like how often a label was visited, what transitions are most common, and so on.

Although a trace can be stored simply as an ordered list of labels, doing so is not always the most efficient. A Trace compresses a trace by observing that many kinds of traces tend to be "bursty". That is, the successor of each visit to label A is likely to be the same as the successor of the previous visit to A. See burstiness. The higher the burstiness the more compression is possible.

In order to compress a trace and to later obtain information on a per-label basis, the Trace needs to be able to form an index of the labels. The second template argument, IndexTag, is a tag that selects an index type from the TraceIndexTraits. Sawyer provides the following tags, but users can create additional tags and their own index types. TraceMapIndexTag is the default and uses an std::map to store labels; TraceVectorIndexTag causes an std::vector to be used instead and is suitable for a dense set of low-numbered labels.

Example: recording a program execution trace for a control flow graph

This example records a program execution trace (ET) over a control flow graph (CFG). An ET is the ordered list of machine instruction addresses executed by a program when it runs, and a CFG is a graph whose vertices are all known instruction addresses and whose edges represent possible execution flow from one instruction to another. Non-branching instructions have only one outgoing edge, and most branches have two outgoing edges (indirect branches have more). For simplicity, we assume that the CFG is complete and is computed prior to obtaining the trace. The important thing to know is that execution traces tend to be bursty: non-branching instructions always have the same successor, and branching instructions (especially those controlling loops) tend to branch one way more often than the other.

using namespace Sawyer;
using namespace Sawyer::Container;
class Instruction { ... } // some user-defined type
class CfgEdge { ... } // some user-defined type
class Program { ... } // some user-define type
Program program("a.out"); // user-defined: starts a program in a debugger
typedef Graph<Instruction, CfgEdge, unsigned> Cfg; // instructions indexed by their unsigned address
typedef Trace<size_t, TraceVectorIndexTag> Trace; // labels are sequential CFG vertex IDs, so a vector is appropriate
Cfg cfg;
Trace trace;
while (program.isRunning()) {
    unsigned address = program.executionAddress();
    Cfg::ConstVertexIterator vertex = cfg.findVertexKey(address); // O(log) or O(1) depending on index type
    trace.append(vertex->id()); // O(1)
    program.singleStep();
}

Later, we can replay the trace without the expense of running the program again:

trace.traverse([&cfg](size_t vertexId) {
    Cfg::ConstVertexIterator vertex = cfg.findVertex(vertexId); // O(1)
    const Instruction &insn = vertex->value();
    std::cout <<"executed " <<insn.toString() <<"\n";
    return true; // continue traversal
});

If we know the address of a branch instruction (such as for an "if" statement in a higher level language), we can query some properties such as burstiness to decide whether speculative execution would be beneficial here:

unsigned branchAddress = ...;
if (trace.exists(branchAddress)) { // branch was executed at least once?
    if (trace.burstiness(branchAddress) >= 2.0) {
        // loosely speaking, the branch predicate is not random; 2.0 is arbitrary
    }
}

Definition at line 262 of file Trace.h.

#include <util/Sawyer/Trace.h>

Classes
class	ConstIterator
	Forward iterator. More...

struct	Successor
	Compressed next-label list. More...

Public Types
typedef T	Label
	Label type. More...

typedef std::vector< Successor >	Successors
	Successors for a label. More...

Public Member Functions
	Trace ()
	Default constructor. More...

ConstIterator	begin () const
	Returns a forward iterator pointing to first element of this trace. More...

ConstIterator	end () const
	Returns a forward iterator pointing past the end of this trace. More...

Label	front () const
	Returns the first item in the trace. More...

Label	back () const
	Returns the last item in the trace. More...

void	clear ()
	Clears the recorded trace. More...

void	reserve (size_t n)
	Reserve space in the label index. More...

bool	isEmpty () const
	Determines if a trace is empty. More...

bool	exists (const Label &label) const
	Determines if a label is present in a trace. More...

size_t	nLabels () const
	Number of distinct labels. More...

Sawyer::Container::Set< Label >	labels () const
	Set of all labels in the trace. More...

void	append (const Label &label)
	Append a label to a trace. More...

template<class Visitor >
void	traverse (Visitor &visitor) const
	Traversal of the trace labels. More...

void	print (std::ostream &out, const std::string &separator=", ") const
	Print as sequence. More...

void	dump (std::ostream &out) const
	Low-level debugging information. More...

std::vector< Label >	toVector () const
	Convert a trace into a vector. More...

std::set< Label >	successorSet (const Label &label) const
	Set of labels which are successors for the specified label. More...

double	burstiness () const
	The burstiness of a trace. More...

const Successors &	successors (const Label &label) const
	Ordered successors for a label. More...


size_t	size () const
	Total length of a trace, or the number of times a label appears in a trace. More...

size_t	size (const Label &label) const
	Total length of a trace, or the number of times a label appears in a trace. More...


double	burstiness (const Label &label) const
	The burstiness of a label. More...

Member Typedef Documentation

template<class T, class IndexTag = TraceMapIndexTag>

typedef T Sawyer::Container::Trace< T, IndexTag >::Label

Label type.

Labels must have an ordering defined by a less-than operator.

Definition at line 275 of file Trace.h.

template<class T, class IndexTag = TraceMapIndexTag>

typedef std::vector<Successor> Sawyer::Container::Trace< T, IndexTag >::Successors

Successors for a label.

Definition at line 289 of file Trace.h.

Constructor & Destructor Documentation

template<class T, class IndexTag = TraceMapIndexTag>

Sawyer::Container::Trace< T, IndexTag >::Trace ( )

inline

Default constructor.

Definition at line 379 of file Trace.h.

Member Function Documentation

template<class T, class IndexTag = TraceMapIndexTag>

ConstIterator Sawyer::Container::Trace< T, IndexTag >::begin ( ) const

inline

Returns a forward iterator pointing to first element of this trace.

Definition at line 382 of file Trace.h.

template<class T, class IndexTag = TraceMapIndexTag>

ConstIterator Sawyer::Container::Trace< T, IndexTag >::end ( ) const

inline

Returns a forward iterator pointing past the end of this trace.

Definition at line 387 of file Trace.h.

template<class T, class IndexTag = TraceMapIndexTag>

Label Sawyer::Container::Trace< T, IndexTag >::front ( ) const

inline

Returns the first item in the trace.

The trace must not be empty. Returns a copy of the item.

Definition at line 394 of file Trace.h.

Referenced by Sawyer::Container::Trace< T, IndexTag >::ConstIterator::ConstIterator().

template<class T, class IndexTag = TraceMapIndexTag>

Label Sawyer::Container::Trace< T, IndexTag >::back ( ) const

inline

Returns the last item in the trace.

The trace must not be empty. Returns a copy of the item.

Definition at line 401 of file Trace.h.

template<class T, class IndexTag = TraceMapIndexTag>

void Sawyer::Container::Trace< T, IndexTag >::clear ( )

inline

Clears the recorded trace.

This Trace is reset to its default-constructed state.

Definition at line 408 of file Trace.h.

template<class T, class IndexTag = TraceMapIndexTag>

void Sawyer::Container::Trace< T, IndexTag >::reserve ( size_t n )

inline

Reserve space in the label index.

This is a hint to reserve space for n distinct labels in the label index. The index need not honor this request.

Definition at line 417 of file Trace.h.

template<class T, class IndexTag = TraceMapIndexTag>

bool Sawyer::Container::Trace< T, IndexTag >::isEmpty ( ) const

inline

Determines if a trace is empty.

Returns true if and only if a trace contains no labels.

Time complexity: constant.

Definition at line 426 of file Trace.h.

Referenced by Sawyer::Container::Trace< T, IndexTag >::append(), Sawyer::Container::Trace< T, IndexTag >::ConstIterator::ConstIterator(), Sawyer::Container::Trace< T, IndexTag >::dump(), Sawyer::Container::Trace< T, IndexTag >::exists(), and Sawyer::Container::Trace< T, IndexTag >::traverse().

template<class T, class IndexTag = TraceMapIndexTag>

bool Sawyer::Container::Trace< T, IndexTag >::exists ( const Label & label ) const

inline

Determines if a label is present in a trace.

Returns true if and only if the specified label occurs in the trace.

Time complexity: depends on the label indexing scheme, but probably constant for labels that can be used as array indexes and logorithmic for labels that are map lookup keys.

Definition at line 436 of file Trace.h.

References Sawyer::Container::Trace< T, IndexTag >::isEmpty().

Referenced by Sawyer::Container::Trace< T, IndexTag >::append().

template<class T, class IndexTag = TraceMapIndexTag>

size_t Sawyer::Container::Trace< T, IndexTag >::size ( void ) const

inline

Total length of a trace, or the number of times a label appears in a trace.

Time complexity: constant.

Definition at line 445 of file Trace.h.

Referenced by Sawyer::Container::Trace< T, IndexTag >::burstiness().

template<class T, class IndexTag = TraceMapIndexTag>

size_t Sawyer::Container::Trace< T, IndexTag >::size ( const Label & label ) const

inline

Total length of a trace, or the number of times a label appears in a trace.

Time complexity: constant.

Definition at line 448 of file Trace.h.

template<class T, class IndexTag = TraceMapIndexTag>

size_t Sawyer::Container::Trace< T, IndexTag >::nLabels ( ) const

inline

Number of distinct labels.

This is the number of unique labels that appear in the trace.

Time complexity: constant.

Definition at line 459 of file Trace.h.

template<class T, class IndexTag = TraceMapIndexTag>

Sawyer::Container::Set<Label> Sawyer::Container::Trace< T, IndexTag >::labels ( ) const

inline

Set of all labels in the trace.

This is the set of labels in no particular order.

Definition at line 466 of file Trace.h.

References Sawyer::Container::Set< T, C, A >::insert().

template<class T, class IndexTag = TraceMapIndexTag>

void Sawyer::Container::Trace< T, IndexTag >::append ( const Label & label )

inline

Append a label to a trace.

Time complexity: amortized constant if labels are array indexes, amortized logirithmic if labels are map keys.

Definition at line 476 of file Trace.h.

References Sawyer::Container::Trace< T, IndexTag >::exists(), and Sawyer::Container::Trace< T, IndexTag >::isEmpty().

Referenced by Rose::BinaryAnalysis::Debugger::Base::trace().

template<class T, class IndexTag = TraceMapIndexTag>

template<class Visitor >

void Sawyer::Container::Trace< T, IndexTag >::traverse ( Visitor & visitor ) const

inline

Traversal of the trace labels.

The visitor functor takes one argument: the label being visited, and should return true if the traversal should continue or false if it should be terminated.

Time complexity: initialization time is proportional to the number of distinct labels in the trace. Advancing from one label to the next is constant time.

Definition at line 505 of file Trace.h.

References Sawyer::Container::Trace< T, IndexTag >::Successor::end, Sawyer::Container::Trace< T, IndexTag >::isEmpty(), and Sawyer::Container::Trace< T, IndexTag >::Successor::next.

Referenced by Sawyer::Container::Trace< T, IndexTag >::print(), and Sawyer::Container::Trace< T, IndexTag >::toVector().

template<class T, class IndexTag = TraceMapIndexTag>

void Sawyer::Container::Trace< T, IndexTag >::print	(	std::ostream &	out,
		const std::string &	separator = `", "`
	)		const

inline

Print as sequence.

Emits the trace to the specified output stream with each element separated by the separator.

Definition at line 555 of file Trace.h.

References Sawyer::Container::Trace< T, IndexTag >::traverse().

template<class T, class IndexTag = TraceMapIndexTag>

void Sawyer::Container::Trace< T, IndexTag >::dump ( std::ostream & out ) const

inline

Low-level debugging information.

This method is intended for debugging. It prints the storage representation of this trace. The output format is not defined.

Definition at line 564 of file Trace.h.

References Sawyer::Container::Trace< T, IndexTag >::Successor::end, Sawyer::Container::Trace< T, IndexTag >::isEmpty(), and Sawyer::Container::Trace< T, IndexTag >::Successor::next.

template<class T, class IndexTag = TraceMapIndexTag>

std::vector<Label> Sawyer::Container::Trace< T, IndexTag >::toVector ( ) const

inline

Convert a trace into a vector.

Converts a trace into a vector of labels. Consider using traverse instead since it's more efficient.

Definition at line 596 of file Trace.h.

References Sawyer::Container::Trace< T, IndexTag >::traverse().

template<class T, class IndexTag = TraceMapIndexTag>

std::set<Label> Sawyer::Container::Trace< T, IndexTag >::successorSet ( const Label & label ) const

inline

Set of labels which are successors for the specified label.

Time complexity: The set must be constructed by traversing successor sequence. The length of the successor sequence is the number of maximal subsequences where the members of a subsequence are all the same. Insertion of each label into the set has logarithmic time.

Definition at line 607 of file Trace.h.

References Sawyer::Container::Trace< T, IndexTag >::Successor::next.

Referenced by Sawyer::Container::Trace< T, IndexTag >::burstiness().

template<class T, class IndexTag = TraceMapIndexTag>

double Sawyer::Container::Trace< T, IndexTag >::burstiness ( const Label & label ) const

inline

The burstiness of a label.

Loosely speaking, the "burstiness" of a label is a measure of how often successive occurrences of the label transition to the same successor and is a floating point value between zero and one, inclusive. Specifically, the burstiness of a label is the number of distinct labels divided by the number of maximal subsequences of the successor sequence where a subsequence's members are all the same label.

For example, if the the entire trace is [5, 5, 5, 4, 5, 5] then the successors of label 5 are the sequence [5, 5, 4, 5] and the maximal subsequences of one label are [5, 5], [4], and [5]. The burstiness of 5 is therefore 2/3 since there are two distinct labels, {4, 5}, and three maximal successor subsequences.

Some properties: A label with only one distinct successor, will have a burstiness of 1.0 no matter how many times the label appears in the trace. A label with N distinct successors will have a burstiness of 1.0 if it visits the first distinct successor, then the second, then the third (in any order) without any interleaving. A label that interleaves its successors as much as possible will have a burstiness of approximately 1/N where N is the number of distinct successors.

If label has no successors then zero is returned. This is distinguishable from other cases since normal return values will always be positive.

Time complexity: O(n) where n is the number of maximal subsequences of the successors where all members of a subsequence are equal. Time to look up the label depends on the label index type.

Definition at line 638 of file Trace.h.

References Sawyer::Container::Trace< T, IndexTag >::size(), and Sawyer::Container::Trace< T, IndexTag >::successorSet().

template<class T, class IndexTag = TraceMapIndexTag>

double Sawyer::Container::Trace< T, IndexTag >::burstiness ( ) const

inline

The burstiness of a trace.

The burstiness of a trace is the average burstiness of its labels.

Definition at line 648 of file Trace.h.

References Sawyer::Container::Trace< T, IndexTag >::size(), and Sawyer::CommandLine::sum().

template<class T, class IndexTag = TraceMapIndexTag>

const Successors& Sawyer::Container::Trace< T, IndexTag >::successors ( const Label & label ) const

inline

Ordered successors for a label.

Given a label, return a vector that describes the ordered successors for this label. The return value is a list whose members are pairs consisting of an integer visit sequence number and a label. For instance, if label A was visited 10 times and the successors were, in order, [B, B, B, B, B, C, C, B, B, D] then the return value will be the list of pairs [(5,B), (7,C), (9,B), (10,D)].

Time complexity: Depends on the label index type. If the TraceVectorIndexTag was specified then this method executes in constant time.

Definition at line 669 of file Trace.h.

The documentation for this class was generated from the following file:

Trace.h

Description

template<class T, class IndexTag = TraceMapIndexTag> class Sawyer::Container::Trace< T, IndexTag >

Example: recording a program execution trace for a control flow graph

Classes

Public Types

Public Member Functions

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

template<class T, class IndexTag = TraceMapIndexTag>
class Sawyer::Container::Trace< T, IndexTag >