4 ms·

It's actually the simplest scheme. Reparse from the top whenever you need to query a setting. When you see one, exit. No need to even bother to store an inte

by ajross 2y ago

It's actually the simplest scheme. Reparse from the top whenever you need to query a setting. When you see one, exit. No need to even bother to store an intermediate representation. No idea if this matches the actual ssh implementation, but that's the way many historical parsers worked. The idea of cooking your text file on disk (into precious RAM!) is fairly modern.

Dylan16807 2y ago
Loading up your parsing code and reopening the file every time a setting is queried sounds to me like it would increase the average memory use of most programs.
- naniwaduni 2y ago
  You don't care about average memory use, you care about peak memory use.
  - NekkoDroid 2y ago
    Doesn't really sound much better. You still load up the file(s) and the parser either way, so parsing all once vs on-demand is just a question of computation duration and considering how many config options are used the on-demand just seems really wasteful, especially after startup.
    - hnlmorg 2y ago
      The GP is correct in terms of super old systems. In said systems, RAM was such an expensive resource that we had to save individual bits wherever we could. Such as only storing the last two digits of the year (aka the millennium bug). The computational cost of infrequently rescanning the config files then freeing the memory afterwards was much cheaper than the cost of storing those config files into RAM. And I say “infrequently rescanning” because you weren’t talking about people logging in and out of TSSs at rapid intervals. That all said, sshd was first written in the 90s so I find it hard to believe RAM considerations was the reason for the “first match” design of sshd’s config. More likely, it inherited that design choice from rsh or some other 1970s predecessor.
      - ajross 2y ago
        > hard to believe RAM considerations was the reason for the “first match” design of sshd’s config And I repeat: first match involves less code. It's a simpler design. The RAM point was an interesting digression, I literally put it in parentheses!
        hnlmorg 2y ago
        I don’t think it does require less code. I don’t think it requires more code either. It’s just not a fundamental code change. The difference is just either: overwriting values or exiting in the presence of a match. Either way it’s the same parser rules you have to write for the config file structure.
        ajross 2y ago
        OK, but now that's a performance regression. The assumption upthread was that the whole file needed to be parsed into an in-memory representation. If you don't do that, sure, you can implement precedence either way. But parsing all the way to the end for every read is ridiculous. The choice is between "parse all at once", which allows for arbitrary precedence rules but involves more code, and "parse at attribute read time", which involves less code but naturally wants to be a "first match" precedence.
        Dylan16807 2y ago
        You introduced an n^2 config algorithm but now you're worried about the much smaller performance impact from going to the end of the file instead of sometimes stopping halfway? And for the record I'm not convinced your way is simpler. The code gets sprinkled with config loading calls instead of just checking a variable, and the vast majority of the parser is the same between versions.
        ajross 2y ago
        You're not discussing in good faith. The performance comparison was to the "parse to the end" variant that you suggested as equivalent. The natural way you implement that (again, very simple) algorithm wants the early exit, yes, for obvious performance reasons. We're done. You're "not convinced" my way is simpler because you're not willing to give ground at all. This is a dumb thing to argue about. Just look at some historical parsers for similar languages, I guess. Nothing I've said here is controversial at all.
    - ajross 2y ago
      > load up the file I/O is done piecewise, a line at a time. The file is never "loaded up". Again you're applying an intuition about how parsers are presented to college students (suck it all into RAM and build a big in-memory representation of the syntax tree) that doesn't match the way actual config file parsers work (read a line and interpret it, then read another).
      - NekkoDroid 2y ago
        I didn't mean it in a way that "all of the file is loaded into memory", just the parts you are always processing at the time (e.g. as you said line wise), which either way result in the same memory usage from the file being loaded.
  - Dylan16807 2y ago
    Same criticism. When the program is in the middle of busy runtime activity, with all the memory that entails, it's the worst time to also load up the parser.
- ajross 2y ago
  The ssh config format has almost no context, and the code is static and always "loaded up". I can all but guarantee this isn't correct. Modern hackers tend to wildly overestimate the complexity of ancient tasks like parsing.
  - Dylan16807 2y ago
    If you're actually concerned about the handfuls of bytes a settings object would take, you would make the page/segment containing parser code able to be unloaded from memory.
Joker_vD 2y ago
Nope, the actual ssh implementation parses all the config files once, at the startup, using buffered file I/O and getline(). That means that on systems with modern libc, the whole config file (if it's small enough, less than 4 KiB IIRC?) gets read into the RAM and then getline() results are served from that buffer. The scheme you propose is insane and if it was ever used (can you actually back that up? The disk I/O would kill your performance for anything remotely loaded), it was rightfully abandoned for much faster and simpler scheme.
- ajross 2y ago
  > getline() results are served from that buffer. So... it doesn't parse them once! It just does its own[1] buffering layer and implements... exactly the algorithm I described? Not seeing where you're getting the "Nope" here, except to be focusing on the one historical note about RAM that I put in parentheses. [1] Somewhat needless given the OS has already done this. It only saves the syscall overhead.
  - Joker_vD 2y ago
    Sorry, my comment was intended to be reply to the one of yours that said I/O is done piecewise, a line at a time. The file is never "loaded up". Again you're applying an intuition about how parsers are presented to college students (suck it all into RAM and build a big in-memory representation of the syntax tree) that doesn't match the way actual config file parsers work (read a line and interpret it, then read another). So, the whole file is usually loaded up (if it's short enough). At this point you might as well parse all of it, instead of re-reading it from the disk over and over, and redoing the same work over and over; parsed configs — if they are parsed into falgs/enums, and not literal strings — usually take about the same, or less, memory than a FILE structure from libc does on the whole. The complexity of the algorithm is about the same, either the early exit is here or it isn't (in fact, the version with the early exit, now that I think of it, has larger cyclotomatic complexity but whatever).

by ajross 2y ago

Dylan16807 2y ago

Loading up your parsing code and reopening the file every time a setting is queried sounds to me like it would increase the average memory use of most programs.

naniwaduni 2y ago
You don't care about average memory use, you care about peak memory use.
- NekkoDroid 2y ago
  Doesn't really sound much better. You still load up the file(s) and the parser either way, so parsing all once vs on-demand is just a question of computation duration and considering how many config options are used the on-demand just seems really wasteful, especially after startup.
  - hnlmorg 2y ago
    The GP is correct in terms of super old systems. In said systems, RAM was such an expensive resource that we had to save individual bits wherever we could. Such as only storing the last two digits of the year (aka the millennium bug). The computational cost of infrequently rescanning the config files then freeing the memory afterwards was much cheaper than the cost of storing those config files into RAM. And I say “infrequently rescanning” because you weren’t talking about people logging in and out of TSSs at rapid intervals. That all said, sshd was first written in the 90s so I find it hard to believe RAM considerations was the reason for the “first match” design of sshd’s config. More likely, it inherited that design choice from rsh or some other 1970s predecessor.
    - ajross 2y ago
      > hard to believe RAM considerations was the reason for the “first match” design of sshd’s config And I repeat: first match involves less code. It's a simpler design. The RAM point was an interesting digression, I literally put it in parentheses!
      - hnlmorg 2y ago
        I don’t think it does require less code. I don’t think it requires more code either. It’s just not a fundamental code change. The difference is just either: overwriting values or exiting in the presence of a match. Either way it’s the same parser rules you have to write for the config file structure.
        ajross 2y ago
        OK, but now that's a performance regression. The assumption upthread was that the whole file needed to be parsed into an in-memory representation. If you don't do that, sure, you can implement precedence either way. But parsing all the way to the end for every read is ridiculous. The choice is between "parse all at once", which allows for arbitrary precedence rules but involves more code, and "parse at attribute read time", which involves less code but naturally wants to be a "first match" precedence.
        Dylan16807 2y ago
        You introduced an n^2 config algorithm but now you're worried about the much smaller performance impact from going to the end of the file instead of sometimes stopping halfway? And for the record I'm not convinced your way is simpler. The code gets sprinkled with config loading calls instead of just checking a variable, and the vast majority of the parser is the same between versions.
        ajross 2y ago
        You're not discussing in good faith. The performance comparison was to the "parse to the end" variant that you suggested as equivalent. The natural way you implement that (again, very simple) algorithm wants the early exit, yes, for obvious performance reasons. We're done. You're "not convinced" my way is simpler because you're not willing to give ground at all. This is a dumb thing to argue about. Just look at some historical parsers for similar languages, I guess. Nothing I've said here is controversial at all.
  - ajross 2y ago
    > load up the file I/O is done piecewise, a line at a time. The file is never "loaded up". Again you're applying an intuition about how parsers are presented to college students (suck it all into RAM and build a big in-memory representation of the syntax tree) that doesn't match the way actual config file parsers work (read a line and interpret it, then read another).
    - NekkoDroid 2y ago
      I didn't mean it in a way that "all of the file is loaded into memory", just the parts you are always processing at the time (e.g. as you said line wise), which either way result in the same memory usage from the file being loaded.
- Dylan16807 2y ago
  Same criticism. When the program is in the middle of busy runtime activity, with all the memory that entails, it's the worst time to also load up the parser.
ajross 2y ago
The ssh config format has almost no context, and the code is static and always "loaded up". I can all but guarantee this isn't correct. Modern hackers tend to wildly overestimate the complexity of ancient tasks like parsing.
- Dylan16807 2y ago
  If you're actually concerned about the handfuls of bytes a settings object would take, you would make the page/segment containing parser code able to be unloaded from memory.

Joker_vD 2y ago

Nope, the actual ssh implementation parses all the config files once, at the startup, using buffered file I/O and getline(). That means that on systems with modern libc, the whole config file (if it's small enough, less than 4 KiB IIRC?) gets read into the RAM and then getline() results are served from that buffer. The scheme you propose is insane and if it was ever used (can you actually back that up? The disk I/O would kill your performance for anything remotely loaded), it was rightfully abandoned for much faster and simpler scheme.

ajross 2y ago
> getline() results are served from that buffer. So... it doesn't parse them once! It just does its own[1] buffering layer and implements... exactly the algorithm I described? Not seeing where you're getting the "Nope" here, except to be focusing on the one historical note about RAM that I put in parentheses. [1] Somewhat needless given the OS has already done this. It only saves the syscall overhead.
- Joker_vD 2y ago
  Sorry, my comment was intended to be reply to the one of yours that said I/O is done piecewise, a line at a time. The file is never "loaded up". Again you're applying an intuition about how parsers are presented to college students (suck it all into RAM and build a big in-memory representation of the syntax tree) that doesn't match the way actual config file parsers work (read a line and interpret it, then read another). So, the whole file is usually loaded up (if it's short enough). At this point you might as well parse all of it, instead of re-reading it from the disk over and over, and redoing the same work over and over; parsed configs — if they are parsed into falgs/enums, and not literal strings — usually take about the same, or less, memory than a FILE structure from libc does on the whole. The complexity of the algorithm is about the same, either the early exit is here or it isn't (in fact, the version with the early exit, now that I think of it, has larger cyclotomatic complexity but whatever).