141–150 of 419 posts
Could the sscanf bug also be a security issue? Most C strings are null terminated, but I could imagine using sscanf to read outside of bounds due to the null-seeking behavior on a non-null terminated array. If it is an issue, I think it probably can’t be used for more than a DoS or a timing attack. That said after meltdown & co anything is possible.
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 am a C programmer who have implemented string to number parsing for this very reason. I know exactly what it does and how fast it is.
If you do use code you didn't write, The chance of a standard library being poorly implemented, is probably lover then most other libraries, so picking a non standard lib as a grantee against bad performance seems misguided.
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…
Earlier quoted context omitted.
C++'s std::string_view is essentially your struct. You can check the methods it provides.
Yes, I’m aware of it. I’m just tired by these layman’s “oh that’s another reason to ditch C strings”, when it has nothing to do with it. Working with offsets requires handling offsets and lengths, be it explicit ‘off’ and ‘n’ or a string_view. All that is needed in this case in C is snscanf (note the ‘n’), so that it would know its limits apriori, like snprintf does. Sadly that ‘n’ never made it into the standard.
Earlier quoted context omitted.
...I fully plan to use "O(whatever)". Not sure for what. But, yes. (naive) Quicksort's amortized complexity being O(nlogn), but its O(n^2) on already sorted data, is all I ever needed to learn to take away that lesson. When sorting already sorted data is worse than sorting randomized data, it's a quick realization that "amortized cost" = "read the fine print".
Quicksort as O(n log n) is not amortized complexity, but average runtime for random data.
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...
Earlier quoted context omitted.
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...
Can you point me towards some source code where a human can't find the algorithmic complexity?
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…
Actually, the worst case possibility is that your program will become Skynet, enslave humanity for 10000 years, collapse all stars in the universe into black holes, and significantly accelerate processes such as the heat death of the universe.
Earlier quoted context omitted.
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 qua…