4 ms·

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".

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".