processing time ...

Started by
2 comments, last by chaosbob 22 years, 1 month ago
This is totaly non game related, but ... I wrote a program in C++ to process a certain text file. When I only had 200 records it took 12 seconds. Not bad i thought, but then i tried 400 records... 96 seconds. 800 records took over 400 seconds and 1600 records was well in the thousands. I narrowed the code down to the point where I was just opening the file and dumping the whole thing onto the heap and then looping through it with a very simple "for" loop. In otherwords, i stripped out all processing code. The results where about the same. So my question is then, why does the computer need an exponentialy longer time to deal with larger memory allocations? Could it be that my "for" loop used strlen?
    
for(unsigned long i = 0; i <= std::strlen(fileBuffer); i++){
}  
Does strlen take much longer to return the length of a buffer that is a quite large? Some of these records where hundreds of bytes so the allocated memory was pretty big. As i'm writing this i'm starting to think that it would have been much better to write...
  
unsigned long bufferSize = std::strlen(fileBuffer);
for(unsigned long i = 0; i <= bufferSize; i++){
}    
~ChaosBob (who probably just answered his own question) Edited by - chaosbob on February 24, 2002 8:03:53 AM
Advertisement
yep, you just answered your own question.

The reason being, is that the program calls ''strlen'' on every loop of the array, and strlen is an O(n) algorithm. It essentially loops through the array on every pass.

So, putting that into a for loop causes your simple loop to become a double-nested loop, with a complexity of O(n^2), which makes your algorithm exponentially slower.

Caching the size of the loop is definitely the right choice.
This is my signature. There are many like it, but this one is mine. My signature is my best friend. It is my life. I must master it as I must master my life. My signature, without me, is useless. Without my signature, I am useless.
Thanks for that explanation. I was thinking more about strlen and how it works. I''m curious, what would be the behaviour resulting from calling strlen on an array of char''s in which no null terminator exists? Would strlen continue reading past the end of the array until it came across the next null byte in memory?

Just curious

~ ChaosBob
Yes, it would.

And you probably need less-than in your loop, not less-than-or-equal-to, by the way.

[ MSVC Fixes | STL | SDL | Game AI | Sockets | C++ Faq Lite | Boost ]

This topic is closed to new replies.

Advertisement