3 ms·

I am confused about this comment. The parent comment gave clear call stack that pointing to the problem where the glibc's sscanf implementation would strlen the

by liuliu 6y ago

I am confused about this comment. The parent comment gave clear call stack that pointing to the problem where the glibc's sscanf implementation would strlen the input string no matter what format string you use (because it need to masquerade as a file and that requires strlen the whole input: https://github.com/bminor/glibc/blob/21c3f4b5368686ade28d90d8c7d79c4c95c72c1b/stdio-common/sscanf.c#L34 https://github.com/bminor/glibc/blob/21c3f4b5368686ade28d90d...) All your magic on format string doesn't change that poor behavior unless you manually add '\0' somewhere to null-terminate the input string early. If you parse the year-month-day in 100 places of that input string, it will strlen 100 times. And now replace the "100 places" to a linear function of the input string length (strlen(input) / 11?), that is quadratic.

deleted 6y ago
[deleted]
jchw 6y ago
I agree with you. However, the point of the parent comment is that you should not use scanf to do this; it is not designed to parse a small part of a large string. And indeed, I would say it is bad for more reasons than just this performance cliff. You should really prefer to use strtod or strtol on the exact scanned token instead. Even then, these functions may be impacted by C locale settings, which means you should probably instead prefer using implementations of this algorithm outside of libc...
- josefx 6y ago
  I just ran strtod through a debugger it at least ends up in strlen.S, so it probably wont improve the runtime complexity . It seems to be best to just assume the worst when it comes to any functions in the C standard library that have to do with string handling and avoid them in favor of literally anything else.
  - jchw 6y ago
    Did you call strtod with a null endptr? If not, I'd be surprised if it actually strlen'd the input rather than a copy of it. Still, I agree, you shouldn't really use the C standard library to do strings.
    - bscphil 6y ago
      > Still, I agree, you shouldn't really use the C standard library to do strings. As someone who's been learning some C, I wonder if you have a recommendation for a guide on how to handle strings properly.
      - cormacrelf 6y ago
        It probably shouldn’t involve writing your own string functions. They’re so hard to get right, obviously. Last time I wrote C, I copied out the Rust Vec and String API as C headers and didn’t quite nail the implementation, but it was fun. There are at least a few libs like sds that store the length information in various ways, which solves at least this kind of problem. https://github.com/antirez/sds https://github.com/antirez/sds
      - jchw 6y ago
        There’s plenty of string libraries, although ultimately no answer is perfect. It’s totally OK to use the libc string routines when learning C, but it would be good to keep in mind that it is not necessarily easy to write safe and correct software using it. (Languages with more advanced string types and slicing mechanics are not impacted; C++, Rust, Go, etc. They do have their own issues of course.)

by liuliu 6y ago

deleted 6y ago

[deleted]

jchw 6y ago

I agree with you. However, the point of the parent comment is that you should not use scanf to do this; it is not designed to parse a small part of a large string. And indeed, I would say it is bad for more reasons than just this performance cliff. You should really prefer to use strtod or strtol on the exact scanned token instead. Even then, these functions may be impacted by C locale settings, which means you should probably instead prefer using implementations of this algorithm outside of libc...

josefx 6y ago
I just ran strtod through a debugger it at least ends up in strlen.S, so it probably wont improve the runtime complexity . It seems to be best to just assume the worst when it comes to any functions in the C standard library that have to do with string handling and avoid them in favor of literally anything else.
- jchw 6y ago
  Did you call strtod with a null endptr? If not, I'd be surprised if it actually strlen'd the input rather than a copy of it. Still, I agree, you shouldn't really use the C standard library to do strings.
  - bscphil 6y ago
    > Still, I agree, you shouldn't really use the C standard library to do strings. As someone who's been learning some C, I wonder if you have a recommendation for a guide on how to handle strings properly.
    - cormacrelf 6y ago
      It probably shouldn’t involve writing your own string functions. They’re so hard to get right, obviously. Last time I wrote C, I copied out the Rust Vec and String API as C headers and didn’t quite nail the implementation, but it was fun. There are at least a few libs like sds that store the length information in various ways, which solves at least this kind of problem. https://github.com/antirez/sds https://github.com/antirez/sds
    - jchw 6y ago
      There’s plenty of string libraries, although ultimately no answer is perfect. It’s totally OK to use the libc string routines when learning C, but it would be good to keep in mind that it is not necessarily easy to write safe and correct software using it. (Languages with more advanced string types and slicing mechanics are not impacted; C++, Rust, Go, etc. They do have their own issues of course.)