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!