I thought this competition sounded fun, so I gave it a shot. The
following is a 2-threaded program that overlaps reads and
computation. I had to use boost::thread for this, but this should all
be doable in C++0x -- but I'll let you be the final judge of whether
it's an acceptable entry. As many pointed out, the problem is I/O
bound, so that's what I tackled first.
The computation part is nearly identical to Chris' code, I could not
beat the simple accumulate-into-256-wide-table. So cheers for finding
the best solution there
FYI timings on my machine were:
Read the entire 280MB file, do no processing : 0.25 seconds
Chris' program : 0.6 seconds
This program : 0.4 seconds
/// This program counts plain ol' alphabet characters' frequency in a
text file.
/// Text file's encoding is assumed to be a superset of ASCII
/// (for example SHIFT-JIS or UTF-8 would work).
/*
CStopWatch s;
s.startTimer();
The_Stuff_You_Want_To_Time_Executes_Here();
s.stopTimer();
You may then get the elapsed time in seconds
via the method getElapsedTime.
*/
#ifdef WIN32
#include <windows.h>
class CStopWatch
{
private:
typedef struct {
LARGE_INTEGER start;
LARGE_INTEGER stop;
} stopWatch;
stopWatch timer;
LARGE_INTEGER frequency;
double LIToSecs( LARGE_INTEGER & L)
{
return ((double)L.QuadPart/(double)frequency.QuadPart);
}
public:
CStopWatch()
{
timer.start.QuadPart=0;
timer.stop.QuadPart=0;
QueryPerformanceFrequency( &frequency );
}
void startTimer() { QueryPerformanceCounter(&timer.start); }
void stopTimer() { QueryPerformanceCounter(&timer.stop); }
double getElapsedTime()
{
LARGE_INTEGER time;
time.QuadPart=timer.stop.QuadPart-timer.start.QuadPart;
return LIToSecs( time );
}
};
#else
#include <sys/time.h>
class CStopWatch
{
private:
typedef struct {
timeval start;
timeval stop;
} stopWatch;
stopWatch timer;
public:
void startTimer( ) { gettimeofday(&(timer.start),0); }
void stopTimer( ) { gettimeofday(&(timer.stop),0); }
double getElapsedTime()
{
timeval res;
timersub(&(timer.stop),&(timer.start),&res);
return res.tv_sec + res.tv_usec/1000000.0;
}
};
#endif
#include <stdio.h>
#include <boost/cstdint.hpp>
#include <boost/thread.hpp>
#include <boost/thread/mutex.hpp>
#include <boost/thread/condition.hpp>
#define BLOCK_SIZE 0x10000u
/// BLOCK_COUNT must be >= 3 for the FIFO to work properly
#define BLOCK_COUNT 0x10u
#define INBUF_SIZE (BLOCK_SIZE * BLOCK_COUNT)
static unsigned char inbuf[INBUF_SIZE];
static volatile int inbufAmt[BLOCK_COUNT];
static volatile size_t readCursor = 0;
static volatile size_t writeCursor = 0;
static size_t totalRead = 0;
static CStopWatch stopWatch;
/// fileReadDone is protected by ioMutex -- otherwise you get a race
condition at EOF
static volatile int fileReadDone = 0;
static boost::mutex ioMutex;
static boost::condition readAvailable;
static boost::condition writeAvailable;
static int totals[256] = {0};
struct Reader {
const char* const pFileName;
Reader(const char* pFileName_) : pFileName(pFileName_) {}
void operator()() {
stopWatch.startTimer();
FILE* pFile = fopen(pFileName, "rb");
if (!pFile)
return;
while (!feof(pFile) && !ferror(pFile)) {
inbufAmt[writeCursor] = fread((void*)&inbuf[BLOCK_SIZE *
writeCursor],
1, BLOCK_SIZE, pFile);
totalRead += inbufAmt[writeCursor];
const size_t nextWriteCursor = (writeCursor + 1) %
BLOCK_COUNT;
while (nextWriteCursor == readCursor) {
boost::mutex::scoped_lock lk(ioMutex);
readAvailable.notify_one();
writeAvailable.wait(lk);
}
writeCursor = nextWriteCursor;
readAvailable.notify_one();
}
{
boost::mutex::scoped_lock lk(ioMutex);
fileReadDone = 1;
readAvailable.notify_one();
}
fclose(pFile);
}
};
static void AccumulateTotals(const unsigned char* pBuffer, size_t
size) {
const unsigned char* pc = pBuffer;
const unsigned char* const pcEnd = pc + size;
for (; pc != pcEnd; ++pc) {
const unsigned char c = *pc;
++totals[c];
}
}
int main(int argc, char** argv) {
if (argc < 2) {
printf("\nusage:\n\t%s <text_file_name>\n", argv[0]);
return -1;
}
// launch a reader thread
Reader reader(argv[1]);
boost::thread readerThread(reader);
// accumulate totals from buffers as they are
while (!fileReadDone) {
while (writeCursor == readCursor) {
boost::mutex::scoped_lock lk(ioMutex);
if (fileReadDone)
break;
writeAvailable.notify_one();
readAvailable.wait(lk);
}
if (fileReadDone)
break;
AccumulateTotals(&inbuf[BLOCK_SIZE * readCursor], inbufAmt
[readCursor]);
readCursor = (readCursor + 1) % BLOCK_COUNT;
writeAvailable.notify_one();
}
long totalAlphaChars = 0;
for (size_t u = 0; u < 26; ++u) {
totalAlphaChars += totals['A' + u] + totals['a' + u];
}
for (size_t u = 0; u < 26; ++u) {
double result = (totals['A' + u] + totals['a' + u]) * 100.0 /
totalAlphaChars;
printf("%c %%%.3f\n", 'a' + u, result);
}
stopWatch.stopTimer();
const double elapsed = stopWatch.getElapsedTime();
printf("\nelapsed time: %f [seconds]\n", elapsed);
return 0;
}
