Random access to long string bodies incurs cache misses

As I described in the last post, shuffling the items in the source vector leaves the string handles in contiguous sequential order while introducing disorder into the sequence of string bodies. The NShuffled “data set” is really a family of 11 related data sets, differing in the fraction of their items that were shuffled. All sets start with the same vector src of 50,000 elements, then std::shuffle() is run on the first N items in the vector, where N ranges from 0 (no items shuffled) to 50,000 (all items shuffled) in increments of 5,000. All the data sets will have 37,500 (75% of 50,000) of their source elements copied to the result vector.

more ...

For long strings, access order determines performance

In the last post, I described several possible causes of the slowdown for long strings in the by-value version of the idioms. I concluded the most likely actual cause was the order in which the string bodies are accessed.

more ...

Sidling up to the long string slowdown

In the last post, I highlighted an anomaly in the results for filtering long strings using the by-value implementation of the loop. The usual suspect for such outcomes, heap fragmentation, didn’t seem to apply in this case. What might be the actual source of the problem?

more ...

Microbenchmarks are highly sensitive to the heap context!

Over two weeks ago, I posted an article about by-value parameters in the loop and transform idioms. Included in one of the plots was an anomaly that, when I considered it more closely, blew up the analysis. In fact, I’ve spent most of the past two weeks following up on the implications of this seemingly small anomaly. Ultimately, it’s given me reason to question the reliability of microbenchmarks in a wide range of circumstances. And after two weeks of work, using a variety of tools, I remain unclear about the underlying phenomenon. I’m writing a series of posts to clarify what I’ve learned to date and to set my future agenda.

more ...

The elegant machine code for char const *

Unique strings—null-terminated strings uniquely identified by their char const *—are the simplest type considered in this series of posts. Constructing, copying, moving, and assigning these strings are trivial operations on a single pointer. No destructor code is required.

more ...