5 ms·

The best "look up" of tokens is to just lex them given an offset into the source file. No need to have a permanent token storage. It's a waste of space.

dataflow 4y ago
That's not as cache-friendly. The "best" way in terms of performance is probably to intern them adjacently in a single string, then have offsets into that.
- jstimpfle 4y ago
  That would be a consideration if you'd have to frequently scan the tokens linearly. But I can't think of a scenario where you'd want to do that at all. And if you've got such a situation, I would say that indexing into the original file contents is pretty close to optimal in terms of cache. Because tokens are already extremely close in the source code, optimizing for a source where they are spaced wide out seems silly. In many scenarios you need token spans / token strings only for diagnostics, in other words you almost never need them. When any individual data item is rarely looked up, being economical about memory footprint will in fact improve your overall cache hit rate. You only want to store enough information to retrieve the tokens just in case, so storing file offsets is exactly the right call.
  - dataflow 4y ago
    > That would be a consideration if you'd have to frequently scan the tokens linearly. But I can't think of a scenario where you'd want to do that at all. Joining them has nothing to do with linear scanning. Binary search or anything else will still be cache friendlier by having them be adjacent rather than spread apart. There are also additional advantages I didn't mention. e.g., you can combine strings from multiple files (and throw away the files) without needing to track or care where they came from. They're not performance-related though. And no, I'm not saying you should do this everywhere. Use what makes sense for your situation.
    - jstimpfle 4y ago
      You still haven't explained what you want to do with the data, so suggesting any particular storage is pointless. I can't imagine why you'd want to binary search a set of tokens (or token strings for that matter), it seems kinda silly. A frequent application of search is binding identifiers to definitions by walking scope-chains, but that's something different than simply a list of tokens.
      - dataflow 4y ago
        I'm saying literally anything you want to do with them is faster due to cache locality if they're closer together than farther apart as with the file offset proposal.
        jstimpfle 4y ago
        Well you're clearly wrong and I've explained why.
        dataflow 4y ago
        I don't even see anywhere where what I wrote is wrong, let alone clearly so. The whole discussion was about string containers, how fast lookups are, etc. and I was talking about how anything you want to do with the strings is faster if they're closer together. I also said you shouldn't that if that doesn't make sense for your situation. Your "you're wrong" comment was that the program can end up slower when you collect the strings but don't use them... which was completely beside the point and ignored the actual point I was making. It was kind of strange too, given the parent you originally replied to said nothing about their use case, and apparently you just picked and assumed the only real use case for string lookups is diagnostic offsets.
        jstimpfle 4y ago
        You're making statements that are unspecific and generalizing ("anything you want to do"), while I've presented an explanation why the "cache-efficient" storage optimization may in fact be a pessimization for common token access patterns, because the cost of additional resource consumption can outweigh any marginal benefits this may have for access times of rarely used data. > The whole discussion was about string containers, how fast lookups are, etc No, it was about token storage. > Your "you're wrong" comment was that the program can end up slower when you collect the strings but don't use them No, it was assuming common access patterns of token data in parsers, which aren't "you don't use them" but "you rarely access them, likely only once when parsing but on rare occasion you have to refer back to specific tokens later".
vitus 4y ago
The less space-efficient but more cpu-efficient alternative is to store an offset and a length. Which is, in essence, a string_view.
- jstimpfle 4y ago
  Note that a string view only gives you the token text, not the token in general (like, most importantly, the token type, i.e. identifier, string literal, integer literal, keywords, etc). So the additional length information that's contained in the file doesn't help much, you'll have to lex again anyway, unless you're only interested in the text. Apart from that -- a string view is typically understood as being implemented using a pointer to the string buffer, which is something else -- a pointer is 64 bits instead of 32 bit (on most systems, of course). And it requires the source file to be cached in memory at a stable location, can't be serialized and deserialized, etc. etc. In short, it's the typical fashionable modern C++ approach that is also wrong.
  - sagarm 4y ago
    What would be the point of adding a string as int32 offset/size pair to the standard library? It would be meaningless without supporting infrastructure to link it to a backing buffer, and it can't represent strings over 4GB. If it's something that you can make work, declaring the typedef or struct is trivial. string_view is a useful general purpose tool that implements the std::string API for e.g. taking strings of various types in general purpose function signatures. Obviously it's not meant to be serialized and deserialized. It works well for its intended purpose. The two are not mutually exclusive: you could turn your 32-bit offset/length pair into a string_view to pass to functions that operate in the context of a single string.
    - jstimpfle 4y ago
      Where did I mention standard library? > It works well for its intended purpose. The intended purpose is quite general. Which admits other, better solutions in specific applications.

dataflow 4y ago

That's not as cache-friendly. The "best" way in terms of performance is probably to intern them adjacently in a single string, then have offsets into that.

jstimpfle 4y ago
That would be a consideration if you'd have to frequently scan the tokens linearly. But I can't think of a scenario where you'd want to do that at all. And if you've got such a situation, I would say that indexing into the original file contents is pretty close to optimal in terms of cache. Because tokens are already extremely close in the source code, optimizing for a source where they are spaced wide out seems silly. In many scenarios you need token spans / token strings only for diagnostics, in other words you almost never need them. When any individual data item is rarely looked up, being economical about memory footprint will in fact improve your overall cache hit rate. You only want to store enough information to retrieve the tokens just in case, so storing file offsets is exactly the right call.
- dataflow 4y ago
  > That would be a consideration if you'd have to frequently scan the tokens linearly. But I can't think of a scenario where you'd want to do that at all. Joining them has nothing to do with linear scanning. Binary search or anything else will still be cache friendlier by having them be adjacent rather than spread apart. There are also additional advantages I didn't mention. e.g., you can combine strings from multiple files (and throw away the files) without needing to track or care where they came from. They're not performance-related though. And no, I'm not saying you should do this everywhere. Use what makes sense for your situation.
  - jstimpfle 4y ago
    You still haven't explained what you want to do with the data, so suggesting any particular storage is pointless. I can't imagine why you'd want to binary search a set of tokens (or token strings for that matter), it seems kinda silly. A frequent application of search is binding identifiers to definitions by walking scope-chains, but that's something different than simply a list of tokens.
    - dataflow 4y ago
      I'm saying literally anything you want to do with them is faster due to cache locality if they're closer together than farther apart as with the file offset proposal.
      - jstimpfle 4y ago
        Well you're clearly wrong and I've explained why.
        dataflow 4y ago
        I don't even see anywhere where what I wrote is wrong, let alone clearly so. The whole discussion was about string containers, how fast lookups are, etc. and I was talking about how anything you want to do with the strings is faster if they're closer together. I also said you shouldn't that if that doesn't make sense for your situation. Your "you're wrong" comment was that the program can end up slower when you collect the strings but don't use them... which was completely beside the point and ignored the actual point I was making. It was kind of strange too, given the parent you originally replied to said nothing about their use case, and apparently you just picked and assumed the only real use case for string lookups is diagnostic offsets.
        jstimpfle 4y ago
        You're making statements that are unspecific and generalizing ("anything you want to do"), while I've presented an explanation why the "cache-efficient" storage optimization may in fact be a pessimization for common token access patterns, because the cost of additional resource consumption can outweigh any marginal benefits this may have for access times of rarely used data. > The whole discussion was about string containers, how fast lookups are, etc No, it was about token storage. > Your "you're wrong" comment was that the program can end up slower when you collect the strings but don't use them No, it was assuming common access patterns of token data in parsers, which aren't "you don't use them" but "you rarely access them, likely only once when parsing but on rare occasion you have to refer back to specific tokens later".

vitus 4y ago

The less space-efficient but more cpu-efficient alternative is to store an offset and a length. Which is, in essence, a string_view.

jstimpfle 4y ago
Note that a string view only gives you the token text, not the token in general (like, most importantly, the token type, i.e. identifier, string literal, integer literal, keywords, etc). So the additional length information that's contained in the file doesn't help much, you'll have to lex again anyway, unless you're only interested in the text. Apart from that -- a string view is typically understood as being implemented using a pointer to the string buffer, which is something else -- a pointer is 64 bits instead of 32 bit (on most systems, of course). And it requires the source file to be cached in memory at a stable location, can't be serialized and deserialized, etc. etc. In short, it's the typical fashionable modern C++ approach that is also wrong.
- sagarm 4y ago
  What would be the point of adding a string as int32 offset/size pair to the standard library? It would be meaningless without supporting infrastructure to link it to a backing buffer, and it can't represent strings over 4GB. If it's something that you can make work, declaring the typedef or struct is trivial. string_view is a useful general purpose tool that implements the std::string API for e.g. taking strings of various types in general purpose function signatures. Obviously it's not meant to be serialized and deserialized. It works well for its intended purpose. The two are not mutually exclusive: you could turn your 32-bit offset/length pair into a string_view to pass to functions that operate in the context of a single string.
  - jstimpfle 4y ago
    Where did I mention standard library? > It works well for its intended purpose. The intended purpose is quite general. Which admits other, better solutions in specific applications.