New subject: list trouble

21 Jun 2002

      Speaking of optimization, are you using any "heavy" optimization settings
that may be giving side-effects?
Joe.
...
-----Original Message-----
From:	CBFalconer [SMTP:cbfalconer@yahoo.com]
Sent:	Friday, June 21, 2002 5:59 AM
To:	gpc@gnu.de
Subject:	Re: list trouble
Toby Ewing wrote:
...
CBFalconer wrote:
...
Toby Ewing wrote:
...
I'm having trouble with list management again.
... snip ...
...
...
It's probably an obvious problem, and I'm hoping fresh eyes can see
it.
...
...
All I have done below is reformat, so I could follow it, and
separate out the mundane operations into a local procedure, so
that the actual list manipulation stands alone, and also because I
have no idea what that piece of code is doing.  Many variables
should be moved into the local, and the item to manipulate should
be passed into it, but that is another matter.
It's a trade-off between clarity and speed.  The loop will execute
several billions of times, and the run time is several days.  I try not
to call functions or procedures from inner loops.  But as you say,
that's a whole other discussion.
You are doing enough in that routine that there should be no
perceptible difference in speed.  The first rule of optimization
is don't.  The second is profile first.
...
...
Now go to the end
...
Procedure Advance(VAR Root   : PRec;   {rx, ry, rz: medcard; next:
PRec}
...
...
...
              VAR Latt   : PPLary; (3D lattice in schema format}
              VAR here,
                  count  : medCard);

{Local to NumLatt.

Identify adjacent, accessible sites.
if sites are unoccupied, insert them into LNext.
Delete Self from Root.
Set Root = Lnext.}

VAR
    LNext,
    PSelf       : PRec;
    lx, ly, lz,                       {neighboring locations}
    dir         : medCard;            {directions}
    Conduct     : boolean;            {=accessible site}
(* 2--------------------2 *)
PROCEDURE operate;
BEGIN (* operate *)

... snip ...
...
...
...
END; (* operate *)

(* 2--------------------2 *)
BEGIN (* advance *)
  LNext := Nil;
  WHILE (Root <> Nil) DO BEGIN
    PSelf := Root;
    operate;
    Root := Root^.next;                        {advance through
list}
...
...
...
write('a');
    dispose(PSelf);            { <<=== program crashes here }
write('b. ');
    END; (* while *)
  Root := LNext;
  END; {Advance}
The above makes it pretty obvious that the problem is NOT in the
operate action, but in the list itself.  The fact that dispose
crashes shows that PSelf is not a valid pointer to a record, which
includes *the fact that the record was created with new*
I agree that the problem is that PSelf is apparently not a valid
pointer.  I don't understand what you're saying about New.  Is New not
stable or trustworthy?
Perfectly stable and trustworthy.
...
...
I think you should look into the areas where the list is created.
You may have a global instance of an element, for example, that
you are incorporating into the list somehow.
The list is created by

declaring the variable Root : PRec (outside procedure Advance), and
using the procedure LInsert to add elements to the list.

LInsert is:
Procedure LInsert(var Root      : PRec;
                  var x, y, z   : medCard);
var temp      : PRec;
begin
  new(temp);
  with temp^ do begin
    rx := x;
    ry := y;
    rz := z;
    next := Root;
  end;
  Root := temp;
end;
The only list manipulation is the LInsert procedure, and the dispose
line that sometimes crashes the program.  All records in the list come
from LInsert.  What I find disturbing is that this is a very simple
piece of list work.  The program sometimes runs through over 2,000,000
records without crashing - and sometimes crashes after about 100
records.  Frustrating.
CBFalconer continues:
...
GPC new/dispose is dependant on the C malloc, I believe.  If you
are using DJGPP you can probably use my nmalloc, available on my
site, which provides some hooks for examining the allocation
chains and also detects most illegal frees.  If it is linked ahead
of the runtime library it will replace the library malloc stuff.
But that should be only a last resort.
Yes, I'm using DJGPP and will check out your nmalloc.  I'm also
installing GPC on a Linux box so I can try te program there.  Because
this is memory weirdness, I'm wondering if at heart it's a windows
problem.
I assume you have a declaration somewhere like:
TYPE
    prec = ^rec;
    rec  = RECORD
      ...
      next : prec;
      END;
and I was envisioning you had done something like declare
VAR
    root  : rec;
...
but you say not.  Have you ever initialized root to be NIL?
VAR
     root  : prec;
....
   root := NIL;      (* <---- absolutely crucial *)
   WHILE whatever DO linsert(root, ...);
....
If you don't have ECC memory it is conceivable you have hardware
problems.  Another possibility is some bad indexing fouling the
chains (gpc doesn't have range checking :-[) where the nmalloc
stuff might come in handy.
You could build a list validator, which only walks the list from
root to final NIL. To use it add a field set to a constant value,
and the validator checks that value is there for each entry. 
Should be quite fast, and you can then call it here and there in
the program. This would give an early indication of fouled
storage.
CONST
    VALIDMARK = 1234;
TYPE
    rec = RECORD
      validation : integer;
      ....
      END;
PROCEDURE linsert(....)
     ....
     new(temp);
     temp.validation := VALIDMARK;
     ...
PROCEDURE listvalidate(calledfrom : integer);
 LABEL 10;

 VAR temp : prec;

 BEGIN (* listvalidate *)
 temp := root;
 WHILE temp <> NIL DO
   IF temp.validation <> VALIDMARK THEN BEGIN
      takesomeaction(calledfrom);
      goto 10; END;

10:  END; (* listvalidate *)
(you may notice I don't believe in using things outside of ISO7185
without very good reasons, none of which I see here <g>)
If all else fails see line 2 of the sig.
-- 
Chuck F (cbfalconer@yahX-Mozilla-Status: 0009rldnet.att.net)
   Available for consulting/temporary embedded and systems.
   http://cbfalconer.home.att.net  USE worldnet address!