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

231–240 of 419 posts

Re: It Can Happen to You

#231

Post by Guillaume86 »

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…

The premise of the post is wrong, from what I read here and on reddit the people were rightfully complaining about the lack of reaction of Rockstar, not the initial bug that could happen to most people.

Re: It Can Happen to You

#232

Post by TeMPOraL »

geerlingguy wrote: post #52

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…

In a project I worked on few years ago, we had persistent performance problems, present for a long time before I showed up. One of the first things I did when I joined the team was do some unsolicited statistical profiling and narrow it down to database interactions. Since we were using a custom-written connector to a graph database, we assumed it's the connector, or the JSON-based API it's using.

The issue got on the back burner, but it bugged me for a long time. I was later writing some performance-intensive number crunching code, and ended up writing a hacky tracing profiler[0] to aid my work. Having that available, I took another swing at our database connector issue...

And it turned out the connector was perfectly fine, its overhead was lower than the time the DB typically spent filtering data. The problem was, where I expected a simple operation in our application to do a few DB queries, it did several hundreds of them! Something that, for some reason, wasn't obvious on the statistical profiler, but it stood out on the full trace like a sore thumb.

I cut the run time of most user-facing operations by half by doing a simple tweak to the data connector - it turns out even a tiny unnecessary inefficiency becomes important when it's run a thousand times in a row. But ultimately, we were doing 100x as many queries as we should have, nobody noticed, and fixing it would be a huge architecture rework. We put it on the roadmap, but then the company blew up for unrelated reasons.

I sometimes think that maybe if we tracked and fixed this problem early in the development, our sales would have been better, and the company would have been still alive. For sure, we'd be able to iterate faster.

--

[0] - https://github.com/TeMPOraL/tracer

Re: It Can Happen to You

#233

Post by imtringued »

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

Wow, the problems are so deep that no human should ever use sscanf again. It's just as bad as gets() because there is no way for the programmer to deal with the error case.

Re: It Can Happen to You

#234

Post by iainmerrick »

thaumasiotes wrote: post #220
TeMPOraL wrote: post #201

Earlier quoted context omitted.

I'm guessing GP means the complexity guarantee sidesteps the complexity of the hashing function. It probably doesn't matter all that much in typical case - I'm guessing 80-90% of hash map use is with very short strings.

Short strings, long strings; they're going to use the same key length. Calculating the key may take longer for the long string, if you're basing the hash on the contents of the string[1], but the key won't end up being a different size. The md5 of a 3-byte string is 16 bytes and the md5 of a 40GB string is also 16 bytes. [1] Not typical. e.g. Java takes the hash key of an object to be its address in memory, which doe…

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 to use IDs instead of values as your map keys, but they’re rare.

Re: It Can Happen to You

#235

Post by TeMPOraL »

matheusmoreira wrote: post #197
tpetry wrote: 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…

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 make a O(n^2) or O(n^3) out of something you thought is O(n). I technically knew this (there was a popular article about it many years ago, I think by Joel Spolsky, but I can't find it now), but I didn't bother to look out for it in my current project. Thanks to this debacle, I'll do a performance review looking for "accidental quadratics", and I'm guessing many other developers will do it too. So it's a win!

Re: It Can Happen to You

#236

Post by TeMPOraL »

beaconstudios wrote: post #230
TeMPOraL wrote: post #208

Earlier quoted context omitted.

I personally would, if it was listed in documentation. Doing stuff and profiling later is the right general approach to performance optimization. But what's better is not doing stupid mistakes in the first place, if they are trivial to avoid. To achieve that, you need to know the complexity guarantees of functions and data structures - or at least their ballpark (like, "this could be O(n) or perhaps O(n logn), defini…

Part of the issue in my mind is that big O complexity values don't (can't?) tell you the point of inflection, if they are nonlinear. Sscanf could be O(N^10) (does the rule about ignoring the coefficient also apply to the exponent?) but if it only starts to hurt your application at the point of 10tb string reads then it's still unimportant. I do agree that people often take "don't optimise early" as licence to not mak…

I agree. And I'd personally probably trip over it too, if I used C functions much (I use C++ standard library equivalents, and I'm going to recheck string parsing code in our project now, because we may have that same problem, just with different API!). strlen() in a loop is something that can sneak up on you by virtue of having too many layers of abstraction - scanf() family being one of them.

But what I'm saying is, documenting big O complexity is useful, even if imperfect (and if the function has "tricky" complexity, the conditions where it gets bad should be documented too!).

> Sscanf could be O(N^10) (does the rule about ignoring the coefficient also apply to the exponent?) but if it only starts to hurt your application at the point of 10tb string reads then it's still unimportant.

Sure, but then applications grow, functions get reused. Iff it's trivial to spot and replace O(N^10) Sscanf with a O(n) alternative, I'd want to know the complexity and do the replacement immediately - otherwise, you may discover two years later that the company is investing employee-years into horizontally scaling your application as it's slow under workload, where fixing that one thing would let it run that same workload on a laptop, on a single core.

(This is not a joke, there are "big data" stories like this.)

Re: It Can Happen to You

#237

Post by virgilp »

SuchAnonMuchWow wrote: post #203
virgilp wrote: post #173

Earlier quoted context omitted.

Also, already sorted data.. in reverse order. If it's already sorted in the right order, quicksort takes linear time. This is an important difference - data you use might indeed often be appropriately sorted, but in practice will seldom be sorted in reverse order.

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).

Re: It Can Happen to You

#238

Post by imtringued »

beaconstudios wrote: post #230
TeMPOraL wrote: post #208

Earlier quoted context omitted.

I personally would, if it was listed in documentation. Doing stuff and profiling later is the right general approach to performance optimization. But what's better is not doing stupid mistakes in the first place, if they are trivial to avoid. To achieve that, you need to know the complexity guarantees of functions and data structures - or at least their ballpark (like, "this could be O(n) or perhaps O(n logn), defini…

Part of the issue in my mind is that big O complexity values don't (can't?) tell you the point of inflection, if they are nonlinear. Sscanf could be O(N^10) (does the rule about ignoring the coefficient also apply to the exponent?) but if it only starts to hurt your application at the point of 10tb string reads then it's still unimportant. I do agree that people often take "don't optimise early" as licence to not mak…

The important part of the documentation would be that N is the length of the entire string, not just the subset of data that needs to be processed. The actual complexity isn't relevant in this case.

Re: It Can Happen to You

#239

Post by beaconstudios »

TeMPOraL wrote: post #236
beaconstudios wrote: post #230

Earlier quoted context omitted.

Part of the issue in my mind is that big O complexity values don't (can't?) tell you the point of inflection, if they are nonlinear. Sscanf could be O(N^10) (does the rule about ignoring the coefficient also apply to the exponent?) but if it only starts to hurt your application at the point of 10tb string reads then it's still unimportant. I do agree that people often take "don't optimise early" as licence to not mak…

I agree. And I'd personally probably trip over it too, if I used C functions much (I use C++ standard library equivalents, and I'm going to recheck string parsing code in our project now, because we may have that same problem, just with different API!). strlen() in a loop is something that can sneak up on you by virtue of having too many layers of abstraction - scanf() family being one of them. But what I'm saying is…

> But what I'm saying is, documenting big O complexity is useful, even if imperfect (and if the function has "tricky" complexity, the conditions where it gets bad should be documented too!).

Ah yes I totally agree on this point, it should be documented for those who are more cautious/mathematical in their engineering efforts. I'm just not one of those people! I prefer to focus on the structural behaviour of a team (if it's my responsibility) to ensure that cases like:

> two years later that the company is investing employee-years into horizontally scaling your application as it's slow under workload

Resolve correctly - if a team is set up to respond healthily to production slowdowns (of course the equation is different for software with a slow/nonexistent update loop) then IMO you don't need to invest as heavily into up-front optimisation and can instead invest into features, allowing (sample-based for busy paths) profiling in production to notify you when optimisation is warranted.

At the end of the day, up front optimisation is an exchange of time with your future self/colleagues. It's worth it in some cases, not in others - but knowing where the balance in a tradeoff lies in your circumstance is a good chunk of all engineering decisions!

Re: It Can Happen to You

#240

Post by yread »

CGamesPlay wrote: post #72
johnfn wrote: 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.

And maybe, in a decade or so, the man page for these functions will list their algorithmic complexity! That was the most interesting takeaway from this article, for me at least. I have only seen a one or two libraries that actually list this in their documentation.

How would it help you knowing that it's O(n)? It needs to read all the characters of the float. Problem is that it's needlessly reading characters even after the float
Post reply on HN