3 ms·

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

by fsloth 5y ago

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.

jstimpfle 5y ago
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 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".

3 ms·

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

by fsloth 5y ago

jstimpfle 5y ago
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 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".