This paper describes the SDMLib solution to the MovieDB case for the TTC2014 [4]. We explain a model transformation based solution and a plain Java solution based on a set-based model layer generated by SDMLib. In addition we discuss several refactorings we have used to improve the runtime performance of our solutions. SDMLib [3] is a light-weight model transformation approach based on graph grammar theory. SDMLib provides a Java API that allows to build a class model and to generate an SDMLib specific Java implementation for it. The generated model classes provide bidirectional association implementations, a reflection layer, and XML and JSON serialization mechanisms. In addition, SDMLib generates a set based layer for the model, where each method provided for a single model object is also provided for a set of such model objects. This is frequently used for model navigation e.g in actor1.getMovies().getPersons(). Here we ask an actor for the set of movies the actor has done and on this set we ask for the set of persons that participated in (at least one of) these movies. Finally, SDMLib generates a pattern matching layer for the model that provides classes to build model specific object patterns and model transformations. To solve the MovieDB case, we mainly use the set based layer. This enables a very efficient implementation of the clique detection task. However, for completeness, we also provide a solution using SDMLib model transformations.
1 p r i v a t e v o i d l o o k F o r C l i q u e s ( M o v i e S e t commonMovies , i n t w a n t e d S i z e , 2 P e r s o n S e t p e r s o n s ) f 3 i f ( w a n t e d S i z e <= m a x C l i q u e S i z e ) f 4 P e r s o n S e t n e w C l i q u e = ( P e r s o n S e t ) p e r s o n s . c l o n e ( ) ; 5 n e w C l i q u e . add ( dummyPerson ) ; 6 f o r ( P e r s o n p : commonMovies . g e t P e r s o n s ( ) ) f 7 i f ( p e r s o n s . g e t ( p e r s o n s . s i z e ( ) 1 ) . getName ( ) . compareTo ( p . getName ( ) ) < 0 ) f 8 M o v i e S e t i n t e r s e c t i o n = commonMovies . i n t e r s e c t i o n ( p . g e t M o v i e s ( ) ) ; 9 i f ( i n t e r s e c t i o n . s i z e ( ) >= 3 ) f 10 n e w C l i q u e . s e t ( w a n t e d S i z e 1 , p ) ; 11 a d d T o C l i q u e s ( i n t e r s e c t i o n , n e w C l i q u e ) ; 12 // look for larger cliques 13 14 g g g g l o o k F o r C l i q u e s ( commonMovies , w a n t e d S i z e + 1 , n e w C l i q u e ) ;
Listing 1: Set Base Model Transformation lookForCliques
Line 6 loops through the set of all persons that participate in one of the common movies passed as parameter. Note the call to commonMovies.getPersons(). Parameter commonMovies is of type MovieSet. This class is generated by SDMLib as an addition to the model class Movie. Class MovieSet provides all methods provided by class Movie and extends these methods to work on sets of objects. Thus method MovieSet::getPersons() calls methods Movie::getPersons() on each element of commonMovies. Method Movie::getPersons() has return type PersonSet, i.e. the set of persons working on a given movie. Method MovieSet::getPersons() collects these PersonSets within a (flat) result set using a result.union(newSet) operation. In our method lookForCliques this set based getPersons operation saves us an explicit outer loop through the commonMovies set and we do not need an extra data structure to keep track of already handled persons. Similarly, line 8 uses the set based method intersection to compute the set of common movies from the parameter commonMovies and the movies of the current person p. The if statement in line 7 ensures that we consider only persons with a name later than the name of the last person in newClique. This avoids multiple cliques of the same persons that differ only in the ordering. The if statement in line 9 ensures that the intersection of movies has at least 3 entries. Thus, when we reach line 10 we have found a new clique and line 11 adds this new clique to the rankings and line 13 tries to extend the new clique recursively. 3
The first version of our solution used the SDMLib generated model implementation, the set based model layer, and plain Java code as outlined in listing 1. In that version we did not create all found cliques explicitly but we only collected the 15 best cliques for each ranking. Without further optimizations the 20,000 synthetic MovieDB case needed about 50 seconds on a 2.67 GHz Intel i7 dual core (M60) 64 bit CPU (with hyper threading) and 8 GB main memory running windows 7. We call this our reference laptop from now on. Actually, first measurements with different case sizes for the synthetic MovieDB produced strange results where e.g the 10,000 case was much slower then the 20,000 case. We figured out that the Java virtual machine hot compile has a strong influence on our measurements. Hot compile causes up to 10 times speed-ups. Thus we added a warm up phase to our benchmark where we run a large synthetic case just to trigger the hot compile.
Then we replaced the java.util.LinkedHashSet implementation used for Cliques to store sets of common movies and sets of persons by an java.util.ArrayList based implementation. Our ArrayList based implementation still ensured set semantics, i.e. before adding e.g. a new Person object, it checks whether this object is already contained. As this benchmark uses many small sets of objects, using ArrayLists resulted in a speed-up of factor 5.
Next, the call for solutions states that the benchmark shall be done on workstation with an 8 core CPU. Thus we redesigned our solution to run in multiple threads. On our dual core reference laptop this created a speed-up of roughly factor 2. We have also tested it on a 12 core workstation where we achieved a speed-up of factor 10. With the parallelization we achieved an execution time of 12,263 seconds for the N=200,000 synthetic case using only one core and 5,695 seconds using both cores of our reference laptop, cf. row one of table 1.
In the synthetic case movies are generated with ascending rankings. Thus looping through the persons in order of their creation results in cliques with an ascending order of average ranking. Thus, when we maintain the list of the 15 best ranked cliques, we constantly replace old entries with higher ranked new entries. To avoid this, we just visit the persons in reverse order. This saves again 2.4 seconds on our reference laptop. Well, to some extend this is cheating as this trick will not show an improvement on the real data.
Next we learned from a conversation with the organizer that the call for solutions requires to create all cliques explicitly. Actually, explicit clique creation needs about 0.5 seconds for two threads and thus probably about 1 second on a single thread. Finally, we need about 5 seconds to detect all couples and all cliques in a single thread for the N=200,000 synthetic case.
solution feature Introduced ArrayList for cliques Changed PersonSet to ArrayList<Person> Looping through persons in reverse order Changed MovieSet to Array List Added trafo, improved it by factor 5 Caching trafos trafo (sec)
At this point in time, we added the model transformation based solution to the clique detection mechanism as discussed in section 2. Initially, the trafo solution already took some 200 seconds for the N=20,000 case. We identified that the SDMLib model transformation mechanism did a lot of copying of candidate sets during search. By removing many of these copies and by using ArrayList where possible we achieved a speed-up of about factor 6 resulting in the times reported in row 5 of table 1. Thus, the improved model transformation used 213 seconds for the N=200,000 synthetic case. Unhappy with this execution time, we identified that the lookForCliques transformation is called recursively some million times and that we construct the object structure that represents the model transformation each time anew. Thus, we added a cache for the object structure that represents the model transformation and just reinitialized it to start the pattern matching from a new clique each time. This reduced the execution time to some 75 seconds, cf. last row of table 1. Overall, the transformation based solution is still 15 times slower than the set based solution. Actually, we have already spotted some other inefficient heap operations within our interpreter. We work on more improvements on that. 4
Our first approach to attack the MovieDB case was a manually written Java method exploiting the model implementation generated by SDMLib and especially exploiting the generated set-based model layer as shown in listing 1. Coming up with this solution was quite straight forward and we think it is reasonably concise and it seems to be reasonably efficient.
For comparison, we also developed a model transformation based approach. While the graphical
representation of the model transformations in figure 1 and figure 2 is reasonably understandable (at least if you
have developed them yourself :), the Java code that creates the object structure that represents the model
transformations is about double the size of the set-based solution. In addition, the Java code is not as
comprehensible as the set-based code. And finally, the model transformation based solution is slower by a factor
of 15. Note, the set-based model layer generated by SDMLib compares to simple OCL expressions [