Re: [gnugo-devel] DFA space savings

[Dave Denholm]

Trevor Morris <address@hidden> writes:

> >The runtime structure probably doesn't need maxStates, lastState, 
> >maxIndexes,lastIndex
> >Or at least, I didn't bother to have them in the version I was playing with.
> Good point.
> 
> >Probably worth making the state and index arrays const - no effect on 
> >executable
> >size, but core files will be smaller since (I assume) system won't write
> >const data into core file.
> Yes, I remember you mentioning that before. Good idea.
> 
> >Out of interest, did you measure speed and space-saving by just making 
> >next[] an array
> >of short rather than array of int ?
> No.
> My real goal is to try to use incremental offsets and cram each next into a 
> single unsigned char.
> 


Yeah, but you can use a short today and a char tomorrow. That would save all
the extra code to split longs or combine chars.



> >Is it really both faster and smaller to store two char's and combine them, 
> >rather
> >than using one short ?
> Certainly smaller.

2 chars is smaller than a short ?  How big is a short on your system ?


> No slower, according to 2 complete regression runs overnight, but not faster,
> despite what the comments in the text currently read.  Some owl tests I

(Only comments I saw were comparing longs, not shorts... ?)



> did early looked to be slightly faster.  The compiler may be able to be quite
> clever here.
> 


If the compiler can combine two chars into a short faster than it can load
a short, then someone should teach it to load the short character at a time !!!



If you are using gcc, maybe it decides it can pack a char[8] array
but it can't pack a short[4] for some reason. You can override packing
decisions :


`packed'
     The `packed' attribute specifies that a variable or structure field
     should have the smallest possible alignment--one byte for a
     variable, and one bit for a field, unless you specify a larger
     value with the `aligned' attribute.

     Here is a structure in which the field `x' is packed, so that it
     immediately follows `a':

          struct foo
          {
            char a;
            int x[2] __attribute__ ((packed));
          };




> 
> >> No speed difference, but the size improvement is probably worth putting
> >> the patch in anyway.  I believe by using unsigned chars that it will be
> >> platform independent.  The patch is also a good step towards making other 
> >> DFA 
> >> optimization experiments easier.
> >> 


It's true that using two unsigned chars guarantees the size, but I'd be
surprised if many platforms have short > 16 bits, and it's not worth
complicating the code for their sake. Especially if you are aiming for
one unsigned char in the long run...


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