Search Degredation w/ C++
Chris Jason Richards
What kind of performance hit does a chess engine coded in C++ take?
I have been told that C++ is approx. 10% slower than C.
Cheers,
cjr
--
_______________________________________________________________________
Chris Richards rich...@tamu.edu | Texas A&M University
Project Coordinator | Department of Computer Science
http://www.cs.tamu.edu/people/richards | Internet Publishing Services
A bus stops at a bus station; a train stops at a train station.
On my desk I have a workstation...
Robert Hyatt
Chris Jason Richards (rich...@www.cs.tamu.edu) wrote:
: What kind of performance hit does a chess engine coded in C++ take?
: I have been told that C++ is approx. 10% slower than C.
: Cheers,
: cjr
program it right, and there is *no* hit at all. You can use the c++
style, without going head-over-heels into creating objects. Joel
Rivat has written such a program using bitmaps and is just as fast
as Crafty... him in C++, me in carefully coded C.
Brian Sheppard
Chris Jason Richards <rich...@www.cs.tamu.edu> wrote in article
<5nphtt$r...@news.tamu.edu>...
> What kind of performance hit does a chess engine coded in C++ take?
> I have been told that C++ is approx. 10% slower than C.
The performance degradation entirely depends on your coding style.
If you understand the compilation models of the c++ language, then
you can avoid any hit whatsoever.
For chess programs: use "C-like" coding style throughout the search
engine, but feel free to use all object-oriented mechanisms is the
remainder of the program. If you follow this guideline you won't
notice any speed difference.
Brian
Amir Ban
Junior is written entirely in C++ (Borland). The entire search engine is
the implementation of class 'Position'. One statement that cannot be
said about Junior is that it is slow.
I've heard these kinds of performance arguments about C++ several times
in the past. As a C++ veteran in many projects, I'm quite mystified
about what is supposed to be slow about the language.
Amir
Robert Hyatt
Amir Ban (ami...@msys.co.il) wrote:
: Amir
it comes from the classic idea of constructing "objects" repeatedly. IE,
imagine an object "position" where each time you make a move you first
create a new position, and to unmake you destroy the position, which would
be a classic OO approach. And would be slow as all hell, too. Of course,
doing this is C, using malloc() would be just as slow... The trick is to
take "most" of the OO ideas of coding, but leaving the "create" stuff out.
And then you are correct, it will run just like C.
brucemo
Amir Ban wrote:
> I've heard these kinds of performance arguments about C++ several times
> in the past. As a C++ veteran in many projects, I'm quite mystified
> about what is supposed to be slow about the language.
Some people write these incredible byzantine class hierarchies and expect
the compiler to optimize everything for them, but they don't check to see
if the compiler is actually doing this properly.
You can only expect a compiler to inline so much stuff.
I am not a big C++ expert, but one of the problems I have seen was with
an application where folks decided to do error trapping via try/catch,
and this slowed *everything* down.
bruce
Ren Wu
Would you tell us what is Junior's NPS on a typical hardware, like
PPro200 and P133? Thanks.
Ren
On Mon, 16 Jun 1997 13:55:00 +0300, Amir Ban <ami...@msys.co.il>
wrote:
>Brian Sheppard wrote:
>>
>> Chris Jason Richards <rich...@www.cs.tamu.edu> wrote in article
>> <5nphtt$r...@news.tamu.edu>...
>> > What kind of performance hit does a chess engine coded in C++ take?
>> > I have been told that C++ is approx. 10% slower than C.
>>
>> The performance degradation entirely depends on your coding style.
>> If you understand the compilation models of the c++ language, then
>> you can avoid any hit whatsoever.
>>
>> For chess programs: use "C-like" coding style throughout the search
>> engine, but feel free to use all object-oriented mechanisms is the
>> remainder of the program. If you follow this guideline you won't
>> notice any speed difference.
>>
>> Brian
>
>
>Junior is written entirely in C++ (Borland). The entire search engine is
>the implementation of class 'Position'. One statement that cannot be
>said about Junior is that it is slow.
>
>I've heard these kinds of performance arguments about C++ several times
>in the past. As a C++ veteran in many projects, I'm quite mystified
>about what is supposed to be slow about the language.
>
>Amir
Valavan Manohararajah
In article <33A51B...@msys.co.il>, Amir Ban <ami...@msys.co.il> wrote:
>Junior is written entirely in C++ (Borland). The entire search engine is
>the implementation of class 'Position'. One statement that cannot be
>said about Junior is that it is slow.
>
>I've heard these kinds of performance arguments about C++ several times
>in the past. As a C++ veteran in many projects, I'm quite mystified
>about what is supposed to be slow about the language.
>
>Amir
It may depend on your definition of slowness... Do you consider a few
clock ticks to be slow? I have done some game programming in the good
old DOS days with VGA cards.... and man, we were trying to save every
single clock tick possible.
C++ passes in the "this" pointer into many functions. Virtual Functions which
are the foundations of extendable classes are slow. Of course, we have to
talk about the good side of C++ also.... inline functions. For chess
programs, I doubt you use Virtual Functions. But still, would you expect
a GUI app written in MFC to be faster than regular Win32 programming... I
did write some graphic apps in the past with both, and the speed difference
was noticeable - but from a design point of view, MFC version looked simpler.
I think the comparison between C and C++ is kind of like assembly and C.
Although you gain the advantages of an object oriented language like C++,
you move away from the functional type of language that is close to assembly.
Amir Ban
Robert Hyatt wrote:
>
> Amir Ban (ami...@msys.co.il) wrote:
>
> : Junior is written entirely in C++ (Borland). The entire search engine is
> : the implementation of class 'Position'. One statement that cannot be
> : said about Junior is that it is slow.
>
> : I've heard these kinds of performance arguments about C++ several times
> : in the past. As a C++ veteran in many projects, I'm quite mystified
> : about what is supposed to be slow about the language.
>
> : Amir
>
> imagine an object "position" where each time you make a move you first
> create a new position, and to unmake you destroy the position, which would
> be a classic OO approach. And would be slow as all hell, too. Of course,
> doing this is C, using malloc() would be just as slow... The trick is to
> take "most" of the OO ideas of coding, but leaving the "create" stuff out.
> And then you are correct, it will run just like C.
Creating a new Position and detroying it for every node is indeed the
classic OOP approach, and also exactly what my program does. Your
assumption that this involves "malloc" (or "new") is the incorrect one.
mallocing a Position whenever you need one is as unnecesary and silly as
mallocing an int every time you want to do a loop. You should malloc
something when you want it to have dynamic lifetime and/or scope.
You can create an object as you create an int, by putting it as an auto
variable on the stack, e.g. :
alphabeta(...)
{
...
Position newPosition;
...
}
This constructs a Position at the point of declaration and destroys it
on the exit from the block. The constructor and destructor do exactly
what you code in them of course. No more, no less.
The overhead for this is not low. It's zero.
Amir
Mike Tiller
Amir Ban <ami...@msys.co.il> writes:
> Creating a new Position and detroying it for every node is indeed the
> classic OOP approach, and also exactly what my program does. Your
> assumption that this involves "malloc" (or "new") is the incorrect one.
> mallocing a Position whenever you need one is as unnecesary and silly as
> mallocing an int every time you want to do a loop. You should malloc
> something when you want it to have dynamic lifetime and/or scope.
>
> You can create an object as you create an int, by putting it as an auto
> variable on the stack, e.g. :
>
> alphabeta(...)
> {
> ...
> Position newPosition;
> ...
> }
>
> This constructs a Position at the point of declaration and destroys it
> on the exit from the block. The constructor and destructor do exactly
> what you code in them of course. No more, no less.
>
> The overhead for this is not low. It's zero.
>
> Amir
Another approach is to keep a stash of premalloced "Positions" (or any
object for that matter) around and then grab one from the stash when
you call an overloaded operator new and put it back when you call
overloaded operator delete.
The advantage of this approach over the automatic variable one is that
you can have objects of variable size. Picking the ones out of your
stash that are already the correct size. You also get the benefit
that the objects don't have to be in a particular scope. The problem
is there will be some overhead associated with this method, but not as
much as with reallocating the memory every time.
--
Mike
Brian Sheppard
Amir Ban <ami...@msys.co.il> wrote in article
<33A6B4...@msys.co.il>...
> {
> ...
> Position newPosition;
> ...
> }
>
> This constructs a Position at the point of declaration and destroys it
> on the exit from the block. The constructor and destructor do exactly
> what you code in them of course. No more, no less.
>
> The overhead for this is not low. It's zero.
While it is true that this has no object-oriented overhead, you
should still consider using incrementally-updated positions. On
PC-class architectures this is way, way faster than constructing
a new position, because memory bandwidth is very low relative to
CPU speed (and cache size) on PCs. The imbalance gets larger
with each successive generation of Intel hardware.
Brian
Robert Hyatt
Brian Sheppard (bri...@mstone.com) wrote:
: Amir Ban <ami...@msys.co.il> wrote in article
: Brian
You are correct of course. When I went from doing something like:
new_position=MakeMove(old_position,move);
to
MakeMove(move);
...
...
UnMakeMove(move);
Crafty became about 30% faster, because memory bandwidth is so very
bad on the Intel boxes...
Robert Hyatt
Amir Ban (ami...@msys.co.il) wrote:
: Robert Hyatt wrote:
: >
: > Amir Ban (ami...@msys.co.il) wrote:
: >
: > : the implementation of class 'Position'. One statement that cannot be
: > : said about Junior is that it is slow.
: >
: > : I've heard these kinds of performance arguments about C++ several times
: > : in the past. As a C++ veteran in many projects, I'm quite mystified
: > : about what is supposed to be slow about the language.
: >
: > : Amir
: >
: > it comes from the classic idea of constructing "objects" repeatedly. IE,
: > imagine an object "position" where each time you make a move you first
: > create a new position, and to unmake you destroy the position, which would
: > be a classic OO approach. And would be slow as all hell, too. Of course,
: > doing this is C, using malloc() would be just as slow... The trick is to
: > take "most" of the OO ideas of coding, but leaving the "create" stuff out.
: > And then you are correct, it will run just like C.
: Creating a new Position and detroying it for every node is indeed the
: classic OOP approach, and also exactly what my program does. Your
: assumption that this involves "malloc" (or "new") is the incorrect one.
: mallocing a Position whenever you need one is as unnecesary and silly as
: mallocing an int every time you want to do a loop. You should malloc
: something when you want it to have dynamic lifetime and/or scope.
: You can create an object as you create an int, by putting it as an auto
: variable on the stack, e.g. :
: alphabeta(...)
: {
: ...
: Position newPosition;
: ...
: }
: This constructs a Position at the point of declaration and destroys it
: on the exit from the block. The constructor and destructor do exactly
: what you code in them of course. No more, no less.
: The overhead for this is not low. It's zero.
It's not zero by a long shot. Someone still has to allocate memory and
free it on procedure exit so far as I understand programming languages.
This is just like doing the above in C. It is slower than allocating
everything before you start, and then use a subscript into an array,
or a pointer into the block of malloc'ed stuff. The only way you "might"
get away with zero overhead would be to run on a machine with enough
registers that it could put the entire "Position" thing in registers,
and never have to store them, assuming you never call any procedures
from within the place where you use the above. With alpha/beta that
isn't going to work because of the recursive calls.
Try doing it by creating an array of "Position" things, and indexing into
the array. I'd bet it will be faster if you do this (probably using a
pointer rather than an array index is better...)
: Amir
brucemo
> > >
> > > Amir Ban (ami...@msys.co.il) wrote:
> > >
> >
> > alphabeta(...)
> > {
> > ...
> > Position newPosition;
> > ...
> > }
> >
> > This constructs a Position at the point of declaration and destroys it
> > on the exit from the block. The constructor and destructor do exactly
> > what you code in them of course. No more, no less.
> >
> > The overhead for this is not low. It's zero.
>
> should still consider using incrementally-updated positions. On
> PC-class architectures this is way, way faster than constructing
> a new position, because memory bandwidth is very low relative to
> CPU speed (and cache size) on PCs. The imbalance gets larger
> with each successive generation of Intel hardware.
We don't know what is in a "position" object. It may be just a few
variables that are used to make and unmake a move. There would be no more
overhead to this than there would be to declaring a structure on the stack,
i.e. zero.
I have some familiarity with Junior. It is fast and strong, so it's not
like Amir is doing something dumb.
bruce
Mike Tiller
hy...@crafty.cis.uab.edu (Robert Hyatt) writes:
> : You can create an object as you create an int, by putting it as an auto
> : variable on the stack, e.g. :
>
> : alphabeta(...)
> : {
> : ...
> : Position newPosition;
> : ...
> : }
>
> : This constructs a Position at the point of declaration and destroys it
> : on the exit from the block. The constructor and destructor do exactly
> : what you code in them of course. No more, no less.
>
> : The overhead for this is not low. It's zero.
>
> It's not zero by a long shot. Someone still has to allocate memory and
> free it on procedure exit so far as I understand programming languages.
> This is just like doing the above in C. It is slower than allocating
> everything before you start, and then use a subscript into an array,
> or a pointer into the block of malloc'ed stuff. The only way you "might"
> get away with zero overhead would be to run on a machine with enough
> registers that it could put the entire "Position" thing in registers,
> and never have to store them, assuming you never call any procedures
> from within the place where you use the above. With alpha/beta that
> isn't going to work because of the recursive calls.
>
> Try doing it by creating an array of "Position" things, and indexing into
> the array. I'd bet it will be faster if you do this (probably using a
> pointer rather than an array index is better...)
>
> : Amir
Well, it could be zero. If the "Position" class has a static member
array like Crafty for positions and the constructor call is inlined
and amounts to:
MakeMove(move)
and the destructor call is inlined and amounts to
UnMakeMove(move)
Then it seems like it would be absolutely no different than Crafty
right? The only other thing you might need would be a single member
integer to index the stack of positions perhaps. No wait...even that
could be a static member I guess.
I'd like to point out that this is one of the nice things about
encapsulation. You could do it the slow way and then realize later
that you could do it faster but the code wouldn't necessarily have to
change.
--
Mike
Don Fong
In article <5obfob$1...@juniper.cis.uab.edu>,
>: {
>: ...
>: Position newPosition;
>: ...
>: }
>
>: This constructs a Position at the point of declaration and destroys it
>: on the exit from the block. The constructor and destructor do exactly
>: what you code in them of course. No more, no less.
>
>: The overhead for this is not low. It's zero.
>
>It's not zero by a long shot. Someone still has to allocate memory and
>free it on procedure exit so far as I understand programming languages.
no, it doesn't malloc/free the Position object. it just makes
the stack frame that much bigger.
>This is just like doing the above in C.
true, but it wouldn't do malloc/free in C either.
however, this is not to say that "the cost is zero", necessarily.
>It is slower than allocating
>everything before you start, and then use a subscript into an array,
>or a pointer into the block of malloc'ed stuff.
you can play tricks to approximate this behavior in C++,
by overriding the "new" operator. in some cases it is desirable
to keep around "partially constructed" objects instead of completely
destroying them and then having to completely construct them again next
time you need one. you can bet Amir Ban knows about this kind of trick.
David Hanley
Robert Hyatt wrote:
> : alphabeta(...)
> : {
> : ...
> : Position newPosition;
> : ...
> : }
>
> : This constructs a Position at the point of declaration and destroys
> it
> : on the exit from the block. The constructor and destructor do
> exactly
> : what you code in them of course. No more, no less.
>
> : The overhead for this is not low. It's zero.
>
> It's not zero by a long shot. Someone still has to allocate memory
> and
> free it on procedure exit so far as I understand programming
> languages.
I hate to do this, but I have to differ with you here. In C or C++,
you must
make a frame of the stack for a function call. All the above does is to
make
the stack frame a little bit larger. It shouldn't cost anything extra
above and beyond
a regular function call, assuming the constructor is inlined ( e.g. no
heap allocation ).
> This is just like doing the above in C.
Well, yes:
C:
typedef struct Move { .. };
alphaBeta( .. )
{
Move m;
}
Once again just does cheap,cheap (free) stack allocation.
dave
Robert Hyatt
Mike Tiller (mti...@ptrs08.srl.ford.com) wrote:
: Well, it could be zero. If the "Position" class has a static member
: array like Crafty for positions and the constructor call is inlined
: and amounts to:
: MakeMove(move)
: and the destructor call is inlined and amounts to
: UnMakeMove(move)
: Then it seems like it would be absolutely no different than Crafty
: right? The only other thing you might need would be a single member
: integer to index the stack of positions perhaps. No wait...even that
: could be a static member I guess.
: I'd like to point out that this is one of the nice things about
: encapsulation. You could do it the slow way and then realize later
: that you could do it faster but the code wouldn't necessarily have to
: change.
Actually, this was what I had suggested earler in the C++ thread. I like
the syntax for C++, such as position.MakeMove(move) and such, but I don't
like the "full-blown" OO approach of creating/destroying position. I did
just this in regular C many versions of Crafty ago, because on a Cray, you
have memory bandwidth that can keep up with the CPU (ie I can store a word
every cycle for as long as I care to keep that going, or I can load two
words per cycle for as along as I care as well, but on a PC, I can load a
word every 20 cycles or so, which is not in the same planet, much less
the same ballpark.)
Later, I did away with the copying stuff, and took a big jump in performance
on the PC, with a slight performance penalty on the Cray, which I really didn't
care about anyway...
One day we'll get a decent memory architecture on a PC and this will all be
moot...
But I stand by my original statement, writing a program in C++ does not have
to incure *any* penalty at all, but it *can* incur a big penalty if care is
not exercised... Of course, using regular C can also produce slow programs
if done wrong. :)
Robert Hyatt
David Hanley (da...@nospan.netright.com) wrote:
: Robert Hyatt wrote:
: Well, yes:
: dave
Sorry... I really mixed two ideas when I wrote this. I just returned from
a visit to the University of Waterloo, and after no sleep last night, my
writing right in sync with my brain, which was dead. :)
the problem I was thinking about I explained in a later post. When you
create positions like this, there is a definite cost, because you have to
copy an old position to the new position, and then update it by making some
move. That copy is a killer. As I found out in earlier versions of Crafty
that operated like this, before I converted to make/unmake on a simple
statically allocated global position. The global position works much better,
because it sticks in cache. the copying died on a PC, although it was much
faster on the Cray. When I took the copying out, the cray version slowed
down quite a bit, but the PC version went almost 2x faster after all was
finished...
Amir Ban
> : > : the implementation of class 'Position'. One statement that cannot be
> : > : said about Junior is that it is slow.
> : >
> : > : I've heard these kinds of performance arguments about C++ several times
> : > : in the past. As a C++ veteran in many projects, I'm quite mystified
> : > : about what is supposed to be slow about the language.
> : >
> : > : Amir
> : >
> : > it comes from the classic idea of constructing "objects" repeatedly. IE,
> : > imagine an object "position" where each time you make a move you first
> : > create a new position, and to unmake you destroy the position, which would
> : > be a classic OO approach. And would be slow as all hell, too. Of course,
> : > doing this is C, using malloc() would be just as slow... The trick is to
> : > take "most" of the OO ideas of coding, but leaving the "create" stuff out.
> : > And then you are correct, it will run just like C.
>
> : Creating a new Position and detroying it for every node is indeed the
> : classic OOP approach, and also exactly what my program does. Your
> : assumption that this involves "malloc" (or "new") is the incorrect one.
> : mallocing a Position whenever you need one is as unnecesary and silly as
> : mallocing an int every time you want to do a loop. You should malloc
> : something when you want it to have dynamic lifetime and/or scope.
>
> : variable on the stack, e.g. :
>
[snip]
> : The overhead for this is not low. It's zero.
>
> It's not zero by a long shot. Someone still has to allocate memory and
> free it on procedure exit so far as I understand programming languages.
> This is just like doing the above in C. It is slower than allocating
> everything before you start, and then use a subscript into an array,
> or a pointer into the block of malloc'ed stuff. The only way you "might"
> get away with zero overhead would be to run on a machine with enough
> registers that it could put the entire "Position" thing in registers,
> and never have to store them, assuming you never call any procedures
> from within the place where you use the above. With alpha/beta that
> isn't going to work because of the recursive calls.
>
No, that's wrong.
There is no overhead involved in putting objects as auto variables. All
auto variables go on the stack, and the "allocation" is done by the
function prologue in decrementing the stack pointer by the total amount
of memory needed by the function. The only thing that changes when
declaring an auto object is to increase the amount subtracted. "Freeing"
is even simpler, and consists of reverting the original stack pointer,
which does not depend at all on what was allocated.
Try this with your favorite compiler and look at the assembler listings.
Getting back to my original point, the object-oriented approach in C++,
up to simple inheritance, is very successful performance-wise, since the
semantics are almost exclusively done compile-time without any run-time
penalty. A small exception is virtual functions, which need a pointer
indirection for the function entry-point, which does not need to be more
than one machine instruction anyway. Multiple-inheritance is something
different. Although it's not terribly inefficient, it does make a
headache for the compiler (and for the developer even more), so I stay
away from it. Multiple-inheritance is anyway not in great need, and in
Java it was simply abolished.
> Try doing it by creating an array of "Position" things, and indexing into
> the array. I'd bet it will be faster if you do this (probably using a
> pointer rather than an array index is better...)
>
I'm quite sure it will be slower not faster. Would you care to put a sum
of money following the "I'd bet ... " ?
Amir
This stuff put in to bypass ultra-idiotic new server rules:
<encoded_portion_removed>
Jon Dart
One thing I haven't seen mentioned on this thread is that often creating
arrays of objects in C++ is quite expensive. E.g. if you have a Move
class, even if it is a pretty simple one, and you do:
Move *moves = new Move[100];
Then often the compiler will allocate the memory and call the Move
constructor in a loop for each variable. Very expensive. You can get
around this by declaring the array static, like this:
static Move moves[100];
and then it will get created and initialized only once, at startup time.
(Note that this initialization problem exists even if you use stack
memory instead of heap memory, as Move moves[100] on the stack of
a frequently called function will also cost you initialization time).
If your code is structured so that static variables can't work (like, you
are using this array inside a recursive function, or from multiple
threads), then you can bypass the compiler's initialization by doing a
malloc and memset that put the same bytes into the Move array that the
compiler would, only faster. For example:
char *stuff = malloc(100*sizeof(Move));
memset(stuff,'\0',100*sizeof(Move));
Move *moves = (Move*)stuff;
Other tricks have been mentioned, such as overriding new - this is a
also a good technique and I use it in places, but generally I think
the tricks mentioned above are better.
--Jon
Robert Hyatt
Amir Ban (ami...@msys.co.il) wrote:
: [snip]
: No, that's wrong.
: Amir
Sorry... I wrote the above way late, and was thinking about "A" while
writing about "B"... I was "thinking" (if it can be called that) about
the problem of creating a new position at each node in the search, which
is certainly bad... because of the memory traffic needed, assuming the
"position" includes the chess board. Mine is *real* short thanks to
bitmaps, but it still was a performance killer. Make/UnMake is much
faster on the PC type machines, although it is much worse on machines
with a lot of memory bandwidth like the Cray (at least.)
In any case, auto variables are trivial compiler optimizations as you
say... and creating them doesn't have much of a cost, but the work to
copy the old position to the new and then update it is bad...
brucemo
Robert Hyatt wrote:
> the problem I was thinking about I explained in a later post. When you
> create positions like this, there is a definite cost, because you have to
> copy an old position to the new position, and then update it by making some
> move.
I can make something called "position" and put an "int" in it. If that's all
there is in it, no big deal.
If I put 256 bytes of board in there, or something, and do a lot of copying
in my constructors, and make these things all over the place for no apparent
reason, then yes, I will slug.
We don't know what Amir has put in his position object. I assume that he
knows what he is doing, and has put something reasonable in there, so cool.
I assume that (Bob) you also know how to program, so also cool.
Is this the end of this particular sub-thread? I don't think you guys are
arguing about anything, once you know what each other is saying.
You can zap yourself with C++ though, right? For instance, you can take the
compiler documentation literally and assume that it knows something about
inlining functions, which might be wrong. Also, you can try/catch yourself
into the dirt.
bruce
Robert Hyatt
brucemo (bru...@seanet.com) wrote:
: Robert Hyatt wrote:
: > the problem I was thinking about I explained in a later post. When you
: > create positions like this, there is a definite cost, because you have to
: > copy an old position to the new position, and then update it by making some
: > move.
: I can make something called "position" and put an "int" in it. If that's all
: there is in it, no big deal.
: If I put 256 bytes of board in there, or something, and do a lot of copying
: in my constructors, and make these things all over the place for no apparent
: reason, then yes, I will slug.
: We don't know what Amir has put in his position object. I assume that he
: knows what he is doing, and has put something reasonable in there, so cool.
: I assume that (Bob) you also know how to program, so also cool.
I didn't mean to imply that he didn't... he didn't start the original thread,
someone asked about C vs C++ and I responded that either can produce code
just as fast as the other, so long as the programmer doesn't get carried
away with a full OO-type approach.
I've played "junior" (ban) many times on ICC. I agree that he knows what
he's doing and didn't mean to imply otherwise. However, I wouldn't call a
"int" a "position", because there's no way to make that work... IE, this
can be done two ways, make/unmake, or copy/update so that the unmake isn't
needed because the original and new positions both exist at the same time..
: Is this the end of this particular sub-thread? I don't think you guys are
: arguing about anything, once you know what each other is saying.
: You can zap yourself with C++ though, right? For instance, you can take the
: compiler documentation literally and assume that it knows something about
: inlining functions, which might be wrong. Also, you can try/catch yourself
: into the dirt.
: bruce
yep. But you can also do bad things in C, or FORTRAN, or APL or most any
language. In this case, OO programming looks nice, and can run like the
blazes. It can also be a slug. Main point? It's not the language, it's the
programmer...
Chris Jason Richards
In article <5ofgdt$l...@juniper.cis.uab.edu>,
hy...@crafty.cis.uab.edu (Robert Hyatt) writes:
>
> Sorry... I wrote the above way late, and was thinking about "A" while
> writing about "B"... I was "thinking" (if it can be called that) about
> the problem of creating a new position at each node in the search, which
> is certainly bad... because of the memory traffic needed, assuming the
> "position" includes the chess board. Mine is *real* short thanks to
> bitmaps, but it still was a performance killer. Make/UnMake is much
> faster on the PC type machines, although it is much worse on machines
> with a lot of memory bandwidth like the Cray (at least.)
>
> In any case, auto variables are trivial compiler optimizations as you
> say... and creating them doesn't have much of a cost, but the work to
> copy the old position to the new and then update it is bad...
>
On Make/UnMake...
So, instead of generating successors of the current game state in your
search algorithms (which can obviously hog memory on recursive calls), AND
instead of creating a game state for each node, you Make() a move, update
the game state, compute what you need to compute (and possibly Make()
another move), ... and then when you need to go down a different part of
the tree you UnMake() until you are at your branching node and then
start Make()'ing again.
How do you store the "move" information for "unmoves". My guess would
be that you save things like what piece from "here" to "there" as well
as the piece taken (and any other "states" that chess requires). Is
this information pushed onto a stack or is memory for the storage it
requires created on the fly? Or does Make/UnMake only allow for a depth
of 1? I can see how this would be more efficient than creating the
entire board again and again...
Thanks,
Robert Hyatt
: On Make/UnMake...
My move is a "complete" move... from, to, moving piece and captured
piece. So I can completely make or unmake the move, based only on the
info in the move (it also has promote_to, which I forgot, so that a complete
move takes 21 bits in "crafty format."
make/unmake don't need any info at all, other than the current position,
which is global, and the move which is passed in as a formal parameter.
The search has a large list that it uses to maintain the move list for
all the plies. I have a "move_list[n] array, and a last[ply] array
which points to the last move for "ply" (last[ply-1] points to the first
move)...
In the original crafty search, I used what would be very efficient on the
Cray, namely position[ply+1]=MakeMove(position[ply],move); which worked
like a demon on the Cray, but on the PC, with barely adequate memory bandwidth,
it choked badly...
Urban Koistinen
Mon, 16 Jun 1997 09:58:41 -0700 brucemo wrote:
! Amir Ban wrote:
! > I've heard these kinds of performance arguments about C++ several times
! > in the past. As a C++ veteran in many projects, I'm quite mystified
! > about what is supposed to be slow about the language.
! Some people write these incredible byzantine class hierarchies and expect
! the compiler to optimize everything for them, but they don't check to see
! if the compiler is actually doing this properly.
I like to do this,
having one generic inline move generator and then
have one call per piece&square&more.
Only, I tend to compile the code to assembler and
read the result to verify that the compiler does
the right thing.
! You can only expect a compiler to inline so much stuff.
With gcc, it is working fine.
With MS Visual C++ 1.5 inlining is very limited.
I understand later versions are much better, but
are you saying there are still limits, that it is still
better to do the inlining yourself before compiling?
I know inline is only advice to the compiler, so
implementing it as a call is not a violation of
the C++ Standard.
Urban Koistinen
brucemo
Urban Koistinen wrote:
> With MS Visual C++ 1.5 inlining is very limited.
> I understand later versions are much better, but
> are you saying there are still limits, that it is still
> better to do the inlining yourself before compiling?
I am saying that you have to check. I was involved in a
project where nobody ever checked, and the end-result was
a performance disaster.
I'm not saying YOU didn't check, by the way.
bruce
Robert Hyatt
brucemo (bru...@seanet.com) wrote:
: Urban Koistinen wrote:
: bruce
Also, MSVC 5.0 seems *very* good. 1.5 goes back far enough that
I don't remember it. :)
Ren Wu
On 24 Jun 1997 12:36:32 GMT, hy...@crafty.cis.uab.edu (Robert Hyatt)
wrote:
Yes, MSVC IS very good. If you use -Ob2, it can even inline some
library calls, like memset(), which I use to clean the hashtables.
Acturally, one thing I can't say about my programs is that it is fast!
Last year, when I have some time work on my program, I manage to speed
up by 60 %, and I think, that's it, there is not much left I can do.
But when I do some more work this year, with the help of the tools
like vtune, I get another 50% or so speed up, and I still see a lot of
place I can optimize. Now my chinese chess program searched at 70K nps
on Pentium 133, and my chess program searched at 60k nps. I am sure I
can make it to close 100K, if I spent two months on them! Who knows
what is the limit!
What I mean is, there is always a room to improve. compare to youself,
your program will never be fast enough.
Ren.
brucemo
Jon Dart wrote:
>
> One thing I haven't seen mentioned on this thread is that often creating
> arrays of objects in C++ is quite expensive. E.g. if you have a Move
> class, even if it is a pretty simple one, and you do:
>
> Move *moves = new Move[100];
>
> Then often the compiler will allocate the memory and call the Move
> constructor in a loop for each variable. Very expensive. You can get
> around this by declaring the array static, like this:
>
> static Move moves[100];
I would think that if you were using "new" anywhere in a chess program, and
that if you were concerned about the speed of initialization, then you
shouldn't be using "new", since "new" itself is extremely expensive, right? I
thought "new" was a cover for "malloc", effectively?
bruce
Vincent Diepeveen
>Amir Ban (ami...@msys.co.il) wrote:
>: Robert Hyatt wrote:
>: >
>: > Amir Ban (ami...@msys.co.il) wrote:
>: >
>: > : Junior is written entirely in C++ (Borland). The entire search engine is
>: > : the implementation of class 'Position'. One statement that cannot be
>: > : said about Junior is that it is slow.
>: >
>: > : I've heard these kinds of performance arguments about C++ several times
>: > : in the past. As a C++ veteran in many projects, I'm quite mystified
>: > : about what is supposed to be slow about the language.
>: >
>: > : Amir
>: >
>: > it comes from the classic idea of constructing "objects" repeatedly. IE,
>: > imagine an object "position" where each time you make a move you first
>: > create a new position, and to unmake you destroy the position, which would
>: > be a classic OO approach. And would be slow as all hell, too. Of course,
>: > doing this is C, using malloc() would be just as slow... The trick is to
>: > take "most" of the OO ideas of coding, but leaving the "create" stuff out.
>: > And then you are correct, it will run just like C.
>
>
>: Creating a new Position and detroying it for every node is indeed the
>: classic OOP approach, and also exactly what my program does. Your
>: assumption that this involves "malloc" (or "new") is the incorrect one.
>: mallocing a Position whenever you need one is as unnecesary and silly as
>: mallocing an int every time you want to do a loop. You should malloc
>: something when you want it to have dynamic lifetime and/or scope.
>
>: You can create an object as you create an int, by putting it as an auto
>: variable on the stack, e.g. :
>
>: alphabeta(...)
>: {
>: ...
>: Position newPosition;
>: ...
>: }
>
>: This constructs a Position at the point of declaration and destroys it
>: on the exit from the block. The constructor and destructor do exactly
>: what you code in them of course. No more, no less.
>
>: The overhead for this is not low. It's zero.
>
>It's not zero by a long shot. Someone still has to allocate memory and
>free it on procedure exit so far as I understand programming languages.
>This is just like doing the above in C. It is slower than allocating
>everything before you start, and then use a subscript into an array,
>or a pointer into the block of malloc'ed stuff. The only way you "might"
>get away with zero overhead would be to run on a machine with enough
>registers that it could put the entire "Position" thing in registers,
>and never have to store them, assuming you never call any procedures
>from within the place where you use the above. With alpha/beta that
>isn't going to work because of the recursive calls.
>
>Try doing it by creating an array of "Position" things, and indexing into
>the array. I'd bet it will be faster if you do this (probably using a
>pointer rather than an array index is better...)
>
>: Amir
My interface can be considered C++.
Can anyone explain to me how to declare things in C++ such that
it doesn't become slower?
In the past (2 years ago... ahum) i converted my program to
C++: 'extern C {', and it simply became a lot slower, as soon as
i tried to profit from the fact that i was programming in C++ instead of C.
Vincent
--
+----------------------------------------------------+
| Vincent Diepeveen email: vdie...@cs.ruu.nl |
| http://www.students.cs.ruu.nl/~vdiepeve/ |
+----------------------------------------------------+
Dann Corbit
brucemo <bru...@seanet.com> wrote in article <33B0A2...@seanet.com>...
[snip]
> I would think that if you were using "new" anywhere in a chess program, and
> that if you were concerned about the speed of initialization, then you
> shouldn't be using "new", since "new" itself is extremely expensive, right?
I
> thought "new" was a cover for "malloc", effectively?
For the memory allocation part of new, this is typically correct [though
certainly not required]. Creating a new object also fires the constructor,
which does whatever it is designed to do. Memory allocation in general is
slow, especially if you have a large number of tiny blocks. Allocation of
thousands of tiny blocks of memory is unbelievably slow (whether using malloc
or new). Unless constructor time dominates, it is usually much faster to
create auto variables on the stack [though this technique requires a large
linear address space for the stack and pre-knowledge of how many objects are
needed.]
The new operator does more than malloc does, in that it ensures the firing of
the constructor. If you have an object with a constructor, you should use
new/delete and not malloc/free to do your allocations.
Dan Schmidt
brucemo <bru...@seanet.com> writes:
| I would think that if you were using "new" anywhere in a chess
| program, and that if you were concerned about the speed of
| initialization, then you shouldn't be using "new", since "new"
| itself is extremely expensive, right? I thought "new" was a cover
| for "malloc", effectively?
Well, _by default_, new is a cover for malloc.
Semantically, "new" just means "make me an object that won't go away
when I leave this scope." The default implementation of new is
effectively equivalent to malloc, as you say. But you can override
new based on the kind of object you're creating, and have it do more
intelligent things, like grab one element from a preallocated array.
Same with delete.
It's pretty nice, because you can write your whole program just using
new without worrying about where the memory is coming from, and then
write some custom allocators without affecting any other code.
--
Dan Schmidt -> df...@harmonixmusic.com, df...@alum.mit.edu
Honest Bob & the http://www2.thecia.net/users/dfan/
Factory-to-Dealer Incentives -> http://www2.thecia.net/users/dfan/hbob/
Gamelan Galak Tika -> http://web.mit.edu/galak-tika/www/