3 ms·

I found this while making a collection of what C implementation does what at https://news.ycombinator.com/item?id=26298300 https://news.ycombinator.com/item?id=

by JdeBP 6y ago

I found this while making a collection of what C implementation does what at https://news.ycombinator.com/item?id=26298300 https://news.ycombinator.com/item?id=26298300 . There are two basic implementation strategies. The BSD (FreeBSD and OpenBSD and more than likely NetBSD too), Microsoft, GNU, and MUSL C libraries use one, and suffer from this; whereas the OpenWatcom, P.J. Plauger, Tru64 Unix, and my standard C libraries use another, and do not. The 2002 report in the comp.lang.c Usenet newsgroup (listed in that discussion) is the earliest that I've found so far. There have been several assertions that library support for strings in C++ is poor. However, note that the fix here was to switch from the Standard C library function sscanf() to a C++ library. * https://github.com/fastfloat https://github.com/fastfloat One might advocate using other people's libraries, on the grounds that they will have got such things right. However, note that this is RapidYAML, and the bug got fixed several years after GTA Online was released. Other third-party parsing libraries have suffered from being layered on top of sscanf() in other ways. * https://github.com/json-c/json-c/issues/173 https://github.com/json-c/json-c/issues/173 * https://github.com/kgabis/parson/commit/96150ba1fd7f3398aa6a4dead0a63d9d9ac1c189 https://github.com/kgabis/parson/commit/96150ba1fd7f3398aa6a...

Jasper_ 6y ago
Musl reads the "file" in 256 byte increments and calls strlen on each one. Still a strlen, but on short strings it would only be called once, on a short amount of data. It would work fine for this use case.
- JdeBP 6y ago
  As laid out at https://news.ycombinator.com/item?id=26298300 https://news.ycombinator.com/item?id=26298300, it doesn't call strlen(); and it isn't 256 bytes. Moreover that use case is not the use cases at hand, which are people parsing 10MiB of JSON and 504KiB of YAML with parsers that are not calling sscanf() just once. MUSL, with the same implementation strategy of nonce FILE objects, ends up performing multiple passes over those big input strings, once to look for NUL and a second time to pull each character out one by one. And it's doing those multiple passes multiple times, as it sets up and tears down the nonce FILE object each call to sscanf(), meaning that it's scanning the same parts of the string for NUL over and over again as it repeats the same buffer fill(s) from the input string a few characters further on. As I said before, it's not entirely free of this behaviour. With the other implementation strategy, in contrast, there's only a single pass over the whole input string, even with those multiple calls to sscanf().
  - Jasper_ 6y ago
    Let's look at the source: https://git.musl-libc.org/cgit/musl/tree/src/stdio/vsscanf.c https://git.musl-libc.org/cgit/musl/tree/src/stdio/vsscanf.c It fills in a buf with a string_read callback, but if we look at what vfscanf does, it uses shgetc, which eventually calls into __uflow, which is where the read is performed: https://git.musl-libc.org/cgit/musl/tree/src/stdio/vfscanf.c https://git.musl-libc.org/cgit/musl/tree/src/stdio/vfscanf.c https://git.musl-libc.org/cgit/musl/tree/src/internal/shgetc.c https://git.musl-libc.org/cgit/musl/tree/src/internal/shgetc... https://git.musl-libc.org/cgit/musl/tree/src/stdio/__uflow.c https://git.musl-libc.org/cgit/musl/tree/src/stdio/__uflow.c This will call into the string_read callback with a buf size of 1. The string_read will internally do a memchr(buf, 0, len+256);, so, OK, it's memchr-ing at most 257 bytes, sorry. The read data then gets stored in a stdio-internal buffer (the rpos/rlen below), so this code path will actually be skipped on future reads. If it then needs to unparse a character, it will use ungetc to put it back in a stdio-internal buffer. Reading this code isn't that hard, I don't know why you keep insisting it does something else.
    - JdeBP 6y ago
      You haven't read the code properly. The memcpy() copies one character. After shgetc() reads that and possibly a few more characters, the entire FILE object goes away and the next call to sscanf() sets up an entirely fresh nonce FILE object and does the initial fill all over again, including scanning the stuff that it has already scanned for NUL, a few characters further on. As I just explained.
      - Jasper_ 6y ago
        Yes, but it's not scanning the entire string, it's scanning at most 256 bytes. In MSVC, the number of bytes scanned is `M*N` where M is the number of calls to scanf and N is the size of the file. In musl, N is now 257, no matter the size of the file. Compared to ~10MB of data, that's basically free. Sure, it's scanning a bit more than maybe it needs to, but it's much closer to a non-scanning libc in the amount of data it's consuming.
deleted 6y ago
[deleted]
kiwidrew 6y ago
It turns out that the strlen() behaviour was present as far back as the 4BSD libc [1] circa 1980, and via the Net/2 releases has found its way into NetBSD/FreeBSD/OpenBSD along with countless other BSD-derived libc implementations. Of course, the underlying vfscanf() implementation that reads from a FILE* simply proceeds one character at a time; the pseudo-quadratic behaviour arising from the strlen() call is simply an artifact of the simplistic "simulate a file using a string" wrapper in sscanf(). [1] https://minnie.tuhs.org/cgi-bin/utree.pl?file=4BSD/usr/src/libc/stdio/scanf.c https://minnie.tuhs.org/cgi-bin/utree.pl?file=4BSD/usr/src/l...

by JdeBP 6y ago

Jasper_ 6y ago

Musl reads the "file" in 256 byte increments and calls strlen on each one. Still a strlen, but on short strings it would only be called once, on a short amount of data. It would work fine for this use case.

JdeBP 6y ago
As laid out at https://news.ycombinator.com/item?id=26298300 https://news.ycombinator.com/item?id=26298300, it doesn't call strlen(); and it isn't 256 bytes. Moreover that use case is not the use cases at hand, which are people parsing 10MiB of JSON and 504KiB of YAML with parsers that are not calling sscanf() just once. MUSL, with the same implementation strategy of nonce FILE objects, ends up performing multiple passes over those big input strings, once to look for NUL and a second time to pull each character out one by one. And it's doing those multiple passes multiple times, as it sets up and tears down the nonce FILE object each call to sscanf(), meaning that it's scanning the same parts of the string for NUL over and over again as it repeats the same buffer fill(s) from the input string a few characters further on. As I said before, it's not entirely free of this behaviour. With the other implementation strategy, in contrast, there's only a single pass over the whole input string, even with those multiple calls to sscanf().
- Jasper_ 6y ago
  Let's look at the source: https://git.musl-libc.org/cgit/musl/tree/src/stdio/vsscanf.c https://git.musl-libc.org/cgit/musl/tree/src/stdio/vsscanf.c It fills in a buf with a string_read callback, but if we look at what vfscanf does, it uses shgetc, which eventually calls into __uflow, which is where the read is performed: https://git.musl-libc.org/cgit/musl/tree/src/stdio/vfscanf.c https://git.musl-libc.org/cgit/musl/tree/src/stdio/vfscanf.c https://git.musl-libc.org/cgit/musl/tree/src/internal/shgetc.c https://git.musl-libc.org/cgit/musl/tree/src/internal/shgetc... https://git.musl-libc.org/cgit/musl/tree/src/stdio/__uflow.c https://git.musl-libc.org/cgit/musl/tree/src/stdio/__uflow.c This will call into the string_read callback with a buf size of 1. The string_read will internally do a memchr(buf, 0, len+256);, so, OK, it's memchr-ing at most 257 bytes, sorry. The read data then gets stored in a stdio-internal buffer (the rpos/rlen below), so this code path will actually be skipped on future reads. If it then needs to unparse a character, it will use ungetc to put it back in a stdio-internal buffer. Reading this code isn't that hard, I don't know why you keep insisting it does something else.
  - JdeBP 6y ago
    You haven't read the code properly. The memcpy() copies one character. After shgetc() reads that and possibly a few more characters, the entire FILE object goes away and the next call to sscanf() sets up an entirely fresh nonce FILE object and does the initial fill all over again, including scanning the stuff that it has already scanned for NUL, a few characters further on. As I just explained.
    - Jasper_ 6y ago
      Yes, but it's not scanning the entire string, it's scanning at most 256 bytes. In MSVC, the number of bytes scanned is `M*N` where M is the number of calls to scanf and N is the size of the file. In musl, N is now 257, no matter the size of the file. Compared to ~10MB of data, that's basically free. Sure, it's scanning a bit more than maybe it needs to, but it's much closer to a non-scanning libc in the amount of data it's consuming.

deleted 6y ago

[deleted]

kiwidrew 6y ago

It turns out that the strlen() behaviour was present as far back as the 4BSD libc [1] circa 1980, and via the Net/2 releases has found its way into NetBSD/FreeBSD/OpenBSD along with countless other BSD-derived libc implementations. Of course, the underlying vfscanf() implementation that reads from a FILE* simply proceeds one character at a time; the pseudo-quadratic behaviour arising from the strlen() call is simply an artifact of the simplistic "simulate a file using a string" wrapper in sscanf(). [1] https://minnie.tuhs.org/cgi-bin/utree.pl?file=4BSD/usr/src/libc/stdio/scanf.c https://minnie.tuhs.org/cgi-bin/utree.pl?file=4BSD/usr/src/l...