It Can Happen to You • Hacker News Board

Re: It Can Happen to You

#351

Post by SilasX » Thu, Mar 04, 2021, 3:43 PM UTC

thaumasiotes wrote: post #342

SilasX wrote: post #329

Earlier quoted context omitted.

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

So? That's still putting a bound on table size, which makes it in-practice constant, but doesn't make the algorithm O(1), because you can never get such a result by bounding n, for the reasons the GGP gave -- that's cheating.

Your complexity bound has to be written on the assumption that n (number of elements to store in hashtable) increases without bound. Assuming you will never use more that Y bytes of data is not valid.

>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?

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

Re: It Can Happen to You

#352

Post by jedimastert » Thu, Mar 04, 2021, 3:47 PM UTC

mkeeter wrote: post #316

jedimastert wrote: post #299

Quick question: At the top of the parser they define const char VERTEX_STR[] = "vertex "; And a few lines in data += strlen(VERTEX_STR); Would parsers optimize this out? Seems like an easy win to replace that with a "7" (or a constant or something), although I don't know how much of a win it would be.

I was trusting the compiler on this one, but after someone asked this question on Twitter, I doubled-checked: https://cppx.godbolt.org/z/fhTGcx Sure enough, it compiles down to "add rax, 7"

I figured it would, but I didn't want to assume. Thanks!

Re: It Can Happen to You

#353

Post by earthboundkid » Thu, Mar 04, 2021, 3:52 PM UTC

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…

The Go standard library is pretty good, but unfortunately, it includes a scanf clone, so every once in a while you see a poor new developer posting to help forums trying to get it to work properly and you have to break it to them that they're using the wrong tool for basically any job.

Re: It Can Happen to You

#354

Post by coolgeek » Thu, Mar 04, 2021, 4:10 PM UTC

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.

I just got an infinite loop down to 8.6 seconds! And I'm not done yet!

Re: It Can Happen to You

#355

Post by ajmurmann » Thu, Mar 04, 2021, 4:18 PM UTC

vegesm wrote: post #341

ajmurmann wrote: post #338

Earlier quoted context omitted.

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

In other areas of software development are perpetual. You don't hit some milestone at which 90% of developers are moved to a different project or laid off and folks with a different skill set are added.

Usually in software development you have different people over time, because of individual churn, not because you are changing the role mix

Re: It Can Happen to You

#356

Post by dijit » Thu, Mar 04, 2021, 4:21 PM UTC

Hamuko wrote: post #323

lostcolony wrote: post #322

Earlier quoted context omitted.

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.

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

I work in gamedev and I'm on your side in this.

But I should note that once you ship a product in this space there is a heavy emphasis on not breaking much. Changes are for the next milestone (seasons, service packs, new features). There's very rarely any emphasis on "fixing" something because it could introduce even more bugs and Producers prefer sitting on a stack of known issues than addressing them with more unknown ones. Since known issues have a known cost.

Until it gets so bad that you have to make health patches, we made such patches (and referred to them internally as "Sanity" patches)

Re: It Can Happen to You

#357

Post by lostcolony » Thu, Mar 04, 2021, 4:32 PM UTC

Hamuko wrote: post #323

lostcolony wrote: post #322

Earlier quoted context omitted.

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.

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

Sure. I'd be embarrassed if they didn't have the issue on their backlog ("Load times are high"). But the priority seems low, and the actual effort and viability of a fix seems unknown. Speaking as an engineering manager, that is very much going to be a "if you have spare time" ticket. Now, I also try to ensure people have spare time to investigate stuff like that, but that's me, and I don't work in game dev. I can easily see another manager, especially one in game dev (where what keeps players coming back is new content and features, not reduced load times) prioritizing other tickets ahead.

Re: It Can Happen to You

#358

Post by tgtweak » Thu, Mar 04, 2021, 4:37 PM UTC

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 was thinking about it the other day when reading the original article, and this was the only plausible (and defensible) cause for it not being addressed:

When GTA online was released 7 years ago in 2013, the list of DLC items was probably much shorter, and grew over time. The performance issue is exponentially aggravated with list-length. The list growth was probably bell-curve shaped over the lifetime of the game.

This has an interesting dynamic when it comes to perceived performance:

In the beginning, on consoles and PCs - it was already a pretty long load time, but would have been 90s or so on an average gaming PC (I remember this from the early days playing it, on a modest gaming PC with an FX-8150 cpu). This is long, but tolerable for a game of this size. I'm certain that early complaints that it was sluggish to load were profiled and looked at, and at the time it wasn't a 4 minute ordeal to load the json and probably represented a fraction of the CPU time it takes today - not standing out as obviously as in OPs guerilla profiling. Devs put a pin in it and say "this is netcode related, it is what it is"

Over time, the list gets longer, the loading time takes more cycles, BUT, PCs are getting progressively faster year over year as well, with many of those improvements happening at the instruction-level - optimizing for things like, surprise, string scanning. Two console generations are released since, masking the problem on that side. For comparison sake, I just checked and I can load GTA online in about 75s on my Ryzen 3900x. This cpu is probably 4-6x faster in single core performance than the 8150 for most workloads. Again, it's slow but tolerable and by this time it's "yeah GTA online is just a big game and takes a while to load, it's always been that way". Complacency is the enemy of improvement, and things that regress slowly over time are hard for us to notice in general.

Don't take this as a "this is fine" comment, but instead the only reasonable justification I can think of as to why it might have flown under the radar all these years.

Re: It Can Happen to You

#359

Post by SomeCallMeTim » Thu, Mar 04, 2021, 4:39 PM UTC

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…

Agreed. My first instinct was the same: *scanf is never the right tool for pretty much any job.

I learned this 20+ years ago. As far as I'm concerned it should have been considered deprecated along with gets; it was considered dangerous in the early 90s and probably before. Not sure why people are still using it in the 2000s+.

Re: It Can Happen to You

#360

Post by [deleted] » Thu, Mar 04, 2021, 4:42 PM UTC

virgilp wrote: post #237

SuchAnonMuchWow wrote: post #203

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

[deleted]