gnugo-devel
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [gnugo-devel] Crash report for OS X Segmentation fault


From: Dave Denholm
Subject: Re: [gnugo-devel] Crash report for OS X Segmentation fault
Date: 09 Jan 2002 15:29:33 +0000

Dave Denholm <address@hidden> writes:

> Daniel Bump <address@hidden> writes:
> 
> > > Hmm... I'm afraid I've rather lost touch with the current goals
> > > of gnugo. But "wasting" lots of memory as static does increase
> > > the minimum footprint required to run, and there are some people
> > > trying to run it on handhelds...
> > 
> > How does making this array static increase the minimum
> > footprint to run? After all, if the array is not static,
> > then when the function is called, the space for it will
> > have to be allocated then. 
> > 
> > (I think I see but let me ask the question anyway.)
> 

> 
> Simple example :
> 
> void f()
> {
>    AUTO int f_workspace[1024];
>    ...
> }
> 
> 
> void g()
> {
>    AUTO int g_workspace[512];
>    ...
> }
> 
> int main()
> {
>    f();
>    g();
> }
> 
> 
> 
> if AUTO = static, this program needs at least (1024+512) words
> of memory to run. f_workspace[] exists (but is not in scope)
> even while g() is running.
> 
> 
> if AUTO = /*nothing*/, this program needs at least 1024 words
> of stack to run. g_workspace[] and f_workspace[] share the
> same virtual memory, and each exists only while the
> other is running.
> 



A compromise is to make a global union of all the various
workspaces required. A bit like a fortran common-block,
I suppose.

So long as only one function uses it at a time, it acheives
the overlap of workspace, though not the sharing of workspace
with stack frames in recursive reading.

union {
  int f_workspace[1024];
  int g_workspace[512];
  Intersection p[MAX_BOARD][MAX_BOARD];  /* 2d board for matchpat */
} common_block;

For debug builds, could have a guard variable to indicate
whether the workspace is available or in-use.





Incidentally, just noticed that matchpat is still 2d. There's
a small speedup available by mapping to 1d as part of the
transorm to rotate the pattern.

At the moment, it uses a 2x2 matrix of 1's, 0's and -1's  to
map (i,j) to rotated (m,n).

But couldn't it use a 2x1 vector of +/- 1's and MAX_BOARD's  to
map from (i,j) to a single 1d board co-ordinate ?


Lets see if I can remember any matrix algebra...

at the moment, it does

|m|  = |a b| |i|
|n|    |c d| |j|

We would then have to do 

    offset_1d = origin_1d + [A B]|m|
                                 |n|

to map to 1d.

So we really want

 offset = origin +  [A B]|a b| |i|
                         |c d| |j|

and since a,b,c,d,A,B are constants, we can precalculate

  [A B]|a b|  =  (err...)  |(Aa + Bc)|
       |c d|               |(Ab + Bd)|

and so we just tabulate these 8 vectors, one for each rotation.
And that halves the work required to perform each rotation.

( I don't know if the pattern matcher is a performance problem
  at the moment
)



dd
-- 
address@hidden          http://www.insignia.com



reply via email to

[Prev in Thread] Current Thread [Next in Thread]