It's my understanding that expression templates as a technique were discovered significantly prior to the original C++ Standard in 1998. Why weren't they used to improve the performance of several standard classes like std::string and streams?

migrated from stackoverflow.com Jan 25 '12 at 20:16

This question came from our site for professional and enthusiast programmers.

  • @ChrisLively: If I were to submit a proposal suggesting such a change, then it would absolutely be a problem that I didn't know why it wasn't done the first time around, and it is absolutely programming relevant and the answer is very specific. – DeadMG Jan 25 '12 at 20:05
  • What exactly would you do with expression templates to speed up strings? – jalf Jan 25 '12 at 20:09
  • 4
    @jalf: If you were to apply it to operator+, you could achieve O(n) and zero redundant allocations for repeated allocations, something which is still faster than rvalue references. In addition, you could optimize for example COW implementations by copying on write, not just "on index into non-const". There are other applications too where both performance and semantics can be improved with expression templates. – DeadMG Jan 25 '12 at 20:11
  • True enough. Thanks for elaborating:) – jalf Jan 26 '12 at 9:38
  • I realize this question was asked a while ago, but please elaborate some regarding what expression templates are and/or link to relevant material. – einpoklum Dec 22 '15 at 22:59
up vote 15 down vote accepted

Expression templates were first published by Todd Veldhuizen in June 1995, in an article in the C++ Report magazine. By that time, the standard committee was already heavily involved with adding the STL to the C++ standard, a task which all by itself delayed the standard by one or two years. (The STL was presented to the committee in 1993, and officially proposed in 1994. It took another four years to finish the standard.)
Given that the C++ standardization committee is a bunch of volunteers, some of them not even backed by companies paying their expenses, I don't think anyone had any resources to use on adding yet another idea to the C++ standard.

Also, 1995 is just the year Veldhuizen's article was published. For the technique to become known and recognized, it would have taken another few years. (The idea of the STL dates back to the 70s, an Ada implementation was done in the late 80s, work at a C++ implementation must have started around 1990, and it took another three years for the idea to find its way to the C++ standardization committee.)
There were, however, just three years from Todd's article until the final vote on the standard. That was way too little time to incorporate an idea that was still brand-new and basically untested.

Add to that the fact that Expression Templates, being a kind of template meta-programming, stress compilers way more than the comparatively "simple" STL does. And from what I remember, even in 1998, when the standard was published, we didn't have a compiler that could even compile all of the STL.
Given that one of the standardization committee's main goals was to standardize established practice (not that they stuck to this rigorously), Expression Templates should never have been on the agenda back then.

  • 1
    But std::string and iostreams were not in the STL. – R. Martinho Fernandes Jan 25 '12 at 20:06
  • @R.MartinhoFernandes: That doesn't mean, however, the committee had any resources to spare. (And std::string was changed to turn it into an STL container, BTW.) – sbi Jan 25 '12 at 20:08
  • 1
    I think I just have to link this: Is std::string part of the STL? – Xeo Jan 25 '12 at 20:10
  • @sbi ah, that makes sense. – R. Martinho Fernandes Jan 25 '12 at 20:13

The simple answer is: you obviously didn't lobby for it. Nor did I because I had (and have) my own agenda which doesn't include expression templates. Also, the interface in particular for strings is already trying to serve way too many masters, resulting in a class which is used for everything and good for mothing.

The standard library has already std::valarray and family which is intended to support an expression template style of implementation. As far as I can tell it doesn't quite cut it, though. One problem which caused this is that the people who lobbied to get its half-baked version included into the standard stopped working in it the moment it included. There were attempts to rescue it (e.g. David Vandevoorde, Matt Austern, and I worked on it for a day or so at the Stockholm meeting) but in the end nobody was interested enough.

  • 7
    You start off a bit unfair, because DeadMG could not lobby for it due to the simple fact that he had barely outgrown his diapers back then and probably hadn't reached the point where he could properly pronounce "C++". :) – sbi Jan 25 '12 at 20:17
  • 6
    Terribly sorry that as a toddler, I didn't get lobbying :P – DeadMG Jan 25 '12 at 20:18
  • 1
    I realize that not everybody had the opportunity to influence the standard. Although I regularly attend committee meetings since about 15 years my influence on the standard is limited. However, my point is: if somebody wants something in the standard they need to make effort! Things not being there is essentially down to people having other priorities, whether they are technical or otherwise (e.g. fully concentrating on growing up). – Dietmar Kühl Jan 25 '12 at 22:44
  • The libgcc implementation of valarray bases on expression templates. – phresnel Nov 25 '14 at 10:02

The technique now known as "expression templates" was discovered (independently) at least as far back as 1994 by both Todd Veldhuizen and myself (Todd's article is from 1995, but it takes a bit of time for stuff to get published; my own work was first shown in comp.lang.c++).

I actually started attending C++ committee meetings exactly because of this issue. I presented the technique and a complete redesign of std::valarray to the committee at the first Santa Cruz meeting in March 1996. It was deemed too large of a change, but as Dietmar alludes to, we got some words in at the subsequent meetin in Stockholm that enable the use of expression templates for the implementation of std::valarrray. To my surprise, those words are still there: See paragraph 3-6 of subsection [valarray.syn] 29.7.1 in http://wg21.link/N4727 .

  • 1
    wonder what's the point of using link shortener instead of the real URL – gnat Apr 15 at 20:20
  • 1
    @gnat: If you know a document number, it's trivial to write the wg21.link URL for it. That's what I did here. It saves me looking up the particular mailing/year that a document was released in. Also, I'm hoping that if/when WG21 decides to move the hosting URLs, wg21.link will be updated accordingly, thus avoiding stale references. (I.e., the point is not shortening, but readability.) – Daveed V. Apr 16 at 21:27

My best guess is that no compiler would have been able to compile expression templates back in 1998.

  • 1
    Todd Veldhuizen did his expression template work before 1996 using KAI's C++ compiler. The reason is much more profane... – Dietmar Kühl Jan 25 '12 at 20:05
  • 1
    A large percentage of the C++ community wasn't able to use the STL to its full potential until 2003 either (I'm looking at you, Microsoft!), and that hadn't stopped the committee to incorporate the STL into the standard. – sbi Jan 25 '12 at 20:14
  • 1
    Actually, bth Todd and I originally got the expression templates technique to work on the Borland C++ 4 compiler (which was released in 1993). Incidentally, I believe that's also the first compiler on which the STL was made to fully work. I later ported an expression templates library to a variety of other compilers (including Sun's Cfront-based compiler at the time!). The KAI C++ compiler cam a little later. – Daveed V. Apr 15 at 16:17
  • @DaveedV. BCC4 was a very good compiler for its time and much better than that time's VC version! It did have some quirks, though, like the infamous "smiley bug". :-> Plus they failed to improve it fast enough, so it quickly became harder and harder to use the rapidly improving templates techniques with it. When VC7.1 was released and was much more complying, that killed Borland off. – sbi May 13 at 22:27

protected by gnat Apr 15 at 20:19

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.