Feeds:
Posts
Comments

Archive for February, 2011

In Windows, threads run in units of “quantums”. After a thread completes its quantum, Windows may choose to run another thread based on priority or thread states.

This quantum settings is located in the registry called Win32PrioritySeparation. It is a wacky matrix that is represented in a bitfield.

Window XP and Vista uses short variable quantum settings. Thread owned by a process with a foreground window are assigned 18 quantums, and background window (e.g. services) are assigned 6 quantums. The Window Server edition uses 36 quantums for all threads.

So how long exactly is one quantum?

One Quantum

Although the length of a quantum is not exposed to developers, Windows Internal explained that the value is located in a kernel variable called KiCyclesPerClockQuantum. You can extract the value through Windbg with a command “dd nt!KiCyclesPerClockQuantum¬† l1“.

Alternatively, the book devised a method to calculate the value manually. Below is a program I wrote following the described algorithm.

try
{
	CPdhQuery procInfo_frequency(std::tstring(
		_T("\\Processor Information(0,0)\\Processor Frequency"))
		);

	// Step 1: Get the CPU speed in MHz
	__int64 cpuSpeedHz = static_cast<__int64>(
		procInfo_frequency.CollectSingleData()
		);

	// Step 2: Convert it to Hz
	cpuSpeedHz *= 1000000;

	DWORD timeAdjustment = 0;
	DWORD clockInterval100Ns = 0;
	BOOL timeAdjustmentDisabled = 0;

	// Step 3: Get the frequency of the clock interrupt. This value is
	// dependent on your processor type.
	GetSystemTimeAdjustment(
		&timeAdjustment,
		&clockInterval100Ns,
		&timeAdjustmentDisabled);

	// Step 4: Get the rate of the clock fires per second.
	double clockIntervalPerSecond =
		static_cast<double>(clockInterval100Ns)/10000000;

	// Step 5: Get the number of cycles elapsed per clock interval.
	double cyclesPerClockInterval = cpuSpeedHz * clockIntervalPerSecond;

	// Step 6: A quantum is 1/3 of a clock interval.
	__int64 clockCyclePerQuantum =
		static_cast<__int64>(cyclesPerClockInterval / 3);

	// Step 7: The quantum length in time
	double quantumLengthSec =
		static_cast<double>(clockCyclePerQuantum) /
			static_cast<double>(cpuSpeedHz);

	tcout
		<< _T("Clock Cycles Per Quantum = ")
		<< clockCyclePerQuantum
		<< std::endl;

	tcout
		<< _T("Duration Per Quantum = ")
		<< quantumLengthSec
		<< _T(" second")
		<< std::endl;
}
catch(CPdhQuery::CException const &e)
{
	tcout << e.What() << std::endl;
}
Clock Cycles Per Quantum = 13873688
Duration Per Quantum = 0.00520003 second

Thoughts

The quantum value provides insight on how often a thread may be preempted.

This information can be surprising useful. I recently used it to roughly estimate a thread’s response time, and correctly determined a device driver issue.

The output of my program differs slightly (~3%) from the readings in the kernel. It appears that the processor frequency in performance counter is different from the reading in PRCB.

Download

The full source can be found here.

Tools: Visual Studio 2008, Window 7 64bit, Intel I5-750 (quad core)

Read Full Post »

shared_ptr and NULL

The interface of shared_ptr is carefully designed such that it has the syntax of a raw C pointer. So naturally, shared_ptr is comparable against NULL.

shared_ptr<SomeClass> sc;
//...
if(sc != NULL)  { } // is it not NULL
if(sc == NULL)  { } // is it NULL

But NULL is really an abused integer. How would you implement such a comparison?

This is C++.  There is always devil in the details.

Obvious, but wrong solution

Attempt #1:

An obvious solution is to implement an operator== and operator != to compare against a pointer type of its type parameter.

template<typename T>
class shared_ptr
{ //...
   bool operator==(T *p) const // compare against T* and check for equality
   {
      if(px_ == p)
         return true;
      return false;
   }
   bool operator!=(T *p) const { /*inverse of == */}
   T* px_;
}

Why it fails

Yes, this will correctly support the NULL comparison listed above, but there are four other ways in C/C++ to check a pointer for NULL.

The comparison operator fails if the comparison order is reversed, or if implicit boolean conversion is used.

shared_ptr<SomeClass> sc;
//...
if(NULL != sc) {} // no such conversion supported
if(NULL == sc) {}
if(sc) {} // fails the implicit conversion to bool
if(!sc) {}

And it really doesn’t make sense to compare a shared_ptr with a raw pointer.

shared_ptr<SomeClass> sc;
SomeClass*rp;
//...
if(rp != sc) {} // doesn't make sense
if(rp == sc) {} // doesn't make sense

So operator== and operator!= provide a poor coverage to this problem. We need something better.

More sophisticated almost solutions

Attempt #2

So what about operator bool? Maybe we can convert the shared_ptr to a boolean type by return false if it is NULL, and return true otherwise.

template<typename T>
class shared_ptr
{ //...
   operator bool() const // conversion to bool
   {
      if(NULL == px_)
         return false; // implicit conversion to false if NULL
      return true; // implicit conversion to true otherwise
   }
   T* px_;
}

Why it fails

Although this solution supports all six ways of NULL comparison mentioned before, it comes with a bit of baggage.

Thanks to an implicit bool-to-integer promotion, you can now do stuff like this.

shared_ptr<SomeClass> sc;
float f = sc;  // this actually compiles
int i = sc;     // do not want!

Attempt #3

How about operator T*, where shared_ptr implicitly converts to a pointer type of its type parameter?

template<typename T>
class shared_ptr
{ //...
   operator T*() const // conversion to T*
   {
      return px_;
   }
   T* px_;
}

Why it fails

This solves the problem of implicit integer promotion, but opens a major hole. Now your shared_ptr is actually “leaky” and deletable. This behavior allows shared_ptr to be easily abused and misused.

shared_ptr<SomeClass> sp;
SomeClass *rp;
rp = sp; // uh oh, reference count leak
delete sp; // OMG! heap corruption

The Boost Solution

Here’s the solution chosen by boost library (similar solution also observed in VC10).

template<typename T>
class shared_ptr
{ //...
   typedef T * shared_ptr<T>::*unspecified_bool_type;
   operator unspecified_bool_type() const // never throws
   {
       return px_ == 0? 0: &shared_ptr<T>::px_;
   }
   T* px_;
}

This solution is very clever. It implicitly converts the shared_ptr into “a pointer to member variable”. Based on the NULLness of the shared_ptr, it will either return 0 or a pointer to member variable of type T*.

With this implementation, shared_ptr manages to support the six ways of checking for NULL, avoids the dangerous comparisons, and has no integer promotion side effects.

Is the boost solution perfect? Of course not. The code is confusing, and you can still do some crazy stuff.

shared_ptr<SomeClass> sp(new SomeClass);

// Grab the shared_ptr's "pointer to its member variable"
shared_ptr<SomeClass>::unspecified_bool_type ubt = sp;

// Extract the shared_ptr's inner pointer member in the most obscure way
SomeClass *innerPointer = sp.*ubt;

Final Thoughts

For such an innocent comparison, the depth of the solution is astonishing. It is amazing to see how far C++ library writers are willing to go to work around the nastiness of the language.

After figuring this out, I later learned that this technique is called the Safe Bool Idiom. (As usual, google is useless if you don’t know what you are looking for).

C++0x will address this mess with the explicit conversion operator.

Read Full Post »

When writing platform independent libraries at work, I use boost posix_time as the primary mechanism to generate timestamps. But when integrating the platform independent libraries to Windows world, the interface requires everything to be converted Windows FILETIME.

Recall, Windows FILETIME is a 64 bit structure that represents the number of 100-nanosecond intervals since January 1, 1601 (UTC).

Boost posix_time library has an API called from_ftime<ptime>(FILETIME ft), where it can create a ptime object from a Windows FILETIME.

Strangely, it’s counterpart does not exist. In other word, there is no to_ftime.

Code

I really dislike writing this type of basic time conversion routine. It has probably been done before, and I am probably reinventing the wheel (a common disease in my profession).

Believe it or not, I could not find a solution online. At least, I found out I am not the first person to want to do this.

Anyway, here’s one way to do it.

#include <boost/date_time/posix_time/posix_time.hpp>
#include <boost/date_time/gregorian/gregorian.hpp>
#include <windows.h>
#include <boost/cstdint.hpp>

FILETIME PtimeToFileTime(boost::posix_time::ptime const &pt)
{
	// extract the date from boost::posix_time to SYSTEMTIME
	SYSTEMTIME st;
	boost::gregorian::date::ymd_type ymd = pt.date().year_month_day();

	st.wYear = ymd.year;
	st.wMonth = ymd.month;
	st.wDay = ymd.day;
	st.wDayOfWeek = pt.date().day_of_week();

	// Now extract the hour/min/second field from time_duration
	boost::posix_time::time_duration td = pt.time_of_day();
	st.wHour = static_cast<WORD>(td.hours());
	st.wMinute = static_cast<WORD>(td.minutes());
	st.wSecond = static_cast<WORD>(td.seconds());

	// Although ptime has a fractional second field, SYSTEMTIME millisecond
	// field is 16 bit, and will not store microsecond. We will treat this
	// field separately later.
	st.wMilliseconds = 0;

	// Convert SYSTEMTIME to FILETIME structure
	FILETIME ft;
	SystemTimeToFileTime(&st, &ft);

	// Now we are almost done. The FILETIME has date, and time. It is
	// only missing fractional second.

	// Extract the raw FILETIME into a 64 bit integer.
	boost::uint64_t _100nsSince1601 = ft.dwHighDateTime;
	_100nsSince1601 <<=32;
	_100nsSince1601 |= ft.dwLowDateTime;

	// Add in the fractional second, which is in microsecond * 10 to get
	// 100s of nanosecond
	_100nsSince1601 += td.fractional_seconds()*10;

	// Now put the time back inside filetime.
	ft.dwHighDateTime = _100nsSince1601 >> 32;
	ft.dwLowDateTime = _100nsSince1601 & 0x00000000FFFFFFFF;

	return ft;
}

And here’s how I verified it.

  1. Create a ptime object, and convert it to FILETIME with the routine above.
  2. Then use from_ftime<ptime>(FILETIME ft) to convert the generated FILETIME into another ptime object.
  3. Verify that the two ptime object is identical.
boost::posix_time::ptime now =
	boost::posix_time::microsec_clock::universal_time();

FILETIME ft = PtimeToFileTime(now);

std::cout << boost::posix_time::to_iso_extended_string(now) << std::endl;

boost::posix_time::ptime clone =
	boost::posix_time::from_ftime<boost::posix_time::ptime>(ft);

std::cout << boost::posix_time::to_iso_extended_string(clone) << std::endl;

Output:
2011-02-04T06:09:30.723805
2011-02-04T06:09:30.723805

On a side note

The routine PtimeToFileTime does not validate its input.

The year_month_day() routine could contain invalid/uninitialized fields.

SystemTimeToFileTime could fail.

I will leave that as an exercise.

Read Full Post »

A common guideline in best coding practices is to never ignore compiler warnings, and always use the highest warning level possible. For Microsoft C/C++ compilers, this mean level 4 (/W4).

But just because your code compiles cleanly under level 4, it doesn’t mean external libraries would too.

Let’s take Boost library as an example. It is arguably the most well written C++ library in the world. Yet it is not cleared of level 4 warning until 1.40.

The truth is that level 4 warning level is harsh (and often silly), and some code are just not fit to make the cut.

Use L3 for the Uglies

For ugly header files that aren’t designed with level 4 warning in mind, just compile them with level 3 with the #pragma warning(push,3) command.

Here’s an example.

#pragma warning( push, 3 ) // boost make_shared has L4 warnings, so use L3.
	#include <boost/make_shared.hpp>
#pragma warning(pop) // resume to original warning level (4)

An often suggested alternative is to use #pragma warning(disable:xyz), where xyz is the warning number.
This solution is clumsy because it requires you to find out every single warning emitted from every external header file, and then disable them one at a time. I am too busy (lazy) for that. :)

Read Full Post »

Follow

Get every new post delivered to your Inbox.