Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

It Can Happen to You

mattkeeter.com

Post reply on HN
Print view View original

81–90 of 419 posts

Re: It Can Happen to You

#81

Post by kevingadd »

usefulcat wrote: post #55
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…

I would bet that a lot of games receive a lot less development effort after release. Most of the devs probably got moved on to something else (sequel, or maybe a completely different title).

GTA Online is a live game that pulls in over half a billion USD per year in revenue. They release new content on a regular basis. It's actively developed, they just don't care (my guess would be that defects were filed against this on a regular basis and fixing it was never prioritized)

Re: It Can Happen to You

#82

Post by kevingadd »

wruza wrote: post #74
tdeck wrote: post #10

This just makes me think that null-terminated strings are the bad gift that keeps on giving. If we were to design an OS, language, or standard library in 2021 (or even 1999) we probably wouldn't use them, but we're stuck with this relic of a former era.

Ok, let’s assume that 10mb json source was loaded into a not null-terminated opaque struct str_t {size_t; pchar;}. You have to parse a number from a position `i’ and you have (double parse_number(str_t)). Next obvious step?

You can keep the existing sscanf function and now strlen is O(1) so the bug is gone. Any questions?

Re: It Can Happen to You

#83

Post by perl4ever »

harikb wrote: post #30
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.

I would argue the reverse - there is higher chance of this accidentally quadratic problems with more abstraction layers, convenience functions, and advanced language syntax. But I agree we shouldn't write parsing in C, but for other reasons :)

I say there's an equal chance, and it's equally easy to fix, but a high level language provides fewer distractions and temptations to work on small optimizations which don't matter. Getting in the weeds with the details is how you lose sight of the big picture. And allocate your time poorly.

Re: It Can Happen to You

#84

Post by jacobajit »

chii wrote: post #67
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…

> standard library functions to include algorithmic complexity as part of the standard documentation. it would be acceptable to have a graph of the input size vs time, and this graph could be autogenerated using a testbed that is also used by unit testing! two birds one stone!

I don't think we could come up with a standard x axis bounds for such a graph, since n=1000, or 1,000,000 may not be zoomed out enough to showcase the behavior approaching infinity.

Re: It Can Happen to You

#85

Post by jchw »

kazinator wrote: post #18
jchw wrote: post #8

It is a good opportunity to mention that you should not use strtod/strtol either if you can help it, since they are impacted by locale. Exactly what to use instead is a bit of a tough nut to crack; you could extract musl’s floatscan code, or implement the Clinger algorithm yourself. Or, of course, use programming languages that have a more reasonable option in the standard library...

I see you are reiterating this point raised in the previous discussion several days ago, but I don't thing it is particularly well grounded. ISO C allows strtod and strtol to accept, other than in the "C" locale, additional "subject sequence forms". This does not affect programming language implementations which extract specific token patterns from an input stream, which either are, or are transformed into the portab…

I can't really understand what you mean. You can validate yourself that parsing with strtod will break if your system's locale is set to a locale where the decimal separator is a comma ',' instead of a period '.' - as an example, most European locales. Whether or not strtod will try to magically fall back to "C" locale behavior is irrelevant because it is ambiguous. For example, what do you do if you are in Germany and you try to parse 100.001? Is it 100001?

strtod also doesn't guarantee round-trip accuracy that you can achieve when you use Steele & White and Clinger. All in all, I really think it is just not a good idea to use the C standard library for string operations.

Re: It Can Happen to You

#86

Post by wruza »

kevingadd wrote: post #82
wruza wrote: post #74

Earlier quoted context omitted.

Ok, let’s assume that 10mb json source was loaded into a not null-terminated opaque struct str_t {size_t; pchar;}. You have to parse a number from a position `i’ and you have (double parse_number(str_t)). Next obvious step?

You can keep the existing sscanf function and now strlen is O(1) so the bug is gone. Any questions?

I just can’t figure out the exact code.

Re: It Can Happen to You

#88

Post by chihuahua »

decasia wrote: post #14
beaconstudios wrote: post #11

Earlier quoted context omitted.

personally, I think I wouldn't even bother to check the algorithmic complexity of every external function I call. I'd just use the logical choice (like sscanf) and only consider optimising if things started to slow down and profiling the application highlighted it as a bottleneck.

Yes, I absolutely think profiling and then only optimizing the actual problems is always a sound choice. I don't check the docs for every library function I use. I'm just saying, it wouldn't hurt if, when you do read the docs for standard library functions, the algorithmic complexity was mentioned in passing.

In principle, that sounds good. But then it can happen that you profiled when N=1000 and it seems fine. Then a few years later (like in GTA), N has grown to 63,000 and it's no longer fine. It seems unlikely the developer will go back and profile it again. Also, I think the original Windows Update algorithm for figuring out which updates you needed to download started out fine, but 20 years later it turns out it's quadratic and now there are tens of thousands of updates, so it becomes almost impossible to install XP SP2 from a CD and have it update itself.

Re: It Can Happen to You

#90

Post by [deleted] »

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?

[deleted]
Post reply on HN