Would using a virtual destructor make non-virtual functions do v-table lookups?

Only virtual functions require dynamic dispatch (and hence vtable lookups) and not even in all cases. If the compiler is able to determine at compile time what is the final overrider for a method call, it can elide performing the dispatch at runtime. User code can also disable the dynamic dispatch if it so desires:

struct base {
   virtual void foo() const { std::cout << "base" << std::endl; }
   void bar() const { std::cout << "bar" << std::endl; }
};
struct derived : base {
   virtual void foo() const { std::cout << "derived" << std::endl; }
};
void test( base const & b ) {
   b.foo();      // requires runtime dispatch, the type of the referred 
                 // object is unknown at compile time.
   b.base::foo();// runtime dispatch manually disabled: output will be "base"
   b.bar();      // non-virtual, no runtime dispatch
}
int main() {
   derived d;
   d.foo();      // the type of the object is known, the compiler can substitute
                 // the call with d.derived::foo()
   test( d );
}

On whether you should provide virtual destructors in all cases of inheritance, the answer is no, not necessarily. The virtual destructor is required only if code deletes objects of the derived type held through pointers to the base type. The common rule is that you should

• provide a public virtual destructor or a protected non-virtual destructor

The second part of the rule ensures that user code cannot delete your object through a pointer to the base, and this implies that the destructor need not be virtual. The advantage is that if your class does not contain any virtual method, this will not change any of the properties of your class --the memory layout of the class changes when the first virtual method is added-- and you will save the vtable pointer in each instance. From the two reasons, the first being the important one.

struct base1 {};
struct base2 {
   virtual ~base2() {} 
};
struct base3 {
protected:
   ~base3() {}
};
typedef base1 base;
struct derived : base { int x; };
struct other { int y; };
int main() {
   std::auto_ptr<derived> d( new derived() ); // ok: deleting at the right level
   std::auto_ptr<base> b( new derived() );    // error: deleting through a base 
                                              // pointer with non-virtual destructor
}

The problem in the last line of main can be resolved in two different ways. If the typedef is changed to base1 then the destructor will correctly be dispatched to the derived object and the code will not cause undefined behavior. The cost is that derived now requires a virtual table and each instance requires a pointer. More importantly, derived is no longer layout compatible with other. The other solution is changing the typedef to base3, in which case the problem is solved by having the compiler yell at that line. The shortcoming is that you cannot delete through pointers to base, the advantage is that the compiler can statically ensure that there will be no undefined behavior.

In the particular case of the CRTP pattern (excuse the redundant pattern), most authors do not even care to make the destructor protected, as the intention is not to hold objects of the derived type by references to the base (templated) type. To be in the safe side, they should mark the destructor as protected, but that is rarely an issue.

Very unlikely indeed. There's nothing in the standard to stop compilers doing whole classes of stupidly inefficient things, but a non-virtual call is still a non-virtual call, regardless of whether the class has virtual functions too. It has to call the version of the function corresponding to the static type, not the dynamic type:

struct Foo {
    void foo() { std::cout << "Foo\n"; }
    virtual void virtfoo() { std::cout << "Foo\n"; }
};
struct Bar : public Foo {
    void foo() { std::cout << "Bar\n"; }
    void virtfoo() { std::cout << "Bar\n"; }
};

int main() {
    Bar b;
    Foo *pf = &b;  // static type of *pf is Foo, dynamic type is Bar
    pf->foo();     // MUST print "Foo"
    pf->virtfoo(); // MUST print "Bar"
}

So there's absolutely no need for the implementation to put non-virtual functions in the vtable, and indeed in the vtable for Bar you'd need two different slots in this example for Foo::foo() and Bar::foo(). That means it would be a special-case use of the vtable even if the implementation wanted to do it. In practice it doesn't want to do it, it wouldn't make sense to do it, don't worry about it.

CRTP base classes really ought to have destructors that are non-virtual and protected.

A virtual destructor is required if the user of the class might take a pointer to the object, cast it to the base class pointer type, then delete it. A virtual destructor means this will work. A protected destructor in the base class stops them trying it (the delete won't compile since there's no accessible destructor). So either one of virtual or protected solves the problem of the user accidentally provoking undefined behavior.

See guideline #4 here, and note that "recently" in this article means nearly 10 years ago:

http://www.gotw.ca/publications/mill18.htm

No user will create a Base<Derived> object of their own, that isn't a Derived object, since that's not what the CRTP base class is for. They just don't need to be able to access the destructor - so you can leave it out of the public interface, or to save a line of code you can leave it public and rely on the user not doing something silly.

The reason it's undesirable for it to be virtual, given that it doesn't need to be, is just that there's no point giving a class virtual functions if it doesn't need them. Some day it might cost something, in terms of object size, code complexity or even (unlikely) speed, so it's a premature pessimization to make things virtual always. The preferred approach among the kind of C++ programmer who uses CRTP, is to be absolutely clear what classes are for, whether they are designed to be base classes at all, and if so whether they are designed to be used as polymorphic bases. CRTP base classes aren't.

The reason that the user has no business casting to the CRTP base class, even if it's public, is that it doesn't really provide a "better" interface. The CRTP base class depends on the derived class, so it's not as if you're switching to a more general interface if you cast Derived* to Base<Derived>*. No other class will ever have Base<Derived> as a base class, unless it also has Derived as a base class. It's just not useful as a polymorphic base, so don't make it one.

The answer to your first question: No. Only calls to virtual functions will cause an indirection via the virtual table at runtime.

The answer to your second question: The Curiously recurring template pattern is commonly implemented using private inheritance. You don't model an 'IS-A' relationship and hence you don't pass around pointers to the base class.

For instance, in

template <class Derived> class Base
{
};

class Derived : Base<Derived>
{
};

You don't have code which takes a Base<Derived>* and then goes on to call delete on it. So you never attempt to delete an object of a derived class through a pointer to the base class. Hence, the destructor doesn't need to be virtual.