<string>: Consider retuning the Small String Optimization

[StephanTLavavej]

Currently, our basic_string implementation can store up to 15 narrow characters, or 7 wide characters, before dynamically allocating memory:

STL/stl/inc/xstring

Lines 2134 to 2135 in 58bb49d

	// length of internal buffer, [1, 16]:
	static constexpr size_type _BUF_SIZE = 16 / sizeof(value_type) < 1 ? 1 : 16 / sizeof(value_type);

STL/stl/inc/xstring

Lines 2185 to 2196 in 58bb49d

	union _Bxty { // storage for small buffer or pointer to larger one
	_Bxty() {} // user-provided, for fancy pointers
	~_Bxty() noexcept {} // user-provided, for fancy pointers
	value_type _Buf[_BUF_SIZE];
	pointer _Ptr;
	char _Alias[_BUF_SIZE]; // TRANSITION, ABI: _Alias is preserved for binary compatibility (especially /clr)
	} _Bx;
	size_type _Mysize; // current length of string
	size_type _Myres; // current storage reserved for string

We should consider retuning this optimization, given platform evolution over the last 20 years.

Billy O'Neal (@BillyONeal) commented: "Note that libc++'s implementation is a full pointer narrower than ours and stores up to 22 characters instead of 15; optimally small."

Related note: std::function's Small Functor Optimization was retuned before VS 2015 froze binary compatibility, using the heuristic that a function object storing a std::string should be considered small (regardless of architecture or debug mode). We don't necessarily have to retune std::function again, but we should at least check that the heuristic is still satisfied.

Also tracked by Microsoft-internal VSO-154236 / AB#154236.

vNext note: Resolving this issue will require breaking binary compatibility. We won't be able to accept pull requests for this issue until the vNext branch is available. See #169 for more information.

[jonwis]

See also microsoft/wil#159 - is there a way to either disable the SSO or otherwise customize the cleanup of any buffers the SSO uses?

[miscco]

I think it should be trivial to add a flag that memsets unused parts of the SSO array when allocating or destroying.

The Main question is whether the maintainers want to support the additional complexity. These codepathes need to be tested which is a considerable burden

[BillyONeal]

The entire "secure string" or "secure vector" concept are somewhat dubious if something like the SSO leaking stuff is important to you, since CPU registers or other collateral are likely to leak the information just as easily. Actually doing this the "right way" requires very conscious tracking of exactly where the data is going and usually needs something DPAPI to have much effect. (i.e. you CryptProtectMemory at your security boundary and write over the contents at the place where you're CryptProtectMemory-ing)

What is your threat model and/or attack you're trying to prevent here?

[frederick-vs-ja]

libc++'s strategy is incompatible with constant evaluation time SSO unless some utility needed for WG21-P2641 is avaiable.
(IIUC the current core UB can be eliminated in a constant-evaluation-incompatible way, though.)

Edit: I didn't aware of that __builtin_constant_p can also work in SSO-specific cases.

[BillyONeal]

I don't think burning the 99% use case for string at the altar of "constexpr performance" is the right tradeoff.

[frederick-vs-ja]

I don't think burning the 99% use case for string at the altar of "constexpr performance" is the right tradeoff.

Unfortunately, this goes beyond "constexpr performance" due to the nature of constexpr variables. Everything alternating constexpr and SSO probably affects well-formedness.

Via #1735 we've made the following code well-formed in release mode. If constexpr SSO is removed in vNext, there'll likely be a bug report for such regression, despite that the well-formedness of such code is unspecified.

#include <string>
constexpr std::string str{"SSO"}; // relies on constexpr SSO

Perhaps we can do something now to discourage writing non-portable code. But I don't think it's worthwhile reverting #1735.

[BillyONeal]

Via #1735 we've made the following code well-formed in release mode. If constexpr SSO is removed in vNext, there'll likely be a bug report for such regression, despite that the well-formedness of such code is unspecified.

#include <string>
constexpr std::string str{"SSO"}; // relies on constexpr SSO

Too bad. The spec doesn't say it works. The contract has never been "everything that you could possibly reverse engineer about the implementation's behavior"; the contract is the standard.

But I don't think it's worthwhile reverting #1735.

Cutting string's size by 50% (6 pointers to 4) while delivering an SSO almost twice the size (16 bytes to 31) is an extremely worthwhile end.

[philnik777]

I'm quite certain that a constexpr-friendly implementation that comes close to the libc++-non-constexpr-friendly version is possible. If you go for 32 bytes it would be almost trivial I think. This would work (at least for the Itanium ABI):

struct long_string {
  long_string(char* data, std::size_t size, std::size_t capacity)
      : data(data), size(size), capacity(capacity) {}

  char* data;
  std::size_t size;
  std::size_t capacity;
};

struct short_string {
  char buffer[31];
};

struct data {
  union U {
    long_string ls;
    short_string ss;
  };
  [[no_unique_address]] U u;
  std::uint8_t ss_len;
};

This results in a 31 byte buffer without any UB. I might actually implement that for libc++. Seems like it shouldn't be that hard. (Although that would be string ABI #3 in libc++)

[BillyONeal]

Your example will be 5 pointers on every implementation of which I am aware.

https://gcc.godbolt.org/#g:!((g:!((g:!((h:codeEditor,i:(filename:'1',fontScale:14,fontUsePx:'0',j:1,lang:c%2B%2B,selection:(endColumn:1,endLineNumber:27,positionColumn:1,positionLineNumber:27,selectionStartColumn:1,selectionStartLineNumber:27,startColumn:1,startLineNumber:27),source:'%23include+%3Ccstdint%3E%0A%23include+%3Ccstddef%3E%0A%0Astruct+long_string+%7B%0A++long_string(char*+data,+std::size_t+size,+std::size_t+capacity)%0A++++++:+data(data),+size(size),+capacity(capacity)+%7B%7D%0A%0A++char*+data%3B%0A++std::size_t+size%3B%0A++std::size_t+capacity%3B%0A%7D%3B%0A%0Astruct+short_string+%7B%0A++char+buffer%5B31%5D%3B%0A%7D%3B%0A%0Astruct+data+%7B%0A++union+U+%7B%0A++++long_string+ls%3B%0A++++short_string+ss%3B%0A++%7D%3B%0A++%5B%5Bno_unique_address%5D%5D+U+u%3B%0A++std::uint8_t+ss_len%3B%0A%7D%3B%0A%0Astatic_assert(sizeof(data)+%3D%3D+4)%3B%0A'),l:'5',n:'0',o:'C%2B%2B+source+%231',t:'0')),k:50,l:'4',n:'0',o:'',s:0,t:'0'),(g:!((h:compiler,i:(compiler:g131,deviceViewOpen:'1',filters:(b:'0',binary:'1',binaryObject:'1',commentOnly:'0',debugCalls:'1',demangle:'0',directives:'0',execute:'1',intel:'0',libraryCode:'0',trim:'1'),flagsViewOpen:'1',fontScale:14,fontUsePx:'0',j:1,lang:c%2B%2B,libs:!(),options:'',overrides:!(),selection:(endColumn:1,endLineNumber:1,positionColumn:1,positionLineNumber:1,selectionStartColumn:1,selectionStartLineNumber:1,startColumn:1,startLineNumber:1),source:1),l:'5',n:'0',o:'+x86-64+gcc+13.1+(Editor+%231)',t:'0')),k:50,l:'4',n:'0',o:'',s:0,t:'0')),l:'2',n:'0',o:'',t:'0')),version:4

[philnik777]

Billy O'Neal (@BillyONeal) you forgot to multiply by sizeof(void*): https://gcc.godbolt.org/z/dxMT8xhcG

[BillyONeal]

Oops