121–130 of 419 posts
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.
Earlier quoted context omitted.
I just can’t figure out the exact code.
I think your code would be pretty much the same, sscanf, strlen and all. The main differences would be the standard library's implementations of strlen and whatever function you use to read the file into a string in the first place.
str_t json = loadfile();
size_t offset = random();
sscanf(“%d”, ?);
It’s only pretty much the same until you try to write actual code with a new idea in mind.
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…
> It would be nice if it were more common for standard library functions to include algorithmic complexity as part of the standard documentation. Isn’t the point of standard library functions to define the contract and not implementation constraints? In other words, if algorithmic complexity is a significant concern, perhaps a standard library function is not a suitable choice.
Earlier quoted context omitted.
Are there complexity guarantees for std::istream::operator>>?
No, or at least not in general, because you can overload it for your custom types with whatever terrible implementation you like.
Earlier quoted context omitted.
All of the C++ algorithms list complexity guarantees, I believe. This saga stunned me to learn that C doesn’t seem to do this.
It's easy to forget that the original C standards were largely codifying existing practice during an era when using gets() [1] was existing practice. The world wasn't quite ready for Ada, I guess. Best-laid plans of mice and men etc. etc.. Also, keep an eye out for "amortized" complexity. This does have a legitimately rigorous definition, but for latency-bound paths it can practically amount to "O(whatever), except f…
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".
So many times, in higher level code, it's seeing a foreach loop in a foreach loop, and the nested loop is calling an API or re-rerunning the same database call 5000 times. Move things around or just use a cache... and instant 1000%+ speedup. I've seen this too many times to count, often in apps and on sites that are in fairly heavy use. The answer is often to scale up and pay for 10x more server capacity to handle th…
My fav optimization story: A few years back, I was doing some geographic calculations. Basically building a box of lat/lngs and getting all the points within that box. It was slow. Weirdly slow. I made sure the lat and lng of the records were in the index, but it was still slow. More testing revealed that the way I was passing the lat/lng into the query was causing those values to be converted to strings, which were…
At once place our end of month billing was getting slower and slower over the course of months, from one hour out to about twelve and it had to baby sit and run in batches in order to not bring the whole database to it's knees. We couldn't change the mess of legacy classic asp of course, but adding a couple of actual date columns calculated from the string fields on insert/update bought the whole process down to seconds.
For example, if you do something like this:
int n;
sscanf("9999999999999999999999999", "%d", &n);
> ... the result of the conversion is placed in the object pointed to by the first argument following the format argument that has not already received a conversion result. If this object does not have an appropriate type, or if the result of the conversion cannot be represented in the object, the behavior is undefined.
You can control the appropriate type by writing the call directly, but you can't guarantee that the result can be represented unless you have control over the input.
Remember that in C "undefined behavior" doesn't mean that your program will fail, or will crash, or will tell you there was a problem. It means that a conforming implementation can do literally anything. In the worst case, it will do what what you expect until it fails at the most inconvenient possible moment.
Now most implementations will probably do something sane, like setting a floating-point object to infinity or an integer object to some arbitrary value, but the language doesn't guarantee anything.
If you want to write safe code, you can extract a substring that represents a number and pass it to one of the strto*() functions, which do have well defined behavior on overflow. (But I couldn't tell you exactly what that behavior is without looking it up.)
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…
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.
[1] https://cstheory.stackexchange.com/questions/5004/are-runtim...
Earlier quoted context omitted.
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?
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 and that collectively we call C, but really they’re all completely different and share almost no interoperability or common characteristics. And those standards that do exist provide almost no ability to reason about your code including things like ord…
Here's the latest revision of the standard: https://www.iso.org/standard/74528.html
C has had a well-defined memory model since C11, I believe (re: "ordering of statements").
(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…
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...