[cfe-dev] on libc++ extensions and slist

[Howard Hinnant]

In existing C++03 standard libraries there are a ton of extensions.  Some good, some not so good.  Some of the better ones have morphed into official  C++11 libraries.  However, I can't think of a single example where an extension has been standardized unchanged from its extension form.  There is good reason for this.

I'm going to pick on slist.  But my argument is meant to be broader than slist.

slist was first produced by SGI.  I'm not sure how long ago, but I'm betting circa 1996.  I'm also betting (not sure) that Matt Austern was the author (I have the utmost respect for Matt Austern).  At that time, C++ templates were pretty new, and the industry was not very experienced in their use.  For whatever reasons, the committee standardized a doubly linked list, but not the singly linked list (slist) in 1998.

At that time (1998) there was a debate over whether std::list::size() should be O(1) or O(N).  There are good arguments to be made on both sides of the debate (it involves list::splice).  And because the debate became so divisive, the committee drew a compromise:

   container::size() /should/ have constant complexity

(yes, this really does have something to do with slist, please be patient)

I should explain a little about committee-speak.  "Should" doesn't mean "should".  "Should" means "maybe, maybe not".  I'm not kidding. :-(

In practice, the only container that ever did have an O(N) size() was list, and even then, only for some implementations (including SGI and gcc).  And even though all well-read C++ programmers know not to use list::size() unless they are willing to pay O(N), I've seen *a lot* of code that uses list::size() carelessly.  I've even seen it in places you wouldn't expect, such as boost.

    for (size_t i = 0; i < c.size(); ++i)  // quadratic loop, not linear!
    { 
        // ...
    }

Somewhere around 2001-2002 Matt and I were having a friendly debate about this issue.  I said:  list shouldn't even have size().  Having it compile to an O(N) operation is almost always a run time performance bug.  And to Matt's credit, he immediately got it:  A compile time error is infinitely better than a run time performance bug.  And when Matt proposed slist (renamed to forward_list) to the C++ committee, it was missing a size() member.

Casual clients of std::forward_list, when they write:

    for (size_t i = 0; i < c.size(); ++i)
    { 
        // ...
    }

will rightly get a compile time error (as both Matt and I agree they should).

Casual clients of ext::slist, when they write:

    for (size_t i = 0; i < c.size(); ++i)
    { 
        // ...
    }

get a silent run time performance bug.

----

My point is that I believe we would be doing libc++ clients a huge favor by refusing to compile slist::size().  Instead we need to educate them to cache the size themselves, (or rewrite the code to not need size) so that their code has the expected run time characteristics; not only to the author of the code when he writes it, but to the many readers of the code years after he has written it:

    for (size_t i = 0, sz = distance(c.begin(), c.end()); i < sz; ++i)
    { 
        // ...
    }

or:

    for (const_iterator i = c.begin); i != c.end(); ++i)
    { 
        // ...
    }

To have libc++ silently compile slist::size(), in the name of easing migration, is not doing our customers a favor.  It is doing nothing but perpetuating a bad programming practice, known to be dangerous for at least a decade.

When our customers are migrating to libc++, it is at a time of their choosing.  They have set aside time to do the migration.  And shown interest in doing so.  A year after they migrate, when subtle problems surface, they are not going to be in the mood to be educated.  They are going to be in the mood to be educated about the right way to do things *when they are migrating*, and not later when run time problems arise.

----

Possible solutions to ease migration and not lead our customers into horrible mistakes we already know about:

1.  We could create an ext::slist that lacks size().  That way the customer would not have to change their code unless they used size().

Disadvantage:  We haven't delivered a seamless drop in replacement lib.  They still have to change their code.  Why not also change the name of the container to std::forward_list at the same time?  Otherwise we have to support slist.  And not just to ease migration.  Once we introduce it, we have to support it for forever for backward compatibility with our own lib.

2.  Status quo:  We could do nothing.

Disadvantage:  I'm seeing rising complaints about migration efforts.

3.  Educate:  In a private email about a week ago M.E. O'Neill noted that we should provide documentation recommending migration strategies for things like slist -> forward_list.  She suggested actually providing an <slist> header which did nothing but point to the documentation and then error out.  I'm not sure I'd go as far as providing such a header.  But I am really enthusiastic about a "migration document".  Having something to point to which explains why using slist is like playing with a loaded gun.  When people are migrating, they are open to such arguments if those arguments are both convincing and readily available.  And if the migration document provides a way to experiment without committing yourself (i.e. make it easy to backpedal the migration):

#include <ciso646>  // identify library

#ifdef _LIBCPP_VERSION
#   include <forward_list>
    template <class T> using MyList = std::forward_list<T>;
#else
#   include <ext/slist>
    template <class T> using MyList = __gnu_cxx::slist<T>;
#endif

int main()
{
    MyList<int> c;
    c.push_front(1);
    c.push_front(2);
    c.push_front(3);
}

Disadvantage:  Doesn't provide seamless migration.  And it is a fair amount of work to document.

Field experience:  I'm responsible for deprecating auto_ptr.  At the same time I introduced unique_ptr.  This involved a lot of documentation.  Not only with committee papers, but in participating in countless newsgroup and mailing posts to the general public, presentations, etc.  And it is paying off.  I now see lots of people I've never heard of telling others that they should replace auto_ptr with unique_ptr, even though it is not a drop-in replacement.  And the listeners are receptive to the message.

Instead of enabling our customers to continue to use a dangerous piece of code, we should be helping them become people who will educate others on the right migration strategy.

----

Final word:  If after considering my arguments, the majority of concerned readers wants to see an slist (or some other extension), I will not block it.  I will genuinely appreciate the fact that everyone concerned considered all arguments, both pro and con, and came to an informed decision.

Howard