Author: Pat King
Date: 07:32:01 12/03/02
Go up one level in this thread
On December 02, 2002 at 17:34:24, Russell Reagan wrote: >I've never been able to get a clear answer on this. How much time does it take >to allocate memory dynamically, with a call to malloc or new? Are we talking 10 >cycles, 100 cycles, 1000 cycles, or more? > >I ask because I'm considering playing with some object-oriented ideas, but if >it's 1000 cycles to allocate (say) one move object, I could have completely >generated many (or all) of the moves for the position by the time allocation was >complete, and that's no good. If I could find out this information, I could >potentially save myself a lot of work only to find out my performance went into >the toilet. OO is ok, but you have to arrange to do your allocation up front. I use dynamically allocated pieces, but that happens in setboard. Captures don't destroy, undos don't new, they just swap pointers around. The only allocation/destruction that happens within the search is when pawns get promoted. Now that I think of it, a few years ago I was toying with a superpawn class that inherited from all the appropriate pieces, so that even promotions wouldn't have to use new. That was in Pascal, and was pretty unwieldy with single inheritance. Now that I'm working in C++... > >I think there are some interesting issues here, such as using a dynamically >growing array (like std::vector) and not having to worry about making sure I'm >not "too deep" or going to cause a stack overflow, You always have to worry. I use std::vector for my move list, but call reserve on startup with a suitably large number to avoid dynamic reallocation, which would be fatal in the middle of a search, not just for time reasons, but because all the iterators sitting on the stack would be invalidated. I also check bounds in the debug version (this is hidden in asserts in an AddMove function, so its not as painful as you make it sound). >or working with different >sub-classes for different move types. Bad idea for moves. Works for pieces, because you're not allocating in the search. If you have multiple move types, you HAVE to allocate in the search. I just have one type, with a constructor that looks like move::move(square, square, piece = PAWN). Only pawns care about the last argument, everything else avoids the piece field, and the default argument lets it look like you've got multiple types of move. > If allocation is 100 cycles, clearly >that's no good for allocating a new move object _every_ time you generate a >move, but it may not be so bad when using an std::vector, since it only >allocates occasionally. > I had a Pascal engine that used linked lists of moves. VERY slow. As noted earlier, the occasional vector reallocation will kill all your iterators, as well as performance. >Basically, I like the idea of not having to worry about the details of things >like making sure you're within the bounds of an array, and it may be worth a >small performance hit, but I have no idea what the magnitude of the performance >hit is. > You always have to worry about the details, but if you do it right, you only worry about each detail once, in the right place (ie bounds checking in my AddMove function). >Russell Pat, making piddling progress in OO chess programming for over 10 years
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.