Author: Gerd Isenberg
Date: 13:56:37 06/04/05
Go up one level in this thread
On June 03, 2005 at 20:11:33, Dann Corbit wrote:
>On June 03, 2005 at 16:38:23, Gerd Isenberg wrote:
>
>>On June 03, 2005 at 15:28:27, Dann Corbit wrote:
>>
>>>On June 03, 2005 at 13:46:25, Pallav Nawani wrote:
>>>
>>>>On June 03, 2005 at 13:33:52, Dann Corbit wrote:
>>>>
>>>>>On June 03, 2005 at 13:05:58, Peter Fendrich wrote:
>>>>>
>>>>>>On June 02, 2005 at 22:05:10, Dann Corbit wrote:
>>>>>>
>>>>>>>On June 02, 2005 at 20:51:03, Joseph Tadeusz wrote:
>>>>>>>
>>>>>>>>If I reinsert a captured piece into the piece list it is done
>>>>>>>>so at the beginning. This has the result that the pieces in the
>>>>>>>>heart of the action move to the front of the list.
>>>>>>>>
>>>>>>>>I noticed that the resulting order has much better search
>>>>>>>>performance than without such a list and where pieces are
>>>>>>>>searched randomly.
>>>>>>>>
>>>>>>>>It's an unintended but beneficial LRU sorting.
>>>>>>>
>>>>>>>Separate piece lists by type and color.
>>>>>>>
>>>>>>>Better than a single piece list of all pieces.
>>>>>>>
>>>>>>>IMO-YMMV.
>>>>>>
>>>>>>
>>>>>>Why?
>>>>>
>>>>>Lots of reasons. The most important is no switching and no branching.
>>>>
>>>>What are the other reasons? :-)
>>>
>>>The code is also simplified. Instead of looking at a piece in the list and
>>>deciding about its color and type, you know what it is a-priori. Therefore,
>>>move generation, evaluation, and lots of other things have fewer decisions and
>>>are made simpler.
>>
>>Something like serialized bitboards?
>>I guess you mean loop hoisting - instead of one loop over all pieces and
>>switching inside the loop body, you do the switch outside with loops for each
>>case, with small bodies.
>>
>>I like Paul Hsieh's articel about loop hoisting:
>>
>>http://www.azillionmonkeys.com/qed/optimize.html
>>
>>"I was recently working on some performance sensitive code based on the
>>reference source from an enormous software vendor based in Redmond, WA. I was
>>shocked to see that they were making fundamental errors in terms performance
>>optimization. I am talking about simply things like loop hoisting. It got me to
>>thinking that even so called "professional programmers" charged with the goal of
>>optimizing code can miss really totally basic optimizations.
>>...."
>>-----------------------------------------------------------------------
>>
>>OTOH each piece kind loop covers disjoint sets. And each additional loop over up
>>to eight pawns and most likely 0..2 pieces per side has one additional
>>conditional jump to terminate the loop - slightly more difficult to predict
>>while traversing low populated piece sets or lists.
>>
>>>
>>>>Ps: I am now thinking of a Glaurung style piece list in my engine. Any better
>>>>way to do that?
>>>
>>>There is always a better way to do something, though it is not always easy to
>>>find it. Once you have improved it, I will be curious to see the result.
>>>
>>>I think that C99 style automatic arrays are probably a very good way to make
>>>lists, and I don't see anyone doing it.
>>
>>Hmm ... no idea.
>>Can you elaborate about those C99 style automatic arrays?
>>What about keeping piecelists in fixed sized bitboards and to become able to do
>>some setwise aka bitwise operations ;-)
>
>As Deiter pointed out, I really meant VLAs.
>
>Suppose that you have some struct called Move and you want to make an arbitrary
>sized list of moves (suppose that the size is 29 moves right now). You can do
>this:
>
>size_t index;
>size_t movelist_size = MovesCount();
>struct Move MoveList[movelist_size];
>
>MovesGenerate(MoveList);
>MovesQuickSelect(MoveList, movelist_size, 4); // Put 4 best moves on top
>MovesOptimalSort(MoveList, 4); // Order the top 4 moves from best to worst
>for (index = 0; index < 29; index++)
>{
> struct Move current = MoveList[index];
> /* Whatever */
>}
>
>What a VLA will buy you is:
>1. No malloc/calloc/new + free/delete (which are horribly slow)
I see, a variable frame on the stack - eg. on x86 sub esp,eax.
>2. Direct addressing (faster and more compact than a linked list)
>
>As you know, you don't really need them most of the time. In the above example,
>there would be no value to the movelist unless you wanted to do something
>special like store scores in it for comparisons or something like that.
>Otherwise, you could just generate them and not store them in a list at all.
>
>But if you have linked lists or dynamically allocated arrays (other than hash
>tables or something that is allocated only once for the lifetime of a game) then
>a VLA might be a very good alternative.
Yes.
>
>Also, as Dieter mentioned, MS is very backwards here (It is, after all, 6 years
>since 1999 when VLAs were introduced).
>
>Intel C++ handles them correctly, IIRC.
Seems not so hard to implement.
Huge arrays may be problematic, i guess.
With respect to stack size.
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.