It Can Happen to You • Hacker News Board

Re: It Can Happen to You

#311

Post by matkoniecz » Thu, Mar 04, 2021, 1:16 PM UTC

ironmagma wrote: post #226

matkoniecz wrote: post #217

Earlier quoted context omitted.

I always though that code with UB is wrong, and UB allows implementation to deal with it on its own way (it is allowed to ignore it, stop program, corrupt memory, delete hard drive contents...). So if your code has UB then it is wrong, one thing not specified in standard is exact consequences of that. (yes, in some hacks one may rely on UB behaving in some way in some circumstances - it will be hack)

Suppose it is wrong, though; that implies a good chunk of C code out there is wrong code. Yet it compiles and people are using it, which means that their code does not conform to the standard. Just as wrong math isn’t math at all, wrong C is not C. People are therefore writing code whose runtime characteristics are not defined by any standard. Thus it is not actually C, it’s whatever compiler they’re using’s language…

Working and usable program typically contains wrong code of various kinds.

Nontrivial bugfree programs are extreme rarity.

> wrong C is not C

buggy C is still C, if on discovering undefined behavior people treat it as a bug - then it is just C program with some bugs in it.

If on discovering undefined behavior people treat it acceptable people treat it differently "on my compiler it does XYZ, therefore I will knowingly do ABC" then it is becoming something else.

Re: It Can Happen to You

#312

Post by layoutIfNeeded » Thu, Mar 04, 2021, 1:19 PM UTC

thaumasiotes wrote: post #272

ummonk wrote: post #259

Earlier quoted context omitted.

Key length must necessarily be O(log(N)) to be able to identify N different keys.

This is O(1) where N is constant.

Yes. Everything is O(1) if N is constant, including log(N), N^2, 2^N, N!, etc. That's a tautology.

Re: It Can Happen to You

#313

Post by TheOtherHobbes » Thu, Mar 04, 2021, 1:20 PM UTC

BenFrantzDale wrote: post #77

CGamesPlay wrote: post #72

Earlier quoted context omitted.

And maybe, in a decade or so, the man page for these functions will list their algorithmic complexity! That was the most interesting takeaway from this article, for me at least. I have only seen a one or two libraries that actually list this in their documentation.

All of the C++ algorithms list complexity guarantees, I believe. This saga stunned me to learn that C doesn’t seem to do this.

That's because C is just a wrapper for machine code on a cheap PDP-11, and cheap PDP-11s didn't have enough RAM to do complexity.

Re: It Can Happen to You

#314

Post by JdeBP » Thu, Mar 04, 2021, 1:23 PM UTC

tshaddox wrote: post #41

I didn’t follow the original story or comments about GTA, but based on the description in this article, I wouldn’t be surprised that this sort of problem could happen to any coder of any experience level and I wouldn’t give them any grief, but I would be surprised that the problem would be live in production for a very long time without ever having been profiled. Surely seeing JSON parsing taking more than 70% of the…

The problem was reported in the comp.lang.c newsgroup on Usenet in 2002. This very discussion mentions the GNU C library bug report that has been around since 2014. It was reported in RapidYAML in 2020. This problem has been noticed in production, several times over, and yet still lives to this day.

* https://news.ycombinator.com/item?id=26302915

Re: It Can Happen to You

#315

Post by JdeBP » Thu, Mar 04, 2021, 1:33 PM UTC

desertrider12 wrote: post #130

moonchild wrote: post #56

(Originally on lobsters[0].) I maintain my original position that sscanf calculating the entire length of its input is absolutely ridiculous. Are *scanf difficult to use safely, not very robust, and somewhat baroque? Yes. Should sscanf("%f") be a correct (not performance-killing) way of reading floats? Also yes. (Though aside: the OP seems to be reading data from files, so they could have just used fscanf, which has…

Reading this article was a surprise for me, I didn't know of this issue at all. But this is pretty ridiculous. If it's possible to write scanf, which matches chars from a stream, why can't sscanf just do the exact same thing but check for '\0' rather than EOF...

It can, and the people who only check a few well-known open source C library implementations miss that there is quite a range of other C library implementations out there that do this very thing, from P.J. Plauger's through OpenWatcom's and Tru64 Unix's to mine. (-:

* https://news.ycombinator.com/item?id=26300532

Re: It Can Happen to You

#316

Post by mkeeter » Thu, Mar 04, 2021, 1:40 PM UTC

jedimastert wrote: post #299

Quick question: At the top of the parser they define const char VERTEX_STR[] = "vertex "; And a few lines in data += strlen(VERTEX_STR); Would parsers optimize this out? Seems like an easy win to replace that with a "7" (or a constant or something), although I don't know how much of a win it would be.

I was trusting the compiler on this one, but after someone asked this question on Twitter, I doubled-checked: https://cppx.godbolt.org/z/fhTGcx

Sure enough, it compiles down to "add rax, 7"

Re: It Can Happen to You

#317

Post by quelsolaar » Thu, Mar 04, 2021, 1:43 PM UTC

tpetry wrote: post #188

I don‘t get the heat of this topic. Yes they wrote some very slow code because it‘s easy to shoot in your foot with scanf. It‘s nothing new that most software could be heavily optimized by just benchmarking slow parts. There is no reason for this shit storm than to feel better than other developers. The real problem is that they shipped a game with a loading screen which is taking minutes and not looking whether they…

I think that its fairly notable that functionality, that have been arround for so long, and have been implemented so many times, is as poorly implemented as this.

Usually you can count on the C std lib to be very optimized. Many std functions like memcpy are even intrinsics in compiles, and than means they are literally faster then its possible to write in C since someone has gone in and hand optimized the assembler.

Re: It Can Happen to You

#318

Post by thaumasiotes » Thu, Mar 04, 2021, 1:56 PM UTC

layoutIfNeeded wrote: post #312

thaumasiotes wrote: post #272

Earlier quoted context omitted.

This is O(1) where N is constant.

Yes. Everything is O(1) if N is constant, including log(N), N^2, 2^N, N!, etc. That's a tautology.

> Everything is O(1) if N is constant, including log(N), N^2, 2^N, N!, etc.

Not even close. 2^k is not O(1) by virtue of N being constant. Only 2^N.

This has been covered above. It is more common to consider the complexity of hash table operations in terms of the number of operations, or the size of the table; the size of the key is very often constant. These are different variables; the constant size of the key does not trivialize the complexity of inserting N items each with a constant key size.

Re: It Can Happen to You

#319

Post by mkeeter » Thu, Mar 04, 2021, 1:56 PM UTC

scaramanga wrote: post #185

mkeeter wrote: post #40

Earlier quoted context omitted.

Touché – after all, disk-to-RAM is hundreds of MB/s, and faster if it's cached! In practice, I'm racing mesh loading against "how long does the OS take to give you an OpenGL context", which is rarely below 160 ms (longer if it has to switch from integrated to discrete GPU).

Great data-point, I was wondering what the costs of all that would be. How do you measure when the frame is done, are you waiting for a vsync?

It's self-reported by the logging system after glfwShowWindow() returns for the first time, so probably not 100% accurate, but reasonably close.

A truly fancy system would be something like Tristan Hume's keyboard-to-photon latency system: https://thume.ca/2020/05/20/making-a-latency-tester/

Re: It Can Happen to You

#320

Post by simias » Thu, Mar 04, 2021, 2:02 PM UTC

I think the really embarrassing part for Rockstar is that they didn't bother to investigate what took 5+ minutes to load in their star product, a simple profiling would've made the issue obvious. So either they knew and they didn't care, or they didn't know and they didn't care.

That being said both for GTA and for TFA the issue is a very similar sscanf call:

     sscanf(data, "%f", &f);

I already posted a similar comment in the GTA story but I really want to emphasize it: scanf is almost never the right tool for the job, and it's definitely not the right tool in this situation. Just use strtof. That's literally what it's for. String to float. There. Done.

Scanf is crappy and if it were up to me would've been deprecated a while ago. I can sort of see using it for a quick one-off "script", for instance to parse user input, but seeing it in the middle of a program will always raise a huge red flag for me.

Use strtok_r if you need to split a string, then parse every entry individually. It's more robust, more flexible (you can parse custom types and formats that way) and allows for much better error handling and diagnostics. And of course it's also usually vastly faster.

Scanf is an antipattern in my opinion. I literally never use it and I'm better off for it. The last time I interviewed for a C coder position I managed to answer the full C test quizz except for the one question regarding scanf. That's how much I don't use it.

I think it's even worse for developers who come from higher level languages and (reasonably) expect to be able to deserialize data easily. You simply can't do that in C, the type system and general philosophy of the language won't let you, but scanf may convey the illusion that it's sort of possible. Don't believe its lies.