DCT: D compiler as a collection of libraries

[Roman D. Boiko]

On Saturday, 12 May 2012 at 03:32:20 UTC, Ary Manzana wrote:
> I think you are wasting much more memory and performance by 
> storing all the tokens in the lexer.
>
> Imagine I want to implement a simple syntax highlighter: just 
> highlight keywords. How can I tell DCT to *not* store all 
> tokens because I need each one in turn? And since I'll be 
> highlighting in the editor I will need column and line 
> information. That means I'll have to do that O(log(n)) 
> operation for every token.
>
> So you see, for the simplest use case of a lexer the 
> performance of DCT is awful.
>
> Now imagine I want to build an AST. Again, I consume the tokens 
> one by one, probably peeking in some cases. If I want to store 
> line and column information I just copy them to the AST. You 
> say the tokens are discarded but their data is not, and that's 
> why their data is usually copied.

Currently I think about making token a class instead of struct.

A token (from 
https://github.com/roman-d-boiko/dct/blob/master/fe/core.d) is:

// Represents lexed token
struct Token
{
     size_t startIndex; // position of the first code unit in the 
source string
     string spelling; // characters from which this token has been 
lexed
     TokenKind kind; // enum; each keyword and operator, have a 
dedicated kind
     ubyte annotations; // meta information like whether a token 
is valid, or an integer literal is signed, long, hexadecimal, etc.
}

Making it a class would give several benefits:

* allow not to worry about allocating a big array of tokens. 
E.g., on 64-bit OS the largest module in Phobos (IIRC, the 
std.datetime) consumes 13.5MB in an array of almost 500K tokens. 
It would require 4 times smaller chunk of contiguous memory if it 
was an array of class objects, because each would consume only 8 
bytes instead of 32.

* allow subclassing, for example, for storing strongly typed 
literal values; this flexibility could also facilitate future 
extensibility (but it's difficult to predict which kind of 
extension may be needed)

* there would be no need to copy data from tokens into AST, 
passing an object would be enough (again, copy 8 instead of 32 
bytes); the same applies to passing into methods - no need to 
pass by ref to minimise overhead

It would incur some additional memory overhead (at least 8 bytes 
per token), but that's hardly significant. Also there is 
additional price for accessing token members because of 
indirection, and, possibly, worse cache friendliness (token 
instances may be allocated anywhere in memory, not close to each 
other).

These considerations are mostly about performance. I think there 
is also some impact on design, but couldn't find anything 
significant (given that currently I see a token as merely a 
datastructure without associated behavior).

Could anybody suggest other pros and cons? Which option would you 
choose?