News for hackers. Stuff that matters.
Re:Parsing can become accidentally quadratic because of sscanf by kazinator on Monday March 01, 2021 @10:28AM (#26303624)
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
Re:Parsing can become accidentally quadratic because of sscanf by liuliu on Monday March 01, 2021 @12:00PM (#26304911)
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/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.

Re:Parsing can become accidentally quadratic because of sscanf by jchw on Monday March 01, 2021 @03:24PM (#26307907)
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...
Re:Parsing can become accidentally quadratic because of sscanf by josefx on Monday March 01, 2021 @04:50PM (#26308938)
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.
Re:Parsing can become accidentally quadratic because of sscanf by jchw on Monday March 01, 2021 @05:02PM (#26309056)
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.
Re:Parsing can become accidentally quadratic because of sscanf by bscphil on Monday March 01, 2021 @07:48PM (#26310547)
> 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.

Re:Parsing can become accidentally quadratic because of sscanf by cormacrelf on Monday March 01, 2021 @08:58PM (#26311036)
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

Re:Parsing can become accidentally quadratic because of sscanf by jchw on Tuesday March 02, 2021 @01:21PM (#26318493)
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.)

Re:Parsing can become accidentally quadratic because of sscanf by oceanghost on Monday March 01, 2021 @01:35PM (#26306274)
> This is not an intended use case for sscanf.

It's almost like JSON and XML were invented so people didn't have to understand lex/yacc.

And behold... they don't.

Re:Parsing can become accidentally quadratic because of sscanf by adwn on Monday March 01, 2021 @10:44AM (#26303840)
> [...] 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?

Re:Parsing can become accidentally quadratic because of sscanf by kazinator on Monday March 01, 2021 @11:27AM (#26304409)
Yes, scanf is almost completely useless, and sscanf a little less so. sscanf is useful if you need a pattern-based breakdown of some string datum, and the patterns are not out of sscanf's league. It will work "anywhere"; it's been in C since before 1989 ANSI C.

In the entire TXR project, I used sscanf in one function: a floating to integer conversion routine. The context is that integers can be bignums, so we can't just rely on ordinary conversion, except in the fixnum range.

http://www.kylheku.com/cgit/txr/tree/arith.c?h=txr-252#n2912

The approach taken is to sprintf the double value into a generous buffer, with a generous precision, using the %g format which will automatically use the e notation if necessary.

We detect whether the e notation was produced, and other characteristics, and then proceed accordingly.

I see that an impossible case is being tested for; since values with a small magnitude are handled via the fixnum route, we will never hit the case where we can short-circuit to zero.

Can anyone see a bug here, by the way? :)

Re:Parsing can become accidentally quadratic because of sscanf by nitrogen on Monday March 01, 2021 @11:14AM (#26304237)
The 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.

Re:Parsing can become accidentally quadratic because of sscanf by sdenton4 on Monday March 01, 2021 @11:24AM (#26304358)
(As opposed to the comma-separated data files that we enlightened future-folk use!)
Re:Parsing can become accidentally quadratic because of sscanf by Darkphibre on Monday March 01, 2021 @12:09PM (#26305052)
You 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_...

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

Re:Parsing can become accidentally quadratic because of sscanf by jimmaswell on Monday March 01, 2021 @12:17PM (#26305195)
It'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.
Re:Parsing can become accidentally quadratic because of sscanf by JdeBP on Monday March 01, 2021 @01:47PM (#26306507)
Text editors that can put control characters into files, and indeed PC keyboards that have a [Control] key, have been around for decades, though. For example: With WordStar, SideKick, and Microsoft's EDIT, one just typed [Control]+[P] and then the control character. M. Darkphibre mentioned VIM, but really this isn't an idea that was ever limited to just VIM and emacs.
Re:Parsing can become accidentally quadratic because of sscanf by sp332 on Monday March 01, 2021 @01:42PM (#26306403)
It wouldn't take that much effort to add a glyph in the editor for it?
Re:Parsing can become accidentally quadratic because of sscanf by afiori on Monday March 01, 2021 @12:46PM (#26305610)
more than that it is nice to edit files with a standard keyboard,
Re:Parsing can become accidentally quadratic because of sscanf by db48x on Monday March 01, 2021 @05:16PM (#26309210)
If your editor doesn't allow you to enter arbitrary characters using a standard keyboard then you need a better editor.
Re:Parsing can become accidentally quadratic because of sscanf by chousuke on Monday March 01, 2021 @06:00PM (#26309696)
The problem is not the editor, it's the human typing on the keyboard that sees , and thinks "that'll do". Using an obscure dedicated character is not going to happen.
Re:Parsing can become accidentally quadratic because of sscanf by Darkphibre on Wednesday March 03, 2021 @03:53AM (#26326127)
I guess my point was a curiosity that these control codes had become obscure, when text format interchange is so prevalent throughout computing history.
Re:Parsing can become accidentally quadratic because of sscanf by afiori on Tuesday March 02, 2021 @12:56AM (#26312293)
I do not want to learn new input methods for every program, I want a standardized compose-like functionality that allow me to write both diacritics and backticks ( a plus for the rest of unicode)
Re:Parsing can become accidentally quadratic because of sscanf by db48x on Tuesday March 02, 2021 @02:36AM (#26312809)
All operating systems have that too. Look up "Input Method Editor" in your favorite OS's documentation. See also dead keys, compose key, AltGr, etc, etc. If you think you can't edit a file because it has funny characters in it, then you're not trying hard enough.
Re:Parsing can become accidentally quadratic because of sscanf by afiori on Tuesday March 02, 2021 @02:50AM (#26312909)
I know, still there is no reasonable way* to do both common european diacritics and backticks/tilde on windows without installing third-party software.

* I find dead keys irritating beyond reason, so I do not count them as an option

Re:Parsing can become accidentally quadratic because of sscanf by 0xbadcafebee on Monday March 01, 2021 @12:39PM (#26305517)
There are plenty of ways a lazy programmer will want to pass the records into something else that either doesn't handle non-printables, or does but the user doesn't like how it looks.

TSV also works more reliably than CSV, because most people don't put tab characters in the data in these kinds of records. Tab is even the default field delimiter for cut. But everybody uses CSV, because again it's easier to reason about the above. (shrug)

Re:Parsing can become accidentally quadratic because of sscanf by nitrogen on Monday March 01, 2021 @03:56PM (#26308292)
No matter what delimiters we use, we still have either a data sanitization problem or a data escaping problem. I've worked with a wire protocol that used the ASCII record delimiters, but with binary data so you also had to use binary escape (0x1b) and set the eighth bit on the following byte.
Re:Parsing can become accidentally quadratic because of sscanf by elygre on Monday March 01, 2021 @02:15PM (#26306890)
Which is a mess, because some parts of the world use commas as decimal commas: 3,14159etc. So we have to use semicolon for our CSVs.
Re:Parsing can become accidentally quadratic because of sscanf by bmn__ on Monday March 01, 2021 @03:46PM (#26308163)
> some parts of the world

most parts

Why can't you be normal? https://commons.wikimedia.org/wiki/File:DecimalSeparator.svg

Re:Parsing can become accidentally quadratic because of sscanf by dmit on Monday March 01, 2021 @06:08PM (#26309765)
I submitted a patch to support decimal commas when parsing timestamps in Go in 2013. I thought this was a slam dunk because while major users of decimal dots include USA, China, India, and Japan, the decimal comma is used by pretty much every other country in the world. Going from ~40% support to ~99.9% support seemed like an obvious win.

Rob Pike politely declined the patch, commenting "I might prefer to leave it unaddressed for the moment. Proper locale treatment is coming (I hope soon) and this seems like the wrong place to start insinuating special locale handling into the standard library."

Three years later another Go team member commented that "Date localization is definitely still in the planning."

We're in year 8 now. The issue is still open. Rob Pike is still hoping.

Re:Parsing can become accidentally quadratic because of sscanf by boogies on Monday March 01, 2021 @07:12PM (#26310307)
> ~40% support to ~99.9% support

№ of countries ≠ № of people though. ⅘ of the 5 most populous countries¹ use decimal points, and together they alone² have ~42½% of the world’s people. Do all decimal point countries together have ≤50%? (Edit: Is it really not “normal” to do things the Anglophone way?)

¹According to https://en.wikipedia.org/wiki/List_of_countries_and_dependen...

²Not counting territories

Re:Parsing can become accidentally quadratic because of sscanf by nicoburns on Monday March 01, 2021 @06:58PM (#26310201)
This is where Rust's decision to keep such functions out of the standard library entirely starts to look pretty smart.
Re:Parsing can become accidentally quadratic because of sscanf by tyg13 on Monday March 01, 2021 @11:30PM (#26311915)
Wow, taking a look at the related issues, they are really hostile towards fixing this particular pain point. I knew Go had a reputation for being condescending and opinionated, but I had no idea it was this bad.

https://github.com/golang/go/issues/6189

https://github.com/golang/go/issues/26002

https://github.com/golang/go/issues/27746

https://github.com/golang/go/issues/36145

Re:Parsing can become accidentally quadratic because of sscanf by fomine3 on Monday March 01, 2021 @07:21PM (#26310375)
Re:Parsing can become accidentally quadratic because of sscanf by unilynx on Monday March 01, 2021 @12:15PM (#26305149)
C is full of record based stuff. Apart from the numeric modifiers to printf and scanf we have fread, fwrite, calloc all taking record sizes
Re:Parsing can become accidentally quadratic because of sscanf by shawnz on Monday March 01, 2021 @12:49PM (#26305649)
> ... 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.

Then why does it support the "%n" specifier? Isn't it exactly for that use case?

Re:Parsing can become accidentally quadratic because of sscanf by froh on Monday March 01, 2021 @11:57AM (#26304861)
to my understanding there is a long input string, completely in memory. that string consists of a gazillion of floats. the string is walked with a pointer, the floats are sscanf-ed one after the other. each of the sscanfs will call strlen once, but each strlen will scan the full remaining huge string to find the \0 eos byte.

the sum of all scanned bytes is quadratic to the length of the huge input string.

?

edit: oh the autocorrect...

Re:Parsing can become accidentally quadratic because of sscanf by kazinator on Monday March 01, 2021 @12:21PM (#26305263)
That description seems to resemble my remark:

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

Scanning floats with sscanf means undefined behavior on a datum like 1.0E999 against a %lf (double), where the exponent is out of range. IEEEE double goes to E308, if I recall.

C99 says "Unless assignment suppression was indicated by a[n asterisk], the result of the conversion is placed in the object pointed to by the first argument following the format argument that has not already received a conversion result. If this object does not have an appropriate type, or if the result of the conversion cannot be represented in the object, the behavior is undefined."

I'm seeing that on glibc, 1E999 scans to an Inf, but that is not a requirement.

This problem could be solved with sscanf, too, while maintaining the degenerate quadratic behavior. sscanf patterns could be used to destructure a floating-point number textually into pieces like the whole part, fractional part and exponent after the E, which could then be validated separately, like that the E part is between -308 and 308 and so forth. Someone could still do this in a loop over a string with millions of floats. I'd say though that you're way past the point of needing a real lexical analyzer, and not multiple passes through scanf.

Re:Parsing can become accidentally quadratic because of sscanf by 3xccc on Monday March 01, 2021 @03:28PM (#26307960)
What about parsing an unknown number of at-most-4-digits integers from a string (being careful, as you exemplified)? Isn’t that a reasonable use of sscanf?

Do I need a full fledged parser for that? No. Does it have to traverse the whole string every time? No, because I’m being very clear about the maximum length of the thing I’m trying to parse.

You cannot not conclude that it’s a bug.

Re:Parsing can become accidentally quadratic because of sscanf by kazinator on Tuesday March 02, 2021 @12:58PM (#26318172)
My thoughts on that is that the problem is at a level below sscanf; in other words, what else is affected?

A mechanism for turning a string in memory into a string should not be taking its length.

GBLIC has an extension called fmemopen. The API is:

  FILE *fmemopen(void *buf, size_t size, const char *mode);
This interface smells like it might have the flaw that if someone wants "buf" to come from a null-terminated string, they must measure that string in order to supply the size parameter.

I.e. the underlying mechanism is binary, and does not stop at null characters.

There needs to be a separate mechanism with a different underlying stream implementation:

  FILE *fstropen(const char *str); // mode implied: "r"
This doesn't require a size.

That fmemopen extension points to a solution to the original problem, though non-portable: open the entire buffer of numbers as a stream in one fmemopen call, and then use fscanf to march through it.

Re:Parsing can become accidentally quadratic because of sscanf by froh on Thursday March 04, 2021 @11:06PM (#26352549)
fmemopen is meanwhile portable and part of posix.

https://pubs.opengroup.org/onlinepubs/9699919799/functions/f...

Re:Parsing can become accidentally quadratic because of sscanf by knuthsat on Monday March 01, 2021 @10:55AM (#26303976)
let's say you have a newline delimited dates in &junk. now you do a while loop, whoops quadratic.
Re:Parsing can become accidentally quadratic because of sscanf by cozzyd on Monday March 01, 2021 @01:00PM (#26305783)
Well, not if you do something like

   char * start = data; 
   char * next = strchr(data,'\n'); 
   while(next) 
   {

      *next=0; 
      sscanf(start, ...) 
      start=next+1; 
      char * next = strchr(start,'\n'); 
   }
Re:Parsing can become accidentally quadratic because of sscanf by nitrogen on Monday March 01, 2021 @11:16AM (#26304251)
junk is a character, not a string, though.
Re:Parsing can become accidentally quadratic because of sscanf by kazinator on Monday March 01, 2021 @11:25AM (#26304374)
The valid point is that the junk could be arbitrarily long, and that glibc's sscanf will scan through it in taking the length of the input.

But we are not continuing to scan into the junk here to get more tokens here; we don't have a loop that will cause O(N*N) behavior.

E.g. this could be user input from a form field where they are expected to type a date, and we want to reject that if there is trailing junk. At that point, the user gets an error, and has to fix the input. We don't look for anything in the trailing junk.

Re:Parsing can become accidentally quadratic because of sscanf by jemfinch on Monday March 01, 2021 @11:44PM (#26311978)
Are you not listening to what anyone else is telling you here? Did you not read the article?

It's not about "scanning into junk". The problem would happen if you used scanf to extract integers from a string of `' '.join([1]*1000000)`. Because you would make 1,000,000 scanf calls, and _each_ of those calls would call strlen on the string, quadratically scanning over the string to repeatedly find the end.

In fact, every sscanf is O(size of the string) even when the string is well formed. This is not a well behaved function.

Re:Parsing can become accidentally quadratic because of sscanf by JdeBP on Monday March 01, 2021 @11:24AM (#26304356)
The calls to sscanf() in the preceding post have been edited since xe wrote that. My guess is that xe meant the parameter now named "input".