[Bug Report] Issue in btAlignedObjectArray

Post Reply
StrikeCommandr
Posts: 7
Joined: Fri Jun 15, 2007 4:35 pm

[Bug Report] Issue in btAlignedObjectArray

Post by StrikeCommandr »

Hello together!
Im using parts of your library for my diploma thesis and found an issue in your class btAlignedObjectArray. I'm using this array to store objects which need alignment. In normal cases this works nice, but if there are objects stored in your array which have members that needed to be created with "new" in the constructor and deleted with "delete" in the destructor, the issue occurs.

Explanation:
If more objects are put into the vector than space is available, the capacity of the vector is doubled. This is done by calling the function reserve(). In this function various steps are taken: after the need for more space is affirmed, the old space is not expanded, but new space is allocated and the pointer to this is stored in the variable "s". Then all objects are copied from the old space to the new space. Following the function destroy() is called which will call the destructor for every object stored. This is the point where to situation, which was described at the top, directs to an error.

A object is first copied as it is, without a copy constructor, to its new place then there are two identical objects. If this objects contain pointer to member variables (e.g. A) which were created with "new", the pointers of both objects point to the same A. When now a destructor from one of these objects is called, the destructor normally deletes A to avoid garbage. But the second object resists without knowing of the deletion.

This can be verified by outcommenting the destroy() call. If done so the vector works as assumed. But this would no solution, so i evaluated to solutions so far: the copy function could use the copy constructors, which would lead to an unknowing overhead. Second the old vector could be deleted directly without calling the destructor.

Would be nice if you can tell me how you will resolve this issue.

Greets
Sören
DevO
Posts: 95
Joined: Fri Mar 31, 2006 7:13 pm

Post by DevO »

Hello,

not sure if this is suitable for you but may be it is better us store just pointers in the btAlignedObjectArray?

If the object is created with new then it can be big and scold be not copied at all, after the work it must always be destroyed with delete of course.

But yes of course copy constructor could be used too.

regards,
DevO
StrikeCommandr
Posts: 7
Joined: Fri Jun 15, 2007 4:35 pm

Post by StrikeCommandr »

Hi,
thanks for your advice, but I intended a vector which offers me alignment so I can keep objects together and take advantage of the cache coharence. If I would only store pointer in the vector this benefit would be lost.

Besides I could use the STL vector or the boost library for storing pointers, which offers more functions like an iterator.

Greets
Sören
User avatar
Erwin Coumans
Site Admin
Posts: 4221
Joined: Sun Jun 26, 2005 6:43 pm
Location: California, USA
Contact:

Post by Erwin Coumans »

I've just modified the btAlignedObjectArray class, to create objects using the in-place new operator, that calls the copy constructor properly (instead of the operator=).
Please test the code, and use the copy constructor with either duplicating all data (DummyClass) or using reference counting to avoid duplications of this data created in the constructor.
Also, the array sorting was using operator= during the swap, which is not replaced by a memcpy.
This new functionality can be disabled by commenting out 'USE_NEW_INPLACE_NEW'.

By the way, the STL implementation of Visual Studio 2005 has issues with alignment, that's one of the reasons for Bullet to introduced its own vector replacement. A Boost dependency is a bit overkill, just for a resizable array.

You can download the updated btAlignedObjectArray sources here. More changes in other areas will go into Bullet 2.53.

Hope this helps,
Erwin

Code: Select all

struct	DummyClass
{
	int bla;
};

ATTRIBUTE_ALIGNED16(class) TestClass
{
	DummyClass* m_data;
public:
	TestClass(const TestClass& other)
	{
		numCopyConstructors++;
		//m_data = other.m_data;
		m_data = new DummyClass(*other.m_data);

	}

	TestClass(int bla,int bla2)
	{
		numConstructions++;
		printf("const\n");
		m_data=new DummyClass;
	}

	TestClass& operator=(const TestClass& other)
	{
		numAssignments++;
		m_data = new DummyClass(*other.m_data);
	}
	virtual ~TestClass()
	{
		delete m_data;
		numDestructions++;
		printf("dest\n");
	}

};
StrikeCommandr
Posts: 7
Joined: Fri Jun 15, 2007 4:35 pm

Post by StrikeCommandr »

Hi Erwin,
thanks for your fast response. I've tested the code with my testcase and your TestClass. Both cases worked very well. Seems you have cleaned up the "mess". :D

Thanks again!
Sören
StrikeCommandr
Posts: 7
Joined: Fri Jun 15, 2007 4:35 pm

Post by StrikeCommandr »

Hello again,
I've tried to integrate the new version of the btAlignedObjectArray into my project, but there seems to be an issue again. If I use the new functionality (USE_NEW_INPLACE_NEW) has the placement-new operator to be overloaded? Otherwise I think the alignment for objects placed in the array is not guaranteed. Because of I printed one adress used in this function to the screen:

Code: Select all

		SIMD_FORCE_INLINE	void push_back(const T& _Val)
		{	
			int sz = size();
			if( sz == capacity() )
			{
				reserve( allocSize(size()) );
			}
			
#ifdef USE_NEW_INPLACE_NEW
			std::cout << &m_data[m_size] << std::endl;
			
			new ( &m_data[m_size] ) T(_Val);
#else
			m_data[size()] = _Val;			
#endif //USE_NEW_INPLACE_NEW

			m_size++;
		}
The adress was 01B47AB8, so it should be something like XXXXXXX0 to assure 16byte alignment. My class looks like this:

Code: Select all

#pragma pack(push,16)


class Material
{
public:
	
	Material();
	...

protected:
	// Need alignment
	Float4		mDiffus;
	Float4		mSelfIllumination;		
	
	// Need no alignment
	float		mSelfIlluminationBrightness; 
	float		mRho;						 
	short		mDrawMode;					
	Texture*	mTexture;	
};
#pragma pack(pop)

There was no new-placement operator in use, but it seems like the adress where the object shall be stored is wrong and so an access violation occurs.

Greets
Sören
User avatar
Erwin Coumans
Site Admin
Posts: 4221
Joined: Sun Jun 26, 2005 6:43 pm
Location: California, USA
Contact:

Post by Erwin Coumans »

The in-place new operator shouldn't be overloaded. The in-place new operator isn't allocating memory, it calls the constructor on existing memory.

Please use ATTRIBUTE_ALINED16 to make sure your class is aligned on the stack, and is padded.

Code: Select all

ATTRIBUTE_ALIGNED16(class)	Material 
{
....
};
If this still doesn't work, please modify an existing sample (BasicDemo.cpp) to reproduce the problem (make sure it compiles/links properly).

Hope this helps,
Erwin
StrikeCommandr
Posts: 7
Joined: Fri Jun 15, 2007 4:35 pm

Post by StrikeCommandr »

Hello Erwin,
I'm sorry to bother you again, but I've tried again and it seems the bug resists. I have tried the corrected array with the Test class you've posted here. I tested as follows:

At first I created an object array and reserved space for 1000 elements. In a while loop I added more than 1000 objects of your test class and printed the adress for ervery pushback, for which the new-inplace operator is called. Well, the first 1000 elements looked good. All adresses ended with a zero. But if the 1001 element is inserted in the array, this is resized, and after this call the alignment for all objects was gone, so every adress printed, ended with an eight. I've put my test case online, so you can run it yourself.

http://www.sowenig.de/upload/public/dip ... tArray.rar

Greets
Sören
User avatar
Erwin Coumans
Site Admin
Posts: 4221
Joined: Sun Jun 26, 2005 6:43 pm
Location: California, USA
Contact:

Post by Erwin Coumans »

Which compiler version are you using exactly? Only Visual Studio 2005 will use aligned malloc, see btScalar.h.

Have you tried to debug the allocator, by putting a breakpoint in

Code: Select all

void*   btAlignedAlloc  (int size, int alignment)
{
        return _aligned_malloc(size,alignment);
}
Thanks,
Erwin
Dirk Gregorius
Posts: 861
Joined: Sun Jul 03, 2005 4:06 pm
Location: Kirkland, WA

Post by Dirk Gregorius »

Erwin,

you could use the Doug Lea allocator by default and let the user overwrite when he wants to. The allocator is available for most platforms...

Cheers,
-Dirk
User avatar
Erwin Coumans
Site Admin
Posts: 4221
Joined: Sun Jun 26, 2005 6:43 pm
Location: California, USA
Contact:

Post by Erwin Coumans »

StrikeCommandr wrote:Hello Erwin,
I'm sorry to bother you again, but I've tried again and it seems the bug resists. I have tried the corrected array with the Test class you've posted here. I tested as follows
I checked your code, and your version of btScalar is out-of-date, and it doesn't define BT_HAS_ALIGNED_ALOCATOR.

Can you use the latest version of Bullet 2.53 and try it again? Some definitions at the top of btScalar.h should look like:

Code: Select all

#ifdef WIN32

		#if defined(__MINGW32__) || defined(__CYGWIN__) || (defined (_MSC_VER) && _MSC_VER < 1300)
			#define SIMD_FORCE_INLINE inline
			#define ATTRIBUTE_ALIGNED16(a) a
		#else
			#define BT_HAS_ALIGNED_ALOCATOR
			#pragma warning(disable:4530)
			#pragma warning(disable:4996)
			#pragma warning(disable:4786)
			#define SIMD_FORCE_INLINE __forceinline
			#define ATTRIBUTE_ALIGNED16(a) __declspec(align(16)) a
		#endif //__MINGW32__

		#include <assert.h>
		#define btAssert assert
		//btFullAssert is optional, slows down a lot
		#define btFullAssert(x)
#else
Dirk Gregorius wrote: you could use the Doug Lea allocator by default and let the user overwrite when he wants to. The allocator is available for most platforms...
Does it support 16-byte aligned allocations, and is the license as liberal as ZLib?

Thanks for the feedback,
Erwin
Dirk Gregorius
Posts: 861
Joined: Sun Jul 03, 2005 4:06 pm
Location: Kirkland, WA

Post by Dirk Gregorius »

Yeap, it is public domain and it supports aligned allocation. I think it is pretty often used in games since its performance is superior to usual malloc (especially windows)...

http://g.oswego.edu/dl/

See malloc.h and malloc.c
StrikeCommandr
Posts: 7
Joined: Fri Jun 15, 2007 4:35 pm

Post by StrikeCommandr »

Hello Eric,
I have updated the file you mentioned, but the addresses are still unaligned after the first resize call.

Greets
Sören
User avatar
Erwin Coumans
Site Admin
Posts: 4221
Joined: Sun Jun 26, 2005 6:43 pm
Location: California, USA
Contact:

Post by Erwin Coumans »

It is all working fine here. Have you tried to debug the allocator yourself?
Did you already try putting a breakpoint inside

Code: Select all

void*   btAlignedAlloc  (int size, int alignment) 
{ 
        return _aligned_malloc(size,alignment); 
} 
Unless you can demonstrate a bug, I don't have the bandwidth to support this case further.
Thanks,
Erwin
StrikeCommandr
Posts: 7
Joined: Fri Jun 15, 2007 4:35 pm

Post by StrikeCommandr »

Hello Erwin,
sorry for typing the wrong name. I've tried again this morning and it seems you are right, the adresses are aligned. Perhaps I've forgot to recompile after exchanging the 2.52 with the 2.53 bt* files. :roll:

At least I only have one question: If the class that shall be put in the btAlignedObjectArray and this class has an overloaded new operator for heap alignment

Code: Select all

void* operator new (std::size_t size)
{
     return _mm_malloc(size, 16);
}

void operator delete (void* ptr)
{
   _mm_free(ptr);
}
the project won't compile by saying:

Code: Select all

 error C2660: 'TestClass::operator new' : function does not take 2 arguments
        
while compiling class template member function 'void btAlignedObjectArray::push_back(const T &)'
        with
        [
            T=TestClass
        ]
reference to class template instantiation 'btAlignedObjectArray' being compiled
        with
        [
            T=TestClass
        ]
The point which is mentioned is in the btAlignedObjectArray, where the inplace new operator is called. It seems as if the compiler tries to use the overloaded normal new operator for this operation (If marked the position with >>>).

Code: Select all

SIMD_FORCE_INLINE	void push_back(const T& _Val)
{	
    int sz = size();
    if( sz == capacity() )
    {
        reserve( allocSize(size()) );
    }
			
#ifdef USE_NEW_INPLACE_NEW
 >>>  new ( &m_data[m_size] ) T(_Val);
#else
     m_data[size()] = _Val;			
#endif //USE_NEW_INPLACE_NEW
     m_size++;
}
Greets and thanks for your help
Sören
Post Reply