Evgeny Pokhilko's Weblog

Programmer's den

GDB: How do I set current source file for list and break commands

People who start using GDB after GUI debuggers often ask this question in the title. It is not obvious from the documentation and it is not googled easily either. So the trick I use is to specify a function that I want to debug like this.

list GetName

I can type Get and press tab. GDB suggests names. The command above will set the source file with GetName as its current source file.

If I don’t know the function name, I can specify the file name and line number directly.

list document.cpp:1

This is what most people look for. Then list command will output document.cpp and break 10 will set a breakpoint in document.cpp.

May 17, 2015 Posted by | C++ | Leave a comment

Memory Alignment Of Structures and Classes in C++

Everything below was tested in Visual Studio 2012 Win32. The code for this post is here

Introduction

The memory to store a particular structure or object is split into blocks of determined size. This size is called alignment.

The C++ standard requires that members are stored in memory in the order of declaration. Multiple consecutive members can be “packed” in one block. If the next member doesn’t fit into the remained bytes of the block, it’s saved into the following block. Those unused bytes in the previous block are called “padding”.

Normally the alignment is determined by the compiler for each structure type. In a simple scenario where the structure doesn’t contain other structures, the alignment is the size of the largest type stored in the structure. However, in some environments a simple type can have alignment requirement that is smaller than the size of the type. For example double can have alignment of 4. So it would be better to say that alignment of a structure is the maximum alignment of its contained types. Alignment is only allowed to be power of two by the standard.

Examples:

1.

struct Alignment4
{
	char a;
	char b; 
	//char[2] - padding
	int i; // max alignment 4
Alignment4():a(1),b(2),i(3){} 
}; // size is 8

Alignment requirement for int is 4 and char 1. The maximum is 4 so 4 will be the alignment of Alignment4 structure. sizeof(Alignment4)==8

Memory:  01 02 cd cd 03 00 00 00

cd is the special value used for padding in this case (compiled in debug configuration).  (Note that 03 is the first byte of the integer indicating that we see little endian – http://en.wikipedia.org/wiki/Endianness).

2.

struct Alignment8
{
	int i; 
	//char[4]
	double d; // max alignment 8
	short s;
	//char[6]
	Alignment8():i(1), d(2), s(3){}
}; // size is 24

Alignments of the types are the following: int 4, double 8, short 2. The maximum is 8 so the alignment of the structure is 8.

Memory: 01 00 00 00 cd cd cd cd 00 00 00 00 00 00 00 40 03 00 cd cd cd cd cd cd

Note: 00 00 00 00 00 00 00 04 is how the double value of 2 is represented in memory.

The compiler outputs information about padding as below when /Wall (WarningLevel – EnableAllWarnings in C/C++ => General) switch is used:

1>size_test.cpp(16): warning C4820: ‘Alignment4’ : ‘2’ bytes padding added after data member ‘Alignment4::b’

1>size_test.cpp(24): warning C4820: ‘Alignment8’ : ‘4’ bytes padding added after data member ‘Alignment8::i’

1>size_test.cpp(28): warning C4820: ‘Alignment8’ : ‘6’ bytes padding added after data member ‘Alignment8::s’

1>size_test.cpp(35): warning C4820: ‘BetterAlignment8’ : ‘2’ bytes padding added after data member ‘BetterAlignment8::s’

1>size_test.cpp(43): warning C4820: ‘Size8’ : ‘6’ bytes padding added after data member ‘Size8::b’

1>size_test.cpp(46): warning C4820: ‘Size8’ : ‘7’ bytes padding added after data member ‘Size8::c’

1>size_test.cpp(68): warning C4820: ‘Size6’ : ‘3’ bytes padding added after data member ‘Size6::a’

Optimization

We only need 14 bytes to store Alignment8 but it takes 24. The order of the members is the problem. The block is 8 bytes and when we pack d, it has to start from the next block as there is only 4 bytes left in the current block, which is not enough for d. i and s can fit into one block but they are separated by d. BetterAlignment8 (see below) takes only 16 bytes.

struct BetterAlignment8
{
	int i;
	short s;
	//char[2]
	double d; // max alignment 8
	BetterAlignment8():i(1), d(2), s(3){}
}; // size is 16

Memory:  01 00 00 00 03 00 cd cd 00 00 00 00 00 00 00 40

This will reduce the memory consumption and possibly improve the performance as more elements will fit into the CPU cache.

Alignment control

There are several ways you can tell the compiler to change the default alignment:

  1. Across the project /ZpN where N can be 1, 2, 4, 8, 16.
    StructMemberAlignment
  1. Specify alignment within code range of a module.

In this example the alignment of Size7 and Size5 will be 1.

#pragma pack(push, 1)
struct Size7
{
	char a;
	char b;
	double i;
	char c;
	S7():a(1), b(2), c(3), i(0){}
};

struct Size5
{
	char a;
	int i;
};
#pragma pack(pop)

  1. Specify alignment per structure type.
struct __declspec(align(8)) Size6
{
	char a;
	int i;
	Size6():a(1), i(2){}
};

You can even control alignment per member http://msdn.microsoft.com/en-us/library/83ythb65.aspx.

Compiler oddities and limitations

In Visual Studio 2012 if you specify alignment that the compiler doesn’t accept in a particular case, it will be ignored without a warning.  Everything below also has effect in Visual Studio 2012.

  1. Alignment that is not power of two is ignored
#pragma pack(push, 3)

#pragma pack(pop)
  1. Pragma pack instruction is ignored if the alignment is greater than the default alignment for the structure:
#pragma pack(push, 8)
// default alignment is 4. If default_alignment > pragma_alignment, pragma is ignored.
struct Alignment4
{
	char a;
	int i;
	Alignment4():a(1), i(2){}
}; // alignment is still 4
#pragma pack(pop)
  1. __declspec instruction is opposite to #pragma. It is ignored if the alignment is less than the default alignment.
// if declspec_alignment <= default_alignment then the instruction is ignored
struct __declspec(align(2)) Size8a
{
char a;
	int i;
	Size8a():a(1), i(2){}
}; // alignment is still 4

Asserting alignment

If you have specific requirements for the alignment in your piece of code and you don’t know how it will be compiled in the future, it’s always better to assert it in the code. C++11 or TR1 are required.

#include <type_traits>
Struct MyStructure
{
	Char c;
	Int I;
};
Static_assert(std::alignment_of(MyStructure)::value == 4, “Alignment of MyStructure must be 4”);

If the alignment is not 4, there will be a compilation error.

Alignment conflicts

This is the reason why programmers start to learn about alignment most often. If you declare the same structure in two different modules with different alignment parameters, you will get a conflict. See the example below:

module01.cpp

struct Size5
{
	char a;
	int i;
};
Size5 global_size_5;

module02.cpp

#pragma pack(push, 1)
struct Size5
{
	char a;
	int i;
};
#pragma pack(pop)
extern Size5 global_size_5;

You will get this warning:

LINK : warning C4742: ‘struct Size5 global_size_5’ has different alignment in ‘D:\dhome\size_test\size_test.cpp’ and ‘D:\dhome\size_test\notepad.cpp’: 1 and 4

More about C4742 – http://msdn.microsoft.com/en-us/library/k334t9xx(v=vs.110).aspx

However, it doesn’t always happen. If you return a variable from another module by reference or pointer, there will be no warnings.

Conclusion

If the system you are working on demands high performance or low memory consumption, you may want to change the default alignment. It should be measured and tested of course. Sometimes you have to deal with alignment even when you don’t expect. For example the Microsoft code generator for COM proxies inserts alignment control directives. It can cause issues that you need to be prepared to understand. So alignment is worth keeping an eye on.

January 25, 2014 Posted by | C++ | Leave a comment

Google Test Framework and Visual Studio 2010

Here is a few issues people get when they start using Google Test Framework with Visual Studio:

1. When an empty project is created with the default configuration in Visual Studio and you link it with gtest.lib, you get a lot of link errors like the following:

1>msvcprtd.lib(MSVCP100D.dll) : error LNK2005: “public: virtual __thiscall std::basic_iostream<char,struct std::char_traits<char> >::~basic_iostream<char,struct std::char_traits<char> >(void)” (??1?$basic_iostream@DU?$char_traits@D@std@@@std@@UAE@XZ) already defined in gtest.lib(gtest-all.obj)
1>msvcprtd.lib(MSVCP100D.dll) : error LNK2005: “public: virtual __thiscall std::basic_ios<char,struct std::char_traits<char> >::~basic_ios<char,struct std::char_traits<char> >(void)” (??1?$basic_ios@DU?$char_traits@D@std@@@std@@UAE@XZ) already defined in gtest.lib(gtest-all.obj)
1>msvcprtd.lib(MSVCP100D.dll) : error LNK2005: “public: __thiscall std::basic_iostream<char,struct std::char_traits<char> >::basic_iostream<char,struct std::char_traits<char> >(class std::basic_streambuf<char,struct std::char_traits<char> > *)” (??0?$basic_iostream@DU?$char_traits@D@std@@@std@@QAE@PAV?$basic_streambuf@DU?$char_traits@D@std@@@1@@Z) already defined in gtest.lib(gtest-all.obj)

This happens because the default compiler switch of gtest is /MTd and your empty project has /MDd. You need to make them consistent. One option is to change your test project and the tested project to /MTd.

2. You get the following errors when you mix your Release with gtest Debug and vice verse:

gtest.lib(gtest-all.obj) : error LNK2038: mismatch detected for ‘_ITERATOR_DEBUG_LEVEL’: value ‘0’ doesn’t match value ‘2’ in convex_hull_tests.obj
2>LIBCMT.lib(invarg.obj) : error LNK2005: __initp_misc_invarg already defined in LIBCMTD.lib(invarg.obj)
2>LIBCMT.lib(invarg.obj) : error LNK2005: __call_reportfault already defined in LIBCMTD.lib(invarg.obj)
2>LIBCMT.lib(invarg.obj) : error LNK2005: __set_invalid_parameter_handler already defined in LIBCMTD.lib(invarg.obj)
2>LIBCMT.lib(invarg.obj) : error LNK2005: __get_invalid_parameter_handler already defined in LIBCMTD.lib(invarg.obj)
2>LIBCMT.lib(invarg.obj) : error LNK2005: __invoke_watson already defined in LIBCMTD.lib(invarg.obj)

May 20, 2013 Posted by | C++ | | Leave a comment

Convex Hull

I read about the problem of finding Convex Hull in Algorithm Design Manual and knew that the complexity should be N for points sorted by one coordinate. Before reading about existing solutions I determined to find my own. “Invent the wheel” in other words. I spent hours thinking about a solution. In the end I found one:

I have a collection containing convex hull points. It is an stl::list. It’s empty at the beginning. I loop through points sorted by x. So I move from left to right of the picture. At the end of processing each point I maintain the algorithm invariant in which the list contains the convex hull of the points processed so far.  If you imagine this visually, it’s like putting a deflated balloon on an object from left to right.

When I process a point, I calculate if it’s on the top edge of the hull and then I do the same for the bottom edge. I also loop through the points that are already in my existing convex hull collection to see if they are not on the edge yet given the current processed point. If it’s not I remove it from the hull collection.

An important part of the algorithm is the function ConvexHull::compare_vectors. It takes three points and calculates if the point in the middle is on the edge of the convex hull. It represents the three points p1, p2 and p3 as two vectors p1 – p2 and p2 – p3. Then it prolongs p1 – p2 vector until it intersects with x = p3.x line. If y of the intersection point is higher than p3.y, the point is on the top edge of the convex hull (picture 1).

compare_vectors

Picture 1

The algorithm is in a console application that takes an image file (Picture 2), draws the convex hull and saves it to another image file (Picture 3). It supports multiple image file formats thanks to the stbi_image library.

ovals

Picture 2

ovals(hull)

 

After experimenting with my rasterizing algorithm I used Anti-Grain Geometry by Maxim Shemanarev. See the result on Picture 4.

 

 

Picture 3

1942_Nash_Ambassador_X-ray(result)

Picture 4

You can find the sources on GitHub: https://github.com/evpo/ConvexHull

Binaries for windows are also available:

http://sourceforge.net/projects/convexhull/files/ (100% CLEAN award granted by Softpedia)

Download the zip file and run the cmd file to see it in action.

 

May 4, 2013 Posted by | Algorithms, C++ | Leave a comment