It Can Happen to You • Hacker News Board

Re: It Can Happen to You

#251

Post by [deleted] » Thu, Mar 04, 2021, 9:57 AM UTC

TeMPOraL wrote: post #235

matheusmoreira wrote: post #197

Earlier quoted context omitted.

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 enoug…

Yeah, but I think it puts to test the usual mantra of "write now, profile later, and optimize the bottlenecks". As reality repeatedly shows, developers often don't progress past the "write now" part, even if performance issues are crippling and annoying users to no end. We can and should do better. What this topic also is, is a reminder that with null-terminated strings and enough abstraction layers, you can easily m…

[deleted]

Re: It Can Happen to You

#252

Post by beaconstudios » Thu, Mar 04, 2021, 9:59 AM UTC

gifnamething wrote: post #246

beaconstudios wrote: post #227

Earlier quoted context omitted.

No, spending time optimising areas of the code that will never become bottlenecks is the waste of time.

Bugfixing isn't optimisation

The line between bug fixing and faffing around is context based, and there are efficient and inefficient ways to both fix bugs, and faff around. Profiling every stdlib function is probably both inefficient and faffing around unless your circumstances dictate its a worthwhile and effective (there aren't better alternatives to reach the goal) effort.

Re: It Can Happen to You

#253

Post by Gibbon1 » Thu, Mar 04, 2021, 9:59 AM UTC

codetrotter wrote: post #247

I am writing an app for iOS in Swift and I have an array of structs with some 70,000 elements or thereabouts and for some bizarre reason the compiler uses so much memory if I define it as such directly in the source, that I run out of memory. So instead as a workaround for now I am storing the data as a JSON string that I parse at runtime. It’s very sad, but it’s the only option I had because I have a ton of other co…

Your story reminds me of watching a modern CAD program run out of memory and barf when trying to import a DXF file with a few thousand elements.

Re: It Can Happen to You

#254

Post by erik_seaberg » Thu, Mar 04, 2021, 10:00 AM UTC

thaumasiotes wrote: post #244

iainmerrick wrote: post #234

Earlier quoted context omitted.

Calculating the key may take longer for the long string Right, that’s exactly what they are warning about. Not typical. e.g. Java takes the hash key of an object to be its address in memory No, that’s just the base implementation in Object (and arguably it was a bad idea). All useful “value type” classes will override it with a real hash of the content, including String. There are some cases in Java where you do want…

> All useful “value type” classes will override it with a real hash of the content Well, this is necessary for a lot of sensible things you'd want to do with non-numeric value types as hash keys... > including String ...except String is something of an intermediate case. There are loads of use cases where what you're really using is a set of constant strings, not variables that contain arbitrary character data. In th…

Java does intern string literals and constants, but you can’t rely on reference equality unless you intern every string you create at runtime by formatting or decoding, and it isn’t specified whether that creates strong references that will never be GC’d.

Re: It Can Happen to You

#255

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

Honestly, I don't know why people store floats in anything other than binary. IEEE 754, or bfloat16, if you don't want all that precision is so much more compact & efficient to parse. The amount of work the computer does to convert text floating point to binary representations, and the potential for there to be subtle differences/bugs in the encoding are just... tremendous.

Re: It Can Happen to You

#256

Post by Gibbon1 » Thu, Mar 04, 2021, 10:07 AM UTC

ajkjk wrote: post #153

_kst_ wrote: post #127

There's a bigger potential problem with the *scanf() functions than performance. They are inherently unsafe for reading numeric input. For example, if you do something like this: int n; sscanf("9999999999999999999999999", "%d", &n); the behavior is undefined. As the C standard says: > ... the result of the conversion is placed in the object pointed to by the first argument following the format argument that has not a…

Obligatory: it is flabbergasting that this is a quality of language that is still in active use.

It's even more flabbergasting that all these problems haven't been fixed.

Re: It Can Happen to You

#257

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

tux3 wrote: post #15

The moral of the story, as far as I'm concerned: do NOT parse strings in C! Use a library, prefferably in a higher-level language. C string handling is a mess of viciously surprising APIs, juggling those particular footguns is almost certainly not your least bad option.

Wrong conclusion. The problem is the broken C string library in POSIX. Don't use it! Wrong design. Zero-termination is too fragile and the cause of the evil.

Rather use buffers with known lenghts, and for strings you need to known the string (=unicode) rules. Nobody does that. Know libunistring. I have my own, because libunistring is too slow, but know it.

For my string libraries I rather follow the STL, with ranges/views and boehmgc core. const vs dynamic strings. So I will not step into the accidental strlen and buffer-overflow trap.

E.g. For input buffers know if they are zero-terminated and const. With the GTA post I pointed out the libfuzzer design flaw, giving you an ASCII input buffer which is not zero-terminated. Even strtol/strtod cannot be used then. You need to copy the buffer, terminate it, and then you can use the broken string libc. Not talking about sscanf, which I usually use only as sscanf_s if available. Or _snscanf/_snscanf_s. Microsoft does many things wrong, but its libc is far superior to glibc, bsd or musl. musl is better than glibc, but also lacks in this regard.

Re: It Can Happen to You

#258

Post by ummonk » Thu, Mar 04, 2021, 10:23 AM UTC

I agree with the "it can happen to you" bit and the fact that this is largely the fault of C's poor documentation (e.g. not mentioning algorithmic complexity) and poor design choices when it comes to strings (you get similar issues with buffer overruns when using standard library functions).

That said, the GTA thing was far more noteworthy because apparently the GTA developers hadn't bothered to profile loading times and get to the bottom of why exactly game load was taking such a ridiculously long time.

Re: It Can Happen to You

#259

Post by ummonk » Thu, Mar 04, 2021, 10:25 AM UTC

thaumasiotes wrote: post #184

alexchamberlain wrote: post #166

Earlier quoted context omitted.

It makes me chuckle when hash maps are stated to be O(1) insertions. Which is true, in respect to the number of items in the map, assuming the map doesn't need resizing and there isn't a hash collision... but it's generally not true in respect to the key length. (I think most implementations are O(ln), where l is the length of the key and n is the number of inserted items, assuming the hash function is O(l) - the _am…

> assuming the map doesn't need resizing This isn't a big difficulty; it's still amortized O(1). > and there isn't a hash collision This is a real difficulty, unless you allow map resizing. Luckily, we do. > but it's generally not true in respect to the key length. OK, but in most cases the key length is constant, making anything that depends on the key length O(1) by definition.

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

Re: It Can Happen to You

#260

Post by rcxdude » Thu, Mar 04, 2021, 10:29 AM UTC

adrianN wrote: post #128

epr wrote: post #34

Earlier quoted context omitted.

Keeping track of algorithmic complexity would be nice as a language and/or static analysis feature. If you wanted to be exact or do it for a language with complex metaprogramming I assume it would be a nightmare to implement. Absent those complications and especially if you always reduced it to O(1), O(n), O(log(n)), etc it might not even be that difficult given the potential advantages.

There is no general solution to deciding whether a program is O(n^k).[1] So either your static analysis won't know the answer for some programs or report a wrong bound, or report a ridiculous overestimate. [1] https://cstheory.stackexchange.com/questions/5004/are-runtim...

So? Static analysis doesn't need to always produce an answer, only produce an answer most of the time. The question isn't whether you can do it in general for all inputs (this is not possible for basically anything you would want to know), it's whether you can do it enough of the time on the kind of code which people actually write.