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

341–350 of 419 posts

Re: It Can Happen to You

#341

Post by vegesm »

ajmurmann wrote: post #338
Hamuko wrote: post #323

Earlier quoted context omitted.

> AAA game development is rushed; the pressure is to ship. I'd be more understanding if GTA Online hadn't already shipped its first version in October of 2013. Surely there would've been some time after shipping the first version to profile the game.

(disclaimer: I'm not in game development and only read about this) Usually different staff rolls on and off at different times of product development and post-release lifecycle. I understand that most programmers would have been rolled off a while before launch. You early on have people build or adjust the engine and tooling, but later on you don't need most of them anymore and things come down to creating content.

That's true for all software development. In seven years most of your team is replaced.

Re: It Can Happen to You

#342

Post by thaumasiotes »

SilasX wrote: post #329
thaumasiotes wrote: post #318

Earlier quoted context omitted.

> Everything is O(1) if N is constant, including log(N), N^2, 2^N, N!, etc. Not even close. 2^k is not O(1) by virtue of N being constant. Only 2^N. This has been covered above. It is more common to consider the complexity of hash table operations in terms of the number of operations, or the size of the table; the size of the key is very often constant. These are different variables; the constant size of the key does…

Here, the relevant key is the output of the hash function though -- that's what you need to increase in order to ensure you can reach all buckets. And that (k) must increase with the table size. So it is not constant and depends on n (table size). Earlier discussion: https://news.ycombinator.com/item?id=9807739

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 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 addressable bytes cannot need the key to be more than 40 bits long.

On a different note, by "table size" in my earlier comment I meant to refer to the number of entries in the table, not the capacity of the backing store. It seems like you might be using the same word for a different concept?

Re: It Can Happen to You

#343

Post by stefs »

many years ago i slaved away in a low end (5 people) ecommerce web shop with a homebrew php cms. i hated working there, but was too vain to quit. one day our biggest customer by far complained about slow loading speeds and i was set upon the task. it was spaghetti code of the worst sort, but i managed to find the culprit quickly: converting a list of rows (for pages) from the database into the hierarchical menu tree structure; of course it was O(n²). i fixed it and the page generation time went down from 7 seconds to a few milliseconds again.

they didn't let me push the fix back into the main repo because "it only affects this one customer, so we'll only fix it here". luckily i was fired shortly after. fin.

Re: It Can Happen to You

#344

Post by simias »

lostcolony wrote: post #322
simias wrote: post #320

I think the really embarrassing part for Rockstar is that they didn't bother to investigate what took 5+ minutes to load in their star product, a simple profiling would've made the issue obvious. So either they knew and they didn't care, or they didn't know and they didn't care. That being said both for GTA and for TFA the issue is a very similar sscanf call: sscanf(data, "%f", &f); I already posted a similar comment…

I think 'embarrassing' is too strong a word. AAA game development is rushed; the pressure is to ship. Something has to give. This is a user facing issue, but one that doesn't actually affect the gameplay. Assuming they had -time- to profile the load process, given that low a priority, seems extremely optimistic.

I wouldn't have said anything if the game was released one month ago, but GTA V is almost 8 year old now and it's been ported to several generations of hardware (IIRC they've even announced "next gen" ports to release this year). The online function is still maintained and makes them a lot of money. I also do think that it affects the gameplay because these loading times are genuinely terrible. A 30second loading screen is a nuisance, a 5+ minute loading screen just makes me want not to play the game.

I think that Rockstar deserves some blame here, especially since this problem might well be a consequence of their notoriously bad development practices.

Re: It Can Happen to You

#345

Post by another_kel »

stefs wrote: post #343

many years ago i slaved away in a low end (5 people) ecommerce web shop with a homebrew php cms. i hated working there, but was too vain to quit. one day our biggest customer by far complained about slow loading speeds and i was set upon the task. it was spaghetti code of the worst sort, but i managed to find the culprit quickly: converting a list of rows (for pages) from the database into the hierarchical menu tree…

By the way, does anyone know whether red dead redemption online has the same problem? Maybe the issue was fixed for the newer game but they decided not to update gta repo?

Re: It Can Happen to You

#346

Post by aliceryhl »

thaumasiotes wrote: post #184
alexchamberlain wrote: post #166

Earlier quoted context omitted.

It makes me chuckle when hash maps are stated to be O(1) insertions. Which is true, in respect to the number of items in the map, assuming the map doesn't need resizing and there isn't a hash collision... but it's generally not true in respect to the key length. (I think most implementations are O(ln), where l is the length of the key and n is the number of inserted items, assuming the hash function is O(l) - the _am…

> assuming the map doesn't need resizing This isn't a big difficulty; it's still amortized O(1). > and there isn't a hash collision This is a real difficulty, unless you allow map resizing. Luckily, we do. > but it's generally not true in respect to the key length. OK, but in most cases the key length is constant, making anything that depends on the key length O(1) by definition.

If the key length is constant, the map as an upper limit on the number of possible elements, so all operations are constant time.

Re: It Can Happen to You

#347

Post by vlovich123 »

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

You’re misreading the standard a bit I think. It’s saying undefined behavior comes from the format string (which you should control and is a common compiler warning if it’s not a literal) doesn’t match the types of variables you pass it. This is kind of obvious when you think about it. Variadic C functions lose type information so the format string is the source of that.

The “out-of-range” issue just means that the library isn’t going to mandate every implementation of this function is guaranteeing to provide the same overflow behavior (some might stop when you saturate, others might stop at the end of digits input and overflow, others might detect the overflow and saturate).

The Linux man page is clearer here IMO:

> If the number of conversion specifications in format exceeds the number of pointer arguments, the results are undefined. If the number of pointer arguments exceeds the number of conversion specifications, then the excess pointer arguments are evaluated, but are otherwise ignored.

That’s the only spot the word “undefined” appears and doesn’t discuss overflow. My general impression is that the “undefined” problem largely only applies to language operations or user input causing a library to perform such an undefined behavior. Older C functions with older documentation may be using “undefined” with a less strict meaning to also cover “implementation-defined”. The “undefined behavior” brouhaha came up in the past 5-10 years only when compilers actually started leveraging it breaking a lot of assumptions.

Re: It Can Happen to You

#348

Post by undefined1 »

lostcolony wrote: post #322
simias wrote: post #320

I think the really embarrassing part for Rockstar is that they didn't bother to investigate what took 5+ minutes to load in their star product, a simple profiling would've made the issue obvious. So either they knew and they didn't care, or they didn't know and they didn't care. That being said both for GTA and for TFA the issue is a very similar sscanf call: sscanf(data, "%f", &f); I already posted a similar comment…

I think 'embarrassing' is too strong a word. AAA game development is rushed; the pressure is to ship. Something has to give. This is a user facing issue, but one that doesn't actually affect the gameplay. Assuming they had -time- to profile the load process, given that low a priority, seems extremely optimistic.

embarrassing is too light a word.

Rockstar has virtually endless resources and the game has been out for many years. for years, they didn't reduce the extremely long load times? not only embarrassing, but shows deep incompetence and lack of respect for the craft and for end users.

Re: It Can Happen to You

#349

Post by IggleSniggle »

DarkWiiPlayer wrote: post #229
inimino wrote: post #162

Earlier quoted context omitted.

It's also easy to forget that C was competing mainly with assembly, while C++ competed with managed languages. The early C programmer ethos, especially among library authors, was much more along the lines of "look at the generated object code if you want to know what it's doing" while modern practice leans more towards "read the documentation for complexity guarantees". I'm not saying that worse documentation leads t…

Good documentation and inspecting the compiled bytecode are both good ways of finding out about performance characteristics of certain features. The problem starts when people rely on assumptions ("sscanf should be fast because it's widely used") or performance folklore ("localizing every function you'll ever use makes your Lua code faster"), because those tend to either be completely wrong or lack very important con…

I live in js land, and the barrier between “folklore” and “documentation” is extremely thin. Especially since V8 may introduce changes at any time that affect performance characteristics of js.

I’d respond with “well if performance matters it shouldn’t be in js” except for all the shite being written in js these days, with js being the hammer that makes everything else look like a nail.

Re: It Can Happen to You

#350

Post by chihuahua »

ymosy wrote: post #159
telotortium wrote: post #150

Earlier quoted context omitted.

Do you have a link for the Windows Update algorithm being quadratic?

I believe this is what the parent was referring to: https://arstechnica.com/information-technology/2013/12/expon...

Thank you, I had a vague memory of this but this article sums it up perfectly and states that it's worse than quadratic, it's exponential.
Post reply on HN