OpenEuphoria

1. Strange machine-level exception

• Posted by Juergen Luethje <j.lue at gmx.de> Jun 17, 2007
• 654 views
• Last edited Jun 18, 2007

Hi all,

I've changed my private create_set() function a little, in order to take
advantage of find_from(). Then I encountered a strange machine-level
exception.

I've tested it on Windows XP Pro and Euphoria 3.1. The following code runs
fine when interpreted by EX.exe, EXW.exe and EXWC.exe. When I uncomment
the denoted line near the end, the program still runs fine with EX.exe but
crashes reliably with EXW.exe and EXWC.exe. Renaming "safe.e" to "machine.e"
and including it in the program didn't provide any hints.

function create_set (sequence s)
   -- create a set (= remove duplicate entries)
   integer p

   if length(s) < 2 then
      return s
   end if

   p = length(s)
   for i = length(s)-1 to 1 by -1 do
      if find_from(s[i], s, i+1) = 0 then  -- Machine-level exception here ...
         p -= 1
         s[p] = s[i]
      end if
   end for
   return s[p..$]
end function


sequence freq, result, unique
integer n, player

n = 1000

result = {}
for i = 1 to n do
   freq = repeat(0, 3)
   for card = 1 to 4 do
      player = rand(3)
--       freq[player] += 1                 -- ... after uncommenting this line!
   end for
   result = append(result, freq)
end for

unique = create_set(result)
? unique
if getc(0) then end if

Can someone please confirm the problem?

Regards,
   Juergen

3. Re: Strange machine-level exception

• Posted by Derek Parnell <ddparnell at bigpond.com> Jun 17, 2007
• 552 views
• Last edited Jun 18, 2007

Juergen Luethje wrote:
> 
> Hi all,
> 
> I've changed my private create_set() function a little, in order to take
> advantage of find_from(). Then I encountered a strange machine-level
> exception.
> 
> I've tested it on Windows XP Pro and Euphoria 3.1. The following code runs
> fine when interpreted by EX.exe, EXW.exe and EXWC.exe. When I uncomment
> the denoted line near the end, the program still runs fine with EX.exe but
> crashes reliably with EXW.exe and EXWC.exe. Renaming "safe.e" to "machine.e"
> and including it in the program didn't provide any hints.


> Can someone please confirm the problem?

Yes I can confirm it. There does appear to be a problem with find_from(). I
tried to get around it by not assigning back to the 's' sequence and that worked
for small sequence size but it failed for large ones. If you don't use
find_from() it works ...

eg.

function create_set (sequence s)
   -- create a set (= remove duplicate entries)
   sequence t
   object x

   if length(s) < 2 then
      return s
   end if

   t = {s[1]}
   for i = 2 to length(s) - 1 do
      x = s[i]
      if find(x, t) = 0 then
         t = append(t,x)
      end if
   end for
   return t
end function


-- 
Derek Parnell
Melbourne, Australia
Skype name: derek.j.parnell

5. Re: Strange machine-level exception

• Posted by Derek Parnell <ddparnell at bigpond.com> Jun 18, 2007
• 609 views

Ricardo Forno wrote:
> 
> Hi Juergen.
> I did not try your program, but apart from this, I have a suggestion to 
> improve its speed.
>  From the point of view of computational complexity, your code is
> O(n*n).
> This can be improved by first sorting the sequence, which is O(log(n)*n),
> and then examining it linearly eliminating the equal elements, which is
> O(n), giving a joint complexity O(log(n)*n).
> This improvement will be more noticeable as the sequence length increases.

Actually, I tried that too because it sounds sensible. However when I did that,
pre-sorting it makes it run about 3X slower and causes the resulting set to be
ordered differently from the input set, which might be significant to some
applications.

include sort.e
function create2_set (sequence s)
   -- create a set (= remove duplicate entries)
   integer p

   if length(s) < 2 then
      return s
   end if

    s = sort(s)
    p = 1
    for i = 2 to length(s) do
        if not equal(s[p], s[i]) then
            p += 1
            if p != i then
                s[p] = s[i]
            end if
        end if
    end for

    return s[1..p]
end function

-- 
Derek Parnell
Melbourne, Australia
Skype name: derek.j.parnell

7. Re: Strange machine-level exception

• Posted by Juergen Luethje <j.lue at gmx.de> Jun 18, 2007
• 555 views

Derek Parnell wrote:

> Juergen Luethje wrote:
>> 
>> Hi all,
>> 
>> I've changed my private create_set() function a little, in order to take
>> advantage of find_from(). Then I encountered a strange machine-level
>> exception.
>> 
>> I've tested it on Windows XP Pro and Euphoria 3.1. The following code runs
>> fine when interpreted by EX.exe, EXW.exe and EXWC.exe. When I uncomment
>> the denoted line near the end, the program still runs fine with EX.exe but
>> crashes reliably with EXW.exe and EXWC.exe. Renaming "safe.e" to "machine.e"
>> and including it in the program didn't provide any hints.
> 
> 
>> Can someone please confirm the problem?
> 
> Yes I can confirm it.

Thanks, Derek.

> There does appear to be a problem with find_from(). I
> tried to get around it by not assigning back to the 's' sequence and that
> worked
> for small sequence size but it failed for large ones.

A strange point IMHO is, that the problem does not only depend on the size
of s but also on its content. With s = repeat(1000, {0,0,0}) there is no
problem, with other content (when the line at the end of the program is
uncommented) the program crashes.

> If you don't use find_from()
> it works ...
> 
> eg.
> 
> function create_set (sequence s)
>    -- create a set (= remove duplicate entries)
>    sequence t
>    object x
> 
>    if length(s) < 2 then
>       return s
>    end if
> 
>    t = {s[1]}
>    for i = 2 to length(s) - 1 do
>       x = s[i]
>       if find(x, t) = 0 then
>          t = append(t,x)
>       end if
>    end for
>    return t
> end function

Yep.

Regards,
   Juergen

9. Re: Strange machine-level exception

• Posted by Juergen Luethje <j.lue at gmx.de> Jun 18, 2007
• 538 views

Hello Doni,

thanks for looking into it, and for your additional information.

Regards,
   Juergen

11. Re: Strange machine-level exception

• Posted by Bernie Ryan <xotron at bluefrog.com> Jun 18, 2007
• 541 views

Juergen Luethje wrote:
> 
> Hi all,
> 
> I've changed my private create_set() function a little, in order to take
> advantage of find_from(). Then I encountered a strange machine-level
> exception.
> 
> I've tested it on Windows XP Pro and Euphoria 3.1. The following code runs
> fine when interpreted by EX.exe, EXW.exe and EXWC.exe. When I uncomment
> the denoted line near the end, the program still runs fine with EX.exe but
> crashes reliably with EXW.exe and EXWC.exe. Renaming "safe.e" to "machine.e"
> and including it in the program didn't provide any hints.
> }}}
<eucode>
> function create_set (sequence s)
>    -- create a set (= remove duplicate entries)
>    integer p
> 
>    if length(s) < 2 then
>       return s
>    end if
> 
>    p = length(s)
>    for i = length(s)-1 to 1 by -1 do
>       if find_from(s[i], s, i+1) = 0 then  -- Machine-level exception here ...
>          p -= 1
>          s[p] = s[i]
>       end if
>    end for
>    return s[p..$]
> end function
> 
> 
> sequence freq, result, unique
> integer n, player
> 
> n = 1000
> 
> result = {}
> for i = 1 to n do
>    freq = repeat(0, 3)
>    for card = 1 to 4 do
>       player = rand(3)
> --       freq[player] += 1                 -- ... after uncommenting this
> line!
>    end for
>    result = append(result, freq)
> end for
> 
> unique = create_set(result)
> ? unique
> if getc(0) then end if
> </eucode>
{{{

> Can someone please confirm the problem?
> 
> Regards,
>    Juergen

Juergen:
    Could the problem be caused by variations in the RAND() function ?
    The rand() may be compiled different for each compiler or different
    on each OS. The reason I say this is because the rand() occurs before
    the line that is commented out.
Bernie

My files in archive:
WMOTOR, XMOTOR, W32ENGIN, MIXEDLIB, EU_ENGIN, WIN32ERU, WIN32API 

Can be downloaded here:
http://www.rapideuphoria.com/cgi-bin/asearch.exu?dos=on&win=on&lnx=on&gen=on&keywords=bernie+ryan

13. Re: Strange machine-level exception

• Posted by CChris <christian.cuvier at agriculture.gouv.fr> Jun 18, 2007
• 570 views

I just peeked at the code in be_runtime.c. I haven't coded in C for a couple
years, yet something looks wrong to me - but again, *I* might be quite wrong just
as well.

Line 4654 says: "bv = *(++bp);", assuming ++bp can be read always. If the end of
the sequence is being reached, one would expect *(++bp) to be NOVALUE. Aren't
there cases (under Windows) where this might not be true, resulting in a bad read
ptr error?  Or perhaps it is Windows that catches the error and DOS/Linux don't
care.

Additionally, I wondered, reading lines 4633-4638, whether
else if (bv == NOVALUE) {
    break;
}
else if (compare(a, bv) == 0) {  /* not INT-INT case */
    return bp - (object_ptr)b->base;
}

shouldn't read
else {
    if (bv == NOVALUE) 
        break;
    else if (compare(a, bv) == 0)   /* not INT-INT case */
        return bp - (object_ptr)b->base;
}

instead. Perhaps the two are equivalent, but at least the logic is clearer in
the second form.

CChris

15. Re: Strange machine-level exception

• Posted by Juergen Luethje <j.lue at gmx.de> Jun 18, 2007
• 571 views
• Last edited Jun 19, 2007

Bernie Ryan wrote:

<snip>

> Juergen:
>     Could the problem be caused by variations in the RAND() function ?
>     The rand() may be compiled different for each compiler or different
>     on each OS. The reason I say this is because the rand() occurs before
>     the line that is commented out.
> Bernie

I also had a similar suspicion. But now I found that the program still
crashes, when
   player = rand(3)
is replaced with
   player = remainder(i,3) + 1

function create_set (sequence s)
   -- create a set (= remove duplicate entries)
   integer p

   if length(s) < 2 then
      return s
   end if

   p = length(s)
   for i = length(s)-1 to 1 by -1 do
      if find_from(s[i], s, i+1) = 0 then  -- Machine-level exception here
         p -= 1
         s[p] = s[i]
      end if
   end for
   return s[p..$]
end function


sequence freq, result, unique
integer n, player

n = 1000

result = {}
for i = 1 to n do
   freq = repeat(0, 3)
   for card = 1 to 4 do
--       player = rand(3)           -- old
      player = remainder(i,3) + 1   -- new  -->  program still crashes
      freq[player] += 1
   end for
   result = append(result, freq)
end for

unique = create_set(result)
? unique
if getc(0) then end if

Regards,
   Juergen

17. Re: Strange machine-level exception

• Posted by Juergen Luethje <j.lue at gmx.de> Jun 18, 2007
• 548 views
• Last edited Jun 19, 2007

Bernie Ryan wrote:

> Juergen Luethje wrote:
> > 
> > Bernie Ryan wrote:
> > 
> > <snip>
> > 
> > > Juergen:
> > >     Could the problem be caused by variations in the RAND() function ?
> > >     The rand() may be compiled different for each compiler or different
> > >     on each OS. The reason I say this is because the rand() occurs before
> > >     the line that is commented out.
> > > Bernie
> > 
> > I also had a similar suspicion. But now I found that the program still
> > crashes, when
> >    player = rand(3)
> > is replaced with
> >    player = remainder(i,3) + 1
> > 
> > }}}
<eucode>
> > function create_set (sequence s)
> >    -- create a set (= remove duplicate entries)
> >    integer p
> > 
> >    if length(s) < 2 then
> >       return s
> >    end if
> > 
> >    p = length(s)
> >    for i = length(s)-1 to 1 by -1 do
> >       if find_from(s[i], s, i+1) = 0 then  -- Machine-level exception here
> >          p -= 1
> >          s[p] = s[i]
> >       end if
> >    end for
> >    return s[p..$]
> > end function
> > 
> > 
> > sequence freq, result, unique
> > integer n, player
> > 
> > n = 1000
> > 
> > result = {}
> > for i = 1 to n do
> >    freq = repeat(0, 3)
> >    for card = 1 to 4 do
> > --       player = rand(3)           -- old
> >       player = remainder(i,3) + 1   -- new  -->  program still crashes
> >       freq[player] += 1
> >    end for
> >    result = append(result, freq)
> > end for
> > 
> > unique = create_set(result)
> > ? unique
> > if getc(0) then end if
> > </eucode>
{{{

> 
> Juergen:
> 
> I think the result of remainder can be a float and player is an integer 

I don't think that that is a problem, because the program does not crash
on the line:
   player = remainder(i,3) + 1

but as before, it crashes on the line:
   if find_from(s[i], s, i+1) = 0 then

Regards,
   Juergen

19. Re: Strange machine-level exception

• Posted by Juergen Luethje <j.lue at gmx.de> Jun 19, 2007
• 557 views

I've again simplified the code that shows the crash:

integer n
n = 1000

procedure process (sequence s)
   for i = n-1 to n-5 by -1 do
      if find_from(s[2], s, i+1) = 0 then  -- Machine-level exception here
         s[1] = {}
      end if
   end for
end procedure

sequence s
integer r

s = repeat({}, n)
for i = 1 to n do
   r = remainder(i, 3)
   s[i] = {r}
end for

process(s)

puts(1, "If you see this message, there was no crash.")
if getc(0) then end if

Regards,
   Juergen

21. Re: Strange machine-level exception

• Posted by Juergen Luethje <j.lue at gmx.de> Jun 19, 2007
• 536 views

Pete Lomax wrote:

> Juergen Luethje wrote:
> > 
> > I've again simplified the code that shows the crash:
> 
> I even get a crash with just this, and a causeway error on ex.exe as well:
> }}}
<eucode>
> constant n=399
> 
> sequence s
> integer r
> 
> s = repeat(0, n)
> s[2] = {2}
> r=find_from(s[2], s, n-1)  -- Machine-level exception here
> 
> puts(1, "If you see this message, there was no crash.")
> if getc(0) then end if
> </eucode>
{{{


Wow! I wasn't even able to get rid of the procedure.
It looks as if the bug is surrounded now.

Regards,
   Juergen

23. Re: Strange machine-level exception

• Posted by Pete Lomax <petelomax at blueyonder.co.uk> Jun 20, 2007
• 562 views

Bernie Ryan wrote:
> 
> 
> Looking at the source in be_runtime.c for find_from.
> 
> It seems that the code is testing for the value of the length for
> 
> the full sequence instead of the length of the sequence from the
> 
> starting point of the find to the end of the sequence.
> 
> Maybe I'am wrong ?

That's what I thought too. A further test confirms this beyond any remaining
doubt:

sequence x
 x={1,2,3,4,{5}}
 x=x[1..3]
?find_from({5},x,3)

and it prints 5 which is obvious nonsense as length(x) is now 3.

Regards,
Pete

25. Re: Strange machine-level exception

• Posted by Derek Parnell <ddparnell at bigpond.com> Jun 20, 2007
• 556 views

Daryl Border wrote:

> I also think the routines
> should return -1 for an out of bounds condition instead of 0. The current 
> behavior makes a return value of 0 ambiguous.

Maybe, but that is likely to break a lot of code that does this sort of thing
...

    if find_from(a,b,c) = 0 then
        doNotFound()
    end if


Anyhow, below is my version of what the code in be_runtime.c should be doing ...

long find_from(object a, s1_ptr b, object c)
/* find object a as an element of sequence b starting from c*/
{
    register object_ptr bp;
    register object_ptr b_end;
    register object bv;

    if (!IS_SEQUENCE(b))
        RTFatal("second argument of find_from() must be a sequence");

    if (!IS_ATOM_INT(c))
        RTFatal("third argument of find_from() must be an integer");

    b = SEQ_PTR(b);
    if (b->length == 0)
        return 0;

    if (b->length < c) // should this be an error instead?
        return 0;
    if (0 >= c) // should this be an error instead?
        return 0;

    bp = b->base; // Point to start of 'b'
    bp += c - 1;  // Point to start of scan within 'b'
    b_end = b->base + length - 1; // Point to last element in 'b'
    if (IS_ATOM_INT(a)) {
        while (bp <= b_end) {
            bv = *bp;
            bp++;
            if (IS_ATOM_INT(bv)) {
                if (a == bv)
                    return bp - (object_ptr)b->base;
            }
            else if (bv == NOVALUE) {
                return 0;
            }
            else if (compare(a, bv) == 0) {  /* not INT-INT case */
                return bp - (object_ptr)b->base;
            }
        }
    }
    else if (IS_SEQUENCE(a)) {
        long a_len;

        a_len = SEQ_PTR(a)->length;
        if (a_len > 0) {
            while(bp <= b_end) {
                bv = *bp;
                bp++;
                if (IS_SEQUENCE(bv)) {
                    if (a_len == SEQ_PTR(bv)->length) {
                        /* a is SEQUENCE => not INT-INT case */
                        if (compare(a, bv) == 0)
                            return bp - (object_ptr)b->base;
                    }
                }
            }
        }
    }
    else {
        while (bp <= b_end) {
            bv = *bp;
            bp++;
            if ( !IS_SEQUENCE(bv)) {
                if (compare(a, bv) == 0) {
                    return bp - (object_ptr)b->base;
                }
            }
        }
    }
    
    return(0);
}


-- 
Derek Parnell
Melbourne, Australia
Skype name: derek.j.parnell

27. Re: Strange machine-level exception

• Posted by Derek Parnell <ddparnell at bigpond.com> Jun 20, 2007
• 543 views

CChris wrote:

> PS: Derek, by the way, do you check your email these days?

Yes.

-- 
Derek Parnell
Melbourne, Australia
Skype name: derek.j.parnell