Проблема производительности при поиске строки в памяти

Question

Я разрабатываю DLL под Win32, которая делает простую работу: она сканирует виртуальную память хоста на наличие подстроки. Но по какой-то причине он делает это очень медленно по сравнению с Cheat Engine, ArtMoney или даже OllyDbg, который использует один поток для сканирования. Вот код функции, которая сканирует отдельный раздел памяти, который я получил с помощью VirtualQuery(). Хост (приложение.exe) выделяет около 300–400 МБ памяти, и мне приходится сканировать около 170 разделов памяти разного размера от 4 КБ до 32 МБ. Я сканирую только регионы MEM_PRIVATE, MEM_COMMIT, не сканирую PAGE_GUARD, PAGE_NOACCESS, PAGE_READONLY, пропускаю собственную память DLL.

По какой-то причине производительность ужасна - на поиск одной строки уходит 10-12 секунд. Например, OllyDbg находит строку за ~2-3 секунды.

UINT __stdcall ScanAndReplace(UCHAR* pStartAddress, UCHAR* pEndAddress, const char* csSearchFor, const char* csReplaceTo, UINT iLength)
{
    // This function runs inside the single memory section and looks for a specific substring

    // pStartAddress: UCHAR* - The begining of the memory section
    // pEndAddress: UCHAR* - The ending of the memory section
    // csSearchFor: const char* - The pointer to the substring to search for
    // csReplaceTo: const char* - The pointer to the substring to replace with
    // iLength: UINT - max length of csSearchFor substring

    // Total iterations
    UINT iHits = 0;

    // Scan from pStartAddress to (pEndAddress - iLength) and don't overrun memory section
    for (pStartAddress; pStartAddress < (pEndAddress - iLength); ++pStartAddress)
    {
        UINT iIterator = 0;

        // Scan for specific string that begins at current address (pStartAddress) until condition breaks
        for (iIterator; (iIterator < iLength) && (pStartAddress[iIterator] == csSearchFor[iIterator]); ++iIterator);

        // String matches if iIterator == iLength
        if (iIterator == iLength)
        {
            // Found, do something (edit/replace, etc), increment counter...
            ++iHits;
        }

        /*
        // Even if you search for single byte it's very slow
        if (*pStartAddress == 'A')
            ++iHits;
        */
    }

    return iHits;
}

Я использую MSVS 2010.

Командная строка компилятора:

/nologo /W3 /WX- /O2 /Os /Oy- /GL /D "WIN32" /D "NDEBUG" /D "_WINDOWS"
  /D "_USRDLL" /D "MYDLL_EXPORTS" /D "_WINDLL" /GF /Gm- /MD /GS- /Gy
  /fp:precise /Zc:wchar_t /Zc:forScope /Fp"Release\MyDll.pch" /FAcs
  /Fa"Release\" /Fo"Release\" /Fd"Release\vc100.pdb" /Gd /TC /analyze-
  /errorReport:queue

Командная строка компоновщика:

/OUT:"D:\MyDll\Release\MyDll.dll" /INCREMENTAL:NO /NOLOGO /DLL "Dbghelp.lib"
  "msvcrt.lib" "kernel32.lib" "user32.lib" "gdi32.lib" "winspool.lib"
  "comdlg32.lib" "advapi32.lib" "shell32.lib" "ole32.lib" "oleaut32.lib"
  "uuid.lib" "odbc32.lib" "odbccp32.lib" /NODEFAULTLIB /MANIFEST:NO
  /ManifestFile:"Release\MyDll.dll.intermediate.manifest" /ALLOWISOLATION
  /MANIFESTUAC:"level='asInvoker' uiAccess='false'" /DEBUG
  /PDB:"D:\MyDll\Release\MyDll.pdb" /SUBSYSTEM:WINDOWS /OPT:REF /OPT:ICF
  /PGD:"D:\MyDll\Release\MyDll.pgd" /LTCG /TLBID:1 /ENTRY:"DllMain"
  /DYNAMICBASE /NXCOMPAT /MACHINE:X86 /ERRORREPORT:QUEUE

Что я делаю неправильно? Мой алгоритм плох или есть какая-то "магия", которую используют другие сканеры памяти?

Answer 1

Другие сканеры памяти могут использовать "магию" в форме лучших алгоритмов поиска, таких как, например, Бойер-Мур. Возможно, они также проводят дополнительную микрооптимизацию в своем алгоритме поиска, но я думаю, что выбор алгоритма будет учитывать большую часть различий, которые вы видите.