Measuring up

My previous blog post demonstrated my OCL to EMF-IncQuery transformation OCL2IQ in action. Here I am presenting my first performance measurements to investigate whether this solution fulfills the original promise of my research: delivering efficient, incremental query evaluation for a subset of OCL expressions by transforming them to graph patterns of equivalent semantics, and applying EMF-IncQuery on them.

For this purpose, I compare the performance of:

  • a naive Java implementation of the constraint check, as a hypothetical programmer would quickly implement it, without any special effort to improve performance,
  • the OCL interpreter of Eclipse, as it evaluates the OCL representation of the constraint check,
  • the OCL Impact Analyzer toolkit, as it incrementally evaluates the same OCL expressions,
  • hand-written graph patterns interpreted incrementally by EMF-IncQuery,
  • graph patterns automatically derived by my tool OCL2IQ from the OCL expression above, likewise interpreted incrementally by EMF-IncQuery.

Benchmark setup

The performance measurements were carried out in context of the Train Benchmark. This benchmark defines a number of well-formedness constraints in a custom metamodel, and measures the constraint checking performance of various model query tools as they process automatically generated instance models of various sizes conforming to the metamodel. The workload and measured performance indicators involve:

  • phase 1: reading the model,
  • phase 2: checking it for any inconsistencies as defined by the well-formedness constraints,
  • phase 3: simulating a transformation / manual editing of the model that performs a predefined sequence of modifications, and
  • phase 4: checking the updated model as well for inconsistencies

Contrary to traditional stateless query evaluators, incremental query evaluation strategies will complete phase 4 very quickly (instantly, save for the time it takes to return the results), since the set of inconsistencies has already been computed. However, this comes at the cost of maintaining the incremental caches, which imposes an overhead on phase 3 compared to stateless approaches. Similarly, these incremental caches may be initialized as early as during model reading, thereby shifting work from phase 2 to phase 1. Thus when comparing stateless tools against incremental ones, the most relevant performance indicators are phase1+2 ("Batch Validation") execution time and phase 3+4 ("Continuous Validation") execution time.

I have reproduced a subset of the Train Benchmark experiments on four of the original instance models using my Dell Latitude E5420 Laptop with an Intel Core i5-2430M @ 2.4Ghz CPU, 16GB of DDR3-1066/1333 RAM, a Samsung SSD 830 as storage, with software stack Eclipse Kepler on Java SE 1.7.0_05-b06  on Windows 7 x64. The measured tool versions were the following:

  • Eclipse OCL 3.3.0.v20130520-1222
  • Eclipse OCL Impact Analyzer 3.2.100.v20130520-1527
  • EMF-IncQuery 0.8.0 (nightly at 2013-11-29)

Query task

The selected benchmark case was the SignalNeighbor constraint check (Req 4). I reproduce here the OCL definition of this constraint check:

context Route:
oclIsKindOf(Route) and self.Route_exit->exists(signal |
    self.Route_routeDefinition.Sensor_trackElement.TrackElement_connectsTo.TrackElement_sensor->exists(sen2 |
        Route.allInstances()->exists(route2X |
            (route2X <> self) and route2X.Route_routeDefinition->includes(sen2)
        ) and not (
            Route.allInstances()->exists(route2 |
                route2.Route_routeDefinition->includes(sen2)
                  and route2.Route_entry = signal
            )
        )
    )
)

My tool OCL2IQ outputs the following graph patterns as translation:

pattern SignalNeighbor(
    self : Route
) {
    Route(route);
    self == route;
    Route.Route_exit(self, signal);
    signal_1 == signal;
    Route.Route_routeDefinition(self, sensor);
    temp1 == sensor;
    Sensor.Sensor_trackElement(temp1, trackelement);
    temp2 == trackelement;
    Trackelement.TrackElement_connectsTo(temp2, trackelement_0);
    temp3 == trackelement_0;
    Trackelement.TrackElement_sensor(temp3, sensor_0);
    sen2 == sensor_0;
    Route(route_0);
    route2X == route_0;
    route2X != self;
    Route.Route_routeDefinition(route2X, sensor_1);
    sensor_1 == sen2;
    neg find SignalNeighbor_4(sen2, signal_1);
}
pattern SignalNeighbor_4(
    sen2 : Sensor,
    signal_1 : Signal
) {
    Route(route_1);
    route2 == route_1;
    Route.Route_routeDefinition(route2, sensor_2);
    sensor_2 == sen2;
    Route.Route_entry(route2, signal_0);
    signal_0 == signal_1;
}

Whilst the original, hand-written EMF-IncQuery query definition looks like this:

pattern signalNeighbor(R1) =
{
    find exitSignalSensor(SigA, R1, Sen1A);
    find connectingSensors(Sen1A, Sen2A);
    find rDefinition(R3A, Sen2A);
    R3A != R1;
    neg find entrySignalSensor(SigA, _R2A, Sen2A);
}
pattern exitSignalSensor(Sig, R1, Sen1) =
{
    find exitSignal(R1, Sig);
    find rDefinition(R1, Sen1);
}  
pattern entrySignalSensor(Sig, R2, Sen2) =
{
    find entrySignal(R2, Sig);
    find rDefinition(R2, Sen2);
}  
pattern entrySignal(R, Sig) =
{
    Route(R);
    Signal(Sig);
    Route.Route_entry(R, Sig);
}
pattern exitSignal(R, Sig) =
{
    Route(R);
    Signal(Sig);
    Route.Route_exit(R, Sig);
}
pattern rDefinition(R, Sen) =
{
    Route(R);
    Sensor(Sen);
    Route.Route_routeDefinition(R, Sen);
}
pattern connectingSensors(Sen1, Sen2) =
{
    find sensorTrackelement(Sen1, Te1);
    find sensorTrackelement(Sen2, Te2);
    find trackelementConnected(Te1, Te2);
}
pattern trackelementConnected(Te1, Te2) =
{
    Trackelement(Te1);
    Trackelement(Te2);
    Trackelement.TrackElement_connectsTo(Te1, Te2);
}
pattern sensorTrackelement(Sen, Te) =
{
    Sensor(Sen);
    Trackelement(Te);
    Sensor.Sensor_trackElement(Sen, Te);
}

Benchmark results

For now, I only measured execution times. Memory consumption - where incremental tools will show their most important disadvantage - will be investigated later. Also note that the Java implementation was already close to timing out for the smaller instance models, so it was never run for the larger ones.

  Performance on instance models
Model size (#of nodes+edges) 113K 213K 435K 867K
Java Batch Validation Time 37 744 ms 140 630 ms    
Continuous Validation Time 35 421 ms 130 851 ms    
OCL Batch Validation Time 12 019 ms 42 261 ms 134 436 ms 664 327 ms
Continuous Validation Time 6 849 ms 29 813 ms 124 486 ms 659 803 ms
OCL-IA Batch Validation Time 11 309 ms 31 314 ms 132 929 ms 641 865 ms
Continuous Validation Time 58 ms 55 ms 45 ms 54 ms
EMF-IncQuery Batch Validation Time 3 903 ms 4 822 ms 6 670 ms 14 450 ms
Continuous Validation Time 7 ms 5 ms 8 ms 7 ms
OCL2IQ Batch Validation Time 4 376 ms 4 734 ms 9 083 ms 16 441 ms
Continuous Validation Time 24 ms 10 ms 16 ms 7 ms

The measurement data testifies that incremental strategies perform extremely well in the "Continuous Validation" workload, delivering execution times that are essentially independent from the size of the unchanging parts of the model. Furthermore it is apparent that EMF-IncQuery provides consistently higher performance as the other approaches. Finally and most importantly, I would like to point out that while the graph queries automatically generated using the proposed OCL2IQ transformation do not perform quite as well as manually written EMF-IncQuery code, they do come close, and they definitely outperform pure Java as well as stateless or incremental OCL-based approaches.

All in all, I have reached the main goal of my research by providing a way to evaluate (a restricted set of) OCL expressions more efficiently than previously possible.

This research was supported by the European Union and the State of Hungary, co-financed by the European Social Fund in the framework of TÁMOP 4.2.4. A/1-11-1-2012-0001 'National Excellence Program'.