Live data from Hacker News

It Can Happen to You

mattkeeter.com

361–370 of 419 posts

Re: It Can Happen to You

#361

Earlier quoted context omitted.

If it's already sorted in the right order, quicksort runs in O(n log n). quicksort is O(n log n) bestcase, O(n*n) worstcase.

Actually, yeah, my original reply was dumb, I forgot quicksort :) It can be n*n for properly-sorted arrays too, depending on pivot selection (for randomized pivot selection, it's n log n).

Yes; random pivot selection is nlogn (unless you are very, very, statistically impossibly, unlucky. Or using very short arrays where it doesn't matter anyway).

But I'm pretty sure data sorted in either direction (i.e., 'reversed' or not, ascending or descending), and taking a pivot from either end, is n^2. It doesn't have to be reversed; you always end up with everything unsorted ending up on one side or the other of the pivot, with each recursive step being just one less comparison than the step prior, meaning it has N-1 + N-2 + ... + 1 comparisons regardless of which way the array is sorted, or N(N-1)/2 comparisons total (Gauss' formula but starting at one less than the total number of items N, since that's the number of comparisons each step), which is O(N^2). There is no cause where it's linear time, unless you are first iterating across the array to select the first pivot that is out of place (which may be a reasonable optimization, but can also be made to apply regardless of what direction the array is sorted).

Re: It Can Happen to You

#362
post #326

Earlier quoted context omitted.

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

If you have a lot of nesting in the XML, and it is formatted for human reading (i.e. indented), you may want to consider not doing that. We had a project where we were creating human-readable versions of the XML (mostly for developer convenience) and then parsing it. When we stopped adding all the extra white space the parsing speed increased a couple of orders of magnitude. (The downside was we no longer had built i…

That's interesting. I can't think of a mechanism why this would give so much of a performance boost, though - rejecting extra whitespace should be just a matter of a simple forward scan against a small set of characters, shouldn't it?

(Or maybe in your case something was running strlen() a lot during parsing, and just the difference in file size explains the boost?)

Re: It Can Happen to You

#363
post #351

Earlier quoted context omitted.

I remember a proof in CLRS which first developed a function that was bounded above by 5 for all conceivable input ("a very quickly-growing function and its very slowly-growing inverse"), and then substituted the constant 4 or 5 into a complexity calculation in place of that function, giving a result which was "only" correct for all conceivable input. The same approach applies to key length requirements for hash table…

>The same approach applies to key length requirements for hash tables with arbitrarily large backing stores. They do not grow as slowly as the CLRS log* function, but they grow so slowly that there are easily identifiable sharp limits on how large they can be -- an easy example is that a hash table cannot use more memory than the hardware offers no matter how the software is written. A backing store with 1TB of addre…

> No, I was using table size exactly as you, to mean the number of elements stored. Is there a reason my comments only made sense under a different definition? It not, be charitable. (And avoid using obscure terms.)

I interpreted your comment to refer to the size of the backing store, because that is fundamentally what a hash key needs to be able to address.

I didn't mean to say that, if you were using it that way, you were doing anything wrong, only that there appeared to be a mismatch.

Re: It Can Happen to You

#364
post #85

Earlier quoted context omitted.

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

Sorry about that; I see the next now in the description of strtod where it is required that the datum is interpreted like a floating-point constant in C, except that instead of the period character, the decimal point character is recognized. Yikes! There is a way to fix that, other than popping into the "C" locale, which is to look up that decimal character in the current locale, and substitute it into the string tha…

> There are functions in the C library without locale-specific behaviors, though, like strchr, strpbrk, strcpy, and their wide character counterparts.

Obviously these string functions are totally fine if you use them correctly, and their implementations should be fairly optimal. However, I do think they put a lot of onus on the programmer to be very careful.

For example, using strncpy to avoid buffer overflows is an obvious trap, since it doesn’t terminate a string if it overflows... strlcpy exists to help deal with the null termination issue, but it still has the failure mode of truncating on overflow, which can obviously lead to security issues if one is not careful. strcpy_s exists in C11 and Microsoft CRT, though I believe Microsoft’s “secure” functions work differently from C11’s. These functions are a bit better because they fail explicitly on truncation and clobber the destination.

OpenBSD arguably has some of the best security track record of all C projects and I still feel weary about their preferred mechanism for string copying and concatenation (strlcpy and strlcat.) I feel strlcpy and strlcat are both prone to errors if the programmer is not careful to avoid security and correctness issues caused by truncation, and strlcat has efficiency issues in many non-trivial use cases.

While there are obvious cases where dynamically allocated strings of arbitrary length, such as those seen in C++, Rust, Go, etc. can lead to security issues, especially DoS issues, I still feel they are a good foundation to build on because they are less prone to correctness issues that can lead to more serious problems. Whether you are in C or not, you will always need to set limits on inputs to avoid DoS issues (even unintentional ones) so I feel less concerned about the problems that come with strings that grow dynamically.

One of the biggest complaints about prefix-sized strings/Pascal style strings is that you can’t point into the string to get a suffix of the original string. However, in modern programming languages this is alleviated by making not only dynamic strings a primitive, but also string slices. (Even modern C++, with its string_view class.) String slices are even more powerful, since they can specify any range in a string, not just suffixes.

So really locale and strtod are just little microcosms of why I am weary of C string handling. Clearly you can write code using C string functions that is efficient, secure and correct. However, I feel like there are plenty of pitfalls for all three that even experienced programmers have trouble avoiding sometimes. I don’t actually know of a case where locale can break strtol, but it doesn’t matter too much, since anyone can write a decent strtol implementation (as long as they test the edge cases carefully...) strtod though, is not so easy, and I guess that means apps are best off avoiding locales other than C. In a library though, there’s not much you can do about it. At least not without causing thread safety issues :) In other languages, aside from dynamic strings and string slices, locale independent string functions is also typically the default. Rust’s f64::from_str, Go’s strconv.ParseFloat, C++’s std::from_chars and so forth. It’s not too surprising since a lot of the decisions made in these languages were specifically made from trying to improve on C pitfalls. I do wish C itself would also consider at least adding some locale independent string functions for things like strtod in a future standard...

Re: It Can Happen to You

#365
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 kid. But truer things are said in jest.

> ...Tomorrow, someone’s going to reduce the boot times of macOS by 90% by the same principle.

My 2019 MacBook often pauses when I connect the charging cable. Sometimes it just seizes, requiring a hard bounce.

Clearly there's a contended lock buried deep. Something non-obvious.

I'm certain everything these days has dozens of hidden quadratics and contended locks.

Which is one of the reasons I'm excited for stuff like structured concurrency (Java's Project Loom) and retoolings like systemd becoming the norm.

Ages ago I worked on kitchen sink app that had a very finicky startup. Any breeze would break it. Much consternation by mgmt. Apparently if we only clapped louder, Tinkerbell would fly. I couldn't take it any more. LARPing as a bulldozer, I replumbed the innards, changing from something like initd to be more like systemd with some lazy loading for good measure. Voila!

Back to GTA. The failure here is the product owner didn't specify a max load time, and then hold the team to it. Devs will mostly do the work that's expected of them. If load time wasn't measured (and managed), no one is going to bother with expunging sscanfs.

Re: It Can Happen to You

#366
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…

Thing is that they didnt ship it that way. Back when it came out the loading screens were "fast". Things just grew out of proportion with the exponential increase of new items in the online mode.

No they weren’t GTAV had terrible loading times at launch.

Re: It Can Happen to You

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

Forget pride in your work, this is literally costing rockstar money. It may be hard to estimate, but I’m sure it was in the hundreds of dollars a day category at some point. Shaving milliseconds off of loading time has real effects in the web world and so at a previous job we made sure to evangelize that fact to management and did what we could to tie it to revenue as well as other KPI in order to get this kind of thing prioritized. I’m just surprised there isn’t a PM at rockstar pushing hard to reduce load times.

Re: It Can Happen to You

#368

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…

Do you explicitly indicate the type of the array? E.G., `let array: [Bazinga] = [ … 70k elements …]` instead of `let array = [ … 70k elements …]`.

I will try giving it an explicit type when I’m on the computer again. Would be nice if that turns out to make it behave nicely.

Re: It Can Happen to You

#369
post #62

Earlier quoted context omitted.

Recursion is a form of looping. I think it's more clear if you say imperative algorithms.

In what sense is recursion a form of looping? I'm thinking of the memory model for each - one mutates some variables (at least some sort of index, unless you're doing an infinite loop) in a single frame, while the other accumulates function calls and stack frames until you bottom out, then return values are "folded" back up. Semantically, from a caller's perspective, they can achieve the exact same thing, but aside f…

> In computer science, a loop is a programming structure that repeats a sequence of instructions until a specific condition is met.

That's the general definition at least I've always been most aware of. I don't want to claim it is the most common one, cause I don't really have numbers and who is the authority on comp-sci definitons? But I do feel it is at least a somewhat common academic definition for looping.

That would mean that recursion is a form of looping. The distinction between recursion and imperative loops would then be a matter of implementation and exposed programmer interface. Similarly like others have said, goto's can also be used to implement similar loops.

And in that regard, there are variants of recursion as well, such as tail-call recursion which has a similar memory model as what you described and differs only to an imperative loop in the programming interface it exposes.

Re: It Can Happen to You

#370

Earlier quoted context omitted.

Suppose it is wrong, though; that implies a good chunk of C code out there is wrong code. Yet it compiles and people are using it, which means that their code does not conform to the standard. Just as wrong math isn’t math at all, wrong C is not C. People are therefore writing code whose runtime characteristics are not defined by any standard. Thus it is not actually C, it’s whatever compiler they’re using’s language…

Working and usable program typically contains wrong code of various kinds. Nontrivial bugfree programs are extreme rarity. > wrong C is not C buggy C is still C, if on discovering undefined behavior people treat it as a bug - then it is just C program with some bugs in it. If on discovering undefined behavior people treat it acceptable people treat it differently "on my compiler it does XYZ, therefore I will knowingl…

It's not really a bug if it works as the way it was intended by the developer. It just exists in a world outside the law, makes its own laws based on what works, a renegade program. Most people don't read the C standard or care what it says (and it costs money, so it's almost as if reading it is discouraged), so it seems very likely the default human behavior is just to use this UB.
Post reply on HN