Analogous

Duplication

2009-06-01T15:26:00.000-07:00

Its been a while since ive encountered two weird C++ bugs in one week.

The first was on OSX, where the compiler generated two copies of the same class which both contained a union but with different layouts.


template <typename _Kind_>
class Object
{
public:

 enum ObjectType
 {
  TYPE_VOID,
  TYPE_KIND,
 };
 
 union ObjectData;
 {
  void * Void;
  _Kind_ * Kind;
 };

 ObjectType Type; 
 ObjectData Data;
 
 void * operator & () const
 {
  switch(Type)
  {
  case TYPE_VOID: return (void*)Data.Void;
  scase TYPE_KIND: return (void*)Data.Kind;
  }
  
  return 0;
 }
};

The resulting bug was exposed when a non const version of the object was used to call the const operator.


int value = 8;

Object<int> obj;
obj.Type = Object<int>::TYPE_VOID;
obj.Data.Kind = &value;

// This calls the const operator which may return an invalid 
// memory location. When dereferenced this will cause an error.

int * result = &obj;

if (*result == 4)
{
 // ...
}

Strange but true, obviously the code producing the bug was a little more complicated but semantically exactly the same as that above.

The second bug was not quite so serious, but still very confusing as it relates to one of those obscure C++ standard "undefined behaviors". Sometimes i wish the standards body would realise that the language may actually benefit from having some consistency and predictability.

This time the code was to perform some decoding from ascii to binary hex values on Windows and used a lookup table to convert 2 ascii bytes into 1 binary byte.


char entry[] = {0x01,0x02,0x03,0x04,0x05};
int table[] = {0x01,0x02,0x03,0x04,0x05};

int decode[1];
decode[0] = (table[*entry++]<<4)|(table[*entry++]);

However the result was not what you would expect. The assembly generated looked something like this. With the result being that the two post increments did not
occur until after the assignment. Weird... ?


009603A7  mov         eax,dword ptr [entry] 
009603AA  movsx       ecx,byte ptr [eax] 
009603AD  movsx       edx,byte ptr table (0BC4A60h)[ecx] 
009603B4  shl         edx,4 
009603B7  mov         eax,dword ptr [entry] 
009603BA  movsx       ecx,byte ptr [eax] 
009603BD  movsx       eax,byte ptr table (0BC4A60h)[ecx] 
009603C4  or          edx,eax 
009603C6  mov         byte ptr [decode],dl 
009603C9  mov         ecx,dword ptr [entry] 
009603CC  add         ecx,1 
009603CF  mov         dword ptr [entry],ecx 
009603D2  mov         edx,dword ptr [entry] 
009603D5  add         edx,1 
009603D8  mov         dword ptr [entry],edx

But it turns out there is an obscure C++ feature (see section 5, paragraph 4 of the ISO C++ standard) whereby you are not allowed to modify the same variable twice in a single expression. Doing so results in the above "undefined behavior". Great.

Why this needs to be so i dont really understand.

So there you go, two annoying bugs in one week. Both required some pretty heavy problem solving to see.

C++ is a hard language to love.

Privateering

2007-11-09T19:51:00.000-08:00

Nothing divides programmers more than coding style, in particular the representation of private member variables.

Here are some of the options;

class Class
{
    m_member
    m_Member

    _member
    _Member

    member
    Member
};

The problem is, if you are like me you don't particularly like prefixes like m_ or _ and the problem with not using a prefix is that it can conflict with method names.

Using prefixes unfortunately can create bad code since it encourages programmers not to think about naming or the number of members in a class.

The solution can be to use a lower case member name and an upper case method name, but then there is no distinction between local variables and member variables within a method body.

Another less common solution which i use sometimes, since i always prefer to use no prefixes and uppercase member names just like methods, is to wrap my private members in a struct to remove the naiming conflict but keep the cleanliness and readability.



class Class
{

    struct PrivateMembers
    {
        Member;
    }

    PrivateMembers Private;

    void Member()
    {
        Private.Member; 
    }
};

Shifting

2007-11-09T19:43:00.000-08:00

Dos Date Time
Two's Compliment

I recently encountered this strange but simple bug in some code that i had written to convert from posix standard to dos standard time. It was strange becuase it only shows up when you use dates and times which are earlier than a certain magic number.

Dos uses a strange bit packed representation of date and time in two 16 bit words. Within each word the various values occupy a set number of bits as follows.

Date Format

0-4 Day of the month (1–31)
5-8 Month (1 = January, 2 = February, and so on)
9-15 Year offset from 1980 (add 1980 to get actual year)

Time Format
0-4 Second divided by 2
5-10 Minute (0–59)
11-15 Hour (0–23 on a 24-hour clock)

So assuming you have some simple integer representation of time and date, lets call it a Calendar you might use the following code to convert to and from the Dos format.



// Conversion to dos date and time
Calendar calendar;
short date = ((calendar.Year - 1980)<<9)
  + ((calendar.Month)<<5) + calendar.Day;
short time = ((calendar.Hour)<<11) 
  + ((calendar.Minute)<<5) + (calendar.Second/2);

// Conversion from dos date and time
Calendar calendar;
calendar.Year = ((date>>9)&0x007F)+1980; // 7 bits
calendar.Month = ((date>>5)&0x000F);  // 4 bits
calendar.Day = (date&0x001F);   // 5 bits

calendar.Hour = ((time>>11)&0x001F);  // 5 bits
calendar.Minute = ((time>>5)&0x003F);  // 6 bits
calendar.Second = (time&0x001F)*2;  // 5 bits

So wheres the bug ?

Well, the bug occurs when you use a year earlier than 1980, for example 1970. What happens is that thanks to the subtraction of 1980 from the year you end up with a negative number which is left shifted 9 bits into the 16 bit word.

Now usually when you do bit packing, its standard practice to mask the bits as you extract them by using an binary and after the right shift operation. This ensures that the value you get is isolated from the other bits, especially those further to the left since usually you right shift until zero.

In this case though the year is different from the other values in the date word. Becuase the year occupies the left most bits, its two's compliment representation as a negative number is preserved all the way through the right shift operation until the binary and, where it is suddenly forced into being a positive integer with the same 7 bits, changing it from a small negative to a large positive number.

The solution is to remove the binary and mask on the year. For all other values the mask is still necessary, but due to the weird although perhaps purposeful design of the dos date and time format, the year is special.

Released

2007-02-08T21:05:00.000-08:00

Finally after many sleepless nights, numerous relationships, two continents, and a lot of cold weather i have released some of my work into the wild under the GNU General Public License.

Its a C++ framework called Reason, and represents about 40% of the code that ive produced in ecent years. I hope you enjoy reading it, and maybe someone will even find it useful :)

http://reasoning.info/examples.htm

Axioms

2005-07-26T18:59:00.000-07:00

I was fumbling through some old code this evening after discovering that my original interpretaion of the slightly skewed BNF grammar used in FRC2396 was incorrect. Obviously despite creating the standard Sir Tim Burners Lee hadn't quite got the hang of hyperlinking yet, and so it is generally left up to the reader to discover the reference to RFC822 in the third paragraph of section 1.6, and hence forth seek out the correct interpretation.

Speaking of hyperlinking, i found an amusing anecdote in my comments which i thought might be worth sharing. It originates from the W3C axioms of web architecture, and pretty much states that the internet in its current form is a complete abomination.

All the same, a word of caution is appropriate about the indiscriminate or deliberately misleading abuse of the identity of the object referred to by a URI. A web server is often in a position to know a lot of context about a request. This can include for example, the person who is asking, the document they were reading last from which they followed the link. It is possible to use this information to ramatically change the content of the document referred to. This undermines the concept of identity and of reference in general. To do that without making it clear is misleading both to anyone who quotes the URI of a page or who follows the link.

Unless it is clearly indicated on the page (or using a future protocol) , to return differing information for the same URI must be considered a form of deception. It also of course messes up caches.

Reflect on this next time you create some dynamic content...

Superstition

2005-07-23T18:28:00.000-07:00

Sometimes, just sometimes the compiler is actually right.

The problem is, not always. Like every nascent computer user sometimes even seasoned programmers arbitrarily distrust the machine.


Technofear.n - The result of seemingly random 
consequences caused by the actions of inept users 
leeding to a deep sense of confusion and distrust 
for technology. i.e. "programming the vcr"

You see, as a programmer, even more so than a user it is essential to be able to trust the tools that you use to produce the results that you expect. The programmer must have faith that the compiler tells the truth in all matters and all things.

For if the compiler lies, then the programmer is sure to spend many countless frustrating hours chasing bugs which don't exists. And eventually their confidence will be eroded to the point that they will also waste countless hours swearing at the compiler for producing an error, which in fact is genuine.

Unfortunately its a bit of a boy who cried wolf scenario, and the horrible truth and shame about the software industry, is that even today, all compilers lie.

Anyone who has ever misplaced a curly brace or two and received a cascade of endless random errors from their compiler knows this shameful fact of life.

So then, it is left to the programmer to develop their own intuitive understanding of the particular tools and compilers that they use, to the point that they know when an error is and error and when the machine just needs a good kick. This truly is the art of programming, and perhaps more than you might think it can separate the good programmers from the great programmers, and at the very least, the frustrated from the productive.

Ive just fixed a rather good example of such an error. And fortunately for me, i chose wisely in trusting the compiler in what seemed like a perfect opportunity not too. You see, my program was operating correctly in debug, but failing in release.

An obvious problem you may suggest, but not quite. You see, if i slowed the program down in release, it worked correctly. Ahhh! i hear you say, "clearly youve got a race condition between one or more threads". But alas, there is only a single thread and the timing is very subtle.

It sure did look like one of those occasions where one may be tempted to start looking under the rug for a wolf. But i held fast and debugged the code into the long hours of the night. And after much toiling, and tracing, and printing as there are only limited ways one can effectively debug release code, i started to narrow the trail.

After two days of debugging i found the problem.

It was caused by two objects being compared by memory addresses. In the world of debug code, memory addresses are consecutive manufactured things, contrived to make the task of debugging easier for the programmer. But in release code, memory addresses are random highly variable things. So in debug, object A was less than object B, but in release where the memory was different, object B was less than object A.

At its root was an innocuous problem, but it was burried deep in thousands of lines of code. Knowing when to trust and when to distrust your tools is critical, becuase sometimes...

The compiler is actually right.

Epoch

2005-04-19T11:19:00.000-07:00

We are Microsoft, we will store dates with a different epoch and a different granularity to Unix.

An epoch of 01 Jan 1970 00:00:00 isn't good enough for us, no we want 01 Jan 1601, 00:00:00. There much better.

And whats this seconds rubbish, we want 100 nanosecond ticks thanks very much. And we will call it file time so as to really confuse you.

But its ok, well give you this really obvious conversion function so you can make all your code non standard.


#include 

void TimetToFileTime( time_t t, LPFILETIME pft )
{
    LONGLONG ll = Int32x32To64(t, 10000000) 
    + 116444736000000000;
    pft->dwLowDateTime = (DWORD) ll;
    pft->dwHighDateTime = ll >>32;
}

Did you catch that ?


116444736000000000 / 10  = 11644473600000000 (Microseconds)
11644473600000000 / 1000 = 11644473600000 (Milliseconds)
11644473600000 / 1000  = 11644473600 (Seconds)
11644473600 / 60  = 194074560 (Minutes)
194074560 / 60   = 3234576 (Hours)
3234576 /24   = 134774 (Days)
134774 / 365   = ~369 (Years)

Which is roughly the interval between the two epochs, give or take a few leap years and leap seconds.

Oh yea, and then in .NET we will change it all again, just to be cool. Now we want the ultimate epoch - midnight on the 01 Jan A.D. Beat that Richard Stallman.

Multiplicity

2005-04-16T11:52:00.000-07:00

Finally, someone in the C++ community that realises how far the language has fallen behind becuase its missing a decent library.

"I'm going to speculate now, because I haven't been watching Java and I've just got my feet a little bit wet in .NET. But I would say that while the C++ community was focusing on templates, the STL, and exceptions—oddly enough the three are wrapped up together pretty closely—what they were not doing was component-based development. For example, there is no huge collection of class libraries for C++. The standard library for C++ is pretty impoverished. In the meantime, the rest of the world was busy creating huge class libraries that let you write all kinds of really neat applications without having to write very much code. Certainly Java is famous for its libraries. .NET has a huge number of libraries."
- Scott Meyers

Abstract Base Classes

I was reading the above article becuase ive just been using multiple inheritance in my own library. The design forced me to use it and i wanted to validate some of my rational. Multiple inheritance allowed me to connect up the notion of streams with that of lower level IO like files and sockets. So whilst i have a File class and a Socket class i also have a Stream class and an associated FileStream and SocketStream, each of which derive multiply from the base class of that type and implement the Stream interface. The interesting part is that Stream implements two other interfaces, Reader and Writer. File and Socket also implement Reader and Writer which define some standard contracts for reading and writing bytes.


class Reader
{
    ...
    virtual int Read(char * data, int size)=0;
    virtual int Read(Writer & writer, int amount=0);
    ...
};

class Writer
{
    ...
    virtual int Write(char * data, int size)=0;
    virtual int Write(Reader & reader, int amount=0);
    ...
};

This is a very useful notion, it lets me have Stream's which i can use for efficient progressive reading, writing, and seeking, but i can also use these streams interact with their more primitive classes. For instance, to read from a SocketStream directly into a File i can do this:


SocketAddress socketAddress("www.google.com",80);
SocketStream socketStream;
socketStream.Connect(socketAddress);
socketStream.Write("GET / HTTP/1.0\r\n\r\n");

File file("/tmp/google.html");
file.Write(socketStream);

And now i have a local copy of the html page. It works becuase the Reader and Writer interfaces allow direct connections to one another. This provides interoperability between streams and other forms of IO when i just want to do a simple redirection. But i can still harness all the pipelining capability of streams when i need it.

The inheritance heirarchy of the FileStream class looks like this:


FileStream
[
    File
    [
        Filesystem
            [...]
        Reader
        Writer    
    ]    
    Stream    
    [
        Reader
        Writer
    ]
]

Of course the FileStream can do everything that a File can do, but it also blends with it Stream semantics. Multiple inheritance allows the common interfaces to be merged and the simple composition of two distinct usage patterns into a single class.

Its nice when an intuitive design just jumps out at you, its a rare example of a truly useful piece of multiple inheritance.

Maintainability

2005-02-16T01:26:00.000-08:00

OSS Should Strive for Even Greater Maintainability
Open Source Code Maintainability Analyzed
Halstead Complexity Measures
Cyclomatic Complexity

What makes software maintainable. Is it the number of lines of code, the formatting, the density of operators, the frequency of comments, the Halstead Volume, or perhaps the Cyclomatic Complexity ?

I don't think so. Theres only one way you can measure software maintainability, and that's how well it's been written. The problem is there's no algorithm which can tell you how well written a piece of software is.

Like a good movie script or a compelling novel, well written software this has less to do with metrics like the number of syllables or chapters and more to do with how the story is told.

The problem with most software is that it is not written to be read or maintained, it is written to be compiled and run. If the software industry understood even a little of the psychology involved in conveying information they would have realised long ago that like a novel, code needs to be presented in a readable format.

Which brings us to the first important factor in maintainability.

Understanding

For code to be understandable it must be clear, unambiguous and easy to read. This immediately excludes languages like Perl, frameworks like MFC, and standards like Hungarian Notation.

If you are an English speaker then it makes sense that the easiest thing for you to understand is "plain english", so it follows that code should be written in that form. Intent and semantics are far more important than type and scope. Mixed case isMuchEasierToRead than singlecasewithnospaces, or single_case_with_underscores, and MUCH LESS OFFENSIVE THAN UPPERCASE. Understadable code is easier to maintain because it takes less time and effort to comprehend.

Comprehension

Once you understand the code, you can work out what its doing. When you work out what its doing you can determine its purpose and therefore comprehend it. When you can comprehend code you are well on your way to being able to make effective modifications. Maintainable code should always be easy to modify.

But just comprehending the code is not enough. You also need to be able to work within the confines of the implementation.

Implementation

There is no one way to implement an algorithm, a thousand people will implement the same code in a thousand different ways. Implementations differ becuase different people have different priorities and ways of thinking about things. Good implementations are those which don't just achieve the desired outcome, they follow principles.

An implementation is a balance between performance, complexity, size, extensibility, and clarity. It is a common misconception that high performance code necesitates a smaller and less extensible implementation whith reduced clarity and increased complexity. Just as it is also a common misconception that larger code with greater extensibility results in increased clarity and reduced complexity.

The very best implementations are those which break down the problem and express it in terms of domain specific concepts and nomenclature, aiding in comprehension and making it easier to maintain.

Expresive code which is separated into obvious concepts with logical relationships and sensible naming makes it easier for a developer to modify one area wihtout adversly impacting other unrelated areas. It can also assist by removing complexity from otherwise monolithic implementations and encouraging re-use, without which maintenance would be a never ending and impossible task.

Sometimes you may see an implementation which is so simple and understandable that you may wonder why it is that no one thought of it before. Such implementations are akin to graphical proofs of mathematical theorems. Powerful in their impact and yet obvious in their semantics.

Semantics

Possibly the most important aspect of maintainability and yet the least understood. Semantics is the meaning conveyed by the code. It influences how the developer interacts with and uses the libraries or environment with which the develop their software.

Code which is written with good semantics is more likely to be used correctly and extended to produce better, more reliable software. Code with bad semantics on the other hand is more likely to make it difficult for other programmers to use and will therefore result in more maintenance issues.

The essential point here is that ambiguity of purpose leads to incorrect use, and incorrect use leads to bugs.

Difference types of software require different approaches. Writing a library or framework is has vastly different concerns than writing and application.

Writing great software is an art not a technique, but by obeying common sense and using good principles you are more likely to succeed.

My favorite is the principle of least surprise.

There are a lot of common words for the concepts that ive described here which i have deliberately chosen not to use beucase of their ambiguous semantics. Different people interpret things in different ways and often labeling concepts can result in the adoption of a false understanding of what they mean.

Understanding

2005-01-29T18:44:00.000-08:00

Vocabulary

Ive just been reading through the archives in my aggregator and noticed an interesting point that Joel was trying to make but which he said he had trouble describing in english.

The point is about the difference between the discovery and application of knowledge. I like to refer to this divide as the difference between a technician and a scientist.

The technician is someone skilled in the art of applying knowledge. It is easy to learn and to use knowledge without necessarily understanding it. Its just following a set of instructions, a method if you like. The problem with method is that it does not allow you to solve problems or perform tasks which lie outside the rigid definition of what you have learnt.

If on the other hand you are a scientist, then you are skilled in the art of learning. The first thing a good scientist learns is how to learn. A good scientist will always attempt to understand what it is that they are learning, not just memorise the formulae. You see, the scientist recognises that it is not necessarily the knowledge of facts which is important, but rather the path by which those facts were derived. By understanding the path, you understand the reasoning. And if you understand the reasoning which produced the knowledge then you yourself are more likely to be able to extend that knowledge.

Everything has a context, and understanding that context allows us to move beyond mere recognition and application, it allows us to adapt and invent. To draw on our in depth understanding of how the knowledge was acquired and use it to create something new.

How many of use can truly say that we understand something enough to be able to arrive at it by our own powers of reasoning and deduction ?

Those that truly learn can.

Try it for yourself, take something you know for granted and attempt to arrive at it from first principles. Each time you do this, something in your mind will rewire itself, and your ability to do it again will improove until eventually you get to the point where nothing stands in your way. This is learning how to learn, and is the only important and most valuable education you will ever need.

Here are some examples to start you off, but remember that you don't necessarily have to succeed, you just have to understand how the knowledge was derived.

* Proove pythagorases theorem, with a picture.
* Create the basic components of a computer, with leggo.
* Perform long division in base 2, 8, 10, and 16.
* Proove that the earth is round, using two sticks.

Richard P Feynman is famous for having always taught himself from first principles which is perhaps some of the reason why he became such a magician.

"There are two kinds of geniuses: the 'ordinary' and the 'magicians'. An ordinary genius is a fellow whom you and I would be just as good as, if we were only many times better. There is no mystery as to how his mind works. Once we understand what they've done, we feel certain that we, too, could have done it. It is different with the magicians. Even after we understand what they have done it is completely dark. Richard Feynman is a magician of the highest calibre." - Mark Ka

Method

2005-01-29T18:23:00.000-08:00

The moral of the story

Devisive

2005-01-22T11:05:00.000-08:00

Duffs device
The original usenet posting
Google 20 year usenet timeline

I first saw this a few weeks back on googles 20 year usenet timeline. Sometimes optimisation can be so cool.


send(to, from, count)

register short *to, *from;

register count;

{

	register n=(count+7)/8;

	switch(count%8){

	case 0:	do{	*to = *from++;

	case 7:		*to = *from++;

	case 6:		*to = *from++;

	case 5:		*to = *from++;

	case 4:		*to = *from++;

	case 3:		*to = *from++;

	case 2:		*to = *from++;

	case 1:		*to = *from++;

		}while(--n>0);

	}

}

Languages

2005-01-22T10:41:00.000-08:00

Things we tried 4 years ago
Enterprise support for dynamic languages
Language oriented programming
Intentional software

If only parsers and compilers were written in a modular fashion. Then we could add anything we like at the abstract syntax tree level and have it compiled and targeted to our favorite binary format regardless of platform and language.

The distinction between logic and code is clear, why are compilers so far behind. This is the whole concept behind the push for intentional programming and domain specific languages. I want to write a search engine, why can't i have my own language for that which compiles into nice fast x86 instructions using GCC, surely its just a transformation ?

But instead i have to spend a lot of time writing good API's so that i can capture the knowledge which would be much better described in a domain specifc language... the domain specific language is what you scrawl on the whiteboard, its what you can describe to a fellow programmer and have them instantly understand what you want to do. And yet its so hard to put that down in syntax, thats because we have to do translation all the time. Surely its better to speak and think in the native language and only do translation when we want the machine to run it...

Theres such a huge gap between expressing an idea and implementing it. But if we break the problem down so that we produce a grammar for description and then a translator for implementation it becomes much easier. We no longer have to worry about bending our minds to describe and implement something at the same time.

I don't think everyone will ever write code as XML, but it makes sense to store the logic in an independent form. Programming should be more like mathematics with metadata. Less focus on the specifics, more focus on the algorithm and the description of intent.

Using a domain specific language is a natural thing for most programmers to do, after all we deal with abstraction every day. The great thing about abstraction is that it separates the problem from the solution and the implementation. We use interfaces to separate purpose from implementation, but we simply don't have the tools to separate language from logic...

What is required is good grammar processing and language description tools which can be combined with extensible editors and compilers. I can't help but think that if programming were more of a science we would have learnt long ago to separate the modelling from the construction.

Update: I noticed Jon Udell has some discussion on this topic, with a link to the same ACM Queue article that we've all read.

Deep structure redux
The deep structure of code

Inheritance

2004-11-01T11:52:00.000-08:00

Delegate Now

Ouch. Sometimes it scares me how easily programmers can confuse common knowledge. This is one of those times.

The pattern goes like this. Someone takes a readily understood and accepted concept, removes it from its original context, confuses it thoroughly, gives different meaning to it, and then proceeded to extoll the virtues of the new found wisdom as though it were something other than misplaced enthusiasm.

Every language deals with inheritance in a different way. To examine the two mentioned above; Java uses single inheritance, public/private/protected access, abstract classes and interfaces as language constructs, but lacks a mechanism for composition via inheritance. C++ provides multiple inheritance, public/private/protected access, abstract classes and interfaces (via pure virtual methods), but also provides for composition via inheritance and even virtual inheritance. C++ can also alter the access of a class at composition via inheritance using public/private/protected.

In some cases these features are similar and in others they are vastly different. The way C++ uses inheritance is not the same as the way Java uses inheritance. In C++ it actually makes a lot more sense to do composition via inheritance, so inheriting implementation and behaviour is far more common.

In fact, that is the essential point. The issue at stake is not wether inheritance is good or bad, but wether you want to create a heirarchy of classes which share a common behaviour, or simply a common interface.

The reason why most API's implement a Stack as a subclass of List is becuase it makes perfect sense to share the behaviour. To misunderstand this is to misunderstand object oriented programming.

Clarifying what you want and understanding the concepts of type, composition, behaviour, interitance, polymorphism, and deligation are key to object oriented programming. These constructs have not been arrived at without reason or purpose.

Stating that implementation inheritance is bad and should be avioded altogether simly shows that you have not understood the issues at hand. There is no one size fits all solution.

Alignment

2004-09-26T14:01:00.000-07:00

In the ancient world as in the modern one, some events are seen as important, and as such a special significant is associated with them. Both science and psydo-science alike have established the importance of correct alignment.

Myan Calendar
Stonehenge
Nazca Lines
Egyptian Pyramids
Egyptian Astrology

Computer science is no exception. In modern processors memory alignment is important for performance reasons and for correctness. The exact implications of alignment vary with processor architecture, but in general accessing data in memory which is aligned to a N byte boundary where N is the machine word size is faster than accessing that which is not aligned. In older processors which were created when memory was limited alignment was not enforced becuase the performance gain was not as important as saving space. In 64 bit processors alignment is given priority over space saving to maximuse performance.

Becuase alignment is architecture dependent many implementations of system routines such as those found in the standard C runtime library are implemented with deliberately varying behaviour. On Intel x86 processors alignment is not enforced, nor is it critical in all cases. Despite this fact the standard C routines still check for alignment so as to avoid issues with page boundaries and portability.

It is often claimed that accessing unaligned memory even on an x86 architecture incurs a massive performance hit. Recent investigations that i have performed have led me to believe that this is a gross generalisation. In fact i have found that in most cases reading 4 bytes of unaligned data in a single operation is still faster than reading 4 bytes individually.

This contradicts many of the claims made about alignment performance, but can be explained on x86 architectures becuase the processor actually does the alignment correction in hardware. Therefore accessing 2 blocks of memory as happens during an unaligned 4 byte access is still faster than accesing 4 bytes individually.

The following code will perfom up to 200% faster than strcmp() in the general case due to the fact that strcmp() performes a single byte comparison whenever either parameter falls on an unaligned address.


int Compare(char * left, char * right)

{

	if (left == right) return 0;



	while (*(long*)left == *(long*)right)

	{

		long mask = *(long*)left;

		if ( 	(mask&0xFF000000)==0 || 

			(mask&0x00FF0000)==0 || 

			(mask&0x0000FF00)==0 || 

			(mask&0x000000FF)==0 ) return 0;

		

		left+=4;

		right+=4;

	}



	while(*left == *right)

	{

		if (*left==0)return 0;



		++left;

		++right;

	}



	return *left-*right;

}

It is also highly optimised in the way it checks for null characters in either string. Unfortunately i can't confirm if this code is safe in all circumstances though it does compile and run succesfully on both windows and linux. There is potential danger particularly when either string falls on a page boundary in memory, an occurance which is statistically unlikely but non-the less possible.

A similar algoirthm can however be employed as a replacement for memcmp() where the length is known without the uncertainty. Such code performs much faster than memcmp() in the general case. Following from this principle there is also an algorithm for rapid conversion from characters to numbers, i.e. atoi(), which can consume 4 bytes at a time. This is somewhat more complicated but again involved masking in order to caplitalise on the values stored in the cpu registers and cache.

Where does this leave us ?

Given that even with these optimisations aligned access still results in better performance by a factor of 2 it makes sense to ensure that as much memory is aligned as possible, particularly if you are using the standard C routines.

Considder the implications of the following code.


inline void * operator new (size_t size)

{

	char * address = (char *) malloc(size+4);

	return (void *) (address + (((unsigned long)address)&0x00000003));

}

Promotion

2004-09-13T15:08:00.000-07:00

Some recent ramblings from elsewhere on the net.

binkley.blogspot.com
discuss.fogcreek.com
blog.metawrap.com

Beginnings

2004-09-13T14:40:00.000-07:00

All i wanted to do was post a comment, now look what ive gone and done.