TalkChess.com
Hosted by Your Move Chess & Games

Author Message
Gerd Isenberg

Joined: 08 Mar 2006
Posts: 1785
Location: Hattingen, Germany

Post subject: Re: question about symmertic evaluation    Posted: Fri May 25, 2007 6:28 pm

 Uri Blass wrote: My mistake is that I simply did not know that using / has different meaning than using >> I thought that it is simply the same and this is the reason that I even did not think about using / for getting symmetric evaluation. In case of knowing that / make things symmetric I could simply use it without asking questions because I had no reason to believe that / can be significantly slower than >>(I trust the compiler to make good work for every function). I have some /24 in my code and I never cared about speed of these cases I used >>3 instead of /8 simply because I thought it is the same and did not care if I write >>3 and not /8 Uri

Even worse - in C arithmetical shift with signed int is not specified (even twos-complement might not be used for signed int types!). It might be compiler and/or target architecture depending.

With todays processors and compilers I guess this expression is almost ever true:

assert (-1 >> 1 == ~1 + 1)

If some rare systems have only logical shift right, so that always zeros are shifted in from left to right, one has to use something like this (adapted from http://swox.com/~tege/divcnst-pldi94.pdf):

 Code: int shiftArithmeticalRight(int x, int s) {    unsigned int u = x ^ 0x80000000;    return (u >> s) - (1 << (s^31)); }

with K > 0
 Code: -K >> i == -K / 2**i
is only true, if the division goes without remainder, that is the i least significant bits are zero.
Otherwise shift rounds to -oo, while idiv truncates toward zero.

Many programmers are aware of some tricks to avoid very expensive instructions like division or modulo, eg. for making hash indices by "and" for power of two sized tables instead of modulo table size. Same for shift versus division by power of two divisors with unsigned values.

In the meantime recent compiler aka code generators will likely use similar algorithms like I posted from the amd-manual - to replace division by invariant integers with reciprocal imul or sar.

Therefor it is recommend to use "/" by constants rather than own shift- or whatever tricks. But i think it does not hurt to be aware of what the compiler does - and to be aware of div/idiv is really expensive - to better avoid variable divisors in critical code.

Btw. K10 idiv-latency is 23 + number of significant bits in absolute value of the dividend. 32*32=64bit imul still takes 3 cycles.

Gerd
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First
Subject Author Date/Time
Uri Blass Wed May 23, 2007 7:53 pm
Uri Blass Wed May 23, 2007 8:45 pm
Gerd Isenberg Wed May 23, 2007 8:46 pm
Uri Blass Wed May 23, 2007 9:04 pm
Robert Hyatt Wed May 23, 2007 9:51 pm
Uri Blass Wed May 23, 2007 10:04 pm
Gerd Isenberg Wed May 23, 2007 10:09 pm
Robert Hyatt Thu May 24, 2007 12:01 am
Gerd Isenberg Thu May 24, 2007 7:37 am
H.G.Muller Thu May 24, 2007 8:06 am
Gerd Isenberg Thu May 24, 2007 9:24 am
H.G.Muller Thu May 24, 2007 10:39 am
Gerd Isenberg Thu May 24, 2007 11:36 am
H.G.Muller Thu May 24, 2007 11:55 am
Gerd Isenberg Thu May 24, 2007 7:46 pm
Robert Hyatt Thu May 24, 2007 8:18 pm
Gerd Isenberg Thu May 24, 2007 8:55 pm
Uri Blass Fri May 25, 2007 10:44 am
Re: question about symmertic evaluation Gerd Isenberg Fri May 25, 2007 6:28 pm
Uri Blass Fri May 25, 2007 7:42 pm
Gerd Isenberg Fri May 25, 2007 8:00 pm
Robert Hyatt Thu May 24, 2007 8:13 pm
Gerd Isenberg Thu May 24, 2007 8:33 pm
Robert Hyatt Sat May 26, 2007 1:05 am
Gerd Isenberg Sat May 26, 2007 7:18 am
Robert Hyatt Sat May 26, 2007 5:08 pm
Robert Hyatt Sat May 26, 2007 5:25 pm
Gerd Isenberg Sat May 26, 2007 6:23 pm
Robert Hyatt Sun May 27, 2007 2:48 pm
Steven Edwards Thu May 24, 2007 3:42 am
Robert Hyatt Thu May 24, 2007 8:20 pm
Robert Hyatt Wed May 23, 2007 9:50 pm
William H. Rogers Fri May 25, 2007 7:48 pm
Uri Blass Sat May 26, 2007 11:38 am
H.G.Muller Sat May 26, 2007 2:07 pm
Vincent Diepeveen Sat May 26, 2007 7:27 pm
Gerd Isenberg Sat May 26, 2007 8:20 pm
Uri Blass Sat May 26, 2007 9:29 pm

 Jump to: Select a forum Computer Chess Club Forums----------------Computer Chess Club: General TopicsComputer Chess Club: Tournaments and MatchesComputer Chess Club: Programming and Technical DiscussionsComputer Chess Club: Engine Origins Other Forums----------------Chess Thinkers ForumForum Help and Suggestions
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum

Powered by phpBB © 2001, 2005 phpBB Group
Enhanced with Moby Threads