DCT: D compiler as a collection of libraries

[deadalnix]

Le 14/05/2012 17:00, Roman D. Boiko a écrit :
> 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.
>

Why is this a benefice ?

> * 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)
>

I'm pretty sure that D's token will not change that much. If the need 
isn't identified right know, I'd advocate for YAGNI.

> * 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
>

Yes but now you add pressure on the GC and add indirections. I'm not 
sure it worth it. It seems to me like a premature optimization.

> 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?

You are over engineering the whole stuff.