Benchmarks of Cache-Friendly Data Structures in C++

“Small-size optimization” (SSO) means that instead of keeping all its data on the heap (like does), this class preallocates some amount of data (the actual size of which is configurable via a template parameter) locally on the stack, and only performs a (slow!) There is some fine print here: SmallVector can be awkward at interface boundaries, since the preallocated size is part of the template type. Lookup in the is shockingly slow at large data sizes—again, I don’t have a good explanation for why this is.

Source: tylerayoung.com