fastest way to check if memory is zeroed

Question

Hi,

i got a program that needs to check if a chunk of a file is zeroed or has data. This alg runs for the whole file for sizes upto a couple of gigs and takes a while to run. Is there a better way to check to see if its zeroed?

Platform: Linux and 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

How long is 'a while'? ... I'd say attempting to compare as many values in parallel as possible will help, maybe use some SIMD instructions to compare more than 4 bytes at a time?

Do keep in mind though, that no matter how fast you make the comparison, ultimately the data still needs to be read from the file. If the file is not already in a cache somewhere in memory, then you may be limited to in the order of 100-150 MB/s at a maximum before the bandwidth of the disk is saturated. If you have already hit this point, then you may first need to look at an approach that avoids having to load the file, or just accept the fact that it's not going to be faster than that.

Answer 2

Are there places in the file/chunk where it is more likely to have non-zero values? You only have to find one non-zero value (your break condition), so look in places first where you most probably find them - which doesn't have to be the beginning of a file/chunk. It might make sense to start at the end, or check the 1/3 in the middle, depending on the actual application.

However, I would not recommend to jump randomly to different positions; reading from disk might become incredibly ;) ..

Answer 3

I'd like to see the assembly output for this function. Something that you could do that would speed it up by a lot is to use SSE instructions. With these instructions, you can load 8 bytes at a time, check them all for zero and continue. And you could unroll that for loop a few times too.

Answer 4

You algo seems OK, but you can heuristically optimise starting place if you known in advance what type of file you will be getting...but then again if it is a specific file, most likely the info will be in the header (first few bytes).

Also make sure that block->size is not 1 from whoever calls the method :)

Also check out Boost's memory mapped files facilities...It might be of a help, depending on how you calculate the optimal block->size

Answer 5

I have an "out of the box" answer for you, but I am not sure how feasable it is to implement in your situation.

If you don't control the dumping process: Since it is a large recovery (dump?) file produced on excpetional case, why not scan the file (for 0 bytes) on low priority right after it is dumped then and mark it somehow for faster later identification? (or you could zip it and parse/scan the zip file later)

Or if you control the dumping process: (a slow process you have to do anyways) why not indicate at the end of the dump file (or go back and write at the beginning of it), if the dump file is filled with 0 or has some valid data (since you wrote it and you know what is in it)? like that you don't have to pay for I/O overhead twice.

The goal here being to make the reading much faster by deffering the procss to another eralier time, since when the dump happens, there is unlikely to be an operator waiting for it to load.

Answer 6

First, don't allocate a new buffer each time. Allocate one (per thread) and reuse it. Use a nice big chunk, and do multiple read/check passes.
Second, don't compare each character. Do comparisons on a larger integral type. Most likely you will want a 32bit int, but depending on your os/compiler it might be faster to use a 64 or even 128 bit int. With a 32bit int you are reducing your number of comparisons by 4x. Your will, of course, have to worry about end conditions. For this, it is easy, if the buffer you are comparing isn't a even multiple of your int size, just set the last X bytes to 0 before you do the compare. Third, it might help your compiler a bit to unroll the loop. Do 4 or 8 comparisons in the body of the loop. This should help the compiler optimize a bit as well as reduce the number of comparisons for exiting the loop. Make sure your buffer is a multiple of your comparison type x the number of comparisons in the loop. Fourth, it may be faster to use (*pBuffer++) instead of buffer[i], especially if the buffer is big.

For any of these, you will of course, want to get some metrics and see what actually helps.

Answer 7

I will tell you a dirty, non-portable and difficult way, but than can be more efficient... If you are dealing with sparse files, you are really bored and want to mess with the internals of the filesystems you're using, you can try to add a new function that returns you a bitmap indicating which blocks are mapped and which ones aren't (those which are not mapped are zeroed, for the rest you will have still to check manually).

Yeah, I know it's crazy and nobody would ever like to do something like this xD