Mneson announcement and help request

Mneson announcement and help request

[Marius Amado Alves]

Mneson is a developing 100% Ada database system. Latest version 20040601.

   http://www.liacc.up.pt/~maa/mneson

The core seems well, but there's a problem in an auxiliary module that I'm
having difficulty analysing due to an aparent gprof bug. So I appreciate the
help of anyone interested in making Ada the next generation database
technology :-)

An excerpt from "revision_history.txt" follows. Please contact me on any
issue. Thanks a lot.

*******************************
Annex 2. Problem with Get_Value
*******************************

Mneson.Structures.Get_Value shows a miserable absolute time performance
of circa 50 ms. See Mneson.Test.Run2 and others.

I try to analyse this problem with gprof, but it seems gprof is buggy:
the call graph includes functions that are never called!
So I suspect that gprof is confusing function names and leading me astray.

However gprof consistently puts AI302 (old version) internal functions
high up on the flat file.
Tree functions get called tens of millions of times.
So maybe this is a problem with AI302.
A possible course of action is therefore to sycn Mneson with
the new version of AI302 (now) or with Ada.Containers (in 2005).

*** Thanks a lot to anyone willing to help here. ***

I'm not experienced with gprof.

2004-06-01
--MAA

Re: Mneson announcement and help request

[Jeff C,]

"Marius Amado Alves" <amado.alves@netcabo.pt> wrote in message
news:mailman.28.1086105372.391.comp.lang.ada@ada-france.org...
> Mneson is a developing 100% Ada database system. Latest version 20040601.
>
>    http://www.liacc.up.pt/~maa/mneson
>
> The core seems well, but there's a problem in an auxiliary module that I'm
> having difficulty analysing due to an aparent gprof bug. So I appreciate
the
> help of anyone interested in making Ada the next generation database
> technology :-)
>


I know conventional wisdom is that one should not Optimize without
profiling....But since don't even
understand your program structure I would need to take more time to
understand its flow before
understanding the profile data.

So...At the risk of making suggestions that may not apply to speed I'll make
one that applies to style.

In general, I hate to see code that uses exceptions for normal control flow
processing. It certainly appears to
me that your code that makes use of the various For_Each_XXX type procedures
uses an exception
raise to terminate the search when "done".

This is not really desireable from a style point of view and also can
generally be a performance hit.
On compilers that implement zero-cost-exceptions of some sort, the "cost" is
high (or higher) on each
exception occurance.

On compilers that do not implement it, the presence of an exception handler
causes some overhead.

While this is generally small, having this in a traversal search really can
add up over time. In your case, in places like Get_Element and Get_Instance
a "normal" call involves a double exception throw.

In these cases it looks like you wrote your own traverse type procedures and
you want to terminate
the traverse "early" . .. For any container I ever created a Traverse for I
typically provide a pattern like

generic
    with Procedure Process_Element(The_Element : in out Element_Type;
                                                        Terminate_Traverse :
in out Boolean);
procedure Traverse(Container : in Container_Type);


Where the generic body of Traverse checks the Terminate_Traverse out
parameter of Process_Element each
time to see if it should prematurely stop traverse.

Clients need to write Process_Element so it explicitly sets
Terminate_Traverse to true if they want to
stop.  Traverse sets it false before "looping" and checks it after each call
to Process_Element.

In any case, it is not a perfect solution but it avoids the kludges of
multiple exceptions for non-error
based processing.

Again, this may or may not help your performance issue....but it would help
the overall program style IMHO.

Others may not agree with me. Perhaps there is a feeling that using
exceptions for this type of processing
is acceptable and that I am being too ivory tower.......your call.

Re: Mneson announcement and help request

[Marius Amado Alves]

> In general, I hate to see code that uses exceptions for normal control flow
> processing. It certainly appears to
> me that your code that makes use of the various For_Each_XXX type procedures
> uses an exception
> raise to terminate the search when "done".

Yes, that is a controversial style. Some like it, some don't. Note the 
planned Ada standard containers are in this style. If it is found to be 
a performance hitter in Mneson I'll say change it. But my experiments so 
far have shown no speed loss from there. At least with GNAT. I'm more 
inclined to earn speed with inlining. But to do that properly reliable 
profiling is also required.

> On compilers that implement zero-cost-exceptions of some sort, the "cost" is
> high (or higher) on each
> exception occurance.
> 
> On compilers that do not implement it, the presence of an exception handler
> causes some overhead.

So that's how they do it :-)
Yes, we'll have to analyse the algorithms in view of this.

I'll be delighted to answer any questions on Mneson design, here or 
privately. I'll also try to improve the documentation soon, including 
design items.

Re: Mneson announcement and help request

[Georg Bauhaus]

Marius Amado Alves <amado.alves@netcabo.pt> wrote:
:> In general, I hate to see code that uses exceptions for normal control flow
:> processing. It certainly appears to
:> me that your code that makes use of the various For_Each_XXX type procedures
:> uses an exception
:> raise to terminate the search when "done".
: 
: Yes, that is a controversial style. Some like it, some don't. Note the 
: planned Ada standard containers are in this style.

How about this, which doesn't need exceptions:

with AI302.Containers.Ordered_Sets;

package Maa is

   type T is range -5 .. +5;

   package Sets_of_T is new AI302.Containers.Ordered_Sets(T);

   generic
      with procedure Process(Pointee: Sets_of_T.Cursor);
   procedure Traverse
     (container: Sets_of_T.Set; Stop: Sets_of_T.Cursor);


end Maa;

package body Maa is

   procedure Traverse
     (container: Sets_of_T.Set; Stop: Sets_of_T.Cursor)
   is
      use Sets_of_T;

      current: Cursor := first(container);
   begin
      while current /= Stop loop
         process(current);
      end loop;
   end Traverse;

end Maa;

Re: Mneson announcement and help request

[Marius Amado Alves]

Yes, this is a nice idiom. I tried to push something similar to the
Ada.Containers. More general. See the ARG discussion. Look for "Slice".
In time Mneson could grow it's one containers, featuring this. However
until hard evidence that exceptions are evil I don't see a strong reason
to change.

Georg Bauhaus wrote:
> Marius Amado Alves <amado.alves@netcabo.pt> wrote:
> :> In general, I hate to see code that uses exceptions for normal control flow
> :> processing. It certainly appears to
> :> me that your code that makes use of the various For_Each_XXX type procedures
> :> uses an exception
> :> raise to terminate the search when "done".
> : 
> : Yes, that is a controversial style. Some like it, some don't. Note the 
> : planned Ada standard containers are in this style.
> 
> How about this, which doesn't need exceptions:
> 
> with AI302.Containers.Ordered_Sets;
> 
> package Maa is
> 
>    type T is range -5 .. +5;
> 
>    package Sets_of_T is new AI302.Containers.Ordered_Sets(T);
> 
>    generic
>       with procedure Process(Pointee: Sets_of_T.Cursor);
>    procedure Traverse
>      (container: Sets_of_T.Set; Stop: Sets_of_T.Cursor);
> 
> 
> end Maa;
> 
> package body Maa is
> 
>    procedure Traverse
>      (container: Sets_of_T.Set; Stop: Sets_of_T.Cursor)
>    is
>       use Sets_of_T;
> 
>       current: Cursor := first(container);
>    begin
>       while current /= Stop loop
>          process(current);
>       end loop;
>    end Traverse;
> 
> end Maa;
> 
> _______________________________________________
> comp.lang.ada mailing list
> comp.lang.ada@ada-france.org
> http://www.ada-france.org/mailman/listinfo/comp.lang.ada
> 

Re: Mneson announcement and help request

[Marius Amado Alves]

Ok, so the secret formula is:

   cost(exception check) < cost(condition check) < cost(raising)

And of course which idiom is best for algorithm A depends on the nature 
and casuistics of A. Finding the critical algorithms and determining 
these properties for each one is the hard work now.

In the ASCLWG discussion I didn't intend to demonstrate past the case at 
hand then, namely the first two costs above. Maybe I was blissfully 
ignorant of the third.

Now I'll have one more hint next time I find some Mneson function slow.

Thanks for the byte :-)

Re: Mneson announcement and help request

[Martin Dowie]

"Marius Amado Alves" <amado.alves@netcabo.pt> wrote in message
news:mailman.37.1086198453.391.comp.lang.ada@ada-france.org...
> Ok, so the secret formula is:
>
>    cost(exception check) < cost(condition check) < cost(raising)

Quite possibly

"much <" cost(raising)

There might even be times when

    cost(exception check) = cost(condition check)

or


    cost(exception check) > cost(condition check)

> And of course which idiom is best for algorithm A depends on the nature
> and casuistics of A. Finding the critical algorithms and determining
> these properties for each one is the hard work now.

Absolutely but for some systems it might just be worth doing (particularly
hard real-time systems).

> In the ASCLWG discussion I didn't intend to demonstrate past the case at
> hand then, namely the first two costs above. Maybe I was blissfully
> ignorant of the third.
>
> Now I'll have one more hint next time I find some Mneson function slow.
>
> Thanks for the byte :-)

Your welcome! :-)

Cheers

-- Martin

Re: Mneson announcement and help request

[Randy Brukardt]

"Martin Dowie" <martin.dowie@btopenworld.com> wrote in message
news:c9l0vo$pq3$1@sparta.btinternet.com...
...
> If you look at the assembler for the nested instansiation that you found
slow, you will see lots
>of system calls to sort out stack. If you look at assembler for exception
raising and handling,
>you'll see similar calls to save the occurance, reraise an exception,
whatever. Try stepping
>through the GNAT exception mechanism (in particular a-except.adb) - still
look fast
>compared to a check for an End_Of_File?

Well, yes, because End_of_File for Text_IO is very expensive (it has to do
lookahead of as many as two characters, and doing so makes later Gets
expensive as well). But "End_of_File" (or indeed any function call) misses
the point.

Indeed, the issue is the number of raises (in all compilers) and the number
of handlers (in most compilers). The number of these should be relatively
small, because compilers don't (usually can't) make this fast. In
particular, you should never raise and handle an exception in a (tight)
loop. (Our style guide strongly discourages exception handlers in loops.)
But calling expensive functions is no help!

                      Randy.

Re: Mneson announcement and help request

[Martin Dowie]

"Randy Brukardt" <randy@rrsoftware.com> wrote in message
news:xK-dnZHKcKOszSPdRVn-ug@megapath.net...
> Well, yes, because End_of_File for Text_IO is very expensive (it has to do
> lookahead of as many as two characters, and doing so makes later Gets
> expensive as well). But "End_of_File" (or indeed any function call) misses
> the point.

My point was that EOF is relatively cheap compared to raising the exception
not that it is cheap per se. And if GNAT and ObjectAda (the 2 compilers I
have any source for) are typical of most implementations then this is
certainly
true. OA even includes lots of local instantiations of the sort that MAA was
finding very slow (assuming OA is also "slow" in this regard).

Cheers

-- Martin

Re: Mneson announcement and help request

[Randy Brukardt]

"Martin Dowie" <martin.dowie@btopenworld.com> wrote in message
news:c9melj$fg6$1@sparta.btinternet.com...
> "Randy Brukardt" <randy@rrsoftware.com> wrote in message
> news:xK-dnZHKcKOszSPdRVn-ug@megapath.net...
> > Well, yes, because End_of_File for Text_IO is very expensive (it has to
do
> > lookahead of as many as two characters, and doing so makes later Gets
> > expensive as well). But "End_of_File" (or indeed any function call)
misses
> > the point.
>
> My point was that EOF is relatively cheap compared to raising the
exception
> not that it is cheap per se. And if GNAT and ObjectAda (the 2 compilers I
> have any source for) are typical of most implementations then this is
certainly
> true. OA even includes lots of local instantiations of the sort that MAA
was
> finding very slow (assuming OA is also "slow" in this regard).

My point was that as long as you keep the exception handler and raising out
of the loop (which is certainly true for EOF), it can be quite efficient. In
the normal case (where you read many characters before reaching the end of
the file), it's almost always better to handle the exception. That's because
one exception raise/handling pair is a lot cheaper than 10,000 function
calls, especially one as expensive as EOF. (And EOF is more expensive than
exception handling on Janus/Ada if it has to read lookahead, because system
calls always are more expensive than code that doesn't require system calls,
like exception handling. And I'd expect that to be true on most compilers,
as that is more of a function of the OS, not really of the compiler).

Now, the code you originally described (which did the exception raise and
handing inside the loop) would be awful on any compiler. But replacing it
with an expensive function (essentially any that aren't inlined) is not
going to be much help.

                        Randy.

Re: Mneson announcement and help request

[Martin Dowie]

"Randy Brukardt" <randy@rrsoftware.com> wrote in message
news:-NSdneXjh7wndyLdRVn-vw@megapath.net...
> My point was that as long as you keep the exception handler and raising
out
> of the loop (which is certainly true for EOF), it can be quite efficient.
In
> the normal case (where you read many characters before reaching the end of
> the file), it's almost always better to handle the exception. That's
because
> one exception raise/handling pair is a lot cheaper than 10,000 function
> calls, especially one as expensive as EOF.

I think we're in 'violent agreement' :-)

Re: Mneson announcement and help request

[Jean-Pierre Rosen]

> "Randy Brukardt" <randy@rrsoftware.com> wrote in message
> news:-NSdneXjh7wndyLdRVn-vw@megapath.net...
> > My point was that as long as you keep the exception handler and raising
> out
> > of the loop (which is certainly true for EOF), it can be quite efficient.
> In
> > the normal case (where you read many characters before reaching the end of
> > the file), it's almost always better to handle the exception. That's
> because
> > one exception raise/handling pair is a lot cheaper than 10,000 function
> > calls, especially one as expensive as EOF.

I always use the exception mechanism for another reason:
In the presence of a "malformed" file (i.e. one where the last line has no line terminator before EOF), you may have an unexpected
End_Error even if End_Of_File was false. Of course, this is outside Ada semantics, but it's the real world that text files are
sometimes being typed by human beings....

So, in short:
1) when you do a Get, it will have to (more or less) check EoF anyway
2) if you check EoF, you must still be prepared to catch End_Error anyway

=> I never check EoF any more.

-- 
---------------------------------------------------------
           J-P. Rosen (rosen@adalog.fr)
Visit Adalog's web site at http://www.adalog.fr

Re: Mneson announcement and help request

[Larry Kilgallen]

In article <2f8p9c.0p5.ln@skymaster>, "Jean-Pierre Rosen" <rosen@adalog.fr> writes:
> 
>> "Randy Brukardt" <randy@rrsoftware.com> wrote in message
>> news:-NSdneXjh7wndyLdRVn-vw@megapath.net...
>> > My point was that as long as you keep the exception handler and raising
>> out
>> > of the loop (which is certainly true for EOF), it can be quite efficient.
>> In
>> > the normal case (where you read many characters before reaching the end of
>> > the file), it's almost always better to handle the exception. That's
>> because
>> > one exception raise/handling pair is a lot cheaper than 10,000 function
>> > calls, especially one as expensive as EOF.
> 
> I always use the exception mechanism for another reason:
> In the presence of a "malformed" file (i.e. one where the last line has no line terminator before EOF), you may have an unexpected
> End_Error even if End_Of_File was false. Of course, this is outside Ada semantics, but it's the real world that text files are
> sometimes being typed by human beings....

That seems to be restricted to operating systems where the file system
does not handle record semantics.

Re: Mneson announcement and help request

[Jeffrey Carter]

Martin Dowie wrote:

> Standard idiom:                         MAA Idiom:
> 
> while not End_Of_File (Current_Input)   begin
> loop                                       loop
>    Get_Immediate (C);                         Get_Immediate (C);
> end loop;                                  end loop;
>                                         exception
>                                            when End_Error =>
>                                               null;  -- End of file
>                                         end;

The standard idiom should be

loop
    exit when End_Of_File (Current_Input);

    Get_Immediate (C);
end loop;

which eliminates the calls to "not". In addition, it uses positive 
logic, rather than the negative logic required by while, which is easier 
to read and understand.

-- 
Jeff Carter
"You couldn't catch clap in a brothel, silly English K...niggets."
Monty Python & the Holy Grail
19

Re: Mneson announcement and help request

[Martin Dowie]

"Jeffrey Carter" <spam@spam.com> wrote in message
news:Xyxvc.19956$Tn6.3068@newsread1.news.pas.earthlink.net...
> The standard idiom should be
>
> loop
>     exit when End_Of_File (Current_Input);
>
>     Get_Immediate (C);
> end loop;
>
> which eliminates the calls to "not". In addition, it uses positive
> logic, rather than the negative logic required by while, which is easier
> to read and understand.

Well, the "not" is a red herring really as it is just one of two inverse
assembler instructions really.

And my JSP background has always insisted on "while not <exit condition>"
:-)

Re: Mneson announcement and help request

[Martin Krischik]

Jeffrey Carter wrote:

> Martin Dowie wrote:
> 
>> Standard idiom:                         MAA Idiom:
>> 
>> while not End_Of_File (Current_Input)   begin
>> loop                                       loop
>>    Get_Immediate (C);                         Get_Immediate (C);
>> end loop;                                  end loop;
>>                                         exception
>>                                            when End_Error =>
>>                                               null;  -- End of file
>>                                         end;
> 
> The standard idiom should be
> 
> loop
>     exit when End_Of_File (Current_Input);
> 
>     Get_Immediate (C);
> end loop;
> 
> which eliminates the calls to "not". In addition, it uses positive
> logic, rather than the negative logic required by while, which is easier
> to read and understand.

I once tried a "loop optimization" with MS-C 6.00. Tried various options and
looked at the assembler output. Guess what: "do while", "while" and "for"
all redered the very same result in assembler.

Starting with:

loop
  Instructions_1;

   exit when Condition;

   Instructions_2;
end loop;

or alternative:

Instructions_1;

while not Condition loop
   Instructions_2;
   Instructions_1;
end loop;

I got something like this:

goto center;

loop
   Instructions_2;
 
<<center>>

   Instructions_1;

while not Condition;

Disclaimers:

1) I know that Ada does not allow a goto into a loop;
2) I know that Ada does not have a while at the and of a loop. 

I never ever tried to optimize a loop again. I just write it down so I can
read it nicely.

On a side note: At the same time I also made a "if case" optimization. There
where several small groups with large holes in between. Again no matter if
I used "if" or "case" the asembler result was the same: A binary tree
search for the holes and jump tables for the groups.

And that was MSC-6 more then 10 year ago.

With Regards

Martin
-- 
mailto://krischik@users.sourceforge.net
http://www.ada.krischik.com

Re: Mneson announcement and help request

[Georg Bauhaus]

Georg Bauhaus <sb463ba@l1-hrz.uni-duisburg.de> wrote:
: Marius Amado Alves <amado.alves@netcabo.pt> wrote:
: :> In general, I hate to see code that uses exceptions for normal control flow
: :> processing. It certainly appears to
: :> me that your code that makes use of the various For_Each_XXX type procedures
: :> uses an exception
: :> raise to terminate the search when "done".
: : 
: : Yes, that is a controversial style. Some like it, some don't. Note the 
: : planned Ada standard containers are in this style.
: 
: How about this, which doesn't need exceptions:

[...]
OK in my example you need to know where to stop before traversal.
However, there is a third variation, only slightly different from
the one Jeffrey Carter mentioned, and it still doesn't need
exceptions with AI302.

   generic
      with procedure Process(Pointee: Sets_of_T.Cursor);
      with function Stop(Pointee: Sets_of_T.Cursor) return Boolean;
      --  terminate Process-ing when Stop says so

   procedure Traverse (container: Sets_of_T.Set);

The loop is changed to

      while not Stop(current) loop  -- the change
         process(current);
	 next(current);  -- moving the cursor was missing before :-(
      end loop;


-- Georg

Re: Mneson announcement and help request

[Marius Amado Alves]

>    generic
>       with procedure Process(Pointee: Sets_of_T.Cursor);
>       with function Stop(Pointee: Sets_of_T.Cursor) return Boolean;
>    procedure Traverse (container: Sets_of_T.Set);

Nice.

Incidently, I've found out that local instantiations are (intriguingly) 
slow. I've found this out chasing the slowness problem in Mneson 
20040601, solved in 20040602--in part or in full (not researched) by 
eliminating instantiations. I have not played with inline pragmas nor 
compiler optimization options.

BTW, regarding Mneson development, my priorities are optimizing Base and 
Calculus, and improving documentation. Not refactoring into an 
exceptionless idiom. Unless that shows significant speed gains. Feel 
free to do that, but if you really want to help, mind the overall 
priorities. We could have a fully validated system by 2005, to go with 
the new Ada. BTW, note that some tricks are admitedly temporary, in 
expectation of Ada 2005, notable the use of 'Unrestricted_Access for 
callbacks.

Thanks.

Re: Mneson announcement and help request

[Jeffrey Carter]

Georg Bauhaus wrote:
> [...]
> OK in my example you need to know where to stop before traversal.
> However, there is a third variation, only slightly different from
> the one Jeffrey Carter mentioned, and it still doesn't need
> exceptions with AI302.

I haven't posted on this topic. If you're referring to the posting by 
"Jeff C" (jcreem@yahoo.com), that's not me.

-- 
Jeff Carter
"You couldn't catch clap in a brothel, silly English K...niggets."
Monty Python & the Holy Grail
19

Re: Mneson announcement and help request

[Georg Bauhaus]

Jeffrey Carter <spam@spam.com> wrote:
 
: I haven't posted on this topic. If you're referring to the posting by 
: "Jeff C" (jcreem@yahoo.com), that's not me.

I'm sorry.


(I should have been more careful, maybe I associated something with 
PramARC,

   generic -- Iterate
      with procedure Action (Item : in out Element; Continue : out Boolean);
   procedure Iterate (List : in out Skip_List);--)


-- Georg

Re: Mneson announcement and help request

[Marius Amado Alves]

> I know conventional wisdom is that one should not Optimize without
> profiling....But since don't even
> understand your program structure I would need to take more time to
> understand its flow before
> understanding the profile data...

*** Thanks a lot for taking the time to examine Mneson. ***

As I just said I'll try to make a design document.

I'd really love to have a reliable profiling tool--or team partner ;-)

Re: Mneson announcement and help request

[Jacob Sparre Andersen]

Marius Amado Alves wrote:

> I'd really love to have a reliable profiling tool--or team partner
> ;-)

Have you tried `gprof`?  Reliable may be a strong word about it, but
it has definitely helped me find some horrible (and not very
intuitive) inefficiencies in some of my code.

Jacob
-- 
"Science is like sex: sometimes something useful comes out,
 but that is not the reason we are doing it"
                                          -- Richard Feynman

Re: Mneson announcement and help request

[Marius Amado Alves]

> Have you tried `gprof`?  Reliable may be a strong word about it...

Strong word indeed. I tried Gprof, and it listed (with non-null values) 
functions that were never called! But yes it can be helpful even so.