Search This Blog

Thursday, October 13, 2005

Very Clever

So, I was writing a little helper class to use in later projects. It's a chain link class to be used in the construction of circular linked lists. So, I wanted to see what the optimized assembly VC++ would generate would look like. The class and the test function are shown below:

class CChainLink
{
protected:
 CChainLink *m_pNext;
 CChainLink *m_pPrev;

 // Swap pointers to links
 inline static void SwapLinks(CChainLink **ppFirst, CChainLink **ppSecond)
 {
   assert(ppFirst);
   assert(*ppFirst);
   assert(ppSecond);
   assert(*ppSecond);

   CChainLink *pTemp = *ppFirst;
   *ppFirst = *ppSecond;
   *ppSecond = pTemp;
 }

public:
 inline CChainLink()
 {
   m_pNext = m_pPrev = this;
 }

 inline ~CChainLink()
 {
   SpliceOut();
 }

 // Removes self from the chain
 inline void SpliceOut()
 {
   CChainLink &prev = *m_pPrev, &next = *m_pNext;

   SwapLinks(&prev.m_pNext, &m_pNext);
   SwapLinks(&next.m_pPrev, &m_pPrev);
 }

 // Inserts the chain beginning with link between the current link and the next link
 inline void SpliceNext(CChainLink &link)
 {
   assert(&link != this);

   CChainLink &linkPrev = *link.m_pPrev, &next = *m_pNext;

   SwapLinks(&linkPrev.m_pNext, &m_pNext);
   SwapLinks(&next.m_pPrev, &link.m_pPrev);
 }

 // Inserts the chain beginning with link between the previous link and the current link
 inline void SplicePrev(CChainLink &link)
 {
   m_pPrev->SpliceNext(link);
 }

 // Replaces self with the chain beginning with link
 inline void SpliceOver(CChainLink &link)
 {
   assert(&link != this);

   SpliceNext(link);
   SpliceOut();
 }
};

int main(int argc, char* argv[])
{
 CChainLink A, B, C, D, E;
 A.SpliceNext(B);
 B.SpliceNext(C);

 D.SpliceNext(E);

 C.SpliceNext(D);
 // There's actually more test code down here, but I've omitted it since it has nothing to do with the chain class
}


Well, VC++ really pulled a fast one on me. In the end, I didn't learn what I was looking for, but I did see VC++ do some clever optimization. Have a look at the assembly it generated:

CChainLink A, B, C, D, E;
A.SpliceNext(B);
00401868 8D 4C 24 24 lea ecx,[esp+24h]
0040186C 89 4C 24 20 mov dword ptr [esp+20h],ecx
B.SpliceNext(C);
00401870 8D 54 24 14 lea edx,[esp+14h]
00401874 89 54 24 1C mov dword ptr [esp+1Ch],edx
00401878 8D 44 24 1C lea eax,[esp+1Ch]

D.SpliceNext(E);
0040187C 8D 4C 24 04 lea ecx,[esp+4]
00401880 8D 54 24 0C lea edx,[esp+0Ch]
00401884 89 4C 24 0C mov dword ptr [esp+0Ch],ecx

C.SpliceNext(D);
00401888 8B CA mov ecx,edx
0040188A 89 44 24 24 mov dword ptr [esp+24h],eax
0040188E 89 44 24 18 mov dword ptr [esp+18h],eax
00401892 8D 44 24 24 lea eax,[esp+24h]
00401896 89 4C 24 14 mov dword ptr [esp+14h],ecx
0040189A 89 54 24 08 mov dword ptr [esp+8],edx
0040189E 89 44 24 04 mov dword ptr [esp+4],eax

SLIST_HEADER asdfgh;
SLIST_ENTRY lkjhg;

InitializeSListHead(&asdfgh);
004018A2 8D 4C 24 2C lea ecx,[esp+2Ch]
004018A6 8D 54 24 04 lea edx,[esp+4]
004018AA 8D 44 24 14 lea eax,[esp+14h]
004018AE 51 push ecx
004018AF C7 44 24 40 04 00 00 00 mov dword ptr [esp+40h],4
004018B7 89 54 24 2C mov dword ptr [esp+2Ch],edx
004018BB 89 44 24 14 mov dword ptr [esp+14h],eax
004018BF FF 15 38 B0 40 00 call dword ptr [__imp__InitializeSListHead@4 (40B038h)]

No comments: