Problem with optimizations

Problem with optimizations

[Olivier Scalbert]

Hello,

I have write a little program that try to solve Rubik's cube, just to 
practice a little Ada.
The program is really stupid (brute force) but I have a strange problem.
When I compile it with:
gnatmake -O2 rubukmain, it works:

Depth:  1  Positions Counter:                    12
Depth:  2  Positions Counter:                   132
Depth:  3  Positions Counter:                  1440
Depth:  4  Positions Counter:                 15720
Depth:  5  Positions Counter:                171600
Depth:  6  Positions Counter:               1873200
Depth:  7  Positions Counter:              20448000
Depth:  8
Solved !
           1         12          8         10          2          6 
      3          3  Positions Counter:              18104705

When I compile it with:
gnatmake -O3 rubukmain, it does not work:

Depth:  1  Positions Counter:                     1
Then it stops.

When, inside the Recursive_Find_Solution, I replace Is_Solved by 
Is_Solved1, then it works in all cases.

I have try to understand what is happen with gdb and by having a look 
into the generated code, but without success.

I have the same behaviour with:
- Ubuntu 8.10 32 bits (GNATMAKE 4.3.2)
- Debian testing AMD 64bits (GNATMAKE 4.3.3)

The code can be found there:
http://scalbert.dyndns.org/adarubik/

This small project is a really a toy but I would like to understand the 
problem.

Thanks,

Olivier

Re: Problem with optimizations

[Albrecht Käfer]

Olivier Scalbert schrieb::
> Hello,
>
> I have write a little program that try to solve Rubik's cube, just to
> practice a little Ada.
> The program is really stupid (brute force) but I have a strange problem.
> When I compile it with:
> gnatmake -O2 rubukmain, it works:
>
> Depth:  1  Positions Counter:                    12
> Depth:  2  Positions Counter:                   132
> Depth:  3  Positions Counter:                  1440
> Depth:  4  Positions Counter:                 15720
> Depth:  5  Positions Counter:                171600
> Depth:  6  Positions Counter:               1873200
> Depth:  7  Positions Counter:              20448000
> Depth:  8
> Solved !
>            1         12          8         10          2          6
>       3          3  Positions Counter:              18104705
>
> When I compile it with:
> gnatmake -O3 rubukmain, it does not work:
>
> Depth:  1  Positions Counter:                     1
> Then it stops.
>
> When, inside the Recursive_Find_Solution, I replace Is_Solved by
> Is_Solved1, then it works in all cases.
>
> I have try to understand what is happen with gdb and by having a look
> into the generated code, but without success.
>
> I have the same behaviour with:
> - Ubuntu 8.10 32 bits (GNATMAKE 4.3.2)
> - Debian testing AMD 64bits (GNATMAKE 4.3.3)

Works fine on Windows (GNAT GPL 2009).
However, I can't help but notice that you are doing premature
optimization. Did you *test* if it is faster?


Albrecht

Re: Problem with optimizations

[Olivier Scalbert]

Albrecht K�fer wrote:

> Works fine on Windows (GNAT GPL 2009).
> However, I can't help but notice that you are doing premature
> optimization. Did you *test* if it is faster?
> 
> 
> Albrecht

With -O3 also ?

It is not premature optimization. The difference between Is_Solved and 
Is_Solved1 is quite important on my system:

with -O2 and Is_solved:
time ./rubikmain
real    0m2.164s
user    0m2.160s
sys     0m0.000s

with -O2 and Is_solved:
time ./rubikmain
real    0m3.604s
user    0m3.596s
sys     0m0.000s

Olivier

Re: Problem with optimizations

[Albrecht Käfer]

Olivier Scalbert schrieb::
>> Works fine on Windows (GNAT GPL 2009).
>> However, I can't help but notice that you are doing premature
>> optimization. Did you *test* if it is faster?
>> Albrecht
> With -O3 also ?

Very much so.

> It is not premature optimization. The difference between Is_Solved and
> Is_Solved1 is quite important on my system:
>
> with -O2 and Is_solved:
> time ./rubikmain
> real    0m2.164s
> user    0m2.160s
> sys     0m0.000s
>
> with -O2 and Is_solved:
> time ./rubikmain
> real    0m3.604s
> user    0m3.596s
> sys     0m0.000s

That is odd.


Albrecht

Re: Problem with optimizations

[John B. Matthews]

In article <49f742d0$0$2851$ba620e4c@news.skynet.be>,
 Olivier Scalbert <olivier.scalbert@algosyn.com> wrote:

> Albrecht Käfer wrote:
> 
> > Works fine on Windows (GNAT GPL 2009).
> > However, I can't help but notice that you are doing premature
> > optimization. Did you *test* if it is faster?
> > 
> > 
> > Albrecht
> 
> With -O3 also ?
> 
> It is not premature optimization. The difference between Is_Solved and 
> Is_Solved1 is quite important on my system:
> 
> with -O2 and Is_solved:
> time ./rubikmain
> real    0m2.164s
> user    0m2.160s
> sys     0m0.000s
> 
> with -O2 and Is_solved[1]:
> time ./rubikmain
> real    0m3.604s
> user    0m3.596s
> sys     0m0.000s
> 
> Olivier

Using FSF-GNAT[1], I was able to reproduce the -O3 failure. This version 
of Is_Solved seems to work at -O3, and it is similarly faster:

    function Is_Solved(Cube: Cube_T) return Boolean is
    begin
        for i in Face_Index_T'range loop
            for j in Face_T'range(1) loop
                for k in Face_T'range(2) loop   
                    if Cube(i)(j,k) /= Final_Position(i)(j,k) then
                        return False;
                    end if;
                end loop;
            end loop;
        end loop;
        return True;
    end Is_Solved;

This version of Is_Solved1 was not measurably faster:

    function Is_Solved1(Cube: Cube_T) return Boolean is
    begin
        return Cube = Final_Position;
    end Is_Solved1;

[1] GNAT 4.3.4 20090225 (prerelease) [gcc-4_3-branch revision 143854]
Copyright 1996-2007, Free Software Foundation, Inc.

-- 
John B. Matthews
trashgod at gmail dot com
<http://sites.google.com/site/drjohnbmatthews>

Re: Problem with optimizations

[(see below)]

On 28/04/2009 18:04, in article 49f73730$0$2850$ba620e4c@news.skynet.be,
"Olivier Scalbert" <olivier.scalbert@algosyn.com> wrote:

...
> When, inside the Recursive_Find_Solution, I replace Is_Solved by
> Is_Solved1, then it works in all cases.
> 
> I have try to understand what is happen with gdb and by having a look
> into the generated code, but without success.
> 
> I have the same behaviour with:
> - Ubuntu 8.10 32 bits (GNATMAKE 4.3.2)
> - Debian testing AMD 64bits (GNATMAKE 4.3.3)
> 
> The code can be found there:
> http://scalbert.dyndns.org/adarubik/
> 
> This small project is a really a toy but I would like to understand the
> problem.

There is no else part for the following if:

            if Is_Solved(Cube) then
                New_Line;
                Put("Solved !"); New_Line;

                for i in 1..depth-1 loop
                    Ada.Integer_Text_IO.Put(Integer(Moves(i)));
                end loop;
                Result := True;
            end if;

So the procedure can exit with Result undefined. Since the program is
incorrect, varying optimisation, or implementation details, is likely to
give varying results. Some may co-incidentally be the results you expect.

P.S. I did not use gdb.

-- 
Bill Findlay, <surname><forename> chez blueyonder.co.uk
"My own view on religion is that of Lucretius. I regard it as a disease born
of fear and as a source of untold misery to the human race." B. Russell

Re: Problem with optimizations

[Albrecht Käfer]

(see below) schrieb::
> There is no else part for the following if:
>
>             if Is_Solved(Cube) then
>                 New_Line;
>                 Put("Solved !"); New_Line;
>
>                 for i in 1..depth-1 loop
>                     Ada.Integer_Text_IO.Put(Integer(Moves(i)));
>                 end loop;
>                 Result := True;
>             end if;
>
> So the procedure can exit with Result undefined. Since the program is
> incorrect, varying optimisation, or implementation details, is likely to
> give varying results. Some may co-incidentally be the results you expect.

Shouldn't that, you know, create a warning or something?


Albrecht

Re: Problem with optimizations

[Olivier Scalbert]

Albrecht K�fer wrote:
> (see below) schrieb::
>> There is no else part for the following if:
>>
>>             if Is_Solved(Cube) then
>>                 New_Line;
>>                 Put("Solved !"); New_Line;
>>
>>                 for i in 1..depth-1 loop
>>                     Ada.Integer_Text_IO.Put(Integer(Moves(i)));
>>                 end loop;
>>                 Result := True;
>>             end if;
>>
>> So the procedure can exit with Result undefined. Since the program is
>> incorrect, varying optimisation, or implementation details, is likely to
>> give varying results. Some may co-incidentally be the results you expect.
> 
> Shouldn't that, you know, create a warning or something?
> 
> 
> Albrecht

That is what I was thinking, but with:

gnatmake -f -O3 -W -gnatp rubikmain

it detects the bug (and also an other one in the same function)

Shame on me !

Re: Problem with optimizations

[Olivier Scalbert]

Sorry forgot the message:

gnatmake -f -O3 -W -gnatp rubikmain
gcc-4.3 -c -O3 -W -gnatp rubikmain.adb
gcc-4.3 -c -O3 -W -gnatp adarubik.adb
adarubik.adb: In function �Adarubik.Recursive_Find_Solution�:
adarubik.adb:75: warning: �Result� may be used uninitialized in this 
function
gnatbind -x rubikmain.ali
gnatlink rubikmain.ali

Re: Problem with optimizations

[Gautier]

Something else you can try is -O2 and pragma Inline(...) for a few 
selected procedures (add one Inline, test, add another one, test, etc.).
_________________________________________________________
Gautier's Ada programming -- http://sf.net/users/gdemont/
NB: For a direct answer, e-mail address on the Web site!

Re: Problem with optimizations

[sjw]

On Apr 28, 8:15 pm, Olivier Scalbert <olivier.scalb...@algosyn.com>
wrote:

> That is what I was thinking, but with:
>
> gnatmake -f -O3 -W -gnatp rubikmain
>
> it detects the bug (and also an other one in the same function)
>
> Shame on me !

And all this time I've been thinking that -gnatwa (actually we use -
gnatwaL) would detect this problem .. oh dear.

Also, -Wall doesn't detect the problem, clearly 'all' doesn't mean
what I thought it did.

Target: i386-apple-darwin9.6.0
gcc version 4.3.3 (GCC)

Re: Problem with optimizations

[johnscpg]

On Apr 28, 8:15 pm, Olivier Scalbert <olivier.scalb...@algosyn.com>
wrote:
> Albrecht Käfer wrote:
> > (see below) schrieb::
> >> There is no else part for the following if:
>
> >>             if Is_Solved(Cube) then
> >>                 New_Line;
> >>                 Put("Solved !"); New_Line;
>
> >>                 for i in 1..depth-1 loop
> >>                     Ada.Integer_Text_IO.Put(Integer(Moves(i)));
> >>                 end loop;
> >>                 Result := True;
> >>             end if;
>
> >> So the procedure can exit with Result undefined. Since the program is
> >> incorrect, varying optimisation, or implementation details, is likely to
> >> give varying results. Some may co-incidentally be the results you expect.
>
> > Shouldn't that, you know, create a warning or something?
>
> > Albrecht
>
> That is what I was thinking, but with:
>
> gnatmake -f -O3 -W -gnatp rubikmain
>
> it detects the bug (and also an other one in the same function)
>
> Shame on me !

Re: Problem with optimizations

[johnscpg]

On Apr 28, 8:15 pm, Olivier Scalbert <olivier.scalb...@algosyn.com>
wrote:
> Albrecht Käfer wrote:
> > (see below) schrieb::
> >> There is no else part for the following if:
>
> >>             if Is_Solved(Cube) then
> >>                 New_Line;
> >>                 Put("Solved !"); New_Line;
>
> >>                 for i in 1..depth-1 loop
> >>                     Ada.Integer_Text_IO.Put(Integer(Moves(i)));
> >>                 end loop;
> >>                 Result := True;
> >>             end if;
>
> >> So the procedure can exit with Result undefined. Since the program is
> >> incorrect, varying optimisation, or implementation details, is likely to
> >> give varying results. Some may co-incidentally be the results you expect.
>
> > Shouldn't that, you know, create a warning or something?
>
> > Albrecht
>
> That is what I was thinking, but with:
>
> gnatmake -f -O3 -W -gnatp rubikmain
>
> it detects the bug (and also an other one in the same function)
>
> Shame on me !

I also learned this recently (using gfortran).   You have to have -O
to
get the -W to work when you are looking for uninitialized variables.
Exactly as you've shown, it flags variables that may or may not
be initialized in for loops, or if then else blocks.  Its usually
wrong,
(it speculates) but I like it.  In gfortan you can write -O -
Wuninitialized; probably
same with gnatmake (it accepts it anyway).

cheers,
jonathan

Re: Problem with optimizations

[johnscpg]

On Apr 28, 8:15 pm, Olivier Scalbert <olivier.scalb...@algosyn.com>
wrote:
> Albrecht Käfer wrote:
> > (see below) schrieb::
> >> There is no else part for the following if:
>
> >>             if Is_Solved(Cube) then
> >>                 New_Line;
> >>                 Put("Solved !"); New_Line;
>
> >>                 for i in 1..depth-1 loop
> >>                     Ada.Integer_Text_IO.Put(Integer(Moves(i)));
> >>                 end loop;
> >>                 Result := True;
> >>             end if;
>
> >> So the procedure can exit with Result undefined. Since the program is
> >> incorrect, varying optimisation, or implementation details, is likely to
> >> give varying results. Some may co-incidentally be the results you expect.
>
> > Shouldn't that, you know, create a warning or something?
>
> > Albrecht
>
> That is what I was thinking, but with:
>
> gnatmake -f -O3 -W -gnatp rubikmain
>
> it detects the bug (and also an other one in the same function)
>
> Shame on me !

I also learned this recently using gfortran.
You need the -O flag along with the -W to
get the gcc compiler to report uninitialized
variables.  As you've shown, it spots possible
uninitialized variables in  if-then-else
blocks or for-loops.  It mostly speculates - its
usually wrong, but I like it. In gfortran
you can limit the -W with: -O -Wuninitialized.
Don't know about gnatmake, but
gnatmake  accepts it.

cheers
jonathan

(This will be my 3rd and final attempt to post this -
hope 3 of these posts don't eventually appear,
but I can't seem to get gmail to let me through.
It sure likes spam tho' ;)

Re: Problem with optimizations

[Olivier Scalbert]

(see below) wrote:

> 
> There is no else part for the following if:
> 
>             if Is_Solved(Cube) then
>                 New_Line;
>                 Put("Solved !"); New_Line;
> 
>                 for i in 1..depth-1 loop
>                     Ada.Integer_Text_IO.Put(Integer(Moves(i)));
>                 end loop;
>                 Result := True;
>             end if;
> 
> So the procedure can exit with Result undefined. Since the program is
> incorrect, varying optimisation, or implementation details, is likely to
> give varying results. Some may co-incidentally be the results you expect.
> 
> P.S. I did not use gdb.
> 

You are right !

So an Ada compiler can compile incorrect programs !
;-)

Re: Problem with optimizations

[(see below)]

On 28/04/2009 20:06, in article 49f753b9$0$2861$ba620e4c@news.skynet.be,
"Olivier Scalbert" <olivier.scalbert@algosyn.com> wrote:

> (see below) wrote:
> 
>> 
>> There is no else part for the following if:
>> 
>>             if Is_Solved(Cube) then
>>                 New_Line;
>>                 Put("Solved !"); New_Line;
>> 
>>                 for i in 1..depth-1 loop
>>                     Ada.Integer_Text_IO.Put(Integer(Moves(i)));
>>                 end loop;
>>                 Result := True;
>>             end if;
>> 
>> So the procedure can exit with Result undefined. Since the program is
>> incorrect, varying optimisation, or implementation details, is likely to
>> give varying results. Some may co-incidentally be the results you expect.
>> 
>> P.S. I did not use gdb.
>> 
> 
> You are right !
> 
> So an Ada compiler can compile incorrect programs !
> ;-)

It has no alternative, thanks to Turing.
8-) | 8-(

-- 
Bill
"To explain the unknown by the known is a logical procedure; to explain
the known by the unknown is a form of theological lunacy." David Brooks

Re: Problem with optimizations

[Gene]

On Apr 28, 3:12 pm, "(see below)" <yaldni...@blueyonder.co.uk> wrote:
> On 28/04/2009 20:06, in article 49f753b9$0$2861$ba620...@news.skynet.be,
>
>
>
>
>
> "Olivier Scalbert" <olivier.scalb...@algosyn.com> wrote:
> > (see below) wrote:
>
> >> There is no else part for the following if:
>
> >>             if Is_Solved(Cube) then
> >>                 New_Line;
> >>                 Put("Solved !"); New_Line;
>
> >>                 for i in 1..depth-1 loop
> >>                     Ada.Integer_Text_IO.Put(Integer(Moves(i)));
> >>                 end loop;
> >>                 Result := True;
> >>             end if;
>
> >> So the procedure can exit with Result undefined. Since the program is
> >> incorrect, varying optimisation, or implementation details, is likely to
> >> give varying results. Some may co-incidentally be the results you expect.
>
> >> P.S. I did not use gdb.
>
> > You are right !
>
> > So an Ada compiler can compile incorrect programs !
> > ;-)
>
> It has no alternative, thanks to Turing.
> 8-) | 8-(
>
> --
> Bill
> "To explain the unknown by the known is a logical procedure; to explain
> the known by the unknown is a form of theological lunacy." David Brooks- Hide quoted text -

Well... Thanks to God and/or nature, wherein Turing had some
insight...

Re: Problem with optimizations

[(see below)]

On 29/04/2009 03:35, in article
fbc5b194-ff66-422f-a163-a8b38b93f20c@a5g2000pre.googlegroups.com, "Gene"
<gene.ressler@gmail.com> wrote:

> On Apr 28, 3:12�pm, "(see below)" <yaldni...@blueyonder.co.uk> wrote:
>> On 28/04/2009 20:06, in article 49f753b9$0$2861$ba620...@news.skynet.be,
>> 
>> "Olivier Scalbert" <olivier.scalb...@algosyn.com> wrote:
>>> So an Ada compiler can compile incorrect programs !
>>> ;-)
>> 
>> It has no alternative, thanks to Turing.
>> 8-) | 8-(
>> 
>> --
>> Bill
>> "To explain the unknown by the known is a logical procedure; to explain
>> the known by the unknown is a form of theological lunacy." David Brooks- Hide
>> quoted text -
> 
> Well... Thanks to God and/or nature, wherein Turing had some insight...

Indeed, it's thanks to Turing (et al.) that we can allow compilers to err,
and do not in ignorance demand an unattainable perfection.

As for God, see below.

-- 
Bill Findlay
<surname><forename> chez blueyonder.co.uk
"God is, as it were, the sewer into which all contradictions flow." G. Hegel 

Re: Problem with optimizations

[Georg Bauhaus]

(see below) schrieb:
> On 29/04/2009 03:35, in article
> fbc5b194-ff66-422f-a163-a8b38b93f20c@a5g2000pre.googlegroups.com, "Gene"
> <gene.ressler@gmail.com> wrote:
> 
>> On Apr 28, 3:12 pm, "(see below)" <yaldni...@blueyonder.co.uk> wrote:
>>> On 28/04/2009 20:06, in article 49f753b9$0$2861$ba620...@news.skynet.be,
>>>
>>> "Olivier Scalbert" <olivier.scalb...@algosyn.com> wrote:
>>>> So an Ada compiler can compile incorrect programs !
>>>> ;-)
>>> It has no alternative, thanks to Turing.
>>> 8-) | 8-(
>>>
>>> --
>>> Bill
>>> "To explain the unknown by the known is a logical procedure; to explain
>>> the known by the unknown is a form of theological lunacy." David Brooks- Hide
>>> quoted text -
>> Well... Thanks to God and/or nature, wherein Turing had some insight...
> 
> Indeed, it's thanks to Turing (et al.) that we can allow compilers to err,
> and do not in ignorance demand an unattainable perfection.

So I should like to tell my superior powers.

Re: Problem with optimizations

[Gautier]

For your short-cut version of Is_Solved you might want to write:

         for i in Face_Index_T'range loop
           for c in Column_T loop
             for r in Row_T loop
               if Cube(i)(c,r) /= Final_Position(i)(c,r) then
                 return False;
               end if;
...

Just nicer looking, probably as fast as the "unrolled" version you have. 
Anyway, I strongly recommend adding -funroll-loops along with your -O2 
switch. Also -fpeel-loops, -ftracer, -funswitch-loops might help.
_________________________________________________________
Gautier's Ada programming -- http://sf.net/users/gdemont/
NB: For a direct answer, e-mail address on the Web site!

Re: Problem with optimizations

[Olivier Scalbert]

Gautier wrote:
> For your short-cut version of Is_Solved you might want to write:
> 
>         for i in Face_Index_T'range loop
>           for c in Column_T loop
>             for r in Row_T loop
>               if Cube(i)(c,r) /= Final_Position(i)(c,r) then
>                 return False;
>               end if;
> ...
> 
> Just nicer looking, probably as fast as the "unrolled" version you have. 
> Anyway, I strongly recommend adding -funroll-loops along with your -O2 
> switch. Also -fpeel-loops, -ftracer, -funswitch-loops might help.
> _________________________________________________________
> Gautier's Ada programming -- http://sf.net/users/gdemont/
> NB: For a direct answer, e-mail address on the Web site!

Thanks for your help.

Your version, which is nicer and more generic (4*4, 5*5 cube) on my machine:
gnatmake -f -O3 -W -gnatp -fpeel-loops -ftracer -funswitch-loops rubikmain
real    0m3.057s
user    0m2.988s
sys     0m0.004s

Mine (manually unrolled):
real    0m2.935s
user    0m2.876s
sys     0m0.004s

So, nearly the same. So I'll go for the nice one!

But with:
  function Is_Solved1(Cube: Cube_T) return Boolean is
     begin
         return Cube = Final_position;
     end Is_Solved1;

I have:
real    0m4.775s
user    0m4.660s
sys     0m0.004s

That is much longer !

Does it have the same semantic ?

Olivier

Re: Problem with optimizations

[Olivier Scalbert]

Gautier wrote:
> For your short-cut version of Is_Solved you might want to write:
> 
>         for i in Face_Index_T'range loop
>           for c in Column_T loop
>             for r in Row_T loop
>               if Cube(i)(c,r) /= Final_Position(i)(c,r) then
>                 return False;
>               end if;
> ...
> 
> Just nicer looking, probably as fast as the "unrolled" version you have. 
> Anyway, I strongly recommend adding -funroll-loops along with your -O2 
> switch. Also -fpeel-loops, -ftracer, -funswitch-loops might help.
> _________________________________________________________
> Gautier's Ada programming -- http://sf.net/users/gdemont/
> NB: For a direct answer, e-mail address on the Web site!

By the way, it seems that all the 3x3 cube position can be solved in 
less than 26 moves.
As my prog does a full search at a depth of 8 in 15 secondes, it will 
need less than 12^18*15.0 seconds (12663305403769 years)

So I should focus on the algorithm instead of the compilation flags ...
;-)