Problem with optimizations
Olivier Scalbert
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
Albrecht Käfer
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
Olivier Scalbert
> 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
(see below)
"Olivier Scalbert" <olivier....@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
Albrecht Käfer
>> 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
Olivier Scalbert
>
> 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 !
;-)
Albrecht Käfer
> 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
(see below)
"Olivier Scalbert" <olivier....@algosyn.com> wrote:
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
Olivier Scalbert
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 !
John B. Matthews
Olivier Scalbert <olivier....@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>
Olivier Scalbert
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
Gautier
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!
Gautier
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.
Olivier Scalbert
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
Olivier Scalbert
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 ...
;-)
sjw
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)
Gene
> 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
Well... Thanks to God and/or nature, wherein Turing had some
insight...
(see below)
fbc5b194-ff66-422f...@a5g2000pre.googlegroups.com, "Gene"
<gene.r...@gmail.com> wrote:
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
Georg Bauhaus
> On 29/04/2009 03:35, in article
> fbc5b194-ff66-422f...@a5g2000pre.googlegroups.com, "Gene"
> <gene.r...@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.
john...@googlemail.com
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' ;)
john...@googlemail.com
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