Wednesday, August 29, 2012

C++ dynamic arrays

I've seen dozens (at least) of questions and proposed answers about how to create a dynamic array in C++. The typical reply recommends using the array form of the `new` operator to allocate space, something on this order (but usually less complete):


template
class dynamic_array {
    T *data;
    size_t size;
public:
    dynamic_array() :data(0), size(0) {}

    dynamic_array(T *init, size_t i_size) :size(i_size) {
        data = new T[size];
        for (size_t i=0; i<size; i++)
            data[i] = init[i];
   }

    bool add(T const &new_item) {
        T *temp = new T[size+1];
        for (size_t i=0; i<size; i++)
            temp[i] = data[i];
        ++size;
        delete [] data;
        data = temp;
    }
     
    T &operator[](size_t index) {
         assert(index < size);
         return data[index];
    }
    // We also want a const version of operator[].
    // We also probably want something like get()
    // in std::vector, that throws if index is out of bounds.

    size_t get_size() { return size; }

    void clear() { size=0; delete [] data; }

    ~dynamic_array() { delete [] data; }
};



Now, it's certainly true that you could do worse than this. I believe it manages memory correctly (doesn't leak memory or create dangling pointers), and it is dynamic (to some degree -- it allows adding, but not currently removing, elements dynamically). While it's not currently written to be exception safe, that's mostly to keep it from getting too long -- making it exception safe wouldn't be particularly difficult.

It still has some pretty serious problems though. First of all, it requires that T be default constructible and assignable. Assignable isn't so bad (though in C++11, we'd prefer movable), but default constructible is kind of a pain, especially since we never actually *use* any default objects -- but when we expand the allocation, we have no real choice but to default construct the objects, then assign each value from the old array into the new one. That can be a pretty serious burden if creating a default object is slow, and worse still if assigning objects is slow as well. Since it's a template, we don't know much about T. Either or both might be true.

That points to a much bigger problem: adding an item to the array is slower than we'd like, and the bigger it gets, the slower adding items gets. In computer science terms, adding a single item has complexity that's linear on the current size of the array.

Unfortunately, we can't just do a minor rewrite inside of add() to improve the situation. In fact, the basic premise of how this dynamic array works turns out to be wrong. The only way to fix the biggest problem is to start over with something that works a bit differently from the beginning.

Our big problem here is that when/if we use `new whatever[size]`, we not only get enough space to store the specified number of objects, but code is inserted to create that number of objects in the storage. Generally speaking, we don't want that. Unless we change the interface at least a little bit, there's never a circumstance in which we really want objects in that memory. Even if they're created, immediately after allocating those objects, we're going to assign some other object to that position anyway. We'd really prefer to copy construct the new objects from the old objects (or, in C++11, move-construct). This way a new object is created with the correct value instead of being created with a value we know is wrong, then immediately assigning the correct value to the new object.

We'd also prefer to avoid re-allocating space every time we add a new item. We really want to allocate a chunk of raw memory, turn that raw memory into new objects as they're added, and only allocate more space once in a while, when our memory is all used up.

Using new T[size] won't let us do either of those though. Instead, we need to use something (usually operator new, but malloc would also work) that lets us allocate raw memory, then use placement new to create objects in that raw memory.


template
class dynamic_array {
    T *data;
    size_t allocated;
size_t in_use;

size_t round_up(size_t input) {
size_t ret = 1;
while (ret < input)
ret <<= 1;
return ret;
}

void alloc(T *init, size_t current_size, size_t new_size) {
char *temp = (char *)operator new(new_size * sizeof(T));
allocated = new_size;
for (size_t i=0; i<current_size; i++)
new(temp+i*sizeof(T)) T(init[i]);
in_use = current_size;
data = (T *)temp;
}

void destroy(size_t b, size_t e) {
for ( ;b!=e; ++b)
data[b].~T();
}

public:

    dynamic_array() :data(0), allocated(0), in_use(0) {
alloc(0, 0, 10);
}

    dynamic_array(T *init, size_t i_size) {
alloc(init, i_size, round_up(i_size));
}

    void add(T new_item) {
if (in_use == allocated)
alloc(data, allocated, allocated * 3 / 2);
new ((char *)data + in_use++ * sizeof(T)) T(new_item);
    }

    ~dynamic_array() {
destroy(0, in_use);
operator delete(data);
}

    T &operator[](size_t index) {
        assert(index < in_use);
        return data[index];
    }

    size_t size() { return in_use; }

    void clear() {
destroy(0, in_use);
in_use = 0;
}
};

This is starting to run pretty long, so I'll leave further embellishment of this class for a later post. This is still quite a ways short of what std::vector already provides though -- thus the standard advice to just use a standard container if at all possible. Even for something as simple as a dynamic array, the amount of code involved becomes fairly substantial. For a more complex container like std::set or std::map, the savings is greater still.

Sunday, August 26, 2012

Herb's wrong, I'm right, and here's why.

Microsoft's MSDN Channel 9 recently released a video of Herb Sutter, Andrei Alexandrescu, and Scott Meyers from C++ and Beyond 2012. In this video Herb (in particular) argues that further support for meta-programming should not be added to C++.

He points out (quite rightly) that meta-programming is basically used to add features to the language. He argues that rather than supporting meta-programming, we should look at what features meta-programming is used to implement, and add those features directly to the language itself.

In my opinion, there is really only one reasonable answer to this: wrong!

This is utterly and absolutely wrong for a number of reasons, most of which (interestingly enough) have been expounded many times before. One of the mantras of C++ development for years has been that the committee does not and cannot know all the purposes to which the language might be put. Rather than adding features to the language specifically for every individual purpose and each end user, there has been a concentration on adding features to support things like writing libraries so that adding a relatively small number of features can support a wide variety of uses.

Trying to look at all uses of meta-programming and find the features being created with it, then trying to add those features to the language would be a 180 degree reversal of this decision. The problems already cited would become all too real and all too problematic essentially immediately.

Consider what would happen if I wanted to write a library using features not currently included in the base language. My choices would be to implement that code using meta-programming, or else petition the committee to please, please consider my proposal for a new language feature. For the sake of argument, let's assume that the C++ committee starts to produce revisions twice as fast as they have in the past -- or than essentially any other ISO standard committee for any other programming language has either -- and produces an update every five years instead of roughly once every ten years.

That means, on average, the programmer has to wait 2.5 years before he can even get started on his library. Given that the standard is typically frozen for a year or so before being approved, it's really a bit longer than that, but let's just leave it at 2.5 for the sake of argument. I hope I don't have to spend any time convincing anybody that a two and a half year delay in getting started would be unacceptable for many projects.

That's probably the least of the problems though. Much worse is the fact that accepting any more than a minuscule number of such proposals would quickly lead to C++ becoming substantially larger and more complex. Virtually everybody agrees that C++ is already larger and more complex than anybody would like, and going this direction would unavoidably lead to amplifying that problem.

I do agree with Herb that the current meta-programming facilities have serious problems. The code itself, the compile times, and especially the error messages can all be truly horrific. More importantly, these aren't just remote possibilities; they happen on a regular and routine basis.

That does not, however, mean that template meta-programming in general is a problem and should be avoided. It means that the current facility has problems, most of which stem from the fact that its intent was never to support meta-programming at all.

These problems should not lead us to conclude that meta-programming is evil in general and should, therefore, simply be avoided entirely. They should convince us that the current meta-programming facilities are inadequate and in need of replacement. What we should be doing now is looking for a simple, small, relatively easy to understand set of features that will support meta-programming more sanely. I won't try to propound here exactly what features are necessary, much less what form those features should take. This is, however a basic engineering problem. It's the kind of thing that's been solved before, and can be solved again -- and while the result undoubtedly won't be perfect, it will be good enough to fix the problems that are now obvious (and probably quite a few nobody's thought of yet).

Early in the history of programming, many thought of it as a priesthood. It was liberated largely by improvements in tools and education. At least in my opinion, the situation here is similar.
I guess if I were a great leader of men, at this point I'd come up with some ringing phrases about "when faced with such a challenge, do we shrink in fear, or do we rise up and vanquish the foes of free computing everywhere?"

Since I'm an engineer, though, I'll simply reiterate that this type of problem has been met and overcome before, and can be again. What's necessary isn't vilifying template meta-programming or its current users, but to make sound engineering decisions to fix a problem in the most reasonable fashion possible to make meta-programming dependable, accessible, and understandable, so it becomes the tool that can fulfill the promise shown by the current uses of template meta-programming.