Figures
© 2004 Microsoft Corporation. All rights reserved.
Figure 1 Exception Class
class Exception
{
public:
    enum ErrId
    {
        // Keep these in the same order as the string table:
        k_critSecInitFailure,
        k_threadCreationFailure,
        k_threadResumeFailure,
        k_threadWaitFailure
    };

    Exception(ErrId errId, unsigned long osErrId = NOERROR) :
        m_errId(errId), m_osErrId(osErrId) {}
    ~Exception()
        {}

    UINT getErrId() const
        { return m_errId; }
    unsigned long getOsErrId() const
        { return m_osErrId; }

    string getErrorMsg() const;

private:
    static string getOSMsg(unsigned long osErrId);

    static const char*const k_messages[];

    UINT            m_errId;
    unsigned long   m_osErrId;
};
Figure 2 Timer Class
class Timer
{
public:
    Timer() : m_stop(0), m_start(0)
        {
            GetSystemTimeAsFileTime(
                reinterpret_cast<FILETIME*>(&m_start));
        }
    void stop()
        {
            GetSystemTimeAsFileTime(
                reinterpret_cast<FILETIME*>(&m_stop));
        }
    double getMicroSec() const
        { return diffAsDouble() / 10.0; }
    double getMilliSec() const
        { return diffAsDouble() / 10000.0; }
    double getSec() const
        { return diffAsDouble() / 10000000.0; }

private:
    double diffAsDouble() const
        { return static_cast<double>(m_stop - m_start); }

    LONGLONG    m_stop;
    LONGLONG    m_start;
};
Figure 3 CritSec Class
class CritSec
{
public:
    CritSec();
    ~CritSec()
        { DeleteCriticalSection(&m_critSec); }

    void acquire()
        { EnterCriticalSection(&m_critSec); }
    bool tryAcquire()   // use only on Windows NT or Windows 2000
        { return !!TryEnterCriticalSection(&m_critSec); }
    void release()
        { LeaveCriticalSection(&m_critSec); }

private:
    enum { k_spinCount = 3000ul };

    CRITICAL_SECTION m_critSec;
};



template<class T>
class LockKeeper
{
public:
    LockKeeper(T& t) : m_t(t) { m_t.acquire(); }
    ~LockKeeper() { m_t.release(); }

private:
    T& m_t;
};
Figure 4 Thread Class Definition
class Thread
{
public:
    Thread();
    virtual ~Thread();

    virtual void start();
    virtual bool wait(unsigned long timeout = INFINITE);

    unsigned long getId() const
        { return m_id; }
    HANDLE getHandle() const
        { return m_h; }

protected:
    virtual void run() = 0;

private:
    static unsigned __stdcall entryPoint(void* pArg);

    unsigned long   m_id;
    HANDLE          m_h;
};
Figure 5 Thread Implementation
Thread::Thread() : m_id(0), m_h(0)
{
}

Thread::~Thread()
{
    if (m_h != 0)
    {
        wait();
        CloseHandle(m_h);
        m_id = 0;
        m_h = 0;
    }
}

void Thread::start()
{
    if (m_h != 0)
    {
        wait();
        CloseHandle(m_h);
        m_id = 0;
        m_h = 0;
    }
    unsigned id;
    unsigned long h = _beginthreadex(0, 0, entryPoint, this,
        CREATE_SUSPENDED, &id);
    if (h == 0)
    {
        throw Exception(Exception::k_threadCreationFailure);
    }
    m_id = id;
    m_h = reinterpret_cast<HANDLE>(h);
    if (ResumeThread(m_h) == static_cast<DWORD>(-1))
    {
        throw Exception(Exception::k_threadResumeFailure, GetLastError());
    }
}

unsigned __stdcall Thread::entryPoint(void* pArg)
{
    try
    {
        Thread* pThis = static_cast<Thread*>(pArg);
        pThis->run();
    }
    catch (const Exception& e)
    {
        cout << "Thread " << e.getErrorMsg() << endl << endl;
    }
    catch (const exception& e)
    {
        cout << "std::exception in thread:  " << e.what() << endl << endl;
    }
    return 0;
}

bool Thread::wait(unsigned long timeout)
{
    bool result = true;

    if (m_h != 0)
    {
        switch (WaitForSingleObject(m_h, timeout))
        {
        case WAIT_OBJECT_0:
            break;

        case WAIT_TIMEOUT:
            result = false;
            break;

        default:
            throw Exception(Exception::k_threadWaitFailure,
                GetLastError());
            break;
        }
    }
    return result;
}
Figure 6 Database Class
class Database
{
public:
    Database(unsigned long numEntries);

    unsigned long getNumEntries() const
        { return m_entries.size(); }
    DBEntry& getEntry(unsigned long entryId) const
        { return *m_entries.at(entryId).get(); }

private:
    typedef vector<auto_ptr<DBEntry> >  DBEntryList;
    typedef DBEntryList::const_iterator DBEntryIter;

    DBEntryList m_entries;
};



class DBEntry
{
public:
    DBEntry(unsigned long id, const string& value) :
        m_id(id), m_value(value) {}

    unsigned long getId() const
        { return m_id; }
    const char* getValue() const
        { return m_value.c_str(); }     // use of c_str causes cloning
    void setValue(const string& newValue)
        { m_value = newValue.c_str(); } // use of c_str causes cloning

    static void critSecMode(bool useSingleCritSec)
        { g_useSingleCritSec = useSingleCritSec; }

    void acquire();
    void release();

private:
    unsigned long       m_id;
    string              m_value;

    static bool         g_useSingleCritSec;
    static CritSec      g_singleCritSec;
    static CritSecTable g_critSecTable;
};
Figure 7 main
typedef vector<unsigned long>       NumberList;
typedef NumberList::const_iterator  NumberIter;

int main(int argc, char* argv[])
{
    try
    {
        // Interpret command-line arguments:
        unsigned long numEntries;
        unsigned long numIterations;
        NumberList numThreadsList;
        interpretCommandLine(argc, argv, numEntries, numIterations,
            numThreadsList);

        // Initialize the in-memory database:
        Database db(numEntries);

        // Print output header:
        cout <<
            "\n"
            "# of DB entries:," << numEntries << "\n"
            "# of iterations:," << numIterations << "\n"
            "All times in milli-seconds\n"
            "\n"
            "# Threads,Time (Single CritSec),Time (CritSec Table)"
            << flush;

        // Run a test for each number of threads:
        for (NumberIter i = numThreadsList.begin();
            i != numThreadsList.end(); i++)
        {
            cout << '\n' << *i;
            DBEntry::critSecMode(true);     // single critical section
            doTest(db, numIterations, *i);
            DBEntry::critSecMode(false);    // critical section table
            doTest(db, numIterations, *i);
        }

        cout << endl << endl;
    }
    catch (const Exception& e)
    {
        cout << e.getErrorMsg() << endl << endl;
    }
    catch (const exception& e)
    {
        cout << "std::exception:  " << e.what() << endl << endl;
    }
    return 0;
}
Figure 8 doTest
typedef vector<auto_ptr<WorkerThread> > ThreadList;
typedef ThreadList::const_iterator      ThreadIter;

static void doTest(Database& db, unsigned long numIterations,
    unsigned long numThreads)
{
    // Set up thread pool:
    ThreadList threads;
    threads.reserve(numThreads);
    for (unsigned i = 0; i < numThreads; i++)
    {
        WorkerThread* pThread = new WorkerThread(i, numThreads,
            numIterations, db);
        threads.push_back(auto_ptr<WorkerThread>(pThread));
    }

    Timer timer;

    // Start threads running:
    for (ThreadIter j = threads.begin(); j != threads.end(); j++)
    {
        (*j)->start();
    }

    // Wait on threads:
    for (ThreadIter k = threads.begin(); k != threads.end(); k++)
    {
        (*k)->wait();
    }

    timer.stop();

    cout << ',' << timer.getMilliSec() << flush;
}
Figure 9 WorkerThread Class Declaration
class WorkerThread : public Thread
{
public:
    WorkerThread(unsigned long threadNum, unsigned long numThreads,
        unsigned long numIters, Database& db);
    virtual ~WorkerThread();

protected:
    virtual void run();

private:
    enum RequestType { k_read, k_update };

    void getRequest(unsigned long& entryId, RequestType& requestType,
        string& newValue);
    void doUpdate(unsigned long entryId, const string& newValue);
    string doRead(unsigned long entryId);
    static void simulateWork(unsigned long iterations);

    enum
    {
        k_randMax = 1771875ul,
        k_randCoeff = 2416ul,
        k_randOffset = 374441ul
    };
    unsigned long rand(unsigned long hi);

    unsigned long   m_randSeed;
    unsigned long   m_threadNum;
    unsigned long   m_numThreads;
    unsigned long   m_numIters;
    Database&       m_db;
};
Figure 10 WorkerThread Class Implementation
WorkerThread::WorkerThread(unsigned long threadNum,
        unsigned long numThreads, unsigned long numIters, Database& db) :
    m_randSeed(threadNum % k_randMax),
    m_threadNum(threadNum),
    m_numThreads(numThreads),
    m_numIters(numIters),
    m_db(db)
{
}

WorkerThread::~WorkerThread()
{
}

void WorkerThread::run()
{
    // The strange starting point and step size in this loop make sure
    // that there are the correct total number of iterations among all
    // the threads, even if m_numIters is not evenly divisible by
    // m_numThreads.
    for (unsigned long i = m_threadNum; i < m_numIters;
        i += m_numThreads)
    {
        // Get a request:
        unsigned long entryId;
        RequestType requestType;
        string value;
        getRequest(entryId, requestType, value);

        // Process the request:
        if (requestType == k_update)
        {
            doUpdate(entryId, value);
        }
        else
        {
            value = doRead(entryId);
        }

        // In a real-world server, the result would be marshaled back
        // to the client here.
    }
}

void WorkerThread::getRequest(unsigned long& entryId,
    RequestType& requestType, string& newValue)
{
    const unsigned long k_numReadsPerUpdate = 5;

    entryId = rand(m_db.getNumEntries() - 1);
    requestType = (rand(k_numReadsPerUpdate) == 0)
        ? k_update
        : k_read;
    if (requestType == k_update)
    {
        newValue = "new value";
    }
}

void WorkerThread::doUpdate(unsigned long entryId, const string& newValue)
{
    // Update the database:
    DBEntry& entry = m_db.getEntry(entryId);
    LockKeeper<DBEntry> keeper(entry);
    entry.setValue(newValue);

    // Simulate update overhead:
    simulateWork(100);

    // Unlock entry as we return from this method
}

string WorkerThread::doRead(unsigned long entryId)
{
    // Read from the database:
    DBEntry& entry = m_db.getEntry(entryId);
    LockKeeper<DBEntry> keeper(entry);
    string readResult = entry.getValue();

    // Simulate read overhead:
    simulateWork(10);

    return readResult;
    // Unlock entry as we pass out of this scope
}

static double g_dummy = 0;  // prevents optimizing simulateWork away
void WorkerThread::simulateWork(unsigned long iterations)
{
    for (unsigned long i = 0; i < iterations; i++)
    {
        // Meaningless work to take up time:
        unsigned long x = i % 37;
        g_dummy = cos(x) + sin(x) + cosh(x) + sinh(x);
    }
}

// This is a very simple pseudo-random number generator, which overcomes
// two limitations of the built-in rand() function:
//    * Its maximum is considerably higher, and
//    * It doesn't serialize calling threads.
// Derived from "Numerical Recipes in C", by Press, Flannery, Teukolsky,
// and Vetterling, ©1988 by Cambridge University Press, pp.209-211.
unsigned long WorkerThread::rand(unsigned long hi)
{
    assert(hi < k_randMax);
    m_randSeed = (m_randSeed * k_randCoeff + k_randOffset) % k_randMax;
    return (hi * m_randSeed) / (k_randMax - 1);
}
Figure 11 CritSecTable Class Definition
class CritSecTable
{
public:
    CritSecTable()
        {}
    ~CritSecTable()
        {}

    void acquire(void* p)
        { m_table[hash(p)].acquire(); }
    bool tryAcquire(void* p)    // use only on Windows NT or Windows 2000
        { return m_table[hash(p)].tryAcquire(); }
    void release(void* p)
        { m_table[hash(p)].release(); }

private:
    static unsigned char hash(void* p);

    CritSec m_table[256];
};
Figure 12 CritSecTable Class Implementation
unsigned char CritSecTable::hash(void* p)
{
    unsigned char result;

    if (sizeof(void*) == 8)
    {
        assert(sizeof(unsigned long) == 4);
        assert(sizeof(unsigned short) == 2);

        unsigned long temp1 = ((unsigned long*) (&p))[0]
            ^ ((unsigned long*) (&p))[1];
        unsigned short temp2 = ((unsigned short*) (&temp1))[0]
            ^ ((unsigned short*) (&temp1))[1];
        result = ((unsigned char*) (&temp2))[0]
            ^ ((unsigned char*) (&temp2))[1];
    }
    else if (sizeof(void*) == 4)
    {
        assert(sizeof(unsigned short) == 2);

        unsigned short temp = ((unsigned short*) (&p))[0]
            ^ ((unsigned short*) (&p))[1];
        result = ((unsigned char*) (&temp))[0]
            ^ ((unsigned char*) (&temp))[1];
    }
    else
    {
        result = ((unsigned char*) (&p))[0];
        for (unsigned i = 1; i < sizeof(void*); i++)
        {
            result ^= ((unsigned char*) (&p))[i];
        }
    }
    return result;
}
Figure 13 DBEntry Class
bool            DBEntry::g_useSingleCritSec = true;
CritSec         DBEntry::g_singleCritSec;
CritSecTable    DBEntry::g_critSecTable;

void DBEntry::acquire()
{
    if (g_useSingleCritSec)
    {
        g_singleCritSec.acquire();
    }
    else
    {
        g_critSecTable.acquire(this);
    }
}

void DBEntry::release()
{
    if (g_useSingleCritSec)
    {
        g_singleCritSec.release();
    }
    else
    {
        g_critSecTable.release(this);
    }
}
Page view tracker