[Freeciv-Dev] Re: the directional system

[Raimar Falke <hawk@xxxxxxxxxxxxxxxxxxxxxxx>]

On Fri, Sep 14, 2001 at 03:55:24AM +0200, Gaute B Strokkenes wrote:
> 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.  

You misunderstand me somehow. I haven't said this. I can also make the
second statement more precise: "the amount of runtime speed gain is
reasonable compared to the added code obfuscation". So I will also
accept patches which makes the code nicer (ARRAY_SIZE comes to mind)
and have no performance change.

> If anyone can spot an obvious way to make something work faster and
> better without obfuscating the code, then I'm all for it.

I'm also 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.

This may be true. The point however is that the compiler can and does
such optimizations by itself just fine. The compiler is a tool. Use
the strengths of this tool. Prove it if you thing the tool is dumb to
do not such optimizations. I have showd that the compiler _in this
case_ was smart.

> 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

I'm also not very happy to run such a long thread. In the long term
however I hope that people just only submit such "performance
enhancements" if they checked it. 

In a longer run I also hope we, as a community, may also gain a
feeling what kind of optimizations current compilers are capable of.

> , 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.

No comment on this.

> > 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.

Fine.

> > 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.

The loading of a game took long (I'm sorry no more precise measurement
available (maybe 30sec)). And one method was at the top with 80%. What
else do you want? Yes loading will only take place once at the start.

> 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.

I will wait with what you come up.

        Raimar

-- 
 email: rf13@xxxxxxxxxxxxxxxxx
 "The BeOS takes the best features from the major operating systems. 
  It's got the power and flexibility of Unix, the interface and ease 
  of use of the MacOS, and Minesweeper from Windows."