CppCon 2016: Nicholas Ormrod “The strange details of std::string at Facebook'

—
—
Standard strings are slowing you down. Strings are everywhere. Changing the performance of std::string has a measurable impact on the speed of real-world C++ programs. But how can you make strings better? In this talk, we'll explore how Facebook optimizes strings, especially with our open-source std::string replacement, fbstring. We'll dive into implementation tradeoffs, especially the storage of data in the struct; examine which standard rules can and cannot be flouted, such as copy-on-write semantics; and share some of the things we've learned along the way, like how hard it is to abolish the null-terminator. War stories will be provided.
—
Nicholas Ormrod
Software Engineer, Facebook
Nicholas is a developer efficiency engineer at Facebook. If he talks too much, disable him with a well-placed nerd snipe.
—

*-----*
*-----*

[NeonStorm]

Wow, I didn't think a 30 minute talk about string optimisation could be so entertaining, but here we are.

If there's such a thing as a beautiful bug, that jemalloc + kernel + null terminator bug is beautiful :)

[sergiYT]

That bug with the last byte of string going into the new page of memory is beyond scary

[ancientapparition]

thats the cleverest 0 I've ever seen

[Ratstail]

This guy is so passionate! I'm just glad he's not selling MLMs.

[xCAFEFD]

He's really good at talking. Fun subject too.

[TheThirdAttractor]

one of the best talks at CppCon 2016!!!

[chrisanderson]

20:35 "Most people write good code" ... it's sad that this statement made me laugh...

[kim]

9:27 oh my fucking god is that genious! I literally said that out loud. Wow.

[kered]

What was the conclusion!? Does FB use fbstring or gcc string now?

[davidbrown]

Great talk, it made the issues around current strings really clear.

It inspired me to comment; and then research; and then rework my comments somewhat. Especially the undefined behaviour stuff near 25:00 :)

Ok that undefined behaviour setup at 25:00; so 129 bytes is allocated with the first 128 bytes on one page and the last byte on another page. And the last byte is not written.

The bug is explained to be caused by malloc conditionally allocating a page (I think 'conditionally' means, the numa node the page is allocated on will be determined by the numa node of the thread that first touches a virtual address in the page). Then the kernel returns zero for the read because the page has not been assigned a node yet; and on the next write the page is allocated a node, and the address space is allocated a page on that node...

Ok so that requires the OS to have very surprising behaviour: a read fault on a page that is pending assignment is satisfied by a temporary mapping of a zero filled page, a write fault is satisfied by a persistent mapping of a page of data (from memory, swap or etc) that contains non-zero data being mapped into the physical memory of the numa node address space.

Ok; so I googled a bit around conditional page allocation, and found stuff about page allocation based on numa_node_id() ... and then did some searching, and found some more under numa first touch policy, and even numa_next_touch().

The text above suggests that the OS developers define 'touch' as read or write.
This is the sort of conservative approach that I expect from a working OS.

So I understand this to be a theoretical bug, not an actual bug. That is some vendor **could** implement some numa policy as defined (ie reads go to a special zeros page until a write happens, then non zero data is mapped the same address space for the program). No client of such a vendor would be happy, as it would break programs in ways to difficult to imagine. It would be widely parodied as a broken OS. (I don't use windows, please tell me this is not how windows does this).

The next message is about why I think the undefined behaviour of accessing uninitialised POD values should be limited to stating that the initial value is an unknown, but otherwise valid, value.

Argh.. excluding floating point values that might have some codes that generate hardware exceptions.

[IsmeGenius]

data[size()] = '\0' was UB in the first place.
"Favorite thing to do is to put base10 serialized randoms in strings". Gosh, make a class for that.

[matiasbatero]

The historical pascal string is a fixed-size of 256 bytes and allocated in the stack. ;)

[Peregringlk]

The part starting at 22:50 is hilarious Love the characterization.

[GeatMasta]

Wouldn’t valgrind pick up that bug in unit tests just immediately?

[为民程]

really great talk, learns a lot, thanks!

[yackawaytube]

wow... there surely a lot of smart C++ programmers at FB

[MrAbrazildo]

And what about the new benchmark? How fbstring performed vs the new GCC 1, for overall Facebook?

[alexmiller]

Does anyone follow the bug that he was describing? The behavior that he describes sounds like the behavior of madvise DONTNEED, but this would mean that jemalloc would have to be trying to purge a dirty *used* page. That should instead be a jemalloc bug.

So for this to happen, does jemalloc explicitly track the requested allocation size vs size class given to be able to prove that the byte used for the null terminator shouldn't be able to be written to?

[jasplaysbass]

Why do they store the 64 bit random numbers as base 10 encoded string? He says that’s one of their favorite strings and gcc’s smaller string can’t accommodate their random numbers. Well don’t store it as a string then! Store them as a long ie 8 bytes.