It Can Happen to You • Hacker News Board

Re: It Can Happen to You

#191

Post by progre » Thu, Mar 04, 2021, 7:45 AM UTC

loeg wrote: post #170

progre wrote: post #156

Earlier quoted context omitted.

There is a standard, sure. But there are also a lot of compilers out there and I would bet that all but a few has either a "this compiles c11 except for [list of unimplemented features]" caveat or non-standard extensions.

> But there are also a lot of compilers out there and I would bet that all but a few has either a "this compiles c11 except for [list of unimplemented features]" caveat or non-standard extensions. Your statement is broadly reasonable. Here's the GP: > Shouldn’t we just come clean and admit to ourselves that there is no such thing as the C standard ? There is a collection of loosely related languages that look similar…

You are right of course. I was thinking specifically about the early PIC Microchip compilers for "C" where the weird banked memory and Harvard RISC architecture made the "C" you wrote for those essentially non-portable even to other 8-bit micros. I think the Microchip marketing was very carefully trumpeting C but not claiming to follow any version of the standard though.

And, the of course, the community around PIC's where almost uniformly on board with writing in assembly anyway.

Re: It Can Happen to You

#192

Post by quelsolaar » Thu, Mar 04, 2021, 7:51 AM UTC

BenFrantzDale wrote: post #53

mkeeter wrote: post #27

Blog author here! Thanks to HN for warning me about sscanf at exactly the right time – within a day of me trying to load some ASCII STLs and noticing it was slow... Linked deep in the Twitter replies [1], there's an open glibc issue about this, dating back to 2014: https://sourceware.org/bugzilla/show_bug.cgi?id=17577 C doesn't have any requirements on the complexity of sscanf, so it might not be a bug per se, but it…

IMO the lack of a complexity requirement is a bug in the C standard. And really it’s a bug in the implementation(s?) too. If it can be done on O(1), shame on library authors for doing it in O(n). If you want programmers to trust library authors, don’t do this to us. Maybe std::from_chars FTW?

This is not a complexity issue with the function. The function is linear to the input, as it should be. The problem is that the implementation does more work then it needs to (it doesn't need the length of the string). It should be linear to the end of parsing not the end of string. The complexity in this case comes from the loops calling it.

Re: It Can Happen to You

#193

Post by ironmagma » Thu, Mar 04, 2021, 7:52 AM UTC

loeg wrote: post #168

ironmagma wrote: post #136

Earlier quoted context omitted.

> ISO-C11 specifies 203 circumstances that cause undefined behaviors. 203 is enough to make almost every line of code questionable. The result of this is that looking at a simple 3 line C program and being asked whether the program terminates is undecidable without knowing which compiler was used. Null dereference for example is undefined behavior, and could cause a termination or not, depending on the implementation…

> 203 is enough to make almost every line of code questionable. The result of this is that looking at a simple 3 line C program and being asked whether the program terminates is undecidable without knowing which compiler was used. This is hyperbole to the point of being nonsensical. > Null dereference for example is undefined behavior, and could cause a termination or not, depending on the implementation, even if it…

> If your C code has UB, it is wrong.

This goes against the sheer notion of UB. If some code was wrong, the standard would say it is not allowed and it would result in a compile error, or at least a runtime error. As it is, the language standards choose to leave it open almost as if to concede that the standard can’t cover every base. UB isn’t wrong, almost by definition. It’s just implementation specific, and that’s my point. We don’t have an overarching C language, we have a hundred or so C dialects.

Re: It Can Happen to You

#194

Post by quelsolaar » Thu, Mar 04, 2021, 7:54 AM UTC

decasia wrote: post #5

It would be nice if it were more common for standard library functions to include algorithmic complexity as part of the standard documentation. Absent that, of course we can potentially read the source code and find out, but I think for the most part we tend to operate based on an informed assumption about what we imagine the algorithmic complexity of a given operation would be. Inevitably, sometimes the assumption i…

There are many implementations of the C standard library and thy may not have the same complexity. In this case the code has the right complexity(linear) but to the wrong n (string length instead of parse length)

Re: It Can Happen to You

#195

Post by jbluepolarbear » Thu, Mar 04, 2021, 7:57 AM UTC

ThatGeoGuy wrote: post #151

Tyr42 wrote: post #54

Earlier quoted context omitted.

Goto based algorithms generally outperform looped algorithms. (They're just more general, you can always implement a loop based algorithm using gotos, but not the other way around)

Not exactly. This is more an artefact of language design. If you convert everything to continuation passing style, then every function call, tail call, recursion, etc. is just as expensive (and expressive) as a GOTO. This is, incidentally, the main "trick" or lightbulb moment in the classic Cheney on the MTA paper by Henry Baker [1]. Now if we're talking specifically in C, then absolutely! But while this intuition ho…

That was a really good short read.

Re: It Can Happen to You

#196

Post by ironmagma » Thu, Mar 04, 2021, 7:59 AM UTC

ncmncm wrote: post #164

ironmagma wrote: post #136

Earlier quoted context omitted.

> ISO-C11 specifies 203 circumstances that cause undefined behaviors. 203 is enough to make almost every line of code questionable. The result of this is that looking at a simple 3 line C program and being asked whether the program terminates is undecidable without knowing which compiler was used. Null dereference for example is undefined behavior, and could cause a termination or not, depending on the implementation…

A good argument for compiling your debug builds with "-fsanitize=undefined".

There is always a fix for your own code but that’s not the problem. The issue is all the millions of lines of code in the wild that are intended to be compiled without that option.

Re: It Can Happen to You

#197

Post by matheusmoreira » Thu, Mar 04, 2021, 7:59 AM 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…

Exactly. The problem isn't the bug itself or the developers who introduced it. The problem is they simply didn't care enough about their billion dollar game to fix the problem over seven years after release until someone got mad enough to reverse engineer the game, figure out why it was so slow and fix it on their behalf.

People will always make mistakes but it's how they deal with them that matters. Gotta have enough pride in one's work to be bothered when it performs badly. Having an user fix their billion dollar project for them just because they couldn't be bothered is just embarrassing.

Re: It Can Happen to You

#198

Post by metafunctor » Thu, Mar 04, 2021, 8:06 AM UTC

Some of the blame should be placed on the "worse is better" dogma. Often it really just means "my library does whatever was easy to implement". It has it's merits, but it's a very leaky abstraction. It's part of why writing good C code is hard: much of the hard stuff is left to the caller, because the library implementation would be more difficult otherwise.

Re: It Can Happen to You

#199

Post by TeMPOraL » Thu, Mar 04, 2021, 8:10 AM UTC

johnfn wrote: post #32

Loving the progression here. Tomorrow, someone’s going to reduce the boot times of macOS by 90% by the same principle. A week from now, someone will prove P=NP because all the problems we thought were NP were just running strlen() on the whole input.

You're joking, but now I'm thinking about the XML we parse at work and the library we're using to do it. We parse a lot of it, but I've always had this vague feeling that it takes a bit too long (given the codebase is C++).

The XML library we use is rather well-known, so if someone found a bug like this there, I'd suspect a general improvement of performance across the board in the entire industry. Efficient Market Hypothesis tells me it's unlikely the library has this problem, but then again, so I thought about AAA videogames, and then GTA Online thing came out.

Re: It Can Happen to You

#200

Post by ironmagma » Thu, Mar 04, 2021, 8:11 AM UTC

loeg wrote: post #187

blackoil wrote: post #182

Earlier quoted context omitted.

Don't know about C, but In Java/C#/Python, you have a standard, a dominant implementation which is compliant to that standard. Few more independent/niche implementations which may not be 100% compliant. Do we have a similar implementation in C?

I think you're maybe overstating the degree of homogeneity in Java/C#/Python. E.g., CPython3 cannot run Python2 code at all, and there are a lot of platform-specific modules and behaviors in the stdlib ("import os"). I don't think Python has any real single standard to the level of detail that C does, although I may be mistaken. For C, on approximately the same platforms, to approximately the same degree: either GCC…

CPython is looked to as the canonical Python. IronPython and PyPy are all modeled after it and aim to behave as closely to it as possible, while CPython is considered the gold standard. Comparing CPython3 and CPython2 is orthogonal to that; one is not trying to implement or emulate the other. You have similar situations with Mono C# imitating Microsoft C# and IronRuby imitating Ruby. If there is a difference, it is considered a deviation from Ruby which is the reference implementation.