Eric Niebler: out parameters, move semantics, and stateful algorithms

This post from Eric, inspired by a prompt from Andrei Alexcandrescu, examines the interface of std::getline appraising its usability and performance. Eric looks at a few different designs, in particular those that leverage the move semantics introduced in C++11.

This is a particularly good exploration of a small and simple API – almost too simple to bother with – and Eric’s range-based solution is far more natural and still efficient.  The crux of his design approach stems from the insightful realisation that “getline is a curious example because what looks at first blush like a pure out parameter is, in fact, an in/out parameter; on the way in, getline uses the passed-in buffer’s capacity to make it more efficient. This puts getline into a large class of algorithms that work better when they have a chance to cache or precompute something.

The discussion in the comments below the post also merits reading, particularly Bartosz Milewski’s suggestion that front be thought of as take 1 (take n xs is a function in Haskell that returns a list of the first n elements of the list xs.

Link | Posted on by | Tagged , , , , , , | Leave a comment

Autumn [fall] 2013 C++ committee meeting

The C++ Standard Committee met in Chicago this week with a ballot resolution for the Committee Draft of the C++ 2014 Standard being its primary focus. Remaining time was devoted to processing DRs [defect reports] and issues from issue lists, as well as work on proposed new features for future standards. (Edit September 30: Stefanus Du Toit (ISO C++ Project Editor) has reported that C++14 is on track for 2014.)

The full list of papers included in the pre-meeting mailing is available here on the isocpp website, and Jens Weller has compiled an overview of them over the following pages:

I must admit to being somewhat excited about my first contribution to the standard potentially being acted upon this week. Granted it is merely a defect report (#2262), but nevertheless I’d be very happy to see the new wording I proposed appear in the next version of the standard :-)

Below are the changes I’m particularly looking forward to seeing appear.

Concurrency

Futures: continuations (and composability)

The addition of std::future<T>::then(), which sounds like it would dramatically improve the usability of futures. I have little experience of them as of yet, but this article shows the power of ‘continuations’, albeit in a Node.js context. Incidentally Bartosz Milewski wrote an interesting article concerning Functional C++ and continuations…perhaps not for the faint of heart though. If you have some code you wish to be run as soon as a future is ready, you must currently do so either in a dedicated thread or mixed up with other code; sometimes this is fine, but other times it just adds noise.

The composability of futures via  std::when_any() and std::when_all() is also a sensible-looking addition included here.

These extensions will be released in a Concurrency TS [Technical Specification] targeted for Q1 2015.

Software Transactional Memory

Transactional Memory support is being added; this is another feature of which I have no practical experience. Simon Peyton-Jones’ article Beautiful Concurrency covers the subject in the context of Haskell, and shows compelling evidence that this would be a great tool to have when developing concurrent software.

This facility looks to be targeted for C++17 or perhaps earlier.

Concepts Lite

Imposing and checking requirements on template arguments currently requires a rather unpleasant std::enable_if<>-based approach. Concepts is the way to do this properly, but is a massive change that was too unwieldy to add in one go. Concepts Lite is the halfway house, and I believe already has a reference implementation in Clang. Bring it on!

This will be made available via a Concepts TS targeted for 2014.

Exceptions

The std::exception class is extended to support the addition of user-defined information to it, similar to the facility provided by Boost.Exception albeit with a different syntax. Also included in this change is std::exception::diagnostic_information() and some standard information types such as function name, filename & line number. I hope this will dramatically improve the usefulness of information available from a caught exception, particularly since the paper encourages implementations to automatically include the 3 example information types in all exceptions derived from std::exception. It will also negate the need for the BOOST_THROW_EXCEPTION macro at our own throw sites.

My guess is that this will be made available in the ‘Library Fundamentals’ TS targeted for 2014.


Trip Report

Herb Sutter’s trip report is available here.

Posted in Uncategorized | Tagged , , , | Leave a comment

Don’t couple streams with devices

robdesbois:

In this post Marco reviews and improves upon a debug stream implementation that builds on the standard IOstream classes, touching on the separation of concerns built into this area of the C++ standard.

Originally posted on Growing up:

A couple of weeks ago, a friend of mine coded an output stream that outputted strings through Win32 OutputDebugString function (you can use DebugView to monitor these kind of traces). His implementation had two main problems:

  • it was designed quite poorly (as you’ll see in a while),
  • it didn’t allow a real formatting.

With the second point I mean: everytime operator<<(stream&, something) was called, something was sent to OutputDebugString. I paste here a facsimile of his code:

1

What I mostly dislike of this code is the design choice to inherit from std::ostringstream

View original 846 more words

Posted in Uncategorized | Tagged , , | Leave a comment

ISO C++ committee draft

Following the recent meeting of the ISO C++ standards committee, Working Group 21 (WG21) in Bristol, UK, a number of proposals have been accepted into the ‘Committee Draft’ of the next standard, currently scheduled for next year (“C++14″).

Although this is a ‘bug fixes and minor update’ revision of the standard, it contains some improvements that I know will show significant improvement in some areas. Generic lambdas, generalized captures and return type deduction for normal functions, for example, will enable creation of code that is less brittle in the face of type changes, and also allow things that weren’t possible without hacks (e.g. moving unique_ptr objects into lambdas).

Herb Sutter has written up his trip report, which shows an overview of the changes, and below is a list I have compiled of the accepted papers. I wrote the original for my team, so it is ordered by level of relevance/benefit to our own work or my own interest, and I have given less attention to detail for the proposals I don’t see affecting me/us. I will gladly accept suggested corrections and omissions for the list.

[April 26th] Michael Wong has also written a trip report covering some of the discussions and rationale. This is part 1 (Language).
[April 27th] Reddit discussion of  some of the new facilities.
[April 30th] Part 2 (Library) of Michael Wong’s trip report.
[May 1st] Part 3 (Concurrency) of Michael Wong’s trip report.
[Sep 25th] The first Committee Draft of the C++14 standard, N3690, is available here.

N3656 make_unique

Proposes the missing unique_ptr analogue for make_shared. There are 3 overloads: 1 for a single object with argument pack that is forwarded to the object constructor, and 2 for arrays, one of which is deleted to ensure it is used correctly (it takes a single argument: the array size, so cannot be used for a fixed-size array). The implementation of the single object overload matches that suggested by Herb in GotW 102.

N3638 Return type deduction for normal functions

This adds the ability to use auto for any function’s return type, with the same effect as exists now for lambdas, i.e. deduce the return type from the function’s implementation. For both normal functions and lambdas the requirement that the implementation be of the form return expression; is relaxed, and the deduction even works for recursive functions as long as a single type is deducible!

auto sum(int i) {
  if (i == 1)
    return i;  // return type deduced to int
  else
    return sum(i-1)+i; // ok to call it now
}

Return type deduction is not supported for virtual functions.

N3648 Wording Changes for Generalized Lambda-Capture

Adds lambda captures of the form identifier initializer and &identifier initializer, which both behave like a declaration of the same form preceded by auto. The paper is standardese only, but N3610 has a more readable description.

int x = 4;
auto y = [&r = x]() {...}; // equivalent to auto& r = x

// shows moving an object into a capture variable, as well as the capture
// identifier capturing from and hiding the same name from outer scope.
std::unique_ptr p( new int(42) );
auto z = [p = std::move(p)]() {...};

N3649 Generic (Polymorphic) Lambda Expressions (rev3)

Enables ‘templated’ lambdas, and without an angle bracket or template in sight; marvellous!

auto Identity = [](auto a) { return a; };

In addition this change will allow ‘universal references’, parameter packs, and perfect forwarding:

template< class T >
auto make_factory() { // using N3638 return type deduction
  return []( auto&&... args ) {
    return std::unique_ptr( new T( std::forward< decltype(args) >(args)... ));
  }
}

N3659 Shared locking in C++

This provides shared_mutex, and shared_lock for non-exclusive (‘read’) locking, with unique_lock continuing to provide the exclusive (write) locking as it does today.

N3655 Transformation traits redux, v2

This is a ‘convenience’ proposal to simplify usage of the ‘transformation traits’ that produce one type from another, such as add_lvalue_reference.

With today’s library you must write typename add_lvalue_reference<T>::type to use the facility, whereas the proposal adds a template alias interface enabling add_lvalue_reference_t<T>. Note the trailing _t there: each of the transformation traits gains an alias with the same name transformation.

Although I’m sure some will deem these additions too trivial to fill pages of the standard with – indeed section 4, which adds the same treatment for the other traits, was not accepted for this reason – they do clean up syntax particularly where transformations are nested, and I will be using them myself. The paper includes the additions for all traits, so those who wish can use them immediately including the section 4 transformation aliases.

N3672 The standardisation of Boost.Optional

What it sounds like, with some differences to the current Boost.Optional implementation, particularly useful being the addition of move support.

From the paper, “The basic usage of optional can be illustrated with the following example.”

optional<int> str2int(string);    // converts int to string if possible

int get_int_form_user()
{
  string s;

  for (;;) {
    cin >> s;
    optional<int> o = str2int(s); // 'o' may or may not contain an int
    if (o) {                      // does optional contain a value?
      return *o;                  // use the value
    }
  }
}

N3662 C++ dynamic arrays (dynarray)

A kind of std::vector/std::array hybrid; has a capacity fixed on construction (unlike vector) that is not part of the type (unlike array). This provides much-needed sequence container operations over a raw array where we don’t want a different type, or cannot fix size at compile-time.

// construct
std::dynarray<int> ints(5, 42); // the sequence {42,42,42,42,42}
auto another(ints);             // copy-constructed sequence
std::dynarray<int> empty(0);    // empty sequence {}

// size & unchecked element access
for (int i=0; i < ints.size(); ++i)
  ints[i] = i;

ints.at(10) = 10; // throws std::out_of_range

// front/back
ints.front() = 5;
ints.back() = 5;

// sequence iteration output "25 1 25 3 25"
std::copy( ints.begin(), ints.end(), std::ostream_iterator(std::cout, " "));

// contiguous storage access
int* data = another.data();
another.fill(0);

N3639 Runtime-sized arrays with automatic storage duration (rev5)

Based on the recent addition of Variable-Length Arrays (VLAs) in C11, this allows e.g. int a[n]; where n has a runtime value, and restricts a to automatic storage duration. The dynarray proposal (N3662) allows for the freestore-based equivalent.

N3652 Relaxing Constraints on constexpr Functions

Allow some declarations, if, switch, for, while, do-while, and mutation of locally-scoped objects in constexpr functions.

N3668 exchange() utility function (rev3)

Specifies T std::exchange(T& old, U&& new) that updates old to new and returns old‘s original value, similar to the facilities provided for atomics.

N3651 Variable templates

Enables type-parameterized constants e.g. for different representations of pi: pi<double>, pi<float> and, God forbid, pi<int> :-D

N3654 Quoted strings (rev2)

Allows for fixing the inconsistency in the following:

std::stringstream ss;
ss << "Hello world";
std::string in;
ss >> in; // 'in' is "Hello" instead of "Hello world"

N3642 User-defined literals for standard library types

Adds ‘user-defined’ (albeit defined by the library…) literals for std::basic_string (e.g. "blah"s), std::chrono::duration members (e.g. 21min, 42ms), plus binary and complex numbers.

Other proposals

As Herb’s trip report, and the comments beneath it, show, additional proposals have been worked on during the meeting, in particular N3505, a Boost.Filesystem (v3)-based library, is looking good for release in parallel, along with a networking library and N3580 “concepts lite”.

One of the even more exciting things that I hope will truly revolutionise how we use C++ is the ‘modules’ proposal. This formalises package (module) management to make the compiler aware of them, and neatly combines the facilities that are currently rather clunkily provided by namespaces and headers. If my understanding is correct, this will also provide a basis for much faster builds as the include vs. forward declare, and exposure of implementation of class/function templates in headers become non-issues that need not be considered. According to Herb this is being worked on by the Clang guys and “the intent is to issue a Modules technical specification as soon as it’s ready”. Hurrah!

Finally, a massive thanks to all those at the coalface for the work that went into these proposals and last week. The results are impressive, and the scale of accepted proposals stretches the bounds of the ‘bug fixes and minor update’ description. Roll on 2012 :-)

Posted in Uncategorized | Tagged , , , , | 4 Comments

Boost compile error “no class template named ‘result’”

I’ve just come across a compiler error resulting from using boost::result_of with a C++11 lambda.
I wasn’t actually using boost::result_of directly, but provided a lambda as the transforming functor for a boost::transform_iterator, which uses it behind the scenes.

Here’s a small listing that shows the problem:

#include <boost/iterator/transform_iterator.hpp>
#include <iostream>

int main()
{
   int i[] = {1, 2, 3, 4};

   auto square = [](int i) { return i*i; };
   auto begin  = boost::make_transform_iterator( i,   square );
   auto end    = boost::make_transform_iterator( i+4, square );
}

with Boost 1.48 that yields the following error:

In file included from /usr/include/boost/iterator/transform_iterator.hpp:23:0,
                 from boost-result-of-error-with-lambdas.cpp:2:
/usr/include/boost/utility/result_of.hpp: In instantiation of ‘struct boost::detail::result_of_nested_result<main()::, main()::(int&)>’:
/usr/include/boost/utility/result_of.hpp:83:8:   required from ‘struct boost::detail::tr1_result_of_impl<main()::, main()::(int&), false>’
/usr/include/boost/utility/detail/result_of_iterate.hpp:23:8:   required from ‘struct boost::tr1_result_of<main()::(int&)>’
/usr/include/boost/utility/detail/result_of_iterate.hpp:80:8:   required from ‘struct boost::result_of<main()::(int&)>’
/usr/include/boost/mpl/eval_if.hpp:38:31:   required from ‘struct boost::mpl::eval_if<boost::is_same, boost::result_of<main()::(int&)>, boost::mpl::identity >’
/usr/include/boost/iterator/iterator_adaptor.hpp:160:12:   required from ‘struct boost::detail::ia_dflt_help<boost::use_default, boost::result_of<main()::(int&)> >’
/usr/include/boost/iterator/transform_iterator.hpp:50:17:   required from ‘struct boost::detail::transform_iterator_base<main()::, int*, boost::use_default, boost::use_default>’
/usr/include/boost/iterator/transform_iterator.hpp:74:9:   required from ‘class boost::transform_iterator<main()::, int*, boost::use_default, boost::use_default>’
boost-result-of-error-with-lambdas.cpp:10:60:   required from here
/usr/include/boost/utility/result_of.hpp:79:8: error: no class template named ‘result’ in ‘struct main()::’

The problem is that boost::result_of doesn’t play well with C++11 lambdas straight off, fortunately the solution is simple: define preprocessor symbol BOOST_RESULT_OF_USE_DECLTYPE and all is well again :-)

Thanks to Akira Takahashi for the solution in this response to the same issue triggered from the range adaptors.

Posted in Uncategorized | Tagged , , , | 1 Comment

An implementation of generic lambdas (request for feedback)

Faisal Vali has created an initial, alpha implementation (in Clang) of the current Generic (Polymorphic) Lambda Expressions proposal (N3418). This would see the addition of support for templated lambda expressions; the current state achieves this either via explicit parameter list after the lambda introducer, or by using the ‘auto’ keyword in place of a typename.

The article links to an interesting (FSVO interesting) discussion of the proposal, and the Clang source with support for it.

Link | Posted on by | Tagged , , , | Leave a comment

Adventures in lock-free programming

I’ve been intrigued by the idea of lock-free programming since I discovered that C++0x (as it was then) was to gain library facilities for standardised, portable lock-free programming. The new <atomic> header enables us to perform atomic reads and writes on a restricted set of types, and to use atomic operations as synchronisation primitives in lock-free programming.
I am still new to this topic, and have approximately equal measures of interest in the possibilities and fear of the complexity and difficulty, but wish to expose the list of writings I have found informative in my learnings. Get in touch if you know of any good additions to this list as I will be updating it with further discoveries.

volatile vs. volatile [Herb Sutter]

An explanation of what ordered atomic variables do. Also covers the use of volatile in C++ for ‘unusual’ memory semantics.

The Trouble With Locks [Herb Sutter]

Sutter's Mill [from Alena & Jim's 'The C++ Lands']

Lock-based programming, our status quo, is difficult for experts to get right. Worse, it is also fundamentally flawed for building large programs.

Lock-free programming is difficult for gurus to get right.

Herb explains why lock-based programming is difficult, brittle, and why locks are not generally composable.

Lock-Free Code: A False Sense of Security [Herb Sutter]

Herb dissects a lock-free queue implementation to show the flaws in its design, discussing the twin requirements of atomicity and ordering on any lock-free variable. He exposes the points in the lock-free algorithm in which instruction re-ordering can break the queue’s invariants.

Writing Lock-Free Code: A Corrected Queue [Herb Sutter]

The typical coding pattern to use is to do work off to the side, then “publish” each change to the shared data with a single atomic write or compare-and-swap.

In the sequel to A False Sense of Security Herb shows a lock-free queue implementation with a working implementation based on atomic variables.

Writing a Generalized Concurrent Queue [Herb Sutter]

Herb Sutter
In this final part of the series Herb writes a generalized queue structure; he does this without mutexes (mutices?), but uses atomic variables equivalently with no relaxation of the barriers for each read/write operation.

Apply Critical Sections Consistently [Herb Sutter]

Herb shows how to express a critical section with several different synchronisation primitives, and shows some example code too.

Memory Barriers Are Like Source Control Operations [Jeff Preshing]

This article uses the analogy of source code control to explain the different memory barriers (fences). This was a great one for me, though I can’t honestly say I completely grok it yet… Jeff’s other articles linked from that page are also good background on the subject.

C++ atomics and memory ordering [Bartosz Milewski]

Bartosz provides a much more readily understandable description of C++11’s different memory_order enum values than the standard; anyone who understands all of section 1.10 Multi-threaded executions and data races has my respect.

C++ Concurrency in Action: Practical Multithreading [Anthony Williams]

C++ Concurrency In Action
I’ve only just begun reading this loan from a colleague, and so far am very impressed by the clarity with which concepts and techniques are explained and demonstrated. It was written for the new, standard thread support facilities by the creator of the just::thread C++11 implementation who also helped guide the standardisation of threads and other language features.

Posted in Uncategorized | Tagged , , , , , | Leave a comment