Katkat

Optimize a small-string C++ class

NVIDIASoftware Engineer · Onsite

Last updated

This question evaluates low-level C/C++ systems programming skills, including memory management, data layout, small-string optimization, efficient copying semantics, alignment/padding, and cache-aware performance reasoning.

You are implementing a high-performance C/C++ string type that uses a small-string optimization: short strings are stored inline in a fixed buffer, and long strings are stored on the heap.

Given the (simplified) class layout below:

const size_t BUFF_SIZE = 128;

class MyString {
private:
 char buf[BUFF_SIZE]; // inline storage for “small” strings
 size_t length; // number of bytes (not including '\0')
 char* ptr; // heap storage for “large” strings

public:
 MyString(const char* s, size_t len) {
 length = len;
 if (len < BUFF_SIZE) {
 strncpy(buf, s, len);
 buf[len] = '\0';
 } else {
 ptr = (char*)malloc(len + 1);
 if (ptr == nullptr) throw "not enough memory";
 memcpy(ptr, s, len);
 ptr[len] = '\0';
 }
 }
};

Answer the following:

  1. strncpy(buf, s, len) copies characters one-by-one conceptually. How would you speed up copying for the small-string case?
  2. Is using memcpy(buf, s, len) equivalent to strncpy(buf, s, len)? If not, what are the behavioral differences and safety pitfalls?
  3. In a cmp/string-compare function, why can comparing short strings (< 256 bytes) be significantly faster than comparing long strings, even if you “ignore the length difference” conceptually?
  4. If BUFF_SIZE == 1, what is the likely sizeof(MyString) on a 32-bit machine vs a 64-bit machine? Explain the role of alignment/padding.
  5. If BUFF_SIZE == 8 but typical strings are ~10–15 characters, how could you redesign the layout to reduce object size and improve cache locality? (Hint: avoid paying for both inline storage and a pointer when only one is needed.)