std::vector of Aligned Elements

Update: answers to some questions raised below are available in a newer post.

Fact (1):

Functions cannot accept aligned types by value. That is really a fact of nature, but it can make sense:  the function’s stack frame can be located anywhere in memory, and so a hypothetical aligned argument passed by value cannot be passed at a fixed offset relative to the frame base. There would be no sane way for the function to reference that argument – unless some compiler writer out there is willing to pad every stack frame with some slack, generate function prologues that would take ebp modulo the desired alignment, fiddle with it to deduce the aligned argument location by some convention etc etc etc. Let’s not even start to imagine stack frame cleanup.

Fact (2):

Ever since MMX, and more pronouncedly  since SSE, data alignment is a major, major performance boost opportunity for mathematical code. In games and game-like apps, practically every mathematical object (matrices, vectors, and thus every object that holds them as members) are aligned on 16 byte boundaries.

Fact (3):

In VC++, when you try and instantiate an STL vector of aligned types you get slapped by the compiler:

error C2719: '_Val': formal parameter with __declspec(align('16')) won't be aligned

The reason is that the  implementation of std::vector::resize has the signature -

void resize(size_type _Count, _Elem _Ch);

That is, it accepts an element of the contained type by value. Semantically – resize pads the existing buffer with copies of _Ch  as needed to get to size _Count.

Corollary:

MS’s std::vector is pretty close to useless.

I wasn’t as decisive until recently, when several things happened: (1) I discovered gcc’s implementation does not suffer from the same issue, so it’s nothing inherent in the c++ standard. (2) I manually modified vector::resize’s signature to accept a const reference, and the code compiled cleanly and ran well. (3) Most importantly, I mailed Stephan T. Lavavej, Microsoft’s own STL grand master, and asked him whether I was missing something.    His response was:

I filed internal bug number Dev10#891686 about this.  There’s a reason that our resize() is currently taking T by value – it guards against being given one of the vector’s own elements (which is perfectly legal).  We’ll investigate changing this in VC11, but we’d have to make nontrivial changes to resize() and possibly other places throughout <vector>.

Note that header hacking is unsupported.

Frankly, I don’t fully understand this. The only case I can see when you might need to guard against being given one of the vector’s own elements is when that element is potentially changed by resize’s padding itself. It might happen when your vector buffer holds some slack, you pass _Ch from that slack, and resize into that very slack space, e.g.:

std::vector<CWhateva> v;
v.resize(100);
v.resize(50); // v's storage capacity is still 100
v.resize(100, v[80]); // when _SECURE_SCL is off, there would be no runtime checks and this may run.

Indeed if v[80] is accepted by ref, even const, it would be overwritten in the last line. I don’t see an inherent problem here, as it seems it should be overwritten by a copy of itself – but I can understand the feeling that overwriting an object with itself might be sensitive. (anyone has a concrete example?).

Then again, maybe he meant something different altogether.

Most of all, I gotta say I was mightily impressed with the speed and seriousness of MS’s replies.  I’m developing quite an email-CHUTZPA lately (more in coming posts), and am always flattered to get responses from busy people.  MS does deserve some kudos there – before realizing Stephen was the right address for this inquiry I mailed the almighty Herb Sutter himself, and got similarly swift and informative responses.

About these ads
This entry was posted in VC++.

10 comments on “std::vector of Aligned Elements

  1. Joe says:

    I imagine they are guarding themselves from the case where the vector’s internal memory/array is re-allocated in response to the ‘resize()’. If the internal array-data is relocated in memory, then the const-ref could point into “dead” memory by the time it’s used. It’s obviously possible to work around that, but it would require the implementation to be careful about such things. It sounds as though they are using the pass-by-value to specifically avoid that complication/issue, in terms of the implementation.

    • Ofek Shilon says:

      Right – I didn’t think of that. Thanks!

    • rmn says:

      In that case however, it is not an issue if all elements are first moved, then the rest are created, and only then do the previous elements get destructed. I’ve used this program to test what happens on visual studio 2008:

      #include <iostream>
      #include <vector>
      
      struct x {
      	x () { std::cout << "()"; }
      	x (const x &) { std::cout << "(x)"; }
      	~x () { std::cout << "~"; }
      	x &operator= (const x &) { std::cout << "="; return *this; }
      };
      
      int main () {
      	std::vector<x> v(1);
      
      	v.resize(10);
      
      	std::cout << std::endl;
      }

      And judging from the printouts, it works as described above.

      So I am not that sure about the problem either. I was thinking about resizing the vector to a smaller size giving a destructed element as the parameter, but it wouldn’t interrupt anything as there are no new elements to build when the size decreases..

      Thanks for the interesting read!

      • Ofek Shilon says:

        You don’t have to indirectly infer what the CRT does – you have the source. Looking into it (in VS2005) you see

        void resize(size_type _Newsize, _Ty _Val)
        {	
        	if (size() < _Newsize)
        		_Insert_n(end(), _Newsize - size(), _Val);
        ...
        }
        

        and in _Insert_n:

        void _Insert_n(iterator _Where, size_type _Count, const _Ty& _Val)
        {	// insert _Count * _Val at _Where
        ...
        		_Ty _Tmp = _Val;	// in case _Val is in sequence
        ...
        

        so, (1) _Val is passed internally by const reference,
        (2) *a copy is stored locally on the stack*, explicitly marked for the case where “_Val is in sequence” – which I interpret as the case Joe mentioned.
        So all in all, it seems this case *is* well handled in the code (regardless of where the destruction happens), and I’m still at a loss as to the original intention of passing _Val by value..

  2. […] interpretations were suggested by commenters, but the mystery pretty much remained. In the last few days, a StackOverflow post –which I […]

  3. […] With __declspec(align(#)), you can even specify the alignment of the data structure itself. This is very useful for putting shared objects in containers like std::vector. See Okef’s std::vector of Aligned Elements for why this is a bad idea. […]

  4. Anonymous says:

    can you explain how did you modify the resize function?

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s