Innovation on a Shoe String

String value semantics

2013 Keynote: Optimizing the Emergent Structures of C++ – Chandler Carruth


You don’t need output parameters, we have value semantics in C++ […]. Anytime you see someone arguing that “nonono I’m not going to return by value because copy would cost too much”, someone working on an optimizer says they’re wrong. All right? I have never yet seen a piece of code where that argument was correct. […] People don’t realize how important value semantics are to the optimizer because it completely clarifies the aliasing scenarios.

import re for i in range(1000000): re.split(' +', 'a b c')

The previous python code is twice as fast than the following c++ code (which uses libc++’s regex implementation):

#include #include #include using namespace std; vector split(const string &s, const regex &r) { return { sregex_token_iterator(begin(s), end(s), r, -1), sregex_token_iterator }; } int main { const regex r(" +"); for(int i = 0; i < 1000000; ++i) split("a b c", r); return 0; }

It’s easy to spot the performance problem here, the c++ version allocates strings to fill a vector which itself is allocated/destroyed in each iteration of the loop, while the python version should just be doing the right thing: building string slices over the single original string.

The trivial naive way to solve the issue with the c++ code is using parameters by reference for output:

#include #include #include using namespace std; void split(const string &s, const regex &r, vector &v) { auto rit = cregex_token_iterator(, + s.length, r, -1); auto rend = cregex_token_iterator; v.clear; while(rit != rend) { v.push_back(*rit); ++rit; } } int main { const regex r(" +"); vector v; for(int i = 0; i < 1000000; ++i) split("a b c", r, v); return 0; }

This avoids all the abusive string allocations/destructions, the vector grows its memory just once. Still, we could have string slices over the original string instead of allocating memory for the token substrings and there’s now this awkward interface, it’s not as natural as the python version of split which uses a return value as output.

How do we solve this?

You might also like
angela friederici - the N400 and word meaning
angela friederici - the N400 and word meaning
Semantics and Pragmatics - Word Semantics
Semantics and Pragmatics - Word Semantics
Related Posts