7 ms·
By itself, that doesn't add up to N-squared behavior, though. > It looks like the problem is that reading floats is done using c4::from_chars -> c4::atof -> ss
by kazinator 6y ago
By itself, that doesn't add up to N-squared behavior, though.
> It looks like the problem is that reading floats is done using c4::from_chars -> c4::atof -> sscanf which ultimately calls _IO_str_init_static_internal in the glibc implementation. As far as I understand, this essentially causes strlen to be called on the string that rapidyaml passes to it, essentially causing strlen to be called O(n^2) times.
As such, this doesn't follow. Just because sscanf takes the length of the entire source string doesn't mean will get N^2 behavior, unless you do silly things with sscanf, like extract a small token from the beginning of a large string, and then skip past it to do the same thing again after that small token: essentially, build a lexical analyzer in which the pattern matcher consists of calls to scanf. This is not an intended use case for sscanf. No self-respecting language parser designer would do such a thing in a non-throwaway, production program.
sscanf has undefined behaviors for out-of-range numeric values, so you can't use it for just blindly extracting numeric tokens at all, regardless of any other issues.
sscanf should only be used on a string that your program has either prepared itself, or carefully delimited by some other means.
For instance, suppose we have a string which holds a date (could be an input to the program). We can test whether it's in the YYYY-MM-DD format, and get those values out:
int year, month, day;
char junk;
if (sscanf(input, "%4d-%2d-%2d%c", &year, &month, &day, &junk) == 3)
{
/* we got it */
}
The purpose of junk is to test that there is no trailing garbage character. If there is, it will be scanned and the return value will be 4. If we don't care about that, we can just omit that argument and conversion specifier.
This will accept inputs like 01-1-1. Worse, it will scan leading signs!
If you wan to insist on nothing but digits, and exact digit counts, you can break it up as string tokens first:
char yearstr[5], monthstr[3], daystr[3];
char junk;
if (sscanf(input, "%4[0-9]-%2[0-9]-%2[0-9]%c", yearstr, monthstr, daystr, &junk) == 3)
{
int year = atoi(yearstr);
int month = atoi(monthstr);
int day = atoi(daystr);
}
atoi is safe here, by the way, because we know that the integers are decimal strings no more than four digits.
This is the sort of thing where sscanf comes in very handy. If you know how to use it, it solves these sorts of things nicely, and the performance is probably okay. At least not degenerately bad.
Complete sample with all the validation:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main(int argc, char **argv)
{
char yearstr[5] = "", monthstr[3] = "", daystr[3] = "";
char junk;
if (argv[0] && argv[1] &&
sscanf(argv[1], "%4[0-9]-%2[0-9]-%2[0-9]%c", yearstr, monthstr, daystr, &junk) == 3 &&
yearstr[3] && monthstr[1] && daystr[1])
{
int year = atoi(yearstr);
int month = atoi(monthstr);
int day = atoi(daystr);
printf("%d:%d:%d\n", year, month, day);
return 0;
}
return EXIT_FAILURE;
}
Some tests:
$ ./date asdf
$ ./date 1-2-3
$ ./date 2020-01-1
$ ./date 20-01-01
$ ./date 2020-01-01
2020:1:1
$ ./date 2020-01-01z
$ ./date 2020-01-12
2020:1:12
- adwn 6y ago> [...] so you can't use it for just blindly extracting numeric tokens at all [...] So in other words, it's completely useless? > This is not an intended use case for sscanf. Then what is?
- nitrogen 6y agoThe comment to which you reply uses the %[] conversion to impose stricter limits on acceptable characters to be interpreted as numbers. My guess at the historical intention of *scanf is that it was meant for parsing tab-delimited and fixed-width records from old-school data files.
- sdenton4 6y ago(As opposed to the comma-separated data files that we enlightened future-folk use!)
- Darkphibre 6y agoYou know, why don't we use 0x1F (Unit Separator)? Seems like we have had a hierarchical delimiters since ASCII / punch cards, yet I never hear about them. https://en.wikipedia.org/wiki/C0_and_C1_control_codes#Field_separators https://en.wikipedia.org/wiki/C0_and_C1_control_codes#Field_... CSVs are such a pain if you have freeform text (in which you have to handle newlines and escaped quotes). It seems like using FS/GS/RS/US from the C0 control codes would be divine (provided there was implicit support for viewing/editing them in a simple text editor). I get that it's a non-printable control character, and thus not traditionally rendered... but that latter point could have been done ages ago as a standard convention in editors (enter VIM et. al., as they will indeed allow you to see them).
- jimmaswell 6y agoIt's nice being able to edit a CSV in a text editor. It wouldn't be worth it to lose that just to not have to escape some strings.