Critique / Help me make this program run faster.

This is a discussion on Critique / Help me make this program run faster. within the C++ Programming forums, part of the General Programming Boards category; Heres my code. It opens a file and does a CRC32 on it. The problem is that the files that ...

  1. #1
    Codebot
    Join Date
    Jun 2004
    Location
    Toronto
    Posts
    195

    Critique / Help me make this program run faster.

    Heres my code. It opens a file and does a CRC32 on it. The problem is that the files that are ususally run with this are HUGE - 10Mb - 250Mb.

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    // CRC32
    
    int main(int argc, char *argv[])
    {
    
    	unsigned long table[256] = {
    	0x00000000, 0x77073096, 0xee0e612c, 0x990951ba, 0x076dc419, 0x706af48f,
    	0xe963a535, 0x9e6495a3, 0x0edb8832, 0x79dcb8a4, 0xe0d5e91e, 0x97d2d988,
    	0x09b64c2b, 0x7eb17cbd, 0xe7b82d07, 0x90bf1d91, 0x1db71064, 0x6ab020f2,
    	0xf3b97148, 0x84be41de, 0x1adad47d, 0x6ddde4eb, 0xf4d4b551, 0x83d385c7,
    	0x136c9856, 0x646ba8c0, 0xfd62f97a, 0x8a65c9ec, 0x14015c4f, 0x63066cd9,
    	0xfa0f3d63, 0x8d080df5, 0x3b6e20c8, 0x4c69105e, 0xd56041e4, 0xa2677172,
    	0x3c03e4d1, 0x4b04d447, 0xd20d85fd, 0xa50ab56b, 0x35b5a8fa, 0x42b2986c,
    	0xdbbbc9d6, 0xacbcf940, 0x32d86ce3, 0x45df5c75, 0xdcd60dcf, 0xabd13d59,
    	0x26d930ac, 0x51de003a, 0xc8d75180, 0xbfd06116, 0x21b4f4b5, 0x56b3c423,
    	0xcfba9599, 0xb8bda50f, 0x2802b89e, 0x5f058808, 0xc60cd9b2, 0xb10be924,
    	0x2f6f7c87, 0x58684c11, 0xc1611dab, 0xb6662d3d, 0x76dc4190, 0x01db7106,
    	0x98d220bc, 0xefd5102a, 0x71b18589, 0x06b6b51f, 0x9fbfe4a5, 0xe8b8d433,
    	0x7807c9a2, 0x0f00f934, 0x9609a88e, 0xe10e9818, 0x7f6a0dbb, 0x086d3d2d,
    	0x91646c97, 0xe6635c01, 0x6b6b51f4, 0x1c6c6162, 0x856530d8, 0xf262004e,
    	0x6c0695ed, 0x1b01a57b, 0x8208f4c1, 0xf50fc457, 0x65b0d9c6, 0x12b7e950,
    	0x8bbeb8ea, 0xfcb9887c, 0x62dd1ddf, 0x15da2d49, 0x8cd37cf3, 0xfbd44c65,
    	0x4db26158, 0x3ab551ce, 0xa3bc0074, 0xd4bb30e2, 0x4adfa541, 0x3dd895d7,
    	0xa4d1c46d, 0xd3d6f4fb, 0x4369e96a, 0x346ed9fc, 0xad678846, 0xda60b8d0,
    	0x44042d73, 0x33031de5, 0xaa0a4c5f, 0xdd0d7cc9, 0x5005713c, 0x270241aa,
    	0xbe0b1010, 0xc90c2086, 0x5768b525, 0x206f85b3, 0xb966d409, 0xce61e49f,
    	0x5edef90e, 0x29d9c998, 0xb0d09822, 0xc7d7a8b4, 0x59b33d17, 0x2eb40d81,
    	0xb7bd5c3b, 0xc0ba6cad, 0xedb88320, 0x9abfb3b6, 0x03b6e20c, 0x74b1d29a,
    	0xead54739, 0x9dd277af, 0x04db2615, 0x73dc1683, 0xe3630b12, 0x94643b84,
    	0x0d6d6a3e, 0x7a6a5aa8, 0xe40ecf0b, 0x9309ff9d, 0x0a00ae27, 0x7d079eb1,
    	0xf00f9344, 0x8708a3d2, 0x1e01f268, 0x6906c2fe, 0xf762575d, 0x806567cb,
    	0x196c3671, 0x6e6b06e7, 0xfed41b76, 0x89d32be0, 0x10da7a5a, 0x67dd4acc,
    	0xf9b9df6f, 0x8ebeeff9, 0x17b7be43, 0x60b08ed5, 0xd6d6a3e8, 0xa1d1937e,
    	0x38d8c2c4, 0x4fdff252, 0xd1bb67f1, 0xa6bc5767, 0x3fb506dd, 0x48b2364b,
    	0xd80d2bda, 0xaf0a1b4c, 0x36034af6, 0x41047a60, 0xdf60efc3, 0xa867df55,
    	0x316e8eef, 0x4669be79, 0xcb61b38c, 0xbc66831a, 0x256fd2a0, 0x5268e236,
    	0xcc0c7795, 0xbb0b4703, 0x220216b9, 0x5505262f, 0xc5ba3bbe, 0xb2bd0b28,
    	0x2bb45a92, 0x5cb36a04, 0xc2d7ffa7, 0xb5d0cf31, 0x2cd99e8b, 0x5bdeae1d,
    	0x9b64c2b0, 0xec63f226, 0x756aa39c, 0x026d930a, 0x9c0906a9, 0xeb0e363f,
    	0x72076785, 0x05005713, 0x95bf4a82, 0xe2b87a14, 0x7bb12bae, 0x0cb61b38,
    	0x92d28e9b, 0xe5d5be0d, 0x7cdcefb7, 0x0bdbdf21, 0x86d3d2d4, 0xf1d4e242,
    	0x68ddb3f8, 0x1fda836e, 0x81be16cd, 0xf6b9265b, 0x6fb077e1, 0x18b74777,
    	0x88085ae6, 0xff0f6a70, 0x66063bca, 0x11010b5c, 0x8f659eff, 0xf862ae69,
    	0x616bffd3, 0x166ccf45, 0xa00ae278, 0xd70dd2ee, 0x4e048354, 0x3903b3c2,
    	0xa7672661, 0xd06016f7, 0x4969474d, 0x3e6e77db, 0xaed16a4a, 0xd9d65adc,
    	0x40df0b66, 0x37d83bf0, 0xa9bcae53, 0xdebb9ec5, 0x47b2cf7f, 0x30b5ffe9,
    	0xbdbdf21c, 0xcabac28a, 0x53b39330, 0x24b4a3a6, 0xbad03605, 0xcdd70693,
    	0x54de5729, 0x23d967bf, 0xb3667a2e, 0xc4614ab8, 0x5d681b02, 0x2a6f2b94,
    	0xb40bbe37, 0xc30c8ea1, 0x5a05df1b, 0x2d02ef8d};
    
    	register unsigned long iCRC;
    	register long i = 0;
    	register long lSize;
    	register FILE * fp;
    
    	if (argc)
    	{
    		printf("Program Start: %d\n", clock());
    
    		fp = fopen(argv[1], "rb");
    
    		if (fp)
    		{
    			// THIS FINDS THE SIZE OF THE FILE
    			fseek(fp , 0 , SEEK_END);
    			lSize = ftell(fp);
    			rewind (fp);
    
    			printf("SIZE: %d\n", lSize);
    			printf("Reading Started: %d\n", clock());
    
    			iCRC = 0xFFFFFFFF;
    
    			// THE CALCULATION OF THE CRC32
    			for (i = 0; i < lSize; i++){
    				iCRC = ((iCRC >> 8) & 0xFFFFFFFF) ^ table[(iCRC ^ fgetc(fp)) & 0xFF];
    			}
    
    			printf("Reading Complete: %d\n", clock());
    			printf("CRC32: %x", (iCRC ^ 0xFFFFFFFF));
    		}
    
    	}
    
    	return 0;
    }
    Comments, suggestions, demands, alterations?

  2. #2
    C++ Developer XSquared's Avatar
    Join Date
    Jun 2002
    Location
    Ontario, Canada
    Posts
    2,718
    Try reading chunks of the file, and processing them once they're in memory.
    Naturally I didn't feel inspired enough to read all the links for you, since I already slaved away for long hours under a blistering sun pressing the search button after typing four whole words! - Quzah

    You. Fetch me my copy of the Wall Street Journal. You two, fight to the death - Stewie

  3. #3
    Yes, my avatar is stolen anonytmouse's Avatar
    Join Date
    Dec 2002
    Posts
    2,544
    Did you try the map file code that I posted in your earlier thread?

    Code:
    // Declare i and lSize as size_t instead of long.
    
    	if (argc >= 2)
    	{
    		printf("Program Start: %d\n", clock());
    
    		const char * file_view = (const char *) MapFileRead(argv[1], &lSize);
    
    		if (file_view)
    		{
    			printf("SIZE: %d\n", lSize);
    			printf("Reading Started: %d\n", clock());
    
    			iCRC = 0xFFFFFFFF;
    
    			// THE CALCULATION OF THE CRC32
    			for (i = 0; i < lSize; i++){
    				iCRC = ((iCRC >> 8) & 0xFFFFFFFF) ^ table[(iCRC ^ file_view[i]) & 0xFF];
    			}
    
    			printf("Reading Complete: %d\n", clock());
    			printf("CRC32: %x", (iCRC ^ 0xFFFFFFFF));
    			MapFileClose(file_view);
    		}
    	}
    Based on Salem's results of a ~200% speed boost with mmap() instead of fread(), I'd say that it could definitely be worth a few moments to try out this solution.

  4. #4
    Codebot
    Join Date
    Jun 2004
    Location
    Toronto
    Posts
    195
    I tried using your code above and i got a few errors. mainly this:
    Code:
    const char * file_view = (const char *) MapFileRead(argv[1], &lSize);
    gave me a few casting errors that i cant convert the long to and unsigned int. Now i never used mapping before so Im almost clueless about this.

    Im using borland 5.5

  5. #5
    Yes, my avatar is stolen anonytmouse's Avatar
    Join Date
    Dec 2002
    Posts
    2,544
    You need to declare lSize and i as size_t instead of long. lSize can't be register either.
    Code:
     size_t i = 0;
    	size_t lSize;
    Last edited by anonytmouse; 06-25-2004 at 09:46 PM.

  6. #6
    Codebot
    Join Date
    Jun 2004
    Location
    Toronto
    Posts
    195
    hmm I got rid of the register keyword and 7 new errors popped up. *sigh*

  7. #7
    Yes, my avatar is stolen anonytmouse's Avatar
    Join Date
    Dec 2002
    Posts
    2,544
    OK, here is the complete code:
    Code:
    #include <windows.h>
    
    /*
     * Map a file for read access. Returns size of view in lpcbSize
     */
    LPVOID MapFileRead(LPCTSTR szFileName, size_t * lpcbSize)
    {
    	HANDLE hFile, hMapping;
    	DWORD  dwFileSize;
    	LPVOID lpView;
    	MEMORY_BASIC_INFORMATION mbi;
    
    	*lpcbSize = 0;
    
    	hFile = CreateFile(szFileName, GENERIC_READ, FILE_SHARE_READ, NULL,
    	                   OPEN_EXISTING, FILE_ATTRIBUTE_NORMAL|FILE_FLAG_SEQUENTIAL_SCAN, NULL);
    	if (INVALID_HANDLE_VALUE == hFile)
    	{
    		return NULL;
    	}
    
    	dwFileSize = GetFileSize(hFile, NULL);
    	if (INVALID_FILE_SIZE == dwFileSize)
    	{
    		CloseHandle(hFile);
    		return NULL;
    	}
    
    	hMapping = CreateFileMapping(hFile, NULL, PAGE_READONLY, 0, 0, NULL);
    	if (NULL == hMapping)
    	{
    		CloseHandle(hFile);
    		return NULL;
    	}
    
    	lpView = MapViewOfFile(hMapping, FILE_MAP_READ, 0, 0, 0);
    
    	CloseHandle(hMapping);
    	CloseHandle(hFile);
    
    	if (NULL != lpView)
    	{
    		if (VirtualQuery(lpView, &mbi, sizeof(mbi)) >= sizeof(mbi))
    		{
    			*lpcbSize = min(dwFileSize, mbi.RegionSize);
    		}
    		else
    		{
    			*lpcbSize = dwFileSize;
    		}
    	}
    
    	return lpView;
    }
    
    
    /*
     * Close a file mapping view.
     */
    BOOL MapFileClose(LPCVOID lpView)
    {
    	return UnmapViewOfFile(lpView);
    }
    
    #include <stdio.h>
    #include <stdlib.h>
    #include <time.h>
    
    // CRC32
    
    int main(int argc, char *argv[])
    {
    	unsigned long table[256] = {
    	0x00000000, 0x77073096, 0xee0e612c, 0x990951ba, 0x076dc419, 0x706af48f,
    	0xe963a535, 0x9e6495a3, 0x0edb8832, 0x79dcb8a4, 0xe0d5e91e, 0x97d2d988,
    	0x09b64c2b, 0x7eb17cbd, 0xe7b82d07, 0x90bf1d91, 0x1db71064, 0x6ab020f2,
    	0xf3b97148, 0x84be41de, 0x1adad47d, 0x6ddde4eb, 0xf4d4b551, 0x83d385c7,
    	0x136c9856, 0x646ba8c0, 0xfd62f97a, 0x8a65c9ec, 0x14015c4f, 0x63066cd9,
    	0xfa0f3d63, 0x8d080df5, 0x3b6e20c8, 0x4c69105e, 0xd56041e4, 0xa2677172,
    	0x3c03e4d1, 0x4b04d447, 0xd20d85fd, 0xa50ab56b, 0x35b5a8fa, 0x42b2986c,
    	0xdbbbc9d6, 0xacbcf940, 0x32d86ce3, 0x45df5c75, 0xdcd60dcf, 0xabd13d59,
    	0x26d930ac, 0x51de003a, 0xc8d75180, 0xbfd06116, 0x21b4f4b5, 0x56b3c423,
    	0xcfba9599, 0xb8bda50f, 0x2802b89e, 0x5f058808, 0xc60cd9b2, 0xb10be924,
    	0x2f6f7c87, 0x58684c11, 0xc1611dab, 0xb6662d3d, 0x76dc4190, 0x01db7106,
    	0x98d220bc, 0xefd5102a, 0x71b18589, 0x06b6b51f, 0x9fbfe4a5, 0xe8b8d433,
    	0x7807c9a2, 0x0f00f934, 0x9609a88e, 0xe10e9818, 0x7f6a0dbb, 0x086d3d2d,
    	0x91646c97, 0xe6635c01, 0x6b6b51f4, 0x1c6c6162, 0x856530d8, 0xf262004e,
    	0x6c0695ed, 0x1b01a57b, 0x8208f4c1, 0xf50fc457, 0x65b0d9c6, 0x12b7e950,
    	0x8bbeb8ea, 0xfcb9887c, 0x62dd1ddf, 0x15da2d49, 0x8cd37cf3, 0xfbd44c65,
    	0x4db26158, 0x3ab551ce, 0xa3bc0074, 0xd4bb30e2, 0x4adfa541, 0x3dd895d7,
    	0xa4d1c46d, 0xd3d6f4fb, 0x4369e96a, 0x346ed9fc, 0xad678846, 0xda60b8d0,
    	0x44042d73, 0x33031de5, 0xaa0a4c5f, 0xdd0d7cc9, 0x5005713c, 0x270241aa,
    	0xbe0b1010, 0xc90c2086, 0x5768b525, 0x206f85b3, 0xb966d409, 0xce61e49f,
    	0x5edef90e, 0x29d9c998, 0xb0d09822, 0xc7d7a8b4, 0x59b33d17, 0x2eb40d81,
    	0xb7bd5c3b, 0xc0ba6cad, 0xedb88320, 0x9abfb3b6, 0x03b6e20c, 0x74b1d29a,
    	0xead54739, 0x9dd277af, 0x04db2615, 0x73dc1683, 0xe3630b12, 0x94643b84,
    	0x0d6d6a3e, 0x7a6a5aa8, 0xe40ecf0b, 0x9309ff9d, 0x0a00ae27, 0x7d079eb1,
    	0xf00f9344, 0x8708a3d2, 0x1e01f268, 0x6906c2fe, 0xf762575d, 0x806567cb,
    	0x196c3671, 0x6e6b06e7, 0xfed41b76, 0x89d32be0, 0x10da7a5a, 0x67dd4acc,
    	0xf9b9df6f, 0x8ebeeff9, 0x17b7be43, 0x60b08ed5, 0xd6d6a3e8, 0xa1d1937e,
    	0x38d8c2c4, 0x4fdff252, 0xd1bb67f1, 0xa6bc5767, 0x3fb506dd, 0x48b2364b,
    	0xd80d2bda, 0xaf0a1b4c, 0x36034af6, 0x41047a60, 0xdf60efc3, 0xa867df55,
    	0x316e8eef, 0x4669be79, 0xcb61b38c, 0xbc66831a, 0x256fd2a0, 0x5268e236,
    	0xcc0c7795, 0xbb0b4703, 0x220216b9, 0x5505262f, 0xc5ba3bbe, 0xb2bd0b28,
    	0x2bb45a92, 0x5cb36a04, 0xc2d7ffa7, 0xb5d0cf31, 0x2cd99e8b, 0x5bdeae1d,
    	0x9b64c2b0, 0xec63f226, 0x756aa39c, 0x026d930a, 0x9c0906a9, 0xeb0e363f,
    	0x72076785, 0x05005713, 0x95bf4a82, 0xe2b87a14, 0x7bb12bae, 0x0cb61b38,
    	0x92d28e9b, 0xe5d5be0d, 0x7cdcefb7, 0x0bdbdf21, 0x86d3d2d4, 0xf1d4e242,
    	0x68ddb3f8, 0x1fda836e, 0x81be16cd, 0xf6b9265b, 0x6fb077e1, 0x18b74777,
    	0x88085ae6, 0xff0f6a70, 0x66063bca, 0x11010b5c, 0x8f659eff, 0xf862ae69,
    	0x616bffd3, 0x166ccf45, 0xa00ae278, 0xd70dd2ee, 0x4e048354, 0x3903b3c2,
    	0xa7672661, 0xd06016f7, 0x4969474d, 0x3e6e77db, 0xaed16a4a, 0xd9d65adc,
    	0x40df0b66, 0x37d83bf0, 0xa9bcae53, 0xdebb9ec5, 0x47b2cf7f, 0x30b5ffe9,
    	0xbdbdf21c, 0xcabac28a, 0x53b39330, 0x24b4a3a6, 0xbad03605, 0xcdd70693,
    	0x54de5729, 0x23d967bf, 0xb3667a2e, 0xc4614ab8, 0x5d681b02, 0x2a6f2b94,
    	0xb40bbe37, 0xc30c8ea1, 0x5a05df1b, 0x2d02ef8d};
    
    	unsigned long  iCRC;
    	size_t         i;
    	size_t         lSize;
    	const char*    file_view;
    
    	if (argc >= 2)
    	{
    		printf("Program Start: %d\n", clock());
    
    		file_view = (const char *) MapFileRead(argv[1], &lSize);
    
    		if (file_view)
    		{
    			printf("SIZE: %d\n", lSize);
    			printf("Reading Started: %d\n", clock());
    
    			iCRC = 0xFFFFFFFF;
    
    			// THE CALCULATION OF THE CRC32
    			for (i = 0; i < lSize; i++){
    				iCRC = ((iCRC >> 8) & 0xFFFFFFFF) ^ table[(iCRC ^ file_view[i]) & 0xFF];
    			}
    
    			printf("Reading Complete: %d\n", clock());
    			printf("CRC32: %x", (iCRC ^ 0xFFFFFFFF));
    
    			MapFileClose(file_view);
    		}
    	}
    
    	getchar();
    	return 0;
    }
    Interestingly, with optimisation turned off, your version runs about 8% faster than this version. However, with optimisation turned on this version runs about 215% faster than your version. I tested with a 'hot'(ie. a file that has been used several times and is therefore in the memory cache) 80MB file so real world results using 'cold' files may differ.

  8. #8
    Codebot
    Join Date
    Jun 2004
    Location
    Toronto
    Posts
    195
    Well im aiming for 'cold' files because Once i created a CRC for the file, ill just move onto the next one and so on. so the same file wont be tested twice.

    BTW, im still getting and error. min is not defined?? It should be in windows.h but apperantly borland is still complaining about it:

    Code:
    *lpcbSize = min(dwFileSize, mbi.RegionSize);

  9. #9
    Yes, my avatar is stolen anonytmouse's Avatar
    Join Date
    Dec 2002
    Posts
    2,544
    Just chuck this at the top of the file:
    Code:
    #ifndef min
    #define min(a, b)  (((a) < (b)) ? (a) : (b)) 
    #endif

  10. #10
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,484
    Didn't we just do this?

    I made this change to your code
    Code:
    #ifdef READFILE
                    int ch = fgetc(fp);
    #else
                    int ch = 0;
    #endif
                    iCRC = ((iCRC >> 8) & 0xFFFFFFFF) ^ table[(iCRC ^ ch) & 0xFF];
    To separate the calulation time from the file reading time.

    The last figure is the best you'll ever get even if you have a perfect file system which can read the whole file in zero time.
    Sod it, I'm not repeating myself, go read my previous answers!!!

    Code:
    + gcc -DREADFILE hello.c
    + ./a.out aa2
    Program Start: 0
    SIZE: 46644250
    Reading Started: 0
    Reading Complete: 2130000
    CRC32: 7d4a387e
    + gcc -O2 -DREADFILE hello.c
    + ./a.out aa2
    Program Start: 0
    SIZE: 46644250
    Reading Started: 0
    Reading Complete: 1960000
    CRC32: 7d4a387e
    + gcc hello.c
    + ./a.out aa2
    Program Start: 0
    SIZE: 46644250
    Reading Started: 0
    Reading Complete: 470000
    CRC32: f7f87dd2
    + gcc -O2 hello.c
    + ./a.out aa2
    Program Start: 0
    SIZE: 46644250
    Reading Started: 0
    Reading Complete: 190000
    CRC32: f7f87dd2
    You do realise that & 0xFFFFFFFF on an unsigned long is a no-op right?
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  11. #11
    Codebot
    Join Date
    Jun 2004
    Location
    Toronto
    Posts
    195
    Thanks for all your help. After testing both versions of this code (mapping and my original). I noticed that my original way is a bit faster. There might be a bit of difference on slower machines between the two. Im going to test it on a few other machines. If anyone has any other suggestions then please post.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Trying to make this run faster
    By wkohlani in forum C Programming
    Replies: 32
    Last Post: 06-27-2009, 11:42 PM
  2. Program Plan
    By Programmer_P in forum C++ Programming
    Replies: 0
    Last Post: 05-11-2009, 01:42 AM
  3. Help on making program run more efficiently
    By peeweearies in forum C Programming
    Replies: 2
    Last Post: 03-23-2009, 02:01 AM
  4. Client-server system with input from separate program
    By robot-ic in forum Networking/Device Communication
    Replies: 3
    Last Post: 01-16-2009, 02:30 PM
  5. want to make this small program...
    By psycho88 in forum C++ Programming
    Replies: 8
    Last Post: 11-30-2005, 01:05 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21