Fast Digital Sine Oscillator

I originally intended this blog to be about math and digital signal processing as well and not just about C++. Since I recently answered a programming forum question regarding efficient generation of sine waves and took the time to code one in — surprize — C++, I thought to myself, why not sharing the code along with explanations about how it works.

If you’re interested in software synthesizers in general or generating digital representations of DTMF tones and don’t want to waste many CPU cycles when generating sine waves, keep on reading.

C++0x: No concepts no fun?

“Concepts” was a proposed C++0x feature that was supposed to make generic programming more enjoyable. The intention was to render many guru-level “template tricks” superfluous, produce much better compile-time error messages and provide “modular type checking” so errors can be caught early (even before a template is instantiated).

• Fact 1: Concepts have been removed from the C++0x standardization effort. See Doug Gregor’s blog post.
• Fact 2: C++0x still includes a whole lot of other core language and library features.

C++: Exploiting Copy Elisions

This article is about writing efficient code and giving the compiler opportunities for optimizations with respect to copying / “moving” objects in good old C++98. I use a simple function as an example but it should extend to other cases as well. The technique that is described here (“swaptimization”) is not entirely new and I can’t take credit for it. But it is probably little-known which is a good reason to write about it. 🙂

C++0x: Rvalue references 101

If found a very nice article about rvalue references and move semantics (primarily) by Dave Abrahams. It also considers return value optimizations, exception safety and in what state an object should be left in after its resources have been “stolen”. Here it is.

[Edit 2009-08-18: The link doesn’t seem to work anymore. However, Dave Abrahams has started to refine, extend, and convert it into a series of blog posts on his new site ]

– P

C++0x: Do people understand rvalue references?

[last update: 2009-05-27]

Occasionally I happen to see a piece of C++ code from an eager author that tries to utilize rvalue references but doesn’t understand them and gets it wrong. I remember that I had trouble fully grasping the rvalue reference concept. But now, it seems like that was way in the past. I can hardly remember why it was so difficult to understand rvalue references.

It may have something to do with the sources people use to learn about this feature. For example I wouldn’t consider the C++0x wikipedia article to be a good introduction for rvalue references. It seems too short for that. But this wikipedia article is a nice overview of what kind of features can be expected.

Let me just mention the real sources worth reading:

• N1377: Move Proposal (2002)
• N1385: Perfect Forwarding Problem (2002)
• N2027: A Brief Introduction to Rvalue References (2006)
• N2812: A Safety Problem with Rvalue References (2008)
• N2844: Fixing a Safety Problem with Rvalue References (Revision 1, 2009)
• Rvalue References 101by Dave Abrahams

I would recommend N2027 as an introduction and Dave Abraham’s article for more practical details including exception safety and return value optimizations.

A little C++0x finger exercise

Since the C++ compiler of GCC 4.3.2 comes with partial C++0x support and I had not tested all of these features yet, I decided to do a little finger exercise: “function”.

“function” is a useful library feature of Boost, TR1, and the upcoming C++ standard library. It’s basically a class template mimicing the behaviour of a function pointer. But it’s much more flexible because it applies to any “callable object” — function pointers and objects with overloaded function call operator. Also, the signatures don’t have to match perfectly as long as the parameters and return values are implicitly convertible. I’m going to show you how this library feature can be implemented with C++0x features — including variadic templates and rvalue references. But before going into any details let me give an example of how code that uses this “function” library might look like. In case you’re already familiar with this library feature you can skip the following piece of code and paragraph of text.

Surprizing C++ reference-binding rules

Isn’t it amazing? You see a very simple piece of code that looks perfectly fine and wonder why it is supposed to be ill-formed:

  struct foo {
    foo();
  private:
    foo(const foo& rhs);
  };

  void func1(const foo&);

  void func2() {
    foo o;
    func1( o ); // ok
    func1( foo() );  // ill-formed, foo's copy-ctor is private
  }

Although an rvalue is allowed to bind to a reference-to-const, the C++ standard allows a compiler to copy an rvalue to another temporary rvalue before binding it to a reference-to-const. Obviously, you need to have a public copy constructor for that.

I really fail to see the merit in this rule. It seems that every available C++ compiler does not create an extra temporary object here and some of these compilers don’t even bother to report an error in this situation (g++ version 3.4.5 accepts the above code).

Fortunately, the upcoming version of the C++ standard removes the CopyConstructible requirement for reference binding. It makes the code above well-formed.

Source: this usenet thread

– P

Books, Books, Books (on C++)

I already said it once in another post but I think it deserves to be mentioned again: Don’t underestimate the usefulness of good books about C++! Prefer buying a good book over searching the internet for tutorials, examples, explanations if you want to learn the language and/or learn about useful idioms, guidelines, etc…

I recently added two other books to my personal library: “Effective C++” and “C++ Coding Standards”. It took me only 3 weeks to finish both books. That means they were interesting and insightful. 🙂

Now, it’s these four C++ books that are in my posession:

• The C++ Programming Language (Special Edition) by Bjarne Stroustrup
• Modern C++ Design by Andrei Alexandrescu
• Effective C++ (Third Edition) by Scott Meyers
• C++ Coding Standards by Herb Sutter & Andrei Alexandrescu

I wouldn’t mention them here if I didn’t like them. 🙂

– P

C++0x: concepts & rvalue references — 2nd round

Last update: 2009-02-1

Concepts and rvalue references are two new features that are going to be included in the next official version of the C++ language with high probability. I’m not going to mention the basics behind those two features because it has been done before in other articles. Try this google video or this article for an introduction to concepts by Doug Gregor and this article for an introduction to rvalue references by Howard Hinnant et al.

I already wrote a post on concepts and rvalue references here which discussed some problems when concepts are combined with rvalue references. It turned out that David Abrahams and Doug Gregor were also aware of the first issue I addressed. They published an article one day before I wrote about it. In this post I’m going to address other arguments (consistency and intuitivity) for why I think their proposed resolution is a good idea and what other language modification can increase consistency. Before I go into the last bit I will shed some light on what function requirements actually mean and how they can be satisfied.

Update 2009-02-1:[ It turns out you can’t exprapolate the meaning of function requirements from the concept_map checking rules because they don’t cover all use cases in constrained contexts (see hole in concepts system). So, keep this in mind while reading the rest of this article.]

Writing portable C and C++ code

Width and value ranges of Integer types

C and C++ only specify minimum requirements regarding the width and value range of different integer types and how these are converted to each other. If you want to write portable code you should be aware of this. Check out the article Integer Types in C and C++.

C++0x: Interaction between rvalue references & concepts

Last update: 2008-12-08

I noticed some unfortunate gotchas when using two of the upcoming C++ features together: Rvalue references and concepts/templates. One of these problems can actually be seen in the currend draft of the future C++ specification. As far as I can tell, it looks like a subtle but nasty bug. Check out chapter 23.2.6 [vector, page 826]:

scope guards revisited [C++0x style]

If you havn’t heard about scope guards you might want to have a look at this ddj article. The idea of scope guards is to provide a convenient tool for resource management when exception safety is an issue. Of course you can always try to write little special-purpose classes and create instances on the stack so that some specific (“cleanup”) action is performed in the destructor. Sometimes it’s just tedious to have to write those special classes and you wish for a tool that lets you get away without them. That’s a situation where the scope guard idiom could help you.

C versus C++

I know that this is a sensitive subject that has been beaten to death already. Still, I’d like to share my opinion on this. Let me open with a quote by Bjarne Stroustrup about comparing programming languages which can be found in his FAQ:

Fun with C++ namespaces [sarcasm]

Last update: 2008-10-28.

I usually tend to defend C++ but name lookup is probably one of the most complicated things in C++ to wrap your head around. Namespaces are supposed to make your life easier. They provide means to group certain things together, to avoid name clashes between two parts of your program that might have been developed independently. Since typing fully qualified names is tedious people like to use short cuts: using directives and using declarations. So far so good. How well does this work together with generic programming?

Transition from Java to C++ — some insights

In this post I talk about my programming language transition from Java to C++ and my experiences so far.

Fast Inverse Square Root

The article “fast inverse sqrt” came to my attention. It shows a small function written in C which is amazingly fast and approximates sqrt(1/x) pretty well. Appearently it was used in the Quake source code to speed up vector normalizations. But how does it work? Also, can it be improved?

Optimal Integer Linear Prediction Coefficients

Most lossless audio codecs make use of linear prediction as a means to decorrelate signals. Since encoder and decoder need to work with the same set of prediction coefficients they either have to be chosen by the encoder and included in the compressed data stream before they are used (forward adaptive) or there must be a deterministic algorithm to compute these coefficients based on previous data (backward adaptive). FLAC and TAK are two examples of codecs that use forward adaptive linear prediction. This is the case I’m dealing with in this article.