The Artima Developer Community
The C++ Source | C++ Community News | Discuss | Print | Email | First Page | Previous | Next
Sponsored Link

The C++ Source
Backyard Hotrodding C++
by Walter Bright
May 23, 2006

Page 1 of 3  >>

Advertisement

Summary
Ever feel the need for speed? Real speed? If you're careful, you can get it without making a mess of things.
Attend a seminar or read any book or article on C++, and there will be presented more or less the "correct" way to write C++ programs (or at least the way the author feels is correct). Certain practices are deprecated as "buggy", "sloppy", "non-portable", "undefined", "illegal" or just plain "bad." We are exhorted not to do such things, at the risk of bugs, being fired, or the ridicule of our peers.

But to take an analogy from drag racing, sometime what matters is getting across the finish line the fastest. How you did it does not matter. Certainly, everything and anything has been tried by backyard hotrodders.

What are some things that can be done with C++, that a good backyard hotrodder with greasy overalls and a pack of cigs rolled in his shirtsleeve would do, to get a program speeding over the finish line first?

The rules of this game are simple—to be a backyard C++ hotrodding modification, it's got to make the program faster than the "correct" way.

Warning: use of these techniques is rumored to be illegal in at least 5 states. They may cause you to be fired. C++ gurus will heap contempt upon your head. You'll get an "F" from your professor. Your warranty will be voided.

So let's pop the hood and slip that bottle of nitrous in.

Pointer Hydration

Let's say we have a large, in-memory data structure. We'd like to save this data structure into a disk file, and in some other invocation of the program, read it back in and reconstitute the data structure.

The proper way to do this is to serialize the data structure, object by object, into some disk friendly format. The format is then read, parsed, and object by object, it gets recreated back in memory. Each object needs a serialize function, where one must figure out how to represent each member on disk, and a constructor that can build a replica of that object from the serialized data. When the data structure is non-trivial, with cycles, pointers, shared objects, etc., this is not a simple task. Furthermore, it is inherently slow. Each object must be broken down into its serial representation, and when reconstituting, each object must be allocated, constructed, and put back together.

But the data structure is already in memory, in a sequence of bytes. Couldn't that just be copied to disk, and read back in again? Yes, if we're willing to step outside of defined behavior.

The first thing to do is organize the data structure so it is entirely contained within a known block or sequence of blocks of memory. This means it may not contain any pointers or references to objects outside of itself. That also means no references to string literals, which are stored in the static program data, or any other static data.

Next, create a custom allocator/deallocator for the objects that go into the data structure, so that they are allocated within a known block or sequence of blocks, and not mixed up with other allocations that are not to be saved.

So, those blocks can then just be rolled out directly into disk files, and rolled back in. Right? Nope, because there are pointers. When it's rolled back in, it's probably not going to wind up at the same address, and the pointers will all be pointing to the wrong place.

We need a way to dehydrate the pointers when writing the blocks to disk, and hydrate them (just add water!) when reading a block back in, so they become real pointers again. This can be done by walking the data structure, and for each pointer in each object, convert that pointer to an address to an offset from the start of the block. Each class gets a dehydrate function, which handles all the pointers in its objects.

But there's a problem. If the data structure is cyclic, or has multiple pointers to the same object, we need a way to determine if a pointer has been dehydrated already or not. Just comparing the pointer value to see what range it lies in is not enough, as an offset into the block(s) may overlap the physical addresses the block is mapped into.

The solution lies in noticing that allocators typically allocate data that is aligned on 2 or 4 byte boundaries (and since we're writing custom allocator for this, we can ensure this property). That means, for a valid pointer, the least significant bit will always be 0. We can then define a dehydrated pointer as being odd, and a hydrated pointer as being 1. Dehydrating a pointer then becomes:

void ptr_dehydrate(void **p)
{
    if (*p)
       *(long *)p |= 1;
}
and hydrating it becomes:
int isdehydrated(void *p)
{
    return ((long)p & 1) != 0;
}

void ptr_hydrate(void **p)
{
    if (isdehydrated(*p))
       *(char **)p -= ptr_adjust;
}
and for a class:
class Foo
{
    void *p;
    Bar *o;

    virtual void dehydrate()
    {
        ptr_dehydrate(&p);
        if (o && !isdehydrated(o))
        {
            o->dehydrate();
            ptr_dehydrate(&o); 
        }
    }

    virtual void hydrate()
    {
        ptr_hydrate(&p);
        if (isdehydrated(o))
        {
            o->hydrate();
            ptr_hydrate(&o);
        }
    }
}
In practice, this works out really fast. But since it is "bad" C++ code, there are some problem areas that must be avoided or accounted for:

Page 1 of 3  >>

The C++ Source | C++ Community News | Discuss | Print | Email | First Page | Previous | Next

Sponsored Links



Google
  Web Artima.com   
Copyright © 1996-2014 Artima, Inc. All Rights Reserved. - Privacy Policy - Terms of Use - Advertise with Us