самый быстрый способ проверить, обнулена ли память

Question

У меня есть программа, которая должна проверить, обнулен ли кусок файла или есть данные. Этот алгоритм работает для всего файла для размеров до пары гигов и требует времени для запуска. Есть ли лучший способ проверить, обнулено ли оно?

Платформа: Linux и Windows

bool WGTController::isBlockCompleted(wgBlock* block)
{
    if (!block)
        return false;

    uint32 bufSize = (uint32)block->size;
    uint64 fileSize = UTIL::FS::UTIL_getFileSize(m_szFile);

    if (fileSize < (block->size + block->fileOffset))
        return false;

    char* buffer = new char[bufSize];

    FHANDLE fh=NULL;

    try
    {
        fh = UTIL::FS::UTIL_openFile(m_szFile, UTIL::FS::FILE_READ);
        UTIL::FS::UTIL_seekFile(fh, block->fileOffset);
        UTIL::FS::UTIL_readFile(fh, buffer, bufSize);
        UTIL::FS::UTIL_closeFile(fh);
    }
    catch (gcException &)
    {
        SAFE_DELETEA(buffer);
        UTIL::FS::UTIL_closeFile(fh);
        return false;
    }

    bool res = false;

    for (uint32 x=0; x<bufSize; x++)
    {
        if (buffer[x] != 0)
        {
            res = true;
            break;
        }
    }

    SAFE_DELETEA(buffer);
    return res;
}

Answer 1

Как долго это "время"? ... я бы сказал, что попытка сравнить как можно больше значений параллельно поможет, может быть, использовать некоторые SIMD-инструкции для сравнения более 4 байтов за раз?

Имейте в виду, однако, что независимо от того, насколько быстро вы проводите сравнение, в конечном итоге данные все равно необходимо считывать из файла. Если файл еще не находится в кеше где-то в памяти, то вы можете ограничиться максимальным значением порядка 100-150 МБ / с, прежде чем пропускная способность диска будет насыщена. Если вы уже достигли этой точки, то вам, возможно, сначала нужно взглянуть на подход, позволяющий избежать необходимости загружать файл, или просто принять тот факт, что он не будет быстрее этого.

Answer 2

Есть ли в файле / чанке места, где с большей вероятностью могут быть ненулевые значения? Вам нужно только найти one ненулевое значение (ваше условие разрыва), поэтому сначала посмотрите в тех местах, где вы, скорее всего, найдете их - что не обязательно должно быть началом файла / блока. Возможно, имеет смысл начать с конца или проверить 1/3 в середине, в зависимости от фактического приложения.

Однако я бы не рекомендовал случайным образом переходить на разные позиции; чтение с диска может стать невероятным;) ..

Answer 3

Я расскажу вам грязный, непереносимый и сложный способ, но не может быть более эффективным ... Если вы имеете дело с разреженными файлами, вам действительно скучно и вы хотите поработать с внутренностями файловых систем, которые вы При использовании вы можете попытаться добавить новую функцию, которая возвращает вам растровое изображение, указывающее, какие блоки сопоставлены, а какие нет (те, которые не сопоставлены, обнуляются, в остальном вам все равно придется проверять вручную).

Да, я знаю, что это безумие, и никто никогда не хотел бы делать что-то подобное xD

Answer 4

Во-первых, не выделяйте новый буфер каждый раз. Выделите один (на поток) и используйте его повторно. Используйте хороший большой кусок и сделайте несколько проходов чтения / проверки.
Во-вторых, не сравнивайте каждый символ. Сделайте сравнения на более крупном интегральном типе. Скорее всего, вам понадобится 32-битное int, но в зависимости от вашего os / компилятора может быть быстрее использовать 64 или даже 128-битное int. С 32-битным int вы уменьшаете количество сравнений в 4 раза. Ваша воля, конечно, должна беспокоиться о конечных условиях. Для этого легко, если сравниваемый буфер не кратен размеру int, просто установите последние байты X равными 0, прежде чем выполнять сравнение. В-третьих, это может помочь вашему компилятору немного развернуть цикл. Сделайте 4 или 8 сравнений в теле цикла. Это должно помочь компилятору немного оптимизировать, а также уменьшить количество сравнений для выхода из цикла. Убедитесь, что ваш буфер кратен вашему типу сравнения х числу сравнений в цикле. В-четвертых, может быть быстрее использовать (* pBuffer ++) вместо buffer [i], особенно если буфер большой.

Для любого из них вы, конечно, захотите получить некоторые показатели и посмотреть, что на самом деле помогает.

Answer 5

У меня есть для вас ответ «из коробки», но я не уверен, насколько это возможно реализовать в вашей ситуации.

Если вы не контролируете процесс дампа: поскольку это большой файл восстановления (дамп?), Созданный в исключительном случае, почему бы не просканировать файл (на 0 байт) с низким приоритетом сразу после его выгрузки и отметить это как-то для более быстрой последующей идентификации? (или вы можете заархивировать его и позже проанализировать / отсканировать zip-файл)

Или если вы контролируете процесс дампа: (медленный процесс, который вы должны сделать в любом случае), почему бы не указать в конце файла дампа (или вернуться назад и написать в начале его), если файл дампа заполнен с 0 или имеет некоторые действительные данные (так как вы написали это, и вы знаете, что в нем)? например, вам не нужно платить за ввод-вывод дважды.

Цель здесь состоит в том, чтобы сделать чтение намного быстрее, перенося процесс на другое более раннее время, поскольку, когда происходит сброс, вряд ли будет оператор, ожидающий его загрузки.

Answer 6

Вы, возможно, тоже в порядке, но вы можете эвристически оптимизировать начальное место, если заранее знаете, какой тип файла вы будете получать ... но, опять же, если это конкретный файл, скорее всего, информация будет в заголовке (первые несколько байтов).

Также убедитесь, что block-> size не равен 1 от того, кто вызывает метод:)

Также ознакомьтесь с возможностями Boost для отображения файлов в память ... Это может помочь, в зависимости от того, как вы вычисляете оптимальный блок-> размер

Answer 7

Я бы хотел увидеть вывод сборки для этой функции. То, что вы могли бы сделать, что значительно ускорило бы это, - это использовать инструкции SSE. С помощью этих инструкций вы можете загрузить 8 байтов за раз, проверить их все на ноль и продолжить. И вы можете развернуть этот цикл for несколько раз.