Index: /reasoner/reasoner.tex =================================================================== --- /reasoner/reasoner.tex (revision 86) +++ /reasoner/reasoner.tex (revision 87) @@ -7,4 +7,5 @@ \usepackage{graphicx} \usepackage{adjustbox} +\usepackage[toc,page]{appendix} \newcommand\TBD[1]{{\color{blue}TBD: #1}} @@ -46,5 +47,5 @@ \newcommand\tabAlgLine[2]{Alg.\ref{#1},\ref{#2}} \newcommand\tabAlgLines[3]{Alg.\ref{#1},\ref{#2}-\ref{#3}} -\newcommand\tabAlgFollow[0]{$\rightarrow$} +\newcommand\tabAlgFollow[0]{ $\rightarrow$ } \let\emph\relax % there's no \RedeclareTextFontCommand @@ -763,5 +764,5 @@ \subsection{Annotations}\label{sectAnnotationDefaults} -In IVML, annotations are orthogonal typed variables that can be attached to a variable. For all those ortogonal variables, the reasoner must create constraints to perform the evaluation and assignment of the default values before all other constraints are considered for reasoning. Moreover, we must translate assignment-blocks, i.e., blocks assigning specific values to all variables declared within that block. In this section, we discuss first the translation of annotations, then the translation of annotation blocks. +In IVML, annotations are orthogonal typed variables that can be attached to a variable. For all those ortogonal variables, the reasoner must create constraints to perform the evaluation and assignment of the default values before all other constraints are considered for reasoning. It is important to recall that IVML annotations are not recursive \cite{IVML-LS}, although the reasoner algorithms could support this. Moreover, we must translate assignment-blocks, i.e., blocks assigning specific values to all variables declared within that block. In this section, we discuss first the translation of annotations, then the translation of annotation blocks. Algorithm \ref{algTranslateAnnotationDeclarations} receives the declaration of the actual variable and a potential compound access expression $ca$ to $d$ if the algorithm is called for slots of a compound value. For all annotations of $v$ (as for $v$ here all inherited annotations are available), the algorithm creates the respective constraints through calling Algorithm \ref{algTranslateDeclaration}. Plase note that no specific variable accessors are handled for such top-level annotation assignments through a specific constraint syntax tree node, which is created through \IVMLMeta{acc()} in Algorithm \ref{algTranslateDeclaration} line \ref{algTranslateDeclarationTranslateAnnotationAccess}. @@ -773,5 +774,5 @@ \ForEach{$a\in annotations(v)$}{ - $translateDeclaration(decl(a), a, ca)$\; + $translateDeclaration(decl(a), a, ca)$\;\label{algTranslateAnnotationDeclarationsTranslateDecl} } \caption{Translating annotation defaults (\IVML{translateAnnotationDeclarations}).}\label{algTranslateAnnotationDeclarations} @@ -815,5 +816,5 @@ } - \caption{Translating attribute assignments (\IVML{translateAnnotationAssignments}).}\label{algTranslateAnnotationAssignments} + \caption{Translating annotation assignments (\IVML{translateAnnotationAssignments}).}\label{algTranslateAnnotationAssignments} \end{algorithm} @@ -907,5 +908,5 @@ \section{IVML-Completeness}\label{sectCompleteness} -\TBD{Fill table} +In this section, we discuss the completeness of the reasoner with respect to IVML concepts. Reasoning completeness, e.g., involving advanced reasoning capabilities such as narrowing down value instances by limiting constraints or instance creation, is not topic of this section and may be targeted by future work. \begin{table*}[h] @@ -914,49 +915,99 @@ \begin{tabular}{|p{3.5cm}|c||p{6cm}|p{3.5cm}|} \hline -\textbf{IVML concept} & \textbf{Spec} & \textbf{Transformation Trace} & \textbf{Test}\\ -\hline +\textbf{IVML concept} & \textbf{Spec} & \textbf{Transformation Path} & \textbf{Test}\\ +\hline + Decision variable & 2.1.4 & \tabAlgLine{algTranslateConstraints}{algTranslateConstraintsTranslationDeclaration}\tabAlgFollow\tabAlgLine{algTranslateDeclaration}{algTranslateDeclarationTranslateDefault} & \textit{all} \\ + Constraint & 2, 3 & \tabAlgLine{algTranslateConstraints}{algTranslateConstraintsTopLevelConstraints} & B2, ...\\ + Constraint variable & 3.1.10 & \tabAlgLine{algTranslateConstraints}{algTranslateConstraintsTranslationDeclaration}\tabAlgFollow\tabAlgLines{algTranslateDeclaration}{algTranslateDeclarationTranslateConstraintDefaultStart}{algTranslateDeclarationTranslateConstraintDefaultEnd} & \MISSING{!} \\ -Annotation & 2.2.2 & \tabAlgLine{algTranslateConstraints}{algTranslateConstraintsTranslationDeclaration}\tabAlgFollow\tabAlgLine{algTranslateDeclaration}{algTranslateConstraintsTopLevelAnnotationAssignments} & A1, A2, A3\\ + +Annotation & 2.2.2 & \tabAlgLine{algTranslateConstraints}{algTranslateConstraintsTranslationDeclaration}\tabAlgFollow\tabAlgLine{algTranslateDeclaration}{algTranslateDeclarationAnnotationDefault}\tabAlgFollow\tabAlgLine{algTranslateAnnotationDeclarations}{algTranslateAnnotationDeclarationsTranslateDecl}\tabAlgFollow Table \ref{tab:completenessAnnotations} & A1, A2, A3\\ + Assignment block & 2.2.2 & \tabAlgLine{algTranslateConstraints}{algTranslateConstraintsTopLevelAnnotationAssignments}\tabAlgFollow\tabAlg{algTranslateAnnotationAssignments} & CnA1, CnA2, CnA3 \\ + Partial evaluation & 2.2.5.3 & \tabAlgLine{algTranslateConstraints}{algTranslateConstraintsTopLevelEvals} & Ev1, Ev2 \MISSING{prio?}\\ + \hline \multicolumn{4}{|c|}{Types (typed decision variable, starting in \tabAlg{algTranslateDeclaration})}\\ \hline + Integer type & 2.1.3.1 & \tabAlgLine{algTranslateDeclaration}{algTranslateDeclarationTranslateDefault}, cf. Sect. \ref{sectNotationOthers} & I1, I2\\ + Real type & 2.1.3.1 & \tabAlgLine{algTranslateDeclaration}{algTranslateDeclarationTranslateDefault}, cf. Sect. \ref{sectNotationOthers} & R1, R2\\ + Boolean type & 2.1.3.1 & \tabAlgLine{algTranslateDeclaration}{algTranslateDeclarationTranslateDefault}, cf. Sect. \ref{sectNotationOthers} & B1, B2, B3 \\ + String type & 2.1.3.1 & \tabAlgLine{algTranslateDeclaration}{algTranslateDeclarationTranslateDefault}, cf. Sect. \ref{sectNotationOthers} & S1, S2\\ + Enum type & 2.1.3.2 & \tabAlgLine{algTranslateDeclaration}{algTranslateDeclarationTranslateDefault}, cf. Sect. \ref{sectNotationOthers} & E1, E2\\ + Reference type & 2.2.3.2 & \tabAlgLine{algTranslateDeclaration}{algTranslateDeclarationTranslateDefault}, cf. Sect. \ref{sectNotationOthers} & \TBD{tests}\\ + Derived type & 2.1.3.4 & \tabAlgLine{algTranslateDeclaration}{algTranslateDeclarationDerivedDatatype}\tabAlgFollow\tabAlg{algTranslateDerivedDatatypeConstraints} & \TBD{tests} \\ + Constraint type & 3.10.1 & no specific constraints, cf. Section \ref{sectNotationOthers}, constraint value in \ref{algTranslateDeclaration} line \ref{algTranslateDeclarationConstraintVariableConstraint} & \TBD{tests} \\ -\hline - \multicolumn{4}{|c|}{Compound types (typed decision variable, starting with \tabAlgLine{algTranslateDeclaration}{algTranslateDeclarationTranslateCompound}\tabAlgFollow\tabAlg{algTranslateCompoundDeclaration}, mapping in \tabAlg{algRegisterCompoundMapping})}\\ -\hline + +\hline +\end{tabular} +%\end{adjustbox} +\caption{Translations for top-level and non-compex types.} +\label{tab:completenessTopLevelTypes} +\end{table*} + +To indicate the IVML completeness, we enumerate all relevant IVML concepts, their definition in the IVML specification \cite{IVML-LS}, the transformation path along the algorithms presented in this document and the test cases validating the transformation and the reasoning results. We separate the argumentation into four parts and present for each path the relation of specification entry, transformation path and test cases in terms of a summarizing table. The four parts are 1) top-level concepts / basic types (Table \ref{tab:completenessTopLevelTypes}), compound types (Table \ref{tab:completenessCompounds}), container types (Table \ref{tab:completenessContainers}) and annotations (Table \ref{tab:completenessAnnotations}). Test cases are referenced by ids in order to indicate that all relevant combinations are subject to regression testing in the continuous build process of EASy-Producer. The referenced test cases are detailed in Appendix \ref{appendixTestCases}. + +\pagebreak + +\begin{table*}[h] +%\begin{adjustbox}{angle=90} +\centering +\begin{tabular}{|p{3.5cm}|c||p{6cm}|p{3.5cm}|} +\hline +\textbf{IVML concept} & \textbf{Spec} & \textbf{Transformation Path} & \textbf{Test}\\ + +\hline + Integer type & 2.1.3.1 & \tabAlgLine{algTranslateCompoundDeclaration}{algTranslateCompoundDeclarationTranslateSlotsV}\tabAlgFollow \tabAlg{algTranslateDeclaration} & ICo1, ICo2\\ + Real type & 2.1.3.1 & \tabAlgLine{algTranslateCompoundDeclaration}{algTranslateCompoundDeclarationTranslateSlotsV}\tabAlgFollow \tabAlg{algTranslateDeclaration} & RCo1, RCo2\\ + Boolean type & 2.1.3.1 & \tabAlgLine{algTranslateCompoundDeclaration}{algTranslateCompoundDeclarationTranslateSlotsV}\tabAlgFollow \tabAlg{algTranslateDeclaration} & BCo1, BCo2, BCo3 \\ + String type & 2.1.3.1 & \tabAlgLine{algTranslateCompoundDeclaration}{algTranslateCompoundDeclarationTranslateSlotsV}\tabAlgFollow \tabAlg{algTranslateDeclaration} & SCo1, SCo2\\ + Enum type & 2.1.3.2 & \tabAlgLine{algTranslateCompoundDeclaration}{algTranslateCompoundDeclarationTranslateSlotsV}\tabAlgFollow \tabAlg{algTranslateDeclaration} & ECo1, ECo2\\ -Derived type & 2.1.3.4 & Alg. \ref{algTranslateDeclaration} line \ref{algTranslateDeclarationDerivedDatatype} $\rightarrow$ Alg.\ref{algTranslateDerivedDatatypeConstraints} & \TBD{tests} \\ + +Derived type & 2.1.3.4 & \tabAlgLine{algTranslateCompoundContent}{algTranslateCompoundDeclarationTranslateSlotsV} or \tabAlgLine{algTranslateCompoundContent}{algTranslateCompoundDeclarationTranslateSlotsT}\tabAlgFollow\tabAlg{algTranslateDeclaration} & \TBD{tests} \\ + Compound type & 2.1.3.5 & Alg. \ref{algTranslateDeclaration} line \ref{algTranslateDeclarationTranslateCompound} $\rightarrow$ Alg.\ref{algTranslateCompoundDeclaration} & \TBD{tests} \\ + Container type & 2.1.3.3 & & \TBD{tests} \\ + Reference type & 2.2.3.2 & no specific constraints, cf. Section \ref{sectNotationOthers} & \TBD{tests} \\ + Constraint type & 3.10.1 & no specific constraints, cf. Section \ref{sectNotationOthers}, constraint value in \ref{algTranslateDeclaration} line \ref{algTranslateDeclarationConstraintVariableConstraint} via compound access line \ref{algTranslateDeclarationTranslateInCompound} & \TBD{tests} \\ + +Annotation & 2.2.2 & top-level see Table \ref{tab:completenessTopLevelTypes}, nested usage \tabAlgLine{algTranslateCompoundContent}{algTranslateCompoundDeclarationTranslateSlotsV} or \tabAlgLine{algTranslateCompoundContent}{algTranslateCompoundDeclarationTranslateSlotsT}\tabAlgFollow\tabAlg{algTranslateDeclaration} & \TBD{tests}\\ + +Assignment blocks & 2.2.2 & \tabAlgLine{algTranslateCompoundContent}{algTranslateCompoundDeclarationCompoundAssignments}\tabAlgFollow\tabAlg{algTranslateAnnotationAssignments} & \TBD{tests} \\ + +Partial evaluation & 2.2.5.3 & \tabAlgLines{algTranslateCompoundContent}{algTranslateCompoundDeclarationEvalStart}{algTranslateCompoundDeclarationEvalEnd} & - \\ + \hline \end{tabular} %\end{adjustbox} -\caption{IVML concepts vs. reasoning constraint transformations.} -\label{tab:IVMLReasoner} +\caption{Compound translations, starting with \tabAlgLine{algTranslateDeclaration}{algTranslateDeclarationTranslateCompound}\tabAlgFollow\tabAlg{algTranslateCompoundDeclaration} and \tabAlg{algRegisterCompoundMapping}.} +\label{tab:completenessCompounds} \end{table*} +\pagebreak \begin{table*}[h] @@ -965,48 +1016,177 @@ \begin{tabular}{|p{4cm}|r||p{6cm}|p{3cm}|} \hline -\textbf{IVML concept} & \textbf{Spec} & \textbf{Transformation Trace} & \textbf{Test}\\ -\hline - \multicolumn{4}{|c|}{Container type, starting with \tabAlgLine{algTranslateDeclaration}{algTranslateDeclarationTranslateContainer}\tabAlgFollow \tabAlg{algTranslateContainerDeclaration}}\\ -\hline +\textbf{IVML concept} & \textbf{Spec} & \textbf{Transformation Path} & \textbf{Test}\\ + +\hline + Integer type & 2.1.3.1 & no action in \tabAlg{algTranslateContainerDeclaration}, cf. Sect. \ref{sectNotationOthers} & ICt1, ICt2\\ + Real type & 2.1.3.1 & no action in \tabAlg{algTranslateContainerDeclaration}, cf. Sect. \ref{sectNotationOthers} & RCt1, RCt2\\ + Boolean type & 2.1.3.1 & no action in \tabAlg{algTranslateContainerDeclaration}, cf. Sect. \ref{sectNotationOthers} & BCt1, BCt2 \\ + String type & 2.1.3.1 & no action in \tabAlg{algTranslateContainerDeclaration}, cf. Sect. \ref{sectNotationOthers} & SCt1, SCt2\\ + Enum type & 2.1.3.2 & no action in \tabAlg{algTranslateContainerDeclaration}, cf. Sect. \ref{sectNotationOthers} & ECt1, ECt2 \\ -Derived type & 2.1.3.4 & Alg. \ref{algTranslateDeclaration} line \ref{algTranslateDeclarationDerivedDatatype} $\rightarrow$ Alg.\ref{algTranslateDerivedDatatypeConstraints} & \TBD{tests} \\ + +Derived type & 2.1.3.4 & \tabAlgLine{algTranslateContainerDeclaration}{algTranslateContainerDeclarationDerivedTypes}\tabAlgFollow\tabAlg{algTranslateDeclaration} & \TBD{tests} \\ + Compound type & 2.1.3.5 & & \TBD{tests} \\ + Container type & 2.1.3.3 & & \TBD{tests} \\ + Derived Compound Type & & & \TBD{tests} \\ + Derived Container Type & & & \TBD{tests} \\ + Reference type & 2.2.3.2 & no specific constraints, cf. Section \ref{sectNotationOthers} & \TBD{tests} \\ + Constraint type & 3.10.1 & no specific constraints, cf. Section \ref{sectNotationOthers} \TBD{constraint value} & \TBD{tests} \\ + Constraint Container& & & \TBD{CnCt1, CnCt2} \\ + Derived Constraint Container& & & \TBD{tests} \\ -\hline - \multicolumn{4}{|c|}{Annotation of \TBD{path}} \\ -\hline -Basic type & 2.1.3.1 & no specific constraints, cf. Section \ref{sectNotationOthers} & \TBD{tests} \\ -Enum type & 2.1.3.2 & no specific constraints, cf. Section \ref{sectNotationOthers} & \TBD{tests}\\ -Derived type & 2.1.3.4 & & \TBD{tests} \\ -Compound type & 2.1.3.5& & \TBD{tests} \\ -Container type & 2.1.3.3 & & \TBD{tests} \\ -Reference type & 2.2.3.2 & no specific constraints, cf. Section \ref{sectNotationOthers} & \TBD{tests} \\ -Constraint type & 3.10.1 & no specific constraints, cf. Section \ref{sectNotationOthers}& \TBD{tests} \\ + +Annotation & 2.2.2 & top-level only, see Table \ref{tab:completenessTopLevelTypes} & \TBD{tests}\\ + +Assignment blocks & - & - & - \\ + +Partial evaluation & - & - & - \\ + \hline \end{tabular} -\caption{IVML concepts vs. reasoning constraint transformations (continued).} +\caption{Translation of containers, starting with \tabAlgLine{algTranslateDeclaration}{algTranslateDeclarationTranslateContainer}\tabAlgFollow \tabAlg{algTranslateContainerDeclaration}} +\label{tab:completenessContainers} %\end{adjustbox} \end{table*} -% B=Boolean -%Co = Compound -%Cr = Container -%Cn = Constraint -%A=Annotation, AssignmentBlock -%Ev=Eval -%I=Integer -%R=Real -%S=String -%E=Enum +\pagebreak + +\begin{table*}[h] +%\begin{adjustbox}{angle=90} +\centering +\begin{tabular}{|p{4cm}|r||p{6cm}|p{3cm}|} +\hline +\textbf{IVML concept} & \textbf{Spec} & \textbf{Transformation Path} & \textbf{Test}\\ + +Integer type & 2.1.3.1 & \tabAlgLine{algTranslateDeclaration}{algTranslateDeclarationTranslateAnnotationAccess}\tabAlgFollow\tabAlgLine{algTranslateDeclaration}{algTranslateDeclarationTranslateDefault} & \TBD{tests} \\ + +Real type & 2.1.3.1 & \tabAlgLine{algTranslateDeclaration}{algTranslateDeclarationTranslateAnnotationAccess}\tabAlgFollow\tabAlgLine{algTranslateDeclaration}{algTranslateDeclarationTranslateDefault} & \TBD{tests} \\ + +Boolean type & 2.1.3.1 & \tabAlgLine{algTranslateDeclaration}{algTranslateDeclarationTranslateAnnotationAccess}\tabAlgFollow\tabAlgLine{algTranslateDeclaration}{algTranslateDeclarationTranslateDefault} & \TBD{tests} \\ + +String type & 2.1.3.1 & \tabAlgLine{algTranslateDeclaration}{algTranslateDeclarationTranslateAnnotationAccess}\tabAlgFollow\tabAlgLine{algTranslateDeclaration}{algTranslateDeclarationTranslateDefault} & \TBD{tests} \\ + +Enum type & 2.1.3.2 & \tabAlgLine{algTranslateDeclaration}{algTranslateDeclarationTranslateAnnotationAccess}\tabAlgFollow\tabAlgLine{algTranslateDeclaration}{algTranslateDeclarationTranslateDefault} & \TBD{tests}\\ + +Derived type & 2.1.3.4 & \tabAlgLine{algTranslateDeclaration}{algTranslateDeclarationDerivedDatatype}\tabAlgFollow\tabAlg{algTranslateDerivedDatatypeConstraints} & \TBD{tests} \\ + +Compound type & 2.1.3.5& & \TBD{tests} \\ + +Container type & 2.1.3.3 & & \TBD{tests} \\ + +Reference type & 2.2.3.2 & no specific constraints, cf. Section \ref{sectNotationOthers} & \TBD{tests} \\ + +Constraint type & 3.10.1 & no specific constraints, cf. Section \ref{sectNotationOthers}& \TBD{tests} \\ + +Annotation & - & - & - \\ + +Assignment blocks & - & - & - \\ + +Partial evaluation & - & - & - \\ + +\hline +\end{tabular} +\caption{Translation of annotations, starting top-level in Table \ref{tab:completenessTopLevelTypes}} +%\end{adjustbox} +\label{tab:completenessAnnotations} +\end{table*} + +\pagebreak + +%----------------------------------------------------------------------------------------------------------------- + +\section{Performance Considerations}\label{sectPerformance} + +In this section, we briefly collect some observations seen/refactored/solved/left over during the improvement of the reasoner. Although the considerations may appear rather reasoner specific or specific to the IVML object model, they typically stem from more general Java performance optimization knowledge typically hidden behind constraints, reasoner or model data structures. \TBD{The individual texts may be pretty short, and are currently just intended for remembering/recording the obstacles.} + +\begin{itemize} + \item For lists of unknown size and for the expected capacity of IVML models, use \textbf{linked lists} instead of array lists. Main operations are adding, iterating over all, and removing elements to clean up memory incrementally, i.e., linked lists can avoid performance-impacting resizing effects. Index-based access is not needed, constraints are just added and one iteration is needed to build up the constraint base or to perform reasoning. Pre-calculation of the expected size of the data structures per model seems to be unfeasible as this requires a second run over all model elements. + \item Process the \textbf{constraint base} iteratively and remove processed constraints directly after processing. This again requires a linked list as otherwise incremental resizing effects can affect the performance. In summary, building the constraint base and reasoning causes peak memory effects that are better from a performance point of view than (re-)allocating big array memory blocks. + \item Avoid having too many unneeded \textbf{partitions of the constraint base} being stored during the translation in different lists, that are finally added to the constraint base. Try to directly add constraints where possible to the constraint base, e.g., for default constraints to avoid iterating over the complete constraint base before reasoning. However, due to the prioritization of the constraint types and their required sequence, this is not always possible. One alternative, a numeric prioritization of the individual constraints would require sorting the constraint base, at the new parts not the left-over constraints to be re-evaluated from a previous reasoning steps. However, implicit sorting on insertion according to priorities could help here. + \item Create/translate a \textbf{constraint in one step}, if required in compounds split into filling the variability mapping and then creating the constraints based on the actual mapping. + \item Try to figure out whether a certain \textbf{constraint (type) is actually needed} for reasoning and avoid its translation/creation wherever feasible. \TBD{Can we move the decision about keeping a constraint from adding it to the constraint base before constraint creation. However, this requires changes/additional alternatives for different code parts.}. Thus, don't re-process or filter certain constraint types at the end (done in the initial version for default and derived type constraints), as this implies iterating multiple times over the (partial) constraint base and re-creating/throwing away constraint instances in memory. + \item \TBD{Avoid storing constraints that can be \textbf{processed immediately}, e.g., default constraints without dependencies. However, if a default constraint fails, it must be added to the constraint basis for later possible re-evaluation if dependent values become available/right.} + \item For identifying whether constraints are already in the constraint base, use a \textbf{fast look-up structure} instead of an iteration over the constraint base. Although the initial implementation utilized here reference equality (faster than the equals method), the current lookup structure is significantly faster (approx. 600 ms on large models, at that time around 25\% of runtime) than the original approach trading off execution speed for (peek) memory. Here a lookup structure based on reference equality could further speed up reasoning, which, however, may in the end be slower than the built in collections due to JIT compilation and JVM optimization effects. This is even true for the stack-based variable mapping $\variableMapping$, which performs as fast as a flat map, which may roughly serve for the main purpose of $\variableMapping$, but not for composing complex constraints from nested compunds and containers. + \item Incremental reasoning using a \textbf{stored constraint base} may speed up reasoning but only achieves this through large memory allocations. Ensure initializing the model through default constraints so that the actual stored constraint base only contains really needed constraint types, i.e., no default constraints and, if possible, no constraints for which all depending variables are already frozen. + \item \textbf{Reuse visitor instances} if applied more than once, in particular reasoners with more complex internal data structures such as maps or lists. This required some refactoring of the IVML model implementation. + \item \textbf{Avoid temporary instances}, e.g., iterators, temporary constraint creation, temporary data structures wherever possible. One option replacing a collection structure is to define a functor for processing the elements and to create a reusable instance of that functor. If permitted by the Java environment settings (EASy often compiles against JDK 1.6), also a lambda-function instead of a heavy-weight functor class may be appropriated. + \item \textbf{Avoid multipe variable substitutions} per constraint expressions, i.e., join variable substitutions wherever possible. Variable substitution copies the expression. Multiple copies throws away the last copied expression. + \item \textbf{Use instance pooling} if datastructures are temporarily used, e.g., variable accessors in expression evaluation or sets of compounds in reasoning (20-30 ms on larger models, at that time around 10\% of runtime). +\end{itemize} + +There are still opportunities for further speeding up the reasoning operations. On an Intel core i7, the reasoner reaches around 15-43 constraint evaluations in average per millisecond - runtime vs. full reasoning on the latest QualiMasster test model, currently reasoning time includes translation and evaluation time \TBD{Sepearte timing}. This is already an improvement over the initial version, which operated at around 10 evaluations per millisecond in average (also with a higher number of constraint evaluations due to unneeded and uneffective constraints). The constraint evaluation time probably suffers from the immutable structured values in EASy-Producer, which are created for each assignment. Knowing that most of the assignments in this model are done for basic IVML datatypes, a fast track for setting integer, double, boolean and String values could increase the number of evaluations, but requires careful extension, as changing values shall only be allowed via decision variables, which take care of the current assignment state, e.g., \IVML{FROZEN}. + +\section{Evaluation}\label{sectEvaluation} + +\TBD{Keep or remove that section. However, some basic performance evaluations should not be so difficult. All executions need multiple runs, in particular to even out JIT compilation. It seems that this is done during/after the second reasoning run. Potential topics: + +\begin{itemize} + \item Artificial models of some size/variable/constraint ratio. Christian had a generator for that and Roman typically did some evaluations using these models. Compare to known results where available. + \item QualiMaster full, incremental, runtime reasoning (full, no defaults, no frozen, reuse constraint base). Runtime vs. full reasoning seems to behave rather linearly, at around 23 constraints evaluated per ms. Compare to known results where available. + \item All test cases involving reasoning as an overview map. +\end{itemize} + +} + +%----------------------------------------------------------------------------------------------------------------- + +\section{Conclusion}\label{sectConclusion} + +\TBD{We are better than before, we are now more IVML-complete, but not reasoning-complete. Future, integrate with SMT or other solvers for left-over reasoning problems or configuration completion/instance creation (potential student work).} + +%----------------------------------------------------------------------------------------------------------------- + +\section*{Acknowledgements} + +We are grateful to Phani Saripalli for implementing the initial IVML reasoner based on the Jess rules engine. We are also grateful to Roman Sizonenko for implementing and experimenting with the Drools-based IVML reasoner and for realizing the initial SSE IVML reasoner used as basis for the actual version of the reasoner and this documentation. + +\bibliographystyle{abbrv} +\bibliography{reasoner} + +\begin{appendices} +\section{Reasoner test cases}\label{appendixTestCases} + +In this section, we list a subset of the implemented reasoner test cases, which aim at validating translation and reasoning for specific IVML concepts and combinations. In addition, the reasoner test cases defined as part of the test suite for the \class{ReasonerCore} bundle of EASy-Producer contain also more complex test cases taken from real scenarios, evaluation models as well as challenge test cases. + +For referencing the test cases, we use identifiers composed for the main concepts to be validated. We use the abbreviations shown in Table \ref{tab:testCaseIdSchema} to compose identifiers. For example, test case nuber one on Integer (I) variables used as compound (Co) slots is identified by 'ICo1'. Table \ref{tab:reasonerTestCasesBasics} and Table \ref{tab:reasonerTestCasesAdvanced} list the test cases referenced in this document. + +\begin{table*}[h] +%\begin{adjustbox}{angle=90} +\centering +\begin{tabular}{|l|l|} +\hline +\textbf{Id part / abbreviation} & \textbf{IVML concept}\\ +\hline + +B & Boolean \\ +Co & Compound \\ +Cr & Container\\ +Cn & Constraint\\ +A & Annotation, AssignmentBlock\\ +Ev & Eval\\ +I & Integer\\ +R & Real\\ +S & String\\ +E & Enum\protect\footnotemark\\ +\hline +\end{tabular} +\caption{Test case naming schema.} +\label{tab:testCaseIdSchema} +%\end{adjustbox} +\end{table*} +\footnotetext{Similarly, test cases for ordered enums are in place, but not referenced explicitly in this document.} + + \begin{table*}[h] @@ -1043,5 +1223,5 @@ SCt1 & \class{string/StringInContainerAssignTest.ivml}\\ SCt2 & \class{string/StringInContainerDefaultsTest.ivml}\\ -E1 & \class{enums/EnumDefaultsTest.ivml}\footnote{similar tests for ordered enums are in place}\\ +E1 & \class{enums/EnumDefaultsTest.ivml}\\ E2 & \class{enums/EnumAssignTest.ivml}\\ ECo1 & \class{enums/EnumInCompoundDefaultsTest.ivml}\\ @@ -1049,4 +1229,18 @@ ECt1 & \class{enums/EnumInContainerDefaultsTest.ivml}\\ ECt2 & \class{enums/EnumInContainerAssignTest.ivml}\\ +\hline +\end{tabular} +\caption{IVML reasoner test cases for basic types combined with compounds or containers.} +\label{tab:reasonerTestCasesBasics} +%\end{adjustbox} +\end{table*} + +\begin{table*}[h] +%\begin{adjustbox}{angle=90} +\centering +\begin{tabular}{|l|p{12cm}|} +\hline +\textbf{Id} & \textbf{Test model}\\ +\hline CnCt1 & \class{collectionConstraints/constraintSetDefault.ivml}\\ CnCt2 & \class{collectionConstraints/constraintSetSetDefault.ivml}\\ @@ -1061,58 +1255,10 @@ \hline \end{tabular} -\caption{IVML reasoner test cases.} +\caption{IVML reasoner test cases for advanced concepts and types.} +\label{tab:reasonerTestCasesAdvanced} %\end{adjustbox} \end{table*} - -%----------------------------------------------------------------------------------------------------------------- - -\section{Performance Considerations}\label{sectPerformance} - -In this section, we briefly collect some observations seen/refactored/solved/left over during the improvement of the reasoner. Although the considerations may appear rather reasoner specific or specific to the IVML object model, they typically stem from more general Java performance optimization knowledge typically hidden behind constraints, reasoner or model data structures. \TBD{The individual texts may be pretty short, and are currently just intended for remembering/recording the obstacles.} - -\begin{itemize} - \item For lists of unknown size and for the expected capacity of IVML models, use \textbf{linked lists} instead of array lists. Main operations are adding, iterating over all, and removing elements to clean up memory incrementally, i.e., linked lists can avoid performance-impacting resizing effects. Index-based access is not needed, constraints are just added and one iteration is needed to build up the constraint base or to perform reasoning. Pre-calculation of the expected size of the data structures per model seems to be unfeasible as this requires a second run over all model elements. - \item Process the \textbf{constraint base} iteratively and remove processed constraints directly after processing. This again requires a linked list as otherwise incremental resizing effects can affect the performance. In summary, building the constraint base and reasoning causes peak memory effects that are better from a performance point of view than (re-)allocating big array memory blocks. - \item Avoid having too many unneeded \textbf{partitions of the constraint base} being stored during the translation in different lists, that are finally added to the constraint base. Try to directly add constraints where possible to the constraint base, e.g., for default constraints to avoid iterating over the complete constraint base before reasoning. However, due to the prioritization of the constraint types and their required sequence, this is not always possible. One alternative, a numeric prioritization of the individual constraints would require sorting the constraint base, at the new parts not the left-over constraints to be re-evaluated from a previous reasoning steps. However, implicit sorting on insertion according to priorities could help here. - \item Create/translate a \textbf{constraint in one step}, if required in compounds split into filling the variability mapping and then creating the constraints based on the actual mapping. - \item Try to figure out whether a certain \textbf{constraint (type) is actually needed} for reasoning and avoid its translation/creation wherever feasible. \TBD{Can we move the decision about keeping a constraint from adding it to the constraint base before constraint creation. However, this requires changes/additional alternatives for different code parts.}. Thus, don't re-process or filter certain constraint types at the end (done in the initial version for default and derived type constraints), as this implies iterating multiple times over the (partial) constraint base and re-creating/throwing away constraint instances in memory. - \item \TBD{Avoid storing constraints that can be \textbf{processed immediately}, e.g., default constraints without dependencies. However, if a default constraint fails, it must be added to the constraint basis for later possible re-evaluation if dependent values become available/right.} - \item For identifying whether constraints are already in the constraint base, use a \textbf{fast look-up structure} instead of an iteration over the constraint base. Although the initial implementation utilized here reference equality (faster than the equals method), the current lookup structure is significantly faster (approx. 600 ms on large models, at that time around 25\% of runtime) than the original approach trading off execution speed for (peek) memory. Here a lookup structure based on reference equality could further speed up reasoning, which, however, may in the end be slower than the built in collections due to JIT compilation and JVM optimization effects. This is even true for the stack-based variable mapping $\variableMapping$, which performs as fast as a flat map, which may roughly serve for the main purpose of $\variableMapping$, but not for composing complex constraints from nested compunds and containers. - \item Incremental reasoning using a \textbf{stored constraint base} may speed up reasoning but only achieves this through large memory allocations. Ensure initializing the model through default constraints so that the actual stored constraint base only contains really needed constraint types, i.e., no default constraints and, if possible, no constraints for which all depending variables are already frozen. - \item \textbf{Reuse visitor instances} if applied more than once, in particular reasoners with more complex internal data structures such as maps or lists. This required some refactoring of the IVML model implementation. - \item \textbf{Avoid temporary instances}, e.g., iterators, temporary constraint creation, temporary data structures wherever possible. One option replacing a collection structure is to define a functor for processing the elements and to create a reusable instance of that functor. If permitted by the Java environment settings (EASy often compiles against JDK 1.6), also a lambda-function instead of a heavy-weight functor class may be appropriated. - \item \textbf{Avoid multipe variable substitutions} per constraint expressions, i.e., join variable substitutions wherever possible. Variable substitution copies the expression. Multiple copies throws away the last copied expression. - \item \textbf{Use instance pooling} if datastructures are temporarily used, e.g., variable accessors in expression evaluation or sets of compounds in reasoning (20-30 ms on larger models, at that time around 10\% of runtime). -\end{itemize} - -There are still opportunities for further speeding up the reasoning operations. On an Intel core i7, the reasoner reaches around 15-43 constraint evaluations in average per millisecond - runtime vs. full reasoning on the latest QualiMasster test model, currently reasoning time includes translation and evaluation time \TBD{Sepearte timing}. This is already an improvement over the initial version, which operated at around 10 evaluations per millisecond in average (also with a higher number of constraint evaluations due to unneeded and uneffective constraints). The constraint evaluation time probably suffers from the immutable structured values in EASy-Producer, which are created for each assignment. Knowing that most of the assignments in this model are done for basic IVML datatypes, a fast track for setting integer, double, boolean and String values could increase the number of evaluations, but requires careful extension, as changing values shall only be allowed via decision variables, which take care of the current assignment state, e.g., \IVML{FROZEN}. - -\section{Evaluation}\label{sectEvaluation} - -\TBD{Keep or remove that section. However, some basic performance evaluations should not be so difficult. All executions need multiple runs, in particular to even out JIT compilation. It seems that this is done during/after the second reasoning run. Potential topics: - -\begin{itemize} - \item Artificial models of some size/variable/constraint ratio. Christian had a generator for that and Roman typically did some evaluations using these models. Compare to known results where available. - \item QualiMaster full, incremental, runtime reasoning (full, no defaults, no frozen, reuse constraint base). Runtime vs. full reasoning seems to behave rather linearly, at around 23 constraints evaluated per ms. Compare to known results where available. - \item All test cases involving reasoning as an overview map. -\end{itemize} - -} - -%----------------------------------------------------------------------------------------------------------------- - -\section{Conclusion}\label{sectConclusion} - -\TBD{We are better than before, we are now more IVML-complete, but not reasoning-complete. Future, integrate with SMT or other solvers for left-over reasoning problems or configuration completion/instance creation (potential student work).} - -%----------------------------------------------------------------------------------------------------------------- - -\section*{Acknowledgements} - -We are grateful to Phani Saripalli for implementing the initial IVML reasoner based on the Jess rules engine. We are also grateful to Roman Sizonenko for implementing and experimenting with the Drools-based IVML reasoner and for realizing the initial SSE IVML reasoner used as basis for the actual version of the reasoner and this documentation. - -\bibliographystyle{abbrv} -\bibliography{reasoner} +\end{appendices} \end{document}