Being that tokens are the leaves of the AST, there are a lot of them and they can take a lot of space. To save memory it is a good idea to store only a file location instead of a full token. Whenever token information is needed, just lex again to get the full token, starting at the file location. This works only for languages with a context-free lexical syntax, of course (and not entirely sure "context-free" is the right term here but you get what I mean).
Storing row/column in file location data is wasteful - just a file offset should be enough. Whenever the row/column coordinates are needed (normally only in user messages) they can be quickly recomputed.
In effect, parsed tokens can be stored as just an offset - a 4 or 8 byte integer.
This sounds like premature optimization to me (I know, that phrase gets used a lot lately). As with all optimizations it probably makes sense to not do it and keep your code highly readable until the point where you've profiled issues at this level.
And definitely my focus in writing a post like this is to be as explicit as reasonable to serve as the best educational reference.
I also haven't seen real world compilers do what you say (thinking V8, CPython, other mainstream ones) but I'll keep an eye out for it now.
Is this really the right space to optimize? Having the relevant data on hand in tight array is generally much faster than having to fetch and compute something from somewhere else?
In general it is of course better to store an index to a data where it's needed rather than a copy of the data.
I've seen other experienced people do this, like Jonathan Blow (Jai) and Per Vognsen (bitwise) I believe. I recall measuring a large space overhead from tokens myself when working on my toy compiler.
Token data will not typically be needed a lot: The token kind (integer-literal, plus-operator, open-paren etc.) at exactly one point in the parsing phase and possibly in the type checking phase but you could have a separate "literal expression" kind for that. Binary payloads (string bytes, floating point value etc.) will be needed in the constant phase for literal tokens. I wouldn't expect that a little optimization here is a difficult tradeoff to make - neither with regards to speed nor code complexity.
Update, here is bitwise's code. It looks very good to me from a glance: https://github.com/pervognsen/bitwise/blob/master/ion/lex.c . I think thinking about this gives interesting insights, and the token struct approach is an illustration of how "object-oriented" approaches can go wrong. The concept of a token exists merely at the syntactical level, and the token kind controls the code flow of a recursive descent parser, but I don't see any good reasons to store a token represented as a tagged union. Punctuation tokens are completely ephemeral, and constant data, literal kinds, operator kinds etc. all should better go to very distinct places in the data store that have no resemblance to "token objects".
It might be worth storing this data separately, to improve cache usage, but my experience is on any modern machine the amount of space taken by parsed code / ASTs is small enough to not care about, unless you do something like C++ where you "reparse the world" for every tiny file (due to header includes)
Maybe it's only necessary for serious compilers. Let's say 10 tokens / line avg., 40 bytes / token (but a naive token struct could easily be 100s of bytes), then we're in the region of 100s to 1000s of bytes per line. Now let's say compiling 100K lines would not be unheard of, and for benchmarks you want to push the millions. We're getting into regions where tokens alone can fill a computer's memory. If there is an easy to make and effective optimization, I'm all for it :-)
Comments
Being that tokens are the leaves of the AST, there are a lot of them and they can take a lot of space. To save memory it is a good idea to store only a file location instead of a full token. Whenever token information is needed, just lex again to get the full token, starting at the file location. This works only for languages with a context-free lexical syntax, of course (and not entirely sure "context-free" is the right term here but you get what I mean).
Storing row/column in file location data is wasteful - just a file offset should be enough. Whenever the row/column coordinates are needed (normally only in user messages) they can be quickly recomputed.
In effect, parsed tokens can be stored as just an offset - a 4 or 8 byte integer.
This sounds like premature optimization to me (I know, that phrase gets used a lot lately). As with all optimizations it probably makes sense to not do it and keep your code highly readable until the point where you've profiled issues at this level.
And definitely my focus in writing a post like this is to be as explicit as reasonable to serve as the best educational reference.
I also haven't seen real world compilers do what you say (thinking V8, CPython, other mainstream ones) but I'll keep an eye out for it now.
Is this really the right space to optimize? Having the relevant data on hand in tight array is generally much faster than having to fetch and compute something from somewhere else?
In general it is of course better to store an index to a data where it's needed rather than a copy of the data.
I've seen other experienced people do this, like Jonathan Blow (Jai) and Per Vognsen (bitwise) I believe. I recall measuring a large space overhead from tokens myself when working on my toy compiler.
Token data will not typically be needed a lot: The token kind (integer-literal, plus-operator, open-paren etc.) at exactly one point in the parsing phase and possibly in the type checking phase but you could have a separate "literal expression" kind for that. Binary payloads (string bytes, floating point value etc.) will be needed in the constant phase for literal tokens. I wouldn't expect that a little optimization here is a difficult tradeoff to make - neither with regards to speed nor code complexity.
Update, here is bitwise's code. It looks very good to me from a glance: https://github.com/pervognsen/bitwise/blob/master/ion/lex.c . I think thinking about this gives interesting insights, and the token struct approach is an illustration of how "object-oriented" approaches can go wrong. The concept of a token exists merely at the syntactical level, and the token kind controls the code flow of a recursive descent parser, but I don't see any good reasons to store a token represented as a tagged union. Punctuation tokens are completely ephemeral, and constant data, literal kinds, operator kinds etc. all should better go to very distinct places in the data store that have no resemblance to "token objects".
It might be worth storing this data separately, to improve cache usage, but my experience is on any modern machine the amount of space taken by parsed code / ASTs is small enough to not care about, unless you do something like C++ where you "reparse the world" for every tiny file (due to header includes)
Maybe it's only necessary for serious compilers. Let's say 10 tokens / line avg., 40 bytes / token (but a naive token struct could easily be 100s of bytes), then we're in the region of 100s to 1000s of bytes per line. Now let's say compiling 100K lines would not be unheard of, and for benchmarks you want to push the millions. We're getting into regions where tokens alone can fill a computer's memory. If there is an easy to make and effective optimization, I'm all for it :-)