Physics Simulation Forum

 

All times are UTC




Post new topic Reply to topic  [ 15 posts ] 
Author Message
PostPosted: Fri Jun 15, 2007 6:00 pm 
Offline

Joined: Fri Jun 15, 2007 4:35 pm
Posts: 7
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


Top
 Profile  
 
 Post subject:
PostPosted: Fri Jun 15, 2007 6:41 pm 
Offline

Joined: Fri Mar 31, 2006 7:13 pm
Posts: 95
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


Top
 Profile  
 
 Post subject:
PostPosted: Fri Jun 15, 2007 10:36 pm 
Offline

Joined: Fri Jun 15, 2007 4:35 pm
Posts: 7
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


Top
 Profile  
 
 Post subject:
PostPosted: Fri Jun 15, 2007 11:45 pm 
Offline
Site Admin
User avatar

Joined: Sun Jun 26, 2005 6:43 pm
Posts: 3996
Location: California, USA
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:
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");
   }

};


Top
 Profile  
 
 Post subject:
PostPosted: Sat Jun 16, 2007 9:18 am 
Offline

Joined: Fri Jun 15, 2007 4:35 pm
Posts: 7
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


Top
 Profile  
 
 Post subject:
PostPosted: Sun Jun 17, 2007 8:28 pm 
Offline

Joined: Fri Jun 15, 2007 4:35 pm
Posts: 7
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:
      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:
#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


Top
 Profile  
 
 Post subject:
PostPosted: Mon Jun 18, 2007 4:32 pm 
Offline
Site Admin
User avatar

Joined: Sun Jun 26, 2005 6:43 pm
Posts: 3996
Location: California, USA
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:
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


Top
 Profile  
 
 Post subject:
PostPosted: Fri Jun 22, 2007 8:45 am 
Offline

Joined: Fri Jun 15, 2007 4:35 pm
Posts: 7
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


Top
 Profile  
 
 Post subject:
PostPosted: Fri Jun 22, 2007 4:30 pm 
Offline
Site Admin
User avatar

Joined: Sun Jun 26, 2005 6:43 pm
Posts: 3996
Location: California, USA
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:
void*   btAlignedAlloc  (int size, int alignment)
{
        return _aligned_malloc(size,alignment);
}


Thanks,
Erwin


Top
 Profile  
 
 Post subject:
PostPosted: Fri Jun 22, 2007 5:42 pm 
Offline

Joined: Sun Jul 03, 2005 4:06 pm
Posts: 844
Location: Kirkland, WA
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


Top
 Profile  
 
 Post subject:
PostPosted: Fri Jun 22, 2007 10:03 pm 
Offline
Site Admin
User avatar

Joined: Sun Jun 26, 2005 6:43 pm
Posts: 3996
Location: California, USA
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:
#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


Top
 Profile  
 
 Post subject:
PostPosted: Sat Jun 23, 2007 7:08 am 
Offline

Joined: Sun Jul 03, 2005 4:06 pm
Posts: 844
Location: Kirkland, WA
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


Top
 Profile  
 
 Post subject:
PostPosted: Tue Jun 26, 2007 10:30 pm 
Offline

Joined: Fri Jun 15, 2007 4:35 pm
Posts: 7
Hello Eric,
I have updated the file you mentioned, but the addresses are still unaligned after the first resize call.

Greets
Sören


Top
 Profile  
 
 Post subject:
PostPosted: Wed Jun 27, 2007 1:53 am 
Offline
Site Admin
User avatar

Joined: Sun Jun 26, 2005 6:43 pm
Posts: 3996
Location: California, USA
It is all working fine here. Have you tried to debug the allocator yourself?
Did you already try putting a breakpoint inside
Code:
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


Top
 Profile  
 
 Post subject:
PostPosted: Wed Jun 27, 2007 8:53 am 
Offline

Joined: Fri Jun 15, 2007 4:35 pm
Posts: 7
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:
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:
 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:
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


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 15 posts ] 

All times are UTC


Who is online

Users browsing this forum: No registered users and 4 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB® Forum Software © phpBB Group