aki.の月記

■[将棋] プリフェッチ始めました

今年のキーワードは「妥協しない」なので*1、C#の優雅な面はいっせさんに任せて(?)、自分は手始めに、やらないと宣言してたプリフェッチをやってみることにしました。

ネタ元は↓ここ。

http://d.hatena.ne.jp/issei_y/20100501/1272668964

先に結論を書くと、効果の程は、NPSにして5%前後。何故か並列探索時に効果が高かったりとかもしました。

そして実装。↓

まずはC++のコードから。

#include <intrin.h>
extern "C" {

__declspec(dllexport) void CPUID(int CPUInfo[4], int InfoType) {
    __cpuid(CPUInfo, InfoType);
}

__declspec(dllexport) void Prefetch128(void* ptr) {
    char* addr = static_cast<char*>(ptr);
    _mm_prefetch(addr + 0, _MM_HINT_T2);
    _mm_prefetch(addr + 64, _MM_HINT_T2);
}

__declspec(dllexport) void Prefetch256(void* ptr) {
    char* addr = static_cast<char*>(ptr);
    _mm_prefetch(addr + 0, _MM_HINT_T2);
    _mm_prefetch(addr + 64, _MM_HINT_T2);
    _mm_prefetch(addr + 128, _MM_HINT_T2);
    _mm_prefetch(addr + 192, _MM_HINT_T2);
}

// ↓ /nodefaultlib対策
// BOOL WINAPI _DllMainCRTStartup(HANDLE, DWORD, LPVOID lpReserved) {
int __stdcall _DllMainCRTStartup(void*, int, void*) {
    return 1;
}

}

Blunderの置換表は1エントリ32byteを最大8個まで読むので、256バイトのプリフェッチ。

でも必ず8個とも限らなかったり、プリフェッチしても置換表を読みに行かない(その前に枝刈りが発動してしまうなど)ケースもあり得るので比較用に128バイトバージョンも。

あとついでに一応CPUID。

そしてこれをコンパイルする適当バッチファイル。(自分の環境以外で動かす事はあんまり考えてません。VS90とかMSSDKとか。)

@echo off
setlocal ENABLEDELAYEDEXPANSION

if exist "%VS90COMNTOOLS%vsvars32.bat" call "%VS90COMNTOOLS%vsvars32.bat"

call "%MSSdk%\Bin\SetEnv.Cmd" /Release /x86
cl NativeCode.cpp /Fe.\x86\NativeCode.dll /O2 /GS- /GL /LD /link /LTCG /nodefaultlib

call "%MSSdk%\Bin\SetEnv.Cmd" /Release /x64
cl NativeCode.cpp /Fe.\x64\NativeCode.dll /O2 /favor:AMD64 /GS- /GL /Fa /LD /link /LTCG /nodefaultlib

そして最後にC#。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;
using System.IO;
using System.Runtime.InteropServices;
using System.ComponentModel;
using System.Security;

namespace Blunder.NativeCodes {
    /// <summary>
    /// ネイティブコード
    /// </summary>
    public static unsafe class NativeCode {
        /// <summary>
        /// 初期化
        /// </summary>
        static NativeCode() {
            // 32bit/64bitに対応するための黒魔術
            IntPtr handle;
            if (IntPtr.Size == 8) {
                handle = LoadLibrary(Path.Combine(AppDomain.CurrentDomain.BaseDirectory, "NativeCodes", "x64", "NativeCode.dll"));
            } else {
                Debug.Assert(IntPtr.Size == 4);
                handle = LoadLibrary(Path.Combine(AppDomain.CurrentDomain.BaseDirectory, "NativeCodes", "x86", "NativeCode.dll"));
            }
            if (handle == IntPtr.Zero) {
                throw new Win32Exception();
            }

            // CPUIDも適当に。
            int* CPUInfo = stackalloc int[4];
            CPUID(CPUInfo, 1);
            HasMMX = (CPUInfo[3] & (1 << 23)) != 0;
            HasSSE = (CPUInfo[3] & (1 << 25)) != 0;
            HasSSE2 = (CPUInfo[3] & (1 << 26)) != 0;
            HasSSE3 = (CPUInfo[2] & (1 << 0)) != 0;
        }

        #region CPUID結果

        /// <summary>
        /// MMXをサポートしているかどうか
        /// </summary>
        public static bool HasMMX { get; private set; }
        /// <summary>
        /// SSEをサポートしているかどうか
        /// </summary>
        public static bool HasSSE { get; private set; }
        /// <summary>
        /// SSE2をサポートしているかどうか
        /// </summary>
        public static bool HasSSE2 { get; private set; }
        /// <summary>
        /// SSE3をサポートしているかどうか
        /// </summary>
        public static bool HasSSE3 { get; private set; }

        #endregion

        #region DllImport

        [DllImport("kernel32", CharSet = CharSet.Auto, SetLastError = true)]
        static extern IntPtr LoadLibrary(string lpFileName);

        /// <summary>
        /// Generates the cpuid instruction that is available on x86 and x64. This instruction queries the processor for information about the supported features and CPU type.
        /// </summary>
        /// <param name="CPUInfo">An array of four integers that contains the gathered information about supported features and the CPU.</param>
        /// <param name="InfoType">A code that indicates what information this instruction retrieves.</param>
        [DllImport("NativeCode", CharSet = CharSet.None, ExactSpelling = true, CallingConvention = CallingConvention.Cdecl)]
        [SuppressUnmanagedCodeSecurity]
        public static extern void CPUID(int* CPUInfo, int InfoType);

        /// <summary>
        /// 128byteのプリフェッチを行う
        /// </summary>
        /// <param name="ptr">prefetchする先頭アドレス</param>
        [DllImport("NativeCode", CharSet = CharSet.None, ExactSpelling = true, CallingConvention = CallingConvention.Cdecl)]
        [SuppressUnmanagedCodeSecurity]
        public static extern void Prefetch128(void* ptr);

        /// <summary>
        /// 256byteのプリフェッチを行う
        /// </summary>
        /// <param name="ptr">prefetchする先頭アドレス</param>
        [DllImport("NativeCode", CharSet = CharSet.None, ExactSpelling = true, CallingConvention = CallingConvention.Cdecl)]
        [SuppressUnmanagedCodeSecurity]
        public static extern void Prefetch256(void* ptr);

        #endregion
    }
}

多少なりとも早くなりそうなオプションは、計測もせずゴテゴテ指定してみました。

DLLは先に一度読み込んであればそれが使われる、というWindowsの仕様を悪用して32bit/64bitに対応してます。

ちなみに.NET 4.0で増えてたPath.Combine()のオーバーロードを初めて使いました。微妙に便利です。

そして置換表クラス。

    public void Prefetch(Board board) {
        ulong hashValue = board.HashValue;
        uint handValue = board.HandValue;
        int key2 = unchecked(((int)hashValue ^ (int)(hashValue >> 32))) & (Capacity - 1);
        NativeCodes.NativeCode.Prefetch128(list + key2);
        //NativeCodes.NativeCode.Prefetch256(list + key2);
        // ↑やってみたら128バイトの方が早かった。
    }

最後に探索部。(一部簡略化)

    // 枝刈り
    value = PreSearchPrunings(context, alpha, max, depth,
        node, state, newState, i, move, moveIsCheck, ref newDepth,
        ref reductionDepth);
    if (value != InvalidEval) return value;

    context.Do(move, 0); // 手を進める (ここでハッシュ値が求まる)
    if (DepthUnit * 1 <= newDepth) { // 深さがあるなら置換表プリフェッチ
        transpositionTable.Prefetch(context.Board);
    }
    // 詰みとか千日手とか色々チェック
    value = PreSearchCheck(context, move, i, node, state);
    if (value == InvalidEval) {
        // 探索 (この中でPVSとかAsplirationSearchとか)
        value = SearchNextNode(context, alpha, beta, max,
            node, i, isRoot, forecastEval, newState, newDepth, reductionDepth);
        // 頓死チェックなど
        value = PostSearchCheck(context, alpha, beta, value,
            node, state, move, i, newDepth);
    }
    context.Undo(move); // 手を戻す

ハッシュ値が求まってから可能な限り早くプリフェッチして、その後に別の処理をやるのがミソです。

stockfishのソースを見てみたら、なんと局面クラスの中でやってますね。