Home » Modeling » OCL » OCL N^2 Performance
| OCL N^2 Performance [message #18958] |
Thu, 19 April 2007 15:23  |
Eclipse User |
|
|
|
Originally posted by: irbull.cs.uvic.ca
Every since I taught first year CS I look at performance of simple
algorithms in a whole new light :) . I was just looking through the
OCL spec, and I noticed that nested loops are often used for simple
operations (things like isUnique). I wonder if this is the best
approach (since you can sort by the value, and then check in linear time
if there are any duplicates = O(N log N)). Even routines like sortedBy
are specified as selection sort, an N2 algorithm.
I was wondering what people's thoughts are on this? Do people worry
about performance when writing OCL, or is it better to write an elegant
(easy to understand) constraint and worry about implementation details
(as well as performance) later?
Cheers,
ian
|
|
|
| Re: OCL N^2 Performance [message #19006 is a reply to message #18958] |
Thu, 19 April 2007 17:35  |
| Eclipse User |
|
|
|
Originally posted by: cdamus.ca.ibm.com
Hi, Ian,
My take tends towards the latter. OCL is clearly intended to be a
specification (pseudo-declarative) language rather than a programming
language. It is, actually, more or less functionally complete, but I think
that helps more in making it intuitive and easy to use than a practical
implementation language.
It's scary how even the simplest of English statements is very difficult to
formulate as efficient-looking OCL. But, it doesn't matter, because what
you really want to do with OCL (if constraints are to be manifest in the
run-time system) is to transform them to an appropriate programming
language in your system and apply these algorithmic mappings at that stage.
Even so, particular applications or domains may be able to make simplifying
assumptions that allow for even more efficient implementation of
constraints.
Of course, having said that, interpreted OCL is always nice for scratchpad
work and debugging. Anything that can be done to make that more efficient
is welcome, anyway :-)
Cheers,
Christian
Ian Bull wrote:
> Every since I taught first year CS I look at performance of simple
> algorithms in a whole new light :) . I was just looking through the
> OCL spec, and I noticed that nested loops are often used for simple
> operations (things like isUnique). I wonder if this is the best
> approach (since you can sort by the value, and then check in linear time
> if there are any duplicates = O(N log N)). Even routines like sortedBy
> are specified as selection sort, an N2 algorithm.
>
> I was wondering what people's thoughts are on this? Do people worry
> about performance when writing OCL, or is it better to write an elegant
> (easy to understand) constraint and worry about implementation details
> (as well as performance) later?
>
> Cheers,
> ian
|
|
|
| Re: OCL N^2 Performance [message #19275 is a reply to message #19006] |
Thu, 19 April 2007 20:54 |
| Eclipse User |
|
|
|
Originally posted by: carrasco.ModelDrivenDevelopment.co.uk
Chris, Ian,
I agree with Ian that the N^2 problem is preocupying:
Chris is right that mappings to implementation will (must) deal with this,
but IMO, by not paying attention,
one of these days (versions of the spec) we are going to find ourselves
with a really nasty case of complexity we can not really help.
But about mapping to implementation,
I have found that it is not really the processing of OCL logic
what may kill the machine (therefore interpretation works fine, even in
server side):
Heaviest penalty comes from Accessing Objects and Features:
it is very easy in OCL to write an expression
that will traverse a significant portion of your object domain.
If your "persistence" is not "in memory", or something like Gemstone,
(i.e. a relational database mapping)
chances are somebody will write an OCL
subexpression that will take forever.
"Christian W. Damus" <cdamus@ca.ibm.com> wrote in message
news:f08994$qid$1@build.eclipse.org...
>
> Hi, Ian,
>
> My take tends towards the latter. OCL is clearly intended to be a
> specification (pseudo-declarative) language rather than a programming
> language. It is, actually, more or less functionally complete, but I
> think
> that helps more in making it intuitive and easy to use than a practical
> implementation language.
>
> It's scary how even the simplest of English statements is very difficult
> to
> formulate as efficient-looking OCL. But, it doesn't matter, because what
> you really want to do with OCL (if constraints are to be manifest in the
> run-time system) is to transform them to an appropriate programming
> language in your system and apply these algorithmic mappings at that
> stage.
> Even so, particular applications or domains may be able to make
> simplifying
> assumptions that allow for even more efficient implementation of
> constraints.
>
> Of course, having said that, interpreted OCL is always nice for scratchpad
> work and debugging. Anything that can be done to make that more efficient
> is welcome, anyway :-)
>
> Cheers,
>
> Christian
>
>
> Ian Bull wrote:
>
>> Every since I taught first year CS I look at performance of simple
>> algorithms in a whole new light :) . I was just looking through the
>> OCL spec, and I noticed that nested loops are often used for simple
>> operations (things like isUnique). I wonder if this is the best
>> approach (since you can sort by the value, and then check in linear time
>> if there are any duplicates = O(N log N)). Even routines like sortedBy
>> are specified as selection sort, an N2 algorithm.
>>
>> I was wondering what people's thoughts are on this? Do people worry
>> about performance when writing OCL, or is it better to write an elegant
>> (easy to understand) constraint and worry about implementation details
>> (as well as performance) later?
>>
>> Cheers,
>> ian
>
|
|
|
| Re: OCL N^2 Performance [message #19330 is a reply to message #19275] |
Thu, 19 April 2007 21:02 |
| Eclipse User |
|
|
|
Originally posted by: cdamus.ca.ibm.com
Hi, Antonio,
Agreed. As in any coding or specification, one can be sloppy with OCL.
I have a hunch, too, that the majority of OCL expressions that perform well
when interpreted in the most obvious way will probably be easier to read
and understand, anyway. And that's even more of a good thing! :-)
Christian
Antonio Carrasco wrote:
> Chris, Ian,
>
> I agree with Ian that the N^2 problem is preocupying:
>
> Chris is right that mappings to implementation will (must) deal with this,
> but IMO, by not paying attention,
> one of these days (versions of the spec) we are going to find ourselves
> with a really nasty case of complexity we can not really help.
>
> But about mapping to implementation,
> I have found that it is not really the processing of OCL logic
> what may kill the machine (therefore interpretation works fine, even in
> server side):
> Heaviest penalty comes from Accessing Objects and Features:
> it is very easy in OCL to write an expression
> that will traverse a significant portion of your object domain.
>
> If your "persistence" is not "in memory", or something like Gemstone,
> (i.e. a relational database mapping)
> chances are somebody will write an OCL
> subexpression that will take forever.
<snip>
|
|
|
| Re: OCL N^2 Performance [message #24585 is a reply to message #19006] |
Thu, 24 May 2007 14:25 |
 Chris Lenz
Messages: 214
Registered: July 2009 |
Senior Member |
|
|
I have to questions on this:
Has anyone done a OCL Eclipse Performance measurement?
Is it possible to compile OCL statements?
I am just writing a paper comparing Eclipse ocl performance against a
prolog framework, are there some things I have to take into
consideration when measuring evaluation?
Thanx Chris
Christian W. Damus schrieb:
> Hi, Ian,
>
> My take tends towards the latter. OCL is clearly intended to be a
> specification (pseudo-declarative) language rather than a programming
> language. It is, actually, more or less functionally complete, but I think
> that helps more in making it intuitive and easy to use than a practical
> implementation language.
>
> It's scary how even the simplest of English statements is very difficult to
> formulate as efficient-looking OCL. But, it doesn't matter, because what
> you really want to do with OCL (if constraints are to be manifest in the
> run-time system) is to transform them to an appropriate programming
> language in your system and apply these algorithmic mappings at that stage.
> Even so, particular applications or domains may be able to make simplifying
> assumptions that allow for even more efficient implementation of
> constraints.
>
> Of course, having said that, interpreted OCL is always nice for scratchpad
> work and debugging. Anything that can be done to make that more efficient
> is welcome, anyway :-)
>
> Cheers,
>
> Christian
>
>
> Ian Bull wrote:
>
>> Every since I taught first year CS I look at performance of simple
>> algorithms in a whole new light :) . I was just looking through the
>> OCL spec, and I noticed that nested loops are often used for simple
>> operations (things like isUnique). I wonder if this is the best
>> approach (since you can sort by the value, and then check in linear time
>> if there are any duplicates = O(N log N)). Even routines like sortedBy
>> are specified as selection sort, an N2 algorithm.
>>
>> I was wondering what people's thoughts are on this? Do people worry
>> about performance when writing OCL, or is it better to write an elegant
>> (easy to understand) constraint and worry about implementation details
>> (as well as performance) later?
>>
>> Cheers,
>> ian
>
|
|
|
| Re: OCL N^2 Performance [message #24624 is a reply to message #24585] |
Thu, 24 May 2007 14:42 |
| Eclipse User |
|
|
|
Originally posted by: cdamus.ca.ibm.com
Hi, Chris,
To answer your questions:
> Has anyone done a OCL Eclipse Performance measurement?
None that I know of.
> Is it possible to compile OCL statements?
Do you mean, transform them to the implementation language of your model? I
expect that most simple constraints can be implemented with almost any OO
programming language. More advanced capabilities such as association-class
navigation and OclMessage may be more difficult. In Java, I can see the
AssociationClasses being mapped in various ways using common data
structures or just plain classes, and maybe AspectJ has some constructs
that would help to implement OclMessage ...
Performance of evaluation hasn't been a design goal of this OCL
implementation as much as performance of parsing.
I don't think there's anything in particular to account for in measuring the
performance of evaluation. The only really static components of evaluation
are the EvaluationVisitor and the collection implementations. Other
aspects of evaluation, such as the implementation of allInstances(),
operation calls, and property navigation are customizable by clients, so
performance may vary. Clients with special requirements can even implement
custom environments that make simplifying assumptions that improve
performance (such as disabling navigation of non-navigable properties).
Cheers,
Christian
Chris Lenz wrote:
> I have to questions on this:
> Has anyone done a OCL Eclipse Performance measurement?
> Is it possible to compile OCL statements?
>
> I am just writing a paper comparing Eclipse ocl performance against a
> prolog framework, are there some things I have to take into
> consideration when measuring evaluation?
>
> Thanx Chris
>
<snip>
|
|
|
Goto Forum:
Current Time: Thu Apr 18 23:11:53 GMT 2024
Powered by FUDForum. Page generated in 0.02639 seconds |
] 
Search
Help
Register
Login
Home
