[Freeciv-Dev] Re: the directional system

[Gaute B Strokkenes <gs234@xxxxxxxxx>]

On Wed, 12 Sep 2001, hawk@xxxxxxxxxxxxxxxxxxxxxxx wrote:
> On Tue, Sep 11, 2001 at 09:43:24PM +0200, Gaute B Strokkenes wrote:
>> On Sat, 8 Sep 2001, hawk@xxxxxxxxxxxxxxxxxxxxxxx wrote:
>> > On Fri, Sep 07, 2001 at 08:33:02PM -0400, Greg Wooledge wrote:
>> >> Raimar Falke (hawk@xxxxxxxxxxxxxxxxxxxxxxx) wrote:
>> >> > On Fri, Sep 07, 2001 at 04:51:36AM -0700, Trent Piepho wrote:
>> >> > > +#define DIR_REVERSE(dir) (((dir) + 4) % 8)
>> >> > > +#define DIR_REVERSE(dir) (((dir) + 4) & 7)
>> >> 
>> >> > $ gcc -S -O2 a.c
>> >> > $ cat a.s
>> >> 
>> >> Nice demonstration, but it only shows that your version of gcc
>> >> can handle this optimization
>> > 
>> > This is correct.
>> > 
>> >> -- there may be other compilers out there that don't.
>> > 
>> > Than please state the compiler and the version. I don't know what
>> > compiler are used to compile freeciv. I also don't know which
>> > compiler supports such optimization. However I think all
>> > compilers used today are able to perform the optimization since
>> > it is a very easy transformation IMHO.
>> 
>> This transformation is only safe when dir is an unsigned type, or
>> when the compiler can prove that a negative value for dir can not
>> occur.
> 
> This point was: the compiler is capable of doing the transformation
> "/8" -> "&7".  And yes in the signed case the compiler has to emit
> an extra branch.

I belive the point was that 

>> In most cases Freeciv uses plain ints, and it is usually very hard
>> to prove that a given variable can not be negative.  Therefore the
>> compiler will not be able to make this tranformation in the general
>> case.
>> 
>> > Please do the work and compile the small test program with
>> > various compilers. This will give you, me and the freeciv
>> > community a better understanding of how capable various compilers
>> > are.
>> > 
>> >> It's safer to use the bitwise AND operation.
>> > 
>> > Yes it would be safer for performance. However if performance
>> > would be the primary goal freeciv would use X11 directly.
>> 
>> I can't see what you're worried about; the "&" version is hardly
>> any less readable.
> 
> Let me restate: I'm only accepting "performance improvement fixes"
> if: - there is a problem (profiling data for example) in the tree
> and - the patch reduces the time used by a reasonable amount
> (i.e. this depends on the patch size)

I don't think that's a very sensible approach.  The conventional
rationale for avoiding "performance improvement fixes" is that
excessive tinkering aimed at improving performance frequently ends up
making the code harder to read and maintain.  It does not follow from
there that anything that improves performance is necessarily bad for
maintenance, which seems to be what you are implying.  If anyone can
spot an obvious way to make something work faster and better without
obfuscating the code, then I'm all for it.

The "replace divsion/modulo by 2^n with shift by n / and 2^n-1" is one
of the oldest tricks in the book, and I have a hard time imagining
anyone with a decent knowledge of C who would be in the least bit
confused by it.  Personally, I recognise powers of two, with the
occasional one subtracted, much more quikcly than my own birthday.  I
certainly don't understand why you would go to such lengths to show
that Trent's rather innocent, 2-byte suggested change to a patch that
hasn't even been made, much less applied is bad, especially when your
analysis is faulty.  It seems to me that you have settled on a general
principle that is widely recognised as reasonable whitout considering
why the principle exists, or when it doesn't apply.

> Yes I know even without testing the compiler that "&7" isn't slower
> than "%8". But is has to be proven that it is faster. The autogame
> feature makes it really easy to do such test runs.

You're preaching to the converted: I have been advocating and
conducting such empirical investigations for some time.  In fact, I
belive that I was the first person to use the word "profile" in recent
times on this mailing list.  For instance, the present form of
map_adjust_x() is the result of profiling various alternatives and
then picking the fastest one.  The speedup at the time was something
like ten to twenty percent, depending on which benchmark you use.

> Please take a look at the top of the profile I recently posted if
> you try to make freeciv faster. It looks like a new "real" hashtable
> would be a nice project.

Maybe.  ISTR that the profile you posted was the result of timing the
server from startup until the end of the beginning of turn stuff.
This elides the end of turn stuff entirely, and overemphasizes the
startup things.  When I profile the server, I usually run an all-ai
game to the end, which I belive gives a better picture of what an
average turn looks like.  My princial observation is that something
like one quarter to one third of the Freeciv runtime is spent in
functions that do little real work apart from the equivalent of
normalize_map_pos().  Cutting down on that is what I'm focusing on
now.

-- 
Big Gaute                               http://www.srcf.ucam.org/~gs234/
There's a SALE on STRETCH SOCKS down at the "7-11"!!