Memory allocation for a variant-typed token

Question

I am making an interpreter for a custom programming language (concatenative, soft-typed) and for that purpose I have a central datatype Token. A Token can be of one of the many different types, either of scalar ones or vector ones. To minimize the amount of memory, I used a union first but then I could only use plain-old data structures in the union, so I resorted to a struct with all the fields (long asInteger;, boost::shared_ptr<std::string> asString, ...). That was of course a bad idea from a memory consumption viewpoint but it got the job done.

The project has grown quite a bit since the original formulation and is now nearing 5000 lines altogether (mainly consisting of various functions that are built in the interpreter). Since the Token datatype was almost 100 bytes long (making an array of 1,000,000 integers almost 100 megabytes for example), the original formulation showed massively inadequate. Today I revamped the implementation to dynamically allocate the memory needed for each element with copy semantics so that I got something similar to the union if I could use it with classes.

This is the new class definition:

typedef struct _st_VariableData {
  char name[32];
  Context *context;
  vector<long> index;
} VariableData;

typedef struct _st_FuncCallData {
  char asFunctionName[32];
} FuncCallData;

// Opaque pointer type
typedef struct _st_HandleData {
  void * ptr;
  long size;
} HandleData;

class Token {
protected:
    TokenType tokenType_;

    template<class T>
    inline void copyToken(void * src, void * dst)
    {
      *static_cast<T*>(dst) = 
          *static_cast<T*>(src);
    };

    template<class T>
    inline void deleteValue()
    {
      delete static_cast<T*>(data);
    };

    void deleteData()
    {
        switch (tokenType_)
        {
            case T_OPERATOR:  deleteValue<OperatorType>(); break; 
            case T_FUNCCALL:  deleteValue<FuncCallData>(); break; 
            case T_VARIABLE:  deleteValue<VariableData>(); break; 
            case T_INTEGER:   deleteValue<long>(); break; 
            case T_BOOL:      deleteValue<bool>(); break; 
            case T_FLOAT:     deleteValue<double>(); break;
            case T_STRING:    deleteValue<boost::shared_ptr<std::string>>(); break; 
            case T_CODEBLOCK:  
            case T_ARRAY:     deleteValue<boost::shared_ptr<std::vector<Token>>>(); break;
            case T_HANDLE:    deleteValue<HandleData>(); break;
            default: ;
        }
    }

    void allocate(const TokenType tokenType)
    {       
        switch (tokenType)
        {
            case T_OPERATOR:  data = new OperatorType; break; 
            case T_FUNCCALL:  data = new FuncCallData; break; 
            case T_VARIABLE:  data = new VariableData; break; 
            case T_INTEGER:   data = new long; break; 
            case T_BOOL:      data = new bool;  break; 
            case T_FLOAT:     data = new double; break;
            case T_STRING:    data = new boost::shared_ptr<std::string>; break; 
            case T_CODEBLOCK:  
            case T_ARRAY:     data = new boost::shared_ptr<std::vector<Token>>; break;
            case T_HANDLE:    data = new HandleData; break;
            default: data = NULL;
        }     
    };

    void * data;

public:
    char * fileName;
    int lineNum;

    const TokenType type()
    {       
        return tokenType_;
    };

    const TokenType type() const
    {       
        return tokenType_;
    };

    void set_type(const TokenType tokenType)
    {
        deleteData();
        tokenType_ = tokenType;
        allocate(tokenType);
    };

    Token() : tokenType_ (T_EMPTY) { data = NULL; }; 

    Token(const TokenType tokenType) : tokenType_ (tokenType)  
    {
        allocate(tokenType);
    };

    Token(const Token& old_token)  
    {
        fileName = old_token.fileName;
        lineNum  = old_token.lineNum;
        tokenType_ = old_token.tokenType_;
        allocate(old_token.tokenType_);
        switch (old_token.tokenType_)
        {
            case T_OPERATOR:  copyToken<OperatorType>(old_token.data, data); break; 
            case T_FUNCCALL:  copyToken<FuncCallData>(old_token.data, data); break; 
            case T_VARIABLE:  copyToken<VariableData>(old_token.data, data); break; 
            case T_INTEGER:   copyToken<long>(old_token.data, data); break; 
            case T_BOOL:      copyToken<bool>(old_token.data, data); break; 
            case T_FLOAT:     copyToken<double>(old_token.data, data); break;
            case T_STRING:    copyToken<boost::shared_ptr<std::string>>(old_token.data, data); break; 
            case T_CODEBLOCK:  
            case T_ARRAY:     copyToken<boost::shared_ptr<std::vector<Token>>>(old_token.data, data); break;
            case T_HANDLE:    copyToken<HandleData>(old_token.data, data); break;
            default: ;
        }       
    };

    template<class T>
    T& retreive()
    {
        return *static_cast<T*>(data);
    };

    template<class T>
    const T& retreive() const
    {
        return *static_cast<T*>(data);
    };

    void operator=(const Token &rhs) 
    {
        fileName = rhs.fileName;
        lineNum  = rhs.lineNum;
        set_type(rhs.tokenType_);
        switch (rhs.tokenType_)
        {
            case T_OPERATOR:  copyToken<OperatorType>(rhs.data, data); break; 
            case T_FUNCCALL:  copyToken<FuncCallData>(rhs.data, data); break; 
            case T_VARIABLE:  copyToken<VariableData>(rhs.data, data); break; 
            case T_INTEGER:   copyToken<long>(rhs.data, data); break; 
            case T_BOOL:      copyToken<bool>(rhs.data, data); break; 
            case T_FLOAT:     copyToken<double>(rhs.data, data); break;
            case T_STRING:    copyToken<boost::shared_ptr<std::string>>(rhs.data, data); break; 
            case T_CODEBLOCK:  
            case T_ARRAY:     copyToken<boost::shared_ptr<std::vector<Token>>>(rhs.data, data); break;
            case T_HANDLE:    copyToken<HandleData>(rhs.data, data); break;
            default: ;
        }       
    };

    ~Token()
    {
       deleteData();
    };
};

Now the above code works, but is terribly slow (200% slower than the previous implementation). A profiler shows that almost half of the execution time is spent on new and free(). I have tried using placement new syntax with a char data[50] and that speeds it up a lot but still not as fast as original (about 20% slower).

I am quite new to C++ (this is my first large project) so please excuse me if I have made some blatant mistakes arising from misconceptions. Generally I would like to minimize the memory allocation cost while also minimizing the required memory.

If this is usually done a whole different way, please advise me how to do it. The entire source code (bleeding-edge without build automation) is available here.

Thank you for help!

Answer 1

This problem is solved very elegantly by Boost.Variant.

Not only is it easier and more efficient, it’s also completely type safe (meaning, you cannot accidentally retrieve a wrong type) when using the boost::apply_visitor template function to access data.

Furthermore, I’d separate an object and its token representation. Objects can be the result of a computation (1 + 1, say) but this has no representation in the source file, right? This way, you can save storing he line number for tokens which aren’t in a file. I’d also refrain from storing the filename for each token – wouldn’t it be enough to store that once?

With that in mind, a token can be represented by the following variant:

struct token_array;

typedef boost::variant<
    OperatorType,
    FuncCallData,
    VariableData,
    long,
    …,
    boost::recursive_wrapper<token_array>
> token;

struct token_array {
    std::vector<token> tokens;
};

Note that you no longer need to take care of (de)allocation and copying yourself.

---

Apart from that, your code features a few peculiarities from C:

typedef struct _st_FuncCallData {
  char asFunctionName[32];
} FuncCallData;

First of all, there is no need to do typedef struct … { } …; in C++. Second of all, the struct name is invalid: in the global namespace, names starting with an underscore are reserved to the implementation in C++.

The following is completely equivalent:

struct FuncCallData {
    char asFunctionName[32];
};

I’d also question the usefulness of using a fixed-size char array here instead of just a std::string but oh well.