m(e)

v

::=

| new C< T , > | (T )e ι | null

Q

::=

class C<X
T , O
τ ,Owner
τ , This
τ >
N {T f; M }

M

::=

<X
T , O
T > T m (T x) {return e;}

method declarations

N R

::= ::=

C | Object< τ , τ > N | X

class types non-existential types

T, U

::= ∃Δ.N | ∃∅.X |

P

::= T | 

X ,Y ::= Δ B Γ γ H

::= ::= ::= ::= ::=

types

m | ethod type parameters

X | O | v X →[B l T | ⊥ γ:T ι | x ι →{N ;

type parameters

B u ]type environments bounds variable environments locations or variables f→v} heaps

expressions values

T

::=

T | τ

types and contexts

P ::=

T | 

method parameters

τ

World<> | O | v

::=

x, this X, Y O, Owner, This ι C, Object, World f, g m

contexts

variables type variables context variables locations class names field names method names

Fig. 1. Syntax of Tame FJOwn

Syntax. The syntax of Tame FJOwn is given in Fig. 1. For convenience, and following OGJ [27], we syntactically separate types and type parameters used to represent contexts from regular types: we use τ to denote types which represent

Encoding Ownership Types in Java

283

contexts, T to denote regular types, and T to denote either type; likewise for parameters, we use O to denote type parameters which represent context parameters, X for regular type parameters, and X for either kind. Importantly, the two kinds of type are treated almost identically by the type system. We can do without this convenience by examining the type’s top supertype: contexts will be bounded by World, other types by Object. We allow values (v, which are addresses and null; the latter corresponds to World) to be context (and thus type) parameters at runtime so that we can prove enforcement of the ownership hierarchy (see Sect. 4.1); values are not allowed as parameters in source code. We use a few shorthands for types: C for C<>, and R for ∃∅.R.

Well-formed types: Δ  B ok, Δ  P ok, Δ  R ok X ∈Δ Δ  X ok (F-Var)

Δ  World<> ok

Δ ⊥ ok

Δ   ok

Δ  Δ ok Δ, Δ  N ok Δ  ∃Δ .N ok

( F-World )

(F-Bottom)

(F-Star)

(F-Exists)

Δ  T , τ , τo ok T = T , τ , τo , τt Δ(τt ) = [⊥ T ] class C<X
T u >
N {...} Δ  T <: [T /X ]T u Δ  C ok (F-Class)

Δ  τo ok Δ(τt ) = [⊥ T ] Δ  Object< τ o ,τ t > ok (F-Object)

Fig. 2. Tame FJOwn well-formed types, type environments, and heaps

Well-formed Types. Well-formed types are defined in Fig. 2. In F-Class and F-Object, we do not check that the type parameter in the This position is wellformed. Instead we check that it is in the environment and is bounded below by bottom. This ensures that it is always an in-scope variable (in fact it is usually a quantified variable, although this does not need to be enforced) and that no other type can be derived to be a subtype of it (as would be the case if it had a lower bound). This ensures that the This context cannot be named by using subsumption. Type Checking. Selected type rules are given in Fig. 3. Object creation (T-New) does not take any (value) parameters (i.e., we don’t have constructors, at runtime all fields are initialised to null). This requires null and the T-Null rule. Initialising objects in this way is necessary so that fields owned by This can be initialised. The actual type parameter in the This position of new

284

N. Cameron and J. Noble

Expression typing: Δ; Γ  e : T Δ  T ok Δ; Γ  null : T

Δ; Γ  e : ∃Δ .N f T ype(f, N ) = T   Δ; Γ  e : T Δ, Δ  T <: T  Δ; Γ  e.f = e : T

( T-Null )

(T-Assign)

Δ  T , T ok Δ  ∃O → [⊥ T ].C ok Δ; Γ  new C : ∃O → [⊥ T ].C ( T-New ) Class typing:  Q ok Δ = X→[⊥ T u ], Owner→[⊥ τ o ],This→[⊥ Owner],O→[⊥ τ u ] ∅  Δ ok Δ  N , T ok X = X, O, Owner, This N = D

Δ; this:C<X >  M ok in C Δ  N <: Object

 class C<X
T u , O
τ u ,Owner
τ o ,This
Owner >
N {T f; M } ok (T-Class) Fig. 3. Selected Tame FJOwn expression and class typing rules

expressions must always be , so no actual parameter is named at initialisation. New objects are given existential types, with the This parameter existentially quantified (bounded above by the Owner parameter), which ensures that the actual This parameter can never be named directly. The extra well-formedness premise in T-New is stricter than the usual well-formedness premise and ensures that the type parameters are well-formed without the extra, quantified parameter in the environment. We add a rule for casting (T-Cast), which is standard. Unlike in Featherweight Java, we do not distinguish between up-, down-, and stupid casts. In T-Class we enforce that the declared upper bound of This is Owner4 . The last two premises ensure that declared classes fall under the Object hierarchy and are not subtypes of World, which means they cannot be used as context parameters, and that the Owner and This parameters are invariant with respect to inheritance. The latter is an important sanity condition of our encoding of ownership and corresponds to the well-known condition on inheritance and ownership [15]. We assume that Object is declared with parameters Owner and This with the usual bounds. 4

The re-ordering of type parameters is a hangover from supporting owners-asdominators, where the lower bound of each O is Owner.

Encoding Ownership Types in Java

285

Operational Semantics. Operational semantics are mostly defined in the appendix; the most interesting change from Tame FJ is in object creation: ι ∈ dom(H) f ields(C) = f H = H, ι → {C; f→null} new C; H ; ι; H ( R-New ) A new object’s runtime type (stored in the heap) is formed by replacing the  used in the program source by the new object’s address. Together with the usual rules of substitution (in method invocation), occurrences of both this and This in class declarations are replaced by the instantiation’s address (ι), unifying the two representations of the object. Together with the quantification in T-New, objects are, in effect, packed into existential types, with the object’s address as witness ‘type’. 4.1

Discussion

Ownership types are intrinsically dependent because they reflect objects’ positions in the heap. We have shown that ownership types can be encoded as parametric types in a Java-like type system, reminiscent of phantom types [21]. Phantom types are parametric types where type parameters are never used as types5 . Phantom types are used in Haskell to simulate values in types, without the complexity and decidability issues of full dependent types [21]. This is exactly what our system is doing with respect to ownership information. We conclude then, that ownership type systems are, in some sense, no more complex than standard parametric type systems such as Java’s. Despite their dependent character, the full power of dependent types is not required to support ownership type systems. However, we should not overstep the mark and assume that type parametricity is the only, or even the best, foundational model for ownership types. Most of the ownership features described in Sect. 3 can be accommodated in Tame FJOwn . Inner classes require encoding and are discussed below. Paths of final fields cannot easily by encoded in our formal system. Generic Universe Types [19] can be accommodated after encoding. Ownership domains would require a small extension to the formal system, which we have avoided for the sake of simplicity: each class has a list of This type parameters rather than a single parameter. Each parameter represents a domain. Since this change merely changes This to This, we expect very few changes to be necessary to accommodate it. The extensions to support ownership domains and inner classes (below) are fairly superficial changes, modifying only the restrictions on type parameters and which type parameters are hidden in T-New. 5

More precisely, phantom type parameters are not used on the right hand side of the definition of a type constructor.

286

N. Cameron and J. Noble

Inner Classes. Encoding inner classes in Tame FJOwn would require a small extension to our formalisation. References to the surrounding object and the type parameters of the surrounding object must be made available to objects of the inner class. Extending Tame FJOwn could be done by adopting a nesting of classes and objects in the class table and heap or by adding a field to each class pointing to the surrounding object, and type parameters for the surrounding classes’ type parameters; object creation becomes more complex, but otherwise the calculus is not changed too much. The iterator as inner class example from Sect. 3.1 is encoded as (we elide bounds): class Iterator { List out; Node curNode; Object privField; Object next() {...} } class Client { void m(List<World, This, LT> l) { Iterator<World, This, LT, This, ?> i = new Iterator<World, This, LT, This, ?>(); i.out = l; Object<World, ?> first = i.next(); } } Java

We must use (a presumably capture converted) type variable (LT) for the This parameter of l, provide l’s type parameters to i, and must instantiate the out field of i. Type Soundness. We have proved type soundness for Tame FJOwn in the usual way [29] by proving progress and preservation theorems. For the most part, our proofs follow those of Tame FJ [11]; they can be downloaded from [1]. In standard existential type systems, witness types are known at runtime, and type soundness guarantees that no type errors involving witness types occur, even though the type system has only partial knowledge of these types during type checking. Taking this approach with Tame FJOwn would not be very informative, since all witness types (according to T-New) will be . Our static types hold more information (the ownership hierarchy) than is represented by the ‘witness types’. Our soundness result proves that Tame FJOwn does enforce the ownership hierarchy, i.e., Tame FJOwn enforces not only strict type soundness (well-typed programs won’t access non-existent fields or methods), but also that objects reside in the context described by their type. Ownership information is represented at runtime by storing the object’s address into it’s This position (in

Encoding Ownership Types in Java

287

R-New), the address propagates into other ownership positions by substitution (in R-Invk). In proving type soundness for Tame FJOwn , we have proved that a one-stage type checker (corresponding to an integration of our pre-processor and the Java type checker) is sound, rather than proving that a two-stage type checker (corresponding to pre-processing and then Java type checking, as in our implementation) is sound. Our approach is theoretically more direct and reflects what we envision to be the long term use of our techniques.

5

Implementation

We have implemented compilers for Java with ownership types and Generic Universe Types by using the techniques described in this paper. Our implementations are simple source to source translators which translate source code to plain Java; the Java compiler is then used to type check and compile the code. Most type errors are caught by the Java compiler, only a few are handled by our translators. Our translators are extensions to the parser and AST elements of the JKit Java compiler [25]. We encode one class at a time and do not need to be aware of the whole program. Generated classes will behave well together, but will be incompatible with plain Java classes6 . Our approach supports ownership and universe types on top of nearly the entire Java Language, including generics, arrays (including the various kinds of array initialisers; we only support ownership information on the elements in an array, the array itself (like primitive types) is not considered to have an owner), interfaces, inner classes (but not anonymous classes), statics, and wildcards. Our implementations are very much prototypes, an industrial strength compiler would integrate the encoding with Java type checking, as opposed to our two-stage process. Integration would allow for meaningful error messages and support for effects and encapsulation properties. Furthermore, to be usable, a language requires more than a compiler, libraries must be supported, either by support for non-ownership aware classes (currently, all classes must be written with ownership types) or by producing a set of ownership annotated libraries (or a combination of the two approaches). Our compilers can be downloaded [1]. 5.1

Ownership Types

Our source syntax is mostly similar to that used throughout this paper. We support owners, context parameters, orthogonal generics, context- and typeparametric methods, final method parameters as contexts (for dynamic aliases), existential quantification in the form of context wildcards, and inner classes with access to the contexts and context parameters of the surrounding object. We do not support local variables (other than method parameters) or fields as contexts. We support standard casting, including to wildcard owners, but do not directly 6

Strictly, since we generate plain Java, one could write classes which behave well with the generated classes, but not in a way which behaves nicely with the source classes.

288

N. Cameron and J. Noble

support “existential owners”. Since Java implements generics using erasure [22], the runtime checks on casts do not ensure correctness of ownership parameters; with respect to ownership types, casting merely ensures that a program can type check at compile time. This is not a problem in our formalism, because we do not erase type parameters in the operational semantics. The obvious function of our compiler is to strip owners and context parameters and replace them with type parameters, this is done both in class declarations and in types; in the latter case, using wildcards in the This position. Java does not allow wildcard parameters when objects are instantiated: to get around this we use the Owner type parameter in the This position (because it is the only type parameter which satisfies the declared bound) and immediately cast to the required wildcard type (which inherits the upper bound), new world:Object() //source syntax new Object<World, ?>() //pseudo-Java (OwnedObject<World, ?>) new OwnedObject<World, World>() //Java Note also that, as in OGJ, we have to add an OwnedObject which extends Object at the root of our class hierarchy to take the encoded ownership parameters. All classes must extend this class (rather than Object, which may happen implicitly) and all uses of Object changed to OwnedObject. In the source syntax, the object’s owner is implicit in the extends clause, and so translation of the superclass type must be treated differently from other types. Because we add OwnedObject and World to our runtime, we must import these classes into each encoded class file. 5.2

Generic Universe Types

The source syntax is pretty standard for generic universes, e.g., rep List. The translation is much simpler than for ownership types since we do not have to translate context parameters, only types. Most of the issues faced are similar, and simpler, than in the ownership types case: we must check for universe modifiers on all types (but not in extends clauses, because ownership is invariant with respect to inheritance, that is superclasses must be peers), Object is translated to OwnedObject, and care must be taken with array types. As with our ownership types implementation and Java, casting is unsafe and allows for Universe modifiers to be changed improperly; Universes usually requires safe down-casting.

6

Conclusion and Future Work

In this paper we have shown how ownership types, Generic Universe Types, Ownership Domains, and a range of extensions to ownership types systems can be encoded using Java Generics and wildcards. The key concepts are the representation of context parameters as type parameters, the reification of this as a

Encoding Ownership Types in Java

289

type parameter, the hiding of this using wildcards, and the phantom ownership hierarchy thus created. Our developments shed light on the type-theoretic foundations of ownership types and offer a route for practical compilers constructed upon existing technology. Future Work. The main thrust of future work will be in supporting ownersas-dominators, and other encapsulation polices and effects, in our formal work and compilers. This would require integrating our translating compiler with an existing Java compiler, which would also allow for better error messages and more efficient type checking. We would also like to encode libraries with ownership type information for use with our compilers. An alternative would be to develop our encoding so that encoded classes and the un-annotated Java libraries can interact together.

References 1. Accompanying webpage, https://ecs.victoria.ac.nz/Main/Encoding 2. Abi-Antoun, M., Aldrich, J.: Ownership Domains in the Real World. In: International Workshop on Aliasing, Confinement and Ownership in object-oriented programming, IWACO (2008) 3. Aldrich, J., Chambers, C.: Ownership Domains: Separating Aliasing Policy from Mechanism. In: Odersky, M. (ed.) ECOOP 2004. LNCS, vol. 3086, pp. 1–25. Springer, Heidelberg (2004) 4. Armbruster, A., Baker, J., Cunei, A., Flack, C., Holmes, D., Pizlo, F., Pla, E., Prochazka, M., Vitek, J.: A Real-Time Java Virtual Machine with Applications in Avionics. Transactions on Embedded Computing Systems 7(1), 1–49 (2007) 5. Bocchino Jr., R.L., Adve, V.S., Dig, D., Adve, S.V., Heumann, S., Komuravelli, R., Overbey, J., Simmons, P., Sung, H., Vakilian, M.: A Type and Effect System for Deterministic Parallel Java. In: Object-Oriented Programming, Systems, Languages, and Applications, OOPSLA (2009) 6. Boyapati, C., Lee, R., Rinard, M.C.: Ownership Types for Safe Programming: Preventing Data Races and Deadlocks. In: Object-Oriented Programming, Systems, Languages, and Applications, OOPSLA (2002) 7. Boyapati, C., Liskov, B., Shrira, L.: Ownership Types for Object Encapsulation. In: Principles of Programming Languages, POPL (2003) 8. Cameron, N.: Existential Types for Variance | Java Wildcards and Ownership Types. PhD thesis, Imperial College London (2009) 9. Cameron, N., Dietl, W.: Comparing Universes and Existential Own- ership Types. In: International Workshop on Aliasing, Confinement and Ownership in objectoriented programming, IWACO (2009) 10. Cameron, N., Drossopoulou, S.: Existential Quantification for Variant Ownership. In: Castagna, G. (ed.) ESOP 2009. LNCS, vol. 5502, pp. 128–142. Springer, Heidelberg (2009) 11. Cameron, N., Drossopoulou, S., Ernst, E.: A Model for Java with Wildcards. In: Vitek, J. (ed.) ECOOP 2008. LNCS, vol. 5142, pp. 2–26. Springer, Heidelberg (2008) 12. Cameron, N., Drossopoulou, S., Noble, J., Smith, M.: Multiple Ownership. In: Object-Oriented Programming, Systems, Languages, and Applications, OOPSLA (2007)

290

N. Cameron and J. Noble

13. Cameron, N., Noble, J.: OGJ Gone Wild. In: International Workshop on Aliasing, Confinement and Ownership in object-oriented programming, IWACO (2009) 14. Clarke, D.G.: Object Ownership and Containment. PhD thesis, School of Computer Science and Engineering, The University of New South Wales, Sydney, Australia (2001) 15. Clarke, D.G., Drossopoulou, S.: Ownership, Encapsulation and the Disjointness of Type and Effect. In: Object-Oriented Programming, Systems, Languages, and Applications, OOPSLA (2002) 16. Clarke, D.G., Potter, J.M., Noble, J.: Ownership Types for Flexible Alias Protection. In: Object-Oriented Programming, Systems, Languages, and Applications, OOPSLA (1998) 17. Cunningham, D., Dietl, W., Drossopoulou, S., Francalanza, A., M¨ uller, P., Summers, A.J.: Universe Types for Topology and Encapsulation. In: Formal Methods for Components and Objects, FMCO (2008) 18. Cunningham, D., Drossopoulou, S., Eisenbach, S.: Universe Types for Race Safety. In: Verification and Analysis of Multi-threaded Java-like Programs, VAMP (2007) 19. Dietl, W., Drossopoulou, S., M¨ uller, P.: Generic Universe Types. In: Ernst, E. (ed.) ECOOP 2007. LNCS, vol. 4609, pp. 28–53. Springer, Heidelberg (2007) 20. Gosling, J., Joy, B., Steele, G., Bracha, G.: The Java Language Specification, 3rd edn. Addison-Wesley, Boston (2005) 21. Hinze, R.: The Fun. of Programming, pp. 245–262. Palgrave Macmillan, Basingstoke (2003) 22. Igarashi, A., Pierce, B.C., Wadler, P.: Featherweight Java: a Minimal Core Calculus For Java and GJ. ACM Trans. Program. Lang. Syst. 23(3), 396–450 (2001); An earlier version of this work appeared at OOPSLA’99 23. Lu, Y., Potter, J.: On Ownership and Accessibility. In: Thomas, D. (ed.) ECOOP 2006. LNCS, vol. 4067, pp. 99–123. Springer, Heidelberg (2006) 24. M¨ uller, P., Poetzsch-Heffter, A., Leavens, G.T.: Modular Invariants for Layered Object Structures. Science of Computer Programming 62, 253–286 (2006) 25. Pearce, D.: Jkit compiler, http://www.ecs.vuw.ac.nz/~ djp/jkit 26. Potanin, A., Noble, J., Clarke, D., Biddle, R.: Featherweight Generic Confinement. J. Funct. Program. 16(6), 793–811 (2006) 27. Potanin, A., Noble, J., Clarke, D., Biddle, R.: Generic Ownership for Generic Java. In: Object-Oriented Programming, Systems, Languages, and Applications, OOPSLA (2006) 28. Torgersen, M., Hansen, C.P., Ernst, E., von der Ah´e, P., Bracha, G., Gafter, N.: Adding Wildcards to the Java Programming Language. Journal of Object Technology 3(11), 97–116 (2004) 29. Wright, A.K., Felleisen, M.: A Syntactic Approach to Type Soundness. Information and Computation 115(1), 38–94 (1994) 30. Wrigstad, T.: Ownership-Based Alias Managemant. PhD thesis, KTH, Sweden (2006) 31. Wrigstad, T., Clarke, D.G.: Existential Owners for Ownership Types. Journal of Object Technology 6(4) (2007)

Visualizing Dynamic Metrics with Profiling Blueprints Alexandre Bergel1 , Romain Robbes1 , and Walter Binder2 1

Pleiad Lab, DCC, University of Chile, Santiago, Chile http://bergel.eu, http://www.dcc.uchile.cl/∼rrobbes 2 University of Lugano, Switzerland http://www.inf.usi.ch/faculty/binder

Abstract. While traditional approaches to code profiling help locate performance bottlenecks, they offer only limited support for removing these bottlenecks. The main reason is the lack of visual and detailed runtime information to identify and eliminate computation redundancy. We provide two profiling blueprints which help identify and remove performance bottlenecks. The structural distribution blueprint graphically represents the CPU consumption share for each method and class of an application. The behavioral distribution blueprint depicts the distribution of CPU consumption along method invocations, and hints at method candidates for caching optimizations. These two blueprints helped us to significantly optimize Mondrian, an open source visualization engine. Our implementation is freely available for the Pharo development environment and has been evaluated in a number of different scenarios.

1

Introduction

Even though computing resources are abundant, execution optimization through code profiling remains an important software development activity. A CPU time profiler is a crucial tool to identify bottlenecks – program elements that take a large part of the execution time. Today, it is inconceivable to ship a programming environment without a code profiler included or provided by a third party. However, when we retrospectively look at the history of code profiler tools, we see that tool usability and profiling overhead reduction have steadily improved, but that the set of offered abstractions has remained constant. For instance, gprof, which appeared in 1982, offers a number of textual reports focussed on “how much time was spent executing directly in each function” and call graphs1 . JProfiler essentially produces the same output, using a graphical rendering instead of a textual one2 . Most of the research conducted in the field of code profiling focus on reducing the overhead triggered by the code instrumentation and observation. The abstractions used to profile object-oriented applications are very close to the ones for procedural applications. 1 2

http://sourceware.org/binutils/docs/gprof/Output.html#Output http://www.ej-technologies.com/products/jprofiler/screenshots.html

J. Vitek (Ed.): TOOLS 2010, LNCS 6141, pp. 291–309, 2010. c Springer-Verlag Berlin Heidelberg 2010 

292

A. Bergel, R. Robbes, and W. Binder

The contribution of this paper is to apply some visualizations that have been previously used in static software analysis to display dynamic metric for profiling purposes. We propose a visual mechanism for rendering dynamic information that effectively enables comparison of different metrics related to a program execution. Structural distribution blueprint and behavioral distribution blueprint are two visualizations intended to identify bottlenecks and propose hints on how to remove them. The first blueprint represents the distribution of the CPU effort along the program structure. The second blueprint directs the distribution along method invocations and identifies methods prone to one class of optimization, namely caching. The work presented in this paper aims at complementing existing profilers with new visualizations that help specific optimization tasks. We obtained the results presented in this paper using Pharo3 , an open-source Smalltalk-dialect programming language. Nothing in the visualizations we propose prevents one from using them in a different setting. We apply our techniques to the visualization framework Mondrian4 [MGL06], our running example. We first describe our blueprints (Section 2). Subsequently, we identify and implement opportunities for optimization in Mondrian (Section 3). We then review related work (Section 4) and conclude (Section 5).

2

Profiling Blueprints

2.1

Profiling Blueprint in a Nutshell

Time profiling blueprints are graphical representations meant to help programmers (i) assess the time distribution and (ii) identify bottlenecks and give hints on how to remove them for a given program execution. The essence of profiling blueprints is to enable a better comparison of elements constituting the program structure and behavior. To render information, these blueprints use a graph metaphor, composed of nodes and edges. The size of a node hints at its importance in the execution. In the case that nodes represent methods, a large node may say that the program execution spends “a lot of time” in this method. The expression “a lot of time” is then quantified by visually comparing the height and/or the width of the node against other nodes. Color is used to either transmit a boolean property (e.g., a gray node represents a method that always returns the same value) or a metric (e.g., a color gradient is mapped to the number of times a method has been invoked). We propose two blueprints that help identify opportunities for code optimization. They provide hints to programmers to refactor their program along the following two principles: (i) make often-used methods faster and (ii) call slow methods less often. The metrics we adopted in this paper help finding methods that are either unlikely to perform a side effect or return always the same result, good candidates for simple caching optimizations. 3 4

http://www.pharo-project.org/home http://www.moosetechnology.org/tools/mondrian

Visualizing Dynamic Metrics with Profiling Blueprints

293

width property

color property

height property

X property

Y property

edge width and color properties

Fig. 1. Principle of polymetric view

2.2

Polymetric Views

The blueprints we propose are graphically rendered as polymetric views [LD03]. A polymetric view is a lightweight software visualization enriched with software metrics. It has been successfully used to provide “software maps” intended to help software comprehension and visualization. Figure 1 depicts the general aspect of a polymetric view. Given two-dimensional nodes representing entities, we can map up to 5 metrics on the node characteristics: position (X and Y ), size (width and height), and color: – Position. The X and Y coordinates of the position of a node may reflect two measurements. – Size. The width and height of a node can render two measurements. We follow the intuitive notion that the wider and the higher the node, the larger the associated metric. – Color. The color interval between white and black may render one measurement. The convention that is usually adopted [GL04] is that the higher the measurement, the darker the node. Thus light gray represents a smaller measurement than dark gray. Edges may also render properties along a number of dimensions (width, color, direction, etc.). However, for the purpose of this work, all edges are identical. 2.3

Structural Distribution Blueprint

The execution of an object-oriented program yields a large amount of information [DLB04] (e.g., number of objects created at runtime, total execution time of a method). Unfortunately, all these dimensions cannot be visually rendered in a meaningful fashion. The structural distribution blueprint displays a selected number of metrics indicating the distribution of the execution time along the static structure of a program (i.e., classes, methods and class hierarchy). Table 1 gives the specification of the structural distribution blueprint. The blueprint renders a program in terms of classes, methods and inheritance relations. Each method representation exhibits its corresponding CPU time profiling information along three metrics:

294

A. Bergel, R. Robbes, and W. Binder

– number of different receivers: amount of different object receivers the method has been invoked on. Due to implementation limitations, this is at the moment a lower bound estimate. – total execution time of a method : time for which a call frame corresponding to the method is present on the stack at runtime. The precision depends on the underlining profiler used to collect runtime information. – number of executions: number of times the method has been executed, independently of the object receiver. Actual metric values, and additional information, are accessible through a contextual popup window. Table 1. Specification of the structural distribution blueprint Structural distribution blueprint Scope full system execution time Edge class inheritance (upper is superclass of below) Layout tree layout for outer nodes and gridlayout for inner nodes (inner nodes are ordered by increasing height) Metric scale linear (except for node width) Node outer node is a class, an inner node is a method Inner node color Number of different receivers Inner node height total execution time of a method Inner node width number of executions (logarithmic scale) Example Figure 2

Example. Troughout this paper, we use the graph visualization framework Mondrian as a case study. The blueprints described in this paper are also rendered using Mondrian. An example of the structural distribution blueprint is given in Figure 2. Four classes are represented: MOGraphElement, MOViewRenderer, MONode and MORoot. This figure is a small part of a bigger picture obtained by evaluating the following code snippet, which renders a simple visualization of 100 nodes, each containing 100 nodes: ProfilingPackageSpy viewProfiling: [ | view | view := MOViewRenderer new. view nodes: (1 to: 100) forEach: [:each | view nodes: (1 to: 100)]. view root applyLayout ] inPackage: ’Mondrian’

The code being profiled is indicated using a bold font in the example source code. The profiling is realized from the perspective of one package, Mondrian in our case. MOGraphElement inherits from MONode, MORoot from MOGraphElement, and MOViewRenderer from Object. Since Object does not belong to Mondrian (but to the Kernel package), it is not rendered in the blueprint.

Visualizing Dynamic Metrics with Profiling Blueprints

shapeBoundsAt: ifPresent:

295

bounds

translateTo:

legend for methods # executions

execution time

(color) #different receiver

Fig. 2. Example of a structural blueprint

The height of a method node is proportional to the total execution time taken by the method (e.g., 53% of the code execution is spent in the method applyLayout and 38% in bounds). The width is proportional to the number of times the method has been executed. A logarithmic scale is used. The method node color represents the number of different objects this method has been executed on (more than 3 732). The scope of the blueprint is global, which means that the darkest method corresponds to the method that has been executed on the greatest number of object receivers, system-wide. Moving the mouse over a method node pops up additional contextual information. In the example, the contextual window says that the method applyLayout defined in the class MOGraphElement has been executed 10 100 times, and has been executed on more than 3 732 distinct receiver objects (i.e., instances of MOGraphElement or one of its subclasses). It is also indicated that this method returns always the same value for a given object receiver. While the blueprint emphasizes the three metrics indicated above, the contextual information provides useful data when one wants to know more about a particular method. Within a class, methods are ordered along their height. This helps quickly spot the amount of costly methods. For example, it is clear that among MOGraphElement’s methods, 3 are dominating with respect to execution time.

296

A. Bergel, R. Robbes, and W. Binder

Interpretation. Classes represented in Figure 2 illustrate part of a scenario that totals 11 classes. Among the 111 classes that define Mondrian, these 11 classes are the only classes involved in the code snippet execution given above. Only classes that are covered by the execution, even partially, are depicted in the blueprint. MOGraphElement contains “many large and dark” methods. This indicates that this class is central to the code snippet execution: these large and black methods consume a lot of CPU time and are invoked on many different instances. Almost all of MOGraphElement’s methods are executed a large number of times: in the visualization, they are quite wide compared to methods in other classes. For most of them, this is not a problem because they are thin and horizontal: even if these methods are executed many times, they do not consume CPU time. On the left of applyLayout stands the bounds method. This method takes 38% of the CPU time and is invoked 70 201 times on more than 3 732 object receivers. The third costliest method on MOGraphElement, shapeBoundsAt:ifPresent: takes 33% of the CPU time. MONode contains a black and relatively large method: MONode>> translateTo: consumes 22% of the total CPU time. The method has been invoked 10 100 times on at least 3 732 receivers. Comparing to MOGraphElement, we find that classes are not involved in the computation as much. The representation of MOViewRenderer quickly says that its methods are invoked a few times without consuming much CPU. Moreover, methods are white, which tells that they are invoked on few instances only. The contextual information obtained by moving the mouse over the methods reveals that these methods are executed on a unique receiver. This is not surprising since only one instance of MOViewRenderer is created in the code example given above. MORoot also does not seem to be the cause of a bottleneck at runtime. The few methods of this class are not frequently executed since they are relatively narrow. MORoot also defines a method applyLayout. This method is the tall, thin and white method. The contextual information reveals that this method is executed once and on one object only. It consumes 97% of the CPU time. The method MORoot>> applyLayout invokes MOGraphElement>> applyLayout on each of the nodes. The relation between these two applyLayout methods is indicated by a fly-by-highlighting (not represented in the picture) and the behavioral distribution blueprint, described below. All in all, a large piece of the total CPU time is distributed over four methods: MONode>> translateTo: (24%), MOGraphElement>> bounds (32%), MOGraphElement>> shapeBoundsAt:ifPresent: (33%), MOGraphElement>> applyLayout (53%). Note that at this stage, we cannot say that the CPU time share of these three methods is the sum of their individual share. We have 24 + 32 + 33 + 53 = 142. This indicates that some of these methods call each other since their sum cannot exceed 100%. 2.4

Behavioral Distribution Blueprint

In a pure object-oriented setting, computation is solely performed through message sending between objects. The CPU time consumption is distributed along method executions. Assessing the runtime distribution along method

Visualizing Dynamic Metrics with Profiling Blueprints

297

invocations complements the structural distribution described in the previous section. To reflect this profiling along method invocations, we provide the behavioral distribution blueprint. Table 2 gives the specification of the figure. The goal of this blueprint is to assess runtime information alongside method call invocations. It is intended to find optimization opportunities, which may be tackled with caching. In addition to the metrics such as the number of calls and execution time, we also show whether a given method returns constant values, and whether it is likely to perform a side effect or not. As shown later, this information is helpful to identify a class of bottlenecks. Classes do not appear on this blueprint. Methods are represented by nodes and invocations by directed edges. The blueprint uses the two metrics described in the previous blueprint for the width and height of a method. In addition to the shape, node color indicates a property: – the gray color indicates methods that return self , the default return value. When no return value is specified in Pharo, the object receiver is returned. This corresponds to void methods in a statically typed language. No result is expected from the method, strongly suggesting that the method operates via side effects. – the yellow color (which appears as light gray on a black and white printout) indicates methods that are constant on their return value, this value being different from self . – other methods are white. A tree layout is used to order methods, with upper methods calling lower methods. We illustrates this blueprint on the MOGraphElement>> bounds method that we previously saw, a candidate for optimization. Table 2. Specification of the behavioral distribution blueprint Behavioral distribution blueprint all methods directly or indirectly invoked for a given starting method Edge method invocation (upper methods invoke lower ones) Layout tree layout Metric scale linear (except for node width) Nodes methods Node color gray: return always self; yellow: same return value per object receiver; white: remaining methods Node height total execution time Node width number of execution (logarithmic scale) Example Figure 3 Scope

Example. In the previous blueprint (Figure 2), right-clicking on the method MORoot>> applyLayout opens a behavioral distribution blueprint for this method. The complete picture is given in Figure 3. The picture has to be read topdown. Methods in this blueprint have the same dimensions as in the behavioral

298

A. Bergel, R. Robbes, and W. Binder

MORoot>>applyLayout

MOGraphElement>> applyLayout

MOAbstractLayout>>applyOn:

MONode>> translateTo:

legend for methods # executions

execution time

gray = return self yellow = constant on return value

m1

m3

m2

m1 invokes m2 and m3

bounds shapeBoundsAt: ifPresent:

Fig. 3. Example of a behavioral blueprint

blueprint. We recognize the tall and thin MORoot>> applyLayout at the top. All methods in Figure 3 are therefore invoked directly or indirectly by MORoot >> applyLayout. MORoot>> applyLayout invokes 3 methods, including MOGraphElement>> applyLayout (labelled in the figure). MOGraphElement>> applyLayout calls MOAbstractLayout>> applyOn:, and both of these are called by MORoot>> applyLayout. Interpretation. As the first blueprint revealed, bounds, applyLayout, shapeBoundsAt:ifPresent:, translateTo: are expensive in terms of CPU time consumption. The behavior blueprint highlights this fact from a different point of view, along method invocations. In the following we will optimize bounds by identifying the reason of its high cost and provide a solution to fix it. Our experience with Mondrian tells us that this method has a surprisingly high cost. Where to start a refactoring among all potential candidates remains the programmer’s task. Our blueprint only says “how it is” and not “how it should be”, however it is a rich source of indication of what’s going on at runtime.

Visualizing Dynamic Metrics with Profiling Blueprints

299

The return value of MOGraphElement>> bounds is constant over time, hence it is painted in yellow. This method is involved in a rich invocation graph (presented in Figure 3). In general, understanding the interaction of a single method is likely to be difficult when a complete call graph is used. The contextual menu obtained by right-clicking on a method offers a filtered view on the entity of interest. computeExtentHavingChildrenFor:

MOGraphElement>> origin Calling #bounds

bounds

Called by #bounds

shapeBoundsAt:ifPresent:

Fig. 4. Detailed view of MOGraphElement>> bounds

Figure 4 shows a detailed view of a behavioral blueprint, centered on MOGraphElement>> bounds. This method is at the center of the picture. Above are located the methods calling bounds. Below, the unique method that is called by bounds. Among the 5 methods that call bounds, 3 always return the same value when executed. The method called by bounds also remains constant on its return value. Figure 4 renders bounds and shapeBoundsAt:ifPresent: with the same width. It is therefore likely that these two methods are invoked the same number of times. The contextual window indicates that each of these two methods is invoked 70 201 times. We can deduce the following: – bounds belongs to several execution paths in which each method is constant on its return value. This is indicated in the upper part of Figure 4. – bounds calls shapeBoundsAt:ifPresent:, which is constant on return value. – bounds and shapeBoundsAt:ifPresent: are invoked the same number of times. The following section addresses this bottleneck by adding a cache in bounds and unveils another bottleneck in Mondrian.

3

Optimizing Mondrian

The combination of the structural and behavioral blueprints helped us to identify a number of bottlenecks in Mondrian. In this section, we address some of these

300

A. Bergel, R. Robbes, and W. Binder

bottlenecks by using memoization5 , i.e. we cache values to avoid redundant computations. 3.1

Bottleneck MOGraphElement>> Bounds

As we saw earlier, the behavioral blueprint on the method MOGraphElement>> bounds reveals a number of facts about the program’s execution. These facts are good hints that bounds will benefit from a caching mechanism since it always returns the same value and calls a method that is also constant. We inspect its source code: MOGraphElement>> bounds ”Answer the bounds of the receiver.” | basicBounds | self shapeBoundsAt: self shape ifPresent: [ :b | ˆ b ]. basicBounds := shape computeBoundsFor: self. self shapeBoundsAt: self shape put: basicBounds. ˆ basicBounds

The code source confirms that shapeBoundsAt:ifPresent: is invoked once each time bounds is invoked. The method shape is also invoked at each invocation of bounds. The contextual window obtained in the structural blueprint reveals that the return value of shape is constant: It is a simple variable accessor (“getter” method), so it is fast. bounds calls computeBoundsFor: and shapeBoundsAt:put: in addition to shapeBoundsAt:ifPresent: and shape. However, they do not appear in Figure 3 and 4. This means that bounds exits before reaching computeBoundsFor:. The block [:b | ˆb], which has the effect of exiting the method, is therefore always executed in the considered example. We first thought that the last tree lines of bounds may be removed since they are not executed in our scenario. However, the large number of tests in Mondrian indicate that these lines are indeed important in other scenarios, although not in our particular example. We elected to upgrade bounds with a simple cache mechanism. Differences with the original version are indicated using a bold font. The class MOGraphElement is extended with a new instance variable, boundsCache. In addition, the cache variable has to be reset in 5 methods related to graphical bounds manipulation of nodes, such as translating and resizing. MOGraphElement>> bounds ”Answer the bounds of the receiver.” | basicBounds | boundsCache ifNotNil: [ ˆ boundsCache ]. self shapeBoundsAt: self shape ifPresent: [ :b | ˆ boundsCache := b ]. basicBounds := shape computeBoundsFor: self. self shapeBoundsAt: self shape put: basicBounds. ˆ boundsCache := basicBounds 5

http://en.wikipedia.org/wiki/Memoization

Visualizing Dynamic Metrics with Profiling Blueprints

301

There is no risk of concurrent accesses of boundsCache since this variable is set when the layout is being computed. This occurs before the display of the visualization, which is done in a different thread. Result. Adding a statement boundsCache ifNotNil: [ ˆ boundsCache ] significantly reduces the execution time of the code given in Section 2.3. Before adding this simple cache mechanism, the code took 430 ms to execute (on a MacBook Pro, 2Gb of RAM (1067 MHz DDR3), 2.26 GHz Intel Core 2 Duo, Squeak VM 4.2.1beta1U). With the cache, the same execution takes 242 ms only, which represents a speedup of approximately 43%. This gain is reflected on the overall distribution of the computational effort. Figure 5 provides two structural blueprints of the code snippet given in Section 2.3. The left blueprint has been produced before upgrading the method MOGraphElement>> bounds. Figure 2 is a part of it. The right one has been produced after upgrading bounds as described above. Many places are impacted. We annotated the figure with the most significant changes: – the size of the bounds method and the methods invoked by it (C) have seen their height significantly reduced. Before the optimization, bounds used 38% of the total CPU consumption. After the optimization, its CPU use fell to 5%. – the 5 methods denoted by the circle A and B have seen their height increased and their color darkened. The height increase illustrates the augmentation in relative CPU consumption these methods are subject to, now that bounds has been improved. The evolution of the behavioral blueprint is presented in Figure 6. We can clearly see the reduced size of bounds and shapeBoundsAt:ifPresent: (Circle B) and the increase of the applyLayout method (Circle A). 3.2

Bottleneck in MONode>> displayOn:

We fixed an important bottleneck when computing bounds in Mondrian. We push our analysis of bounds computing a step further. We inspect the User Interface (UI) thread of Mondrian. Most applications with a graphical user interface run in at least 2 threads: one for the program logic and another in charge of receiving user events (e.g., keystrokes, mouse events) and virtual machine/OS events (e.g., window refreshes). Mondrian is no exception. The blueprints presented earlier focused on profiling the application logic. Step 1. Figure 7 shows the structural profiling of the UI thread for the Mondrian script given in Section 2.3. The blueprint contains many large methods, indicating methods that received a significant CPU share. Among these, our knowledge of Mondrian lead us to absoluteBounds. This method is very similar to bounds that we previously saw. It returns the bounds of a node using absolute coordinates (instead of relative). The UI thread spends most of the time in MONode>> displayOn: since it is the root of the thread’s computation.

302

A. Bergel, R. Robbes, and W. Binder

Upgrading MOGraphElement>>bounds A B C

Fig. 5. Upgrading bounds has a global structural impact

A

Upgrading MOGraphElement>>bounds

B

Fig. 6. Upgrading bounds has a global behavioral impact

Visualizing Dynamic Metrics with Profiling Blueprints

303

absoluteBounds

shapeBoundsAt: ifPresent:

display:on:

absoluteBoundsFor: legend for methods # executions

execution time

displayOn:

(color) #different receiver

Fig. 7. Profiling of the UI thread in Mondrian

Figure 8 shows the behavioral blueprint opened on MONode>> displayOn:. The blueprint reveals that absoluteBounds and absoluteBoundsFor: call each other. Return values of these two methods are constant as indicated by their yellow color. They are therefore good candidates for caching: MOGraphElement>> absoluteBounds ”Answer the bounds in absolute terms (relative to the entire Canvas, not just the parent).” absoluteBoundsCache ifNotNil: [ ˆabsoluteBoundsCache ]. ˆabsoluteBoundsCache := self shape absoluteBoundsFor: self

Result. Without the cache in absoluteBounds, the scenario takes 356 ms to run. With the cache, it takes 231 ms. We therefore gained 35% when displaying the visualization. Step 2. By adding the cache in absoluteBounds, we significantly reduced the cost of this method. We can still do better. As shown in Figure 8, there is another caller of absoluteBounds. MORectangleShape>> display:on: is 85 lines long and begins with: MORectangleShape>> display: aFigure on: aCanvas | bounds borderWidthValue textExtent c textToDisplay font borderColorValue ... | bounds := self absoluteBoundsFor: aFigure. c := self fillColorFor: aFigure. ...

304

A. Bergel, R. Robbes, and W. Binder

MONode>>displayOn: MORectangleShape>> display:on:

MOShape>> absoluteBoundsFor:

MOGraphElement>> absoluteBounds legend for methods # executions

execution time

gray = return self yellow = constant on return value

m1

m3

m2

m1 invokes m2 and m3

Fig. 8. Profiling of the UI thread in Mondrian

We saw in Step 1 that absoluteBounds calls the expensive and uncached absoluteBoundsFor:. Replacing the call to absoluteBoundsFor: by absoluteBounds improves performance further: MORectangleShape>> display: aFigure on: aCanvas | bounds borderWidthValue textExtent c textToDisplay font borderColorValue ... | bounds := aFigure absoluteBounds. c := self fillColorFor: aFigure. ...

Result. The execution time of the code snippet has been reduced to 198 ms. A speedup of 14% from Step 1, and of 45% overall. Blueprint evolution. Figure 9 summarizes the two evolution steps described previously. Differences with a previous step are denoted using a circle. The effect of caching absoluteBounds considerably diminished the execution time of this method. This is illustrated by Circle C. It has also the effect of reducing the size of MOShape’s methods and increasing MORectangleShape>> display:on:. The share of the CPU consumption increased for this method. Step 2 reduced the

cached absoluteBounds

A'

A

B

C'

B'

C'

C

make display:on: call absoluteBounds instead of absoluteBoundsFor:

D

Visualizing Dynamic Metrics with Profiling Blueprints

Fig. 9. Profiling of the UI thread in Mondrian

305

306

A. Bergel, R. Robbes, and W. Binder

size of MOShape’s method. Their execution time became so small, that it does not appear in the behavioral blueprint (since we use a sampling-based profiler to obtain the runtime information, methods having less than 1% of the CPU do not appear in this blueprint). 3.3

Summary

The cache value of MOGraphElement>> bounds (Section 3.1) is implemented and has been finalized in the version 341 of Mondrian6 . The improvement of absoluteBounds and display:on: may be found in the version 352 of Mondrian. The complete experiment lead to a 43% improvement in creating the layout of a view, and of 45% in displaying the same view. We identify and remove a number of bottlenecks. From this experience, it is tempting to identify and look after some general patterns that would easily expose fixable execution bottleneck. Unfortunately, we haven’t see the opportunity to deduce some general rules. The visualization we provide clearly identify costly methods and classes, potentially being candidates for optimization. Whether the optimization can be easily realized or not depends heavily on a wide range of parameters (e.g., algorithm, architecture, data structure).

4

Related Work

Profiling capabilities have been integrated in IDEs such as the NetBeans Profiler7 and Eclipse’s Tracing and Profiling Project (TPTP)8 . The NetBeans Profiler uses JFluid [Dmi04], which offers a Calling Context Tree (CCT) [ABL97] augmented with the accumulated execution time for individual methods. The CCT is visualized as an expandable tree, where calling contexts are sorted by their execution time and can be expanded (respectively collapsed) in order to show (or hide) callees. However, as CCTs for real-world applications are often large, comprising up to some million nodes, an expandable tree representation makes it difficult to detect hotspots in deep calling contexts. The Calling Context Ring Chart (CCRC) [MBAV09] is a CCT visualization that eases the exploration of large trees. Like the Sunburst visualization [Sta00], CCRC uses a circular layout. Callee methods are represented in ring segments surrounding the caller’s ring segment. In order to reveal hot calling contexts, the ring segments can be sized according to a chosen dynamic metric. Recently, CCRC has been integrated into the Senseo plugin for Eclipse [RHV+ 09], which enriches Eclipse’s static source views with several dynamic metrics. Our blueprints have a different focus, since global information is shown instead of providing a line-of-code granularity. Execution traces may be used to analyze dynamic program behavior. Execution traces are logged events, such as method entry and exit, or object allocation. 6 7 8

The source code is available at: http://www.squeaksource.com/Mondrian.html http://profiler.netbeans.org/ http://www.eclipse.org/tptp/performance/

Visualizing Dynamic Metrics with Profiling Blueprints

307

However, the resulting amount of data can be excessive. In Deelen et al. [DvHHvdW07] execution traces are visualized with nodes representing classes and edges representing method calls. Node size and edge thickness are mapped to properties (e.g., number of method invocations). A time range can be selected in order to limit the data to be visualized. Another approach to visualizing execution traces has been introduced in Holten et al. [HCvW07]. It uses the concept of hierarchical edge bundles [Hol06], where similar edges are put together to improve the visualization of larger traces. Execution traces allow keeping calls in sequences and selecting a precise time interval to be visualized, which helps understand a particular phase in the execution of a program. Blueprint profiling offers a global map of the complete execution without focusing on sequentiality in time. However, they offer hints about the behavior of individual methods that help to solve a class of optimization problem, namely introducing caches. Tree-maps [JS91] visualize hierarchical structures. Nodes are represented as rectangular areas sized proportionally to a metric. Tree-maps have been used to visualize profiling data. For instance, in [WKT04] the authors present KCacheGrind, a front end to a simulator-based cache profiling tool, using a combination of tree-maps and call graphs to visualize the data. Our blueprint use polymetric view to render data. A tree-map solves a problem in a different way that a polymetric view would solve it. A polymetric enables one to compare several different metrics, whereas a tree-map is dedicated to showing a single metric (besides color) in a compact space.

5

Conclusion

In this paper we presented two visualizations helping developers to identify and remove performance bottlenecks. Providing visualizations that are intuitive and easy to use is our primary goal. Our graphical blueprints follow simple principles such as “big nodes are slow methods”, “gray nodes are methods likely to have side-effects”, “yellow nodes remain constant on return values”. Our visualizations helped us to significantly improve Mondrian, a visualization engine. We described a number of optimizations we realized. For space reason, we couldn’t describe all the optimizations. The last version of Mondrian contains an improved version of the applyLayout method, thus mitigating the bottleneck caused by this method. This improvement was recently publicly announced9 . A number of conclusions may be drawn from the experiment described in this paper. First, bottleneck identification and removal are significantly easier when side-effects and constant return values are localized. Second, an extensive set of unit tests remains essential to assess whether a candidate optimization can be applied without changing the behavior of the system. As future work, we plan to focus on architectural views by adopting coarser grain than methods and classes.

9

http://www.iam.unibe.ch/pipermail/moose-dev/2010-January/003781.html

308

A. Bergel, R. Robbes, and W. Binder

We used our blueprint visualizations on a number of case studies not described in this paper: Glamour and Moose, and O210 . Our visualizations and profiler are available in Pharo11 under the MIT license.

References [ABL97]

[DLB04]

[Dmi04]

[DvHHvdW07]

[GL04]

[HCvW07]

[Hol06]

[JS91]

[LD03]

[MBAV09]

10 11

Ammons, G., Ball, T., Larus, J.R.: Exploiting hardware performance counters with flow and context sensitive profiling. In: Proceedings of the ACM SIGPLAN conference on Programming language design and implementation (PLDI’97), pp. 85–96 (1997) Ducasse, S., Lanza, M., Bertuli, R.: High-level polymetric views of condensed run-time information. In: Proceedings of 8th European Conference on Software Maintenance and Reengineering (CSMR 2004), pp. 309–318. IEEE Press, Los Alamitos (2004) Dmitriev, M.: Profiling Java applications using code hotswapping and dynamic call graph revelation. In: Proceedings of the Fourth International Workshop on Software and Performance (WOSP 2004), pp. 139–150 (2004) Deelen, P., van Ham, F., Huizing, C., van de Watering, H.: Visualization of dynamic program aspects. In: Proceedings of the 4th IEEE International Workshop on Visualizing Software for Understanding and Analysis (VISSOFT 2007), June 2007, pp. 39–46 (2007) Gˆırba, T., Lanza, M.: Visualizing and characterizing the evolution of class hierarchies. In: Proceedings of the 5th ECOOP Workshop on Object-Oriented Reengineering (WOOR 2004) Holten, D., Cornelissen, B., van Wijk, J.J.: Trace visualization using hierarchical edge bundles and massive sequence views. In: Proceedings of the 4th IEEE International Workshop on Visualizing Software for Understanding and Analysis (VISSOFT 2007), pp. 47–54 (2007) Holten, D.: Hierarchical edge bundles: Visualization of adjacency relations in hierarchical data. IEEE Transactions on Visualization and Computer Graphics 12(5), 741–748 (2006) Johnson, B., Shneiderman, B.: Tree-maps: a space-filling approach to the visualization of hierarchical information structures. In: Proceedings of the 2nd conference on Visualization (VIS 1991), pp. 284–291. IEEE Computer Society Press, Los Alamitos (1991) Lanza, M., Ducasse, S.: Polymetric views—a lightweight visual approach to reverse engineering. Transactions on Software Engineering (TSE) 29(9), 782–795 (2003) Moret, P., Binder, W., Ansaloni, D., Villaz´ on, A.: Visualizing Calling Context Profiles with Ring Charts. In: Proceedings of the 5th IEEE International Workshop on Visualizing Software for Understanding and Analysis (VISSOFT 2009), pp. 33–36. IEEE Computer Society, Los Alamitos (2009)

http://www.moosetechnology.org/tools/, http://www.squeaksource.com/O2.html http://www.squeaksource.com/Spy.html

Visualizing Dynamic Metrics with Profiling Blueprints [MGL06]

[RHV+ 09]

[Sta00]

[WKT04]

309

Meyer, M., Gˆırba, T., Lungu, M.: Mondrian: An agile visualization framework. In: Proceedings of the 3rd ACM Symposium on Software Visualization (SoftVis 2006), pp. 135–144. ACM Press, New York (2006) R¨ othlisberger, D., H¨ arry, M., Villaz´ on, A., Ansaloni, D., Binder, W., Nierstrasz, O., Moret, P.: Augmenting Static Source Views in IDEs with Dynamic Metrics. In: Proceedings of the 25th IEEE International Conference on Software Maintenance (ICSM 2009), pp. 253–262. IEEE Computer Society, Los Alamitos (2009) Stasko, J.: An evaluation of space-filling information visualizations for depicting hierarchical structures. Int. J. Hum.-Comput. Stud. 53(5), 663–694 (2000) Weidendorfer, J., Kowarschik, M., Trinitis, C.: A tool suite for simulation based analysis of memory access behavior. In: Bubak, M., van Albada, G.D., Sloot, P.M.A., Dongarra, J. (eds.) ICCS 2004. LNCS, vol. 3038, pp. 440–447. Springer, Heidelberg (2004)

Author Index

Arnaud, Jean-Baptiste

117

Madsen, Anders Bach Meyer, Bertrand 79 Mostinckx, Stijn 41 M¨ uller, Peter 79

Bals, Jan-Christopher 21 Bergel, Alexandre 117, 291 Binder, Walter 291

Nelson, Stephen 61 Nierstrasz, Oscar 213 Noble, James 61, 271 Nordio, Martin 79

Calcagno, Cristiano 79 Cameron, Nicholas 271 Christ, Fabian 21 de Halleux, Jonathan 253 de Lara, Juan 1 De Meuter, Wolfgang 41 Denker, Marcus 117 Ducasse, St´ephane 117, 213

¨ Ostlund, Johan

Pearce, David J. 61 Pollet, Damien 117 Renggli, Lukas 213 Robbes, Romain 291

Engels, Gregor 21 Ernst, Erik 233

Selby, Peter 173 St¨ ohr, Daniel 137 Suen, Mathieu 117

Gerth, Christian 21 Gˆırba, Tudor 213 Glesner, Sabine 137 Golbeck, Ryan M. 173 Guerra, Esther 1 Heidegger, Phillip Hundt, Christine

154 137

Kiczales, Gregor

173

Thiemann, Peter 154 Tillmann, Nikolai 253 Tschannen, Julian 79 Van Cutsem, Tom Wrigstad, Tobias

Lombide Carreton, Andoni Luckey, Markus 21

97

41 Xu, Hao

192

41 97

233