'others' - inefficient esp. DEC Ada? [1/1]

'others' - inefficient esp. DEC Ada? [1/1]

[Rob Kirkbride]

I am involved in a project using DEC Ada under Unix OSF1. We are at a
stage in the project now where we are improving performance, reducing
memory requirements etc.

While doing this study I was staggered to find that the 'others'
construct when used to clear an error eg.
My_Array := (others => Null_Element) can be 3-4 times SLOWER than
using a loop eg.

for My_Element in My_Array'range loop
        My_Array (My_Element) := Null_Element;
end loop;

This is because using the 'others' the array is built up in another part
of memory before being copied back to My_Array, apparently because
Null_Element could be a function and it may raise a constraint error.

Apart from the performance this also costs in memory as if this is done
in a task, the stack size of the task could have to be doubled to cope.
In one task this causes us to add 3Mb to the task size!

Obviously the others can be replaced with the loop but as we have over
6000 of them this could be quite expensive! We have asked DEC and they
admitted it was "poor optimisation". We would obviously like them to
improve this situation.

Does anyone know of a compiler that does this efficiently?

Anyone starting to write their coding standards I would seriously look
at this issue as you may find it will cause you to lose some performance
and memory (it has us)

I have attached a small test program to illustrate this point.

[ Section: 1/1 File: check_si.a Encoder: Turnpike Version 3.03 ]

begin 644 check_si.a
<encoded_portion_removed>
end

sum -r/size 19077/4149 section (from "begin" to "end")
sum -r/size 62565/2989 entire input file

-- 
Rob Kirkbride

Re: 'others' - inefficient esp. DEC Ada? [1/1]

[Tom Moran]

Testing your sample with two Ada 95 compilers on a Pentium 60, one of
them takes roughly twice as long for the "others" as for the loop and
the other compiler takes the same time either way (and looking at the
generated code, it's pretty nearly the same loop in both cases).  
  Why does copying 160*354 =56,640 bytes need a 3MB task stack?
  On my P60 a single copy takes a couple of milliseconds.  If your
program performs such large copies so often that the time matters,
perhaps this should be viewed as  a golden opportunity to recode such
foolishness.
  It certainly would be nice if each compiler came with a crib sheet
showing what it does especially well or poorly, instead of each
programmer having to discover for himself (usually painfully).  Does
the standard Ada benchmark suite (whose name escapes me at the moment)
include an others/loop timing test?

Re: 'others' - inefficient esp. DEC Ada? [1/1]

[Michael & Amy Hartsough]

Tom Moran wrote:

>   It certainly would be nice if each compiler came with a crib sheet
> showing what it does especially well or poorly, instead of each
> programmer having to discover for himself (usually painfully).

Yes, one Ada compiler I've used generated 30-40 instructions at
the beginning of every case statement (my guess was this was to
create a "jump table"). So we examined all case statements in the
program and converted those with only two or three selectors to
if statements.

	Michael

Re: 'others' - inefficient esp. DEC Ada? [1/1]

[Rob Kirkbride]

In article <344168c5.21239761@SantaClara01.news.InterNex.Net>, Tom Moran
<tmoran@bix.com> writes
>Testing your sample with two Ada 95 compilers on a Pentium 60, one of
>them takes roughly twice as long for the "others" as for the loop and
>the other compiler takes the same time either way (and looking at the
>generated code, it's pretty nearly the same loop in both cases).  
>  Why does copying 160*354 =56,640 bytes need a 3MB task stack?
>  On my P60 a single copy takes a couple of milliseconds.  If your
>program performs such large copies so often that the time matters,
>perhaps this should be viewed as  a golden opportunity to recode such
>foolishness.
>  It certainly would be nice if each compiler came with a crib sheet
>showing what it does especially well or poorly, instead of each
>programmer having to discover for himself (usually painfully).  Does
>the standard Ada benchmark suite (whose name escapes me at the moment)
>include an others/loop timing test?

Sorry I had cut down Active_Errors_List_Range_Type from 160 to 7920!
You may need to retry to get more representative figures.

The clear is only actually done once (in this particular example).
However, even once will still require the stack to be large which is why
it is worse.

The smaller ones will be having a less if still noticeable affect on
performance.

Having found this issue with the 'others' construct, I tend to agree
with you about a benchmark program, I guess it would difficult to
implement, but with all the pipelining and optimisation that can be done
these days on processors I think it should become an issue.

Rob
-- 
Rob Kirkbride

Re: 'others' - inefficient esp. DEC Ada? [1/1]

[Jeff Creem]

In article <+3g7rFB7dIQ0EwNI@RK-COMP.DEMON.CO.UK>, Rob Kirkbride
<rob@rk-comp.demon.co.uk> wrote:

>
>This is because using the 'others' the array is built up in another part
>of memory before being copied back to My_Array, apparently because
>Null_Element could be a function and it may raise a constraint error.
>
>Apart from the performance this also costs in memory as if this is done
>in a task, the stack size of the task could have to be doubled to cope.
>In one task this causes us to add 3Mb to the task size!
>

Note that most comopilers I have seen do the same thing with any
sort of aggregate assignment (that is a copy is built on the stack and
then the structure is copied back to the final destination).

This has lead to us not using aggregate assignment as much as I would 
like since we often can't take the hit in either stack size or processing time.

There will be some who say that this matters less as processors get faster
(people have been saying that since ...forever) but I can tell you that this
will continue to cause aggregate to be used less than I'd like for a very
long time.

Jeff

Re: 'others' - inefficient esp. DEC Ada? [1/1]

[Matthew Heaney]

In article <+3g7rFB7dIQ0EwNI@RK-COMP.DEMON.CO.UK>, Rob Kirkbride
<rob@rk-comp.demon.co.uk> wrote:


>While doing this study I was staggered to find that the 'others'
>construct when used to clear an error eg.
>My_Array := (others => Null_Element) can be 3-4 times SLOWER than
>using a loop eg.
>
>for My_Element in My_Array'range loop
>        My_Array (My_Element) := Null_Element;
>end loop;
>
>This is because using the 'others' the array is built up in another part
>of memory before being copied back to My_Array, apparently because
>Null_Element could be a function and it may raise a constraint error.

You can't declare a constant prior to doing the assignment? ie

declare
   Value : constant T := Null_Element;
begin
   My_Array := (others => Value);
end;

I don't really know if it would make any difference though.  

Did you try getting rid of others, and using O'Range? ie

declare
   Value : constant T := Null_Element;
begin
   My_Array := (My_Array'Range => Value);
end;

What about the array itself? Is it a static subtype?  Do you know up front
what the index constraint is?  ie

declare
   Value : constant T := Null_Element;
begin
   My_Array := (My_Array_Index_Subtype'Range => Value);
end;

Maybe if the array index subtype were static then the assignment would be
more efficient.

What's the performance constraint?  Is it the construction of the value of
the RHS, or is it the copy itself?  Perhaps you can build the value once,
and then copy it:

   Null_Element_Array : constant My_Array := (others => Null_Element);
   -- In a static scope...

...

   My_Array := Null_Element_Array;
   -- In a dynamic scope...

At least this would get rid of the overhead of the construction of the
value, as you do the construction once and keep reusing it.  You could even
put it on the heap if the Null_Element_Array length can change, and keep
reusing it until its length changes again.

These are all just wild guesses though.  Sometimes you just have to play
the lottery, eh?  Maybe you'll get lucky.

--------------------------------------------------------------------
Matthew Heaney
Software Development Consultant
<mailto:matthew_heaney@acm.org>
(818) 985-1271