51

I was wondering with my colleague today whether std::vector can be implemented to make use of small buffer optimization. By looking into the C++11 draft, I read at 23.3.1p8

The expression a.swap(b), for containers a and b of a standard container type other than array, shall exchange the values of a and b without invoking any move, copy, or swap operations on the individual container elements.

That at first seems to outlaw small buffer optimization, but under the as-if rule, we would be allowed to still do small buffer optimization for non-class types (since we cannot observe the copy being done). The next text appears to be harder to "fool"

Every iterator referring to an element in one container before the swap shall refer to the same element in the other container after the swap.

Is this sufficient to prevent implementing the small buffer optimization for std::vector? Are there any other road-blocks or is it eventually possible to have a std::vector with SBO?

Johannes Schaub - litb
  • 496,577
  • 130
  • 894
  • 1,212
  • Does `string` have the same `swap` clause? – Kerrek SB Nov 19 '11 at 00:48
  • The llvm [libc++](http://libcxx.llvm.org) project page mentions using the SBO, which indicates that either (1) the rules litb has cited don't apply to strings, or (2) there's some way to use SBO with strings despite these rules, or (3) the libc++ authors will be disappointed when they read this part of the standard. – Stuart Berg Nov 19 '11 at 01:31
  • The llvm libc++ project page is referring to string, not vector. I believe the swap/iterator comment Johannes points out does indeed prohibit SBO for vector. – Howard Hinnant Nov 19 '11 at 01:58
  • But see http://home.roadrunner.com/~hinnant/stack_alloc.html – Howard Hinnant Nov 19 '11 at 01:59
  • 3
    21.4.1/p6 specifically allows string::swap to invalidate iterators. – Howard Hinnant Nov 19 '11 at 02:03
  • 1
    Related: http://stackoverflow.com/q/2178281/103167 – Ben Voigt Dec 28 '12 at 22:39

2 Answers2

49

23.2.1 / p10 / b6:

Unless otherwise specified ...

  • no swap() function invalidates any references, pointers, or iterators referring to the elements of the containers being swapped. ...

Nowhere does it "specify otherwise" for vector. So this outlaws the SBO for vector.

string is not bound by this rule because it does "specify otherwise" in 21.4.1/p6:

References, pointers, and iterators referring to the elements of a basic_string sequence may be invalidated by the following uses of that basic_string object:

  • as an argument to any standard library function taking a reference to non-const basic_string as an argument.^234

234) For example, as an argument to non-member functions swap() (21.4.8.8), operator>>() (21.4.8.9), and getline() (21.4.8.9), or as an argument to basic_string::swap()

Howard Hinnant
  • 206,506
  • 52
  • 449
  • 577
  • Off topic, but I was looking at this text recently trying to find a similar guarantee for `move`. It seems obvious, but is `move` required to transfer valid iterators to the destination container? – Potatoswatter Nov 19 '11 at 02:50
  • No, I don't believe it is (but my memory is fallible). If you've got iterators or references into a temporary, you're probably being a little too tricky. :-) However I'd love to see motivating code that suggests otherwise. – Howard Hinnant Nov 19 '11 at 03:12
  • 3
    But `move` isn't just for temporaries, it's also useful for persistent structures that you just don't want to copy. The motivating code is just building a structure in a local variable and then moving it into a more permanent container. (Of course, it's not always moved, or I'd just build it there to begin with.) – Potatoswatter Nov 19 '11 at 04:54
-1

In addition to the problem with iterator invalidation, there's a security argument for avoiding the small buffer optimization.

If writes overrun a std::vector, you get heap corruption, which is quite difficult to predict what gets overwritten and very difficult to leverage for arbitrary code execution.

If the buffer is instead embedded in a local variable, an overrun trashes the stack and the attacker will probably gain control over the return address, which is far more useful (return-to-libc attacks, for example).

Ben Voigt
  • 277,958
  • 43
  • 419
  • 720
  • 1
    Questionably relevant: while it might be easier for the attacker to make use of an overrun on the stack, from the developer's perspective both of these scenarios should be seen as totally undesirable anyway. Heap corruption isn't really "better" it's just differently-unacceptable. – Alex Celeste May 27 '16 at 14:57
  • 1
    @Leushenko: And ASLR doesn't fix any bugs, but it's still considered very desirable as security defense-in-depth. Ditto non-executable stack. – Ben Voigt May 27 '16 at 15:01