12 ms·

Fixing the Loading in Myst IV: Revelation

264 points by davikr 2y ago

tomcam 2y ago
> the author explains they used a tool called Luke Stackwalker to profile the game Can anyone confirm my memory that Microsoft had a tool called Luke Heapwalker in the mid-1980s, and that Lucasfilms demanded they change the name?
- keyle 2y ago
  I can't find an exact story but this pdf [1] has a foot note about the naming being changed (search for Luke). [1] https://libros.metabiblioteca.org/server/api/core/bitstreams/405db7a0-020f-4460-807a-7d7c9bc146b4/content https://libros.metabiblioteca.org/server/api/core/bitstreams... [pdf]
  - tomcam 2y ago
    Many thanks. I love the whole book.
EDEdDNEdDYFaN 2y ago
Very good read! love detailed explanations on the "bad" original code and steps taken toward improving it. a lot of it comes down to personal preference and the author did a good job at respecting what might have been an intentional design decision with their optimizations by making it all configurable
zetafunction 2y ago
Great read! Though there is an unnecessary double map lookup in part 2: https://github.com/tomysshadow/M4Revolution/blob/094764c87aa4e3d5b822d18a23e6729b04b14236/M4Revolution/Ubi.cpp#L1341 https://github.com/tomysshadow/M4Revolution/blob/094764c87aa...
rkagerer 2y ago
This is awesome (and very impressive)! Two questions: 1. What tool was used to generate that "Ange Albertini-inspired file format diagram"? 2. Is there an emulator that would make this easy to play under Android?
- tomysshadow 2y ago
  1. There are probably better tools to do it, but I just used Google Drawings. 2. Not for Myst IV currently. All of the prior games are supported by ScummVM, which would work on an Android device, but Myst IV is not in there yet. Maybe someday though
kubb 2y ago
My manager takes one look at this and asks: so, in the end the effort was unsuccessful? No impact? That’s OK, let’s get you refocused on something productive :)
throwaway284534 2y ago
I really enjoyed the author's technical deep-dive and approach to debugging performance issues. Mild spoilers for anyone who hasn't played Riven, but the method for fixing Gehn's faulty linking books is a perfect analogy for the author's more counterintuitive performance optimizations. While I don’t have a write-up as detailed as this one, I spent a month on a similar journey optimizing an animated ASCII art rasterizer. What started as an excuse to learn more about browser performance became a deep dive into image processing, WebGL, and the intricacies of the Canvas API. I’m proud of the results but I’ve annotated the source for a greater mind to squeeze another 5 or 10 FPS out of the browser. Maybe it’s time to brush up on those WebGL docs again… - [1] https://asciify.sister.software/ https://asciify.sister.software/ - [2] https://github.com/sister-software/asciify/blob/main/Asciify.mts https://github.com/sister-software/asciify/blob/main/Asciify...
iforgotpassword 2y ago
Great writeup. A typical "this shouldn't be too hard" story with yet another surprise around every corner. Seems familiar... :) One thing I wondered is whether with that optimized loader library, is it even still necessary to do the DXT conversion at all? Sounds like mango and pixman could be fast enough already....
- tomysshadow 2y ago
  For me at least, with the optimized loader library, yes, the impact of the DDS conversion is almost unnoticeable. However, I have a pretty fast CPU so I don't want to assume that it'd be the case for everyone, and the DDS conversion was done first, so even if it is overkill it costs me nothing to leave in and will better serve anyone with a slow CPU where mango and Pixman aren't enough. Shortly after I released my tool, I had someone report that it was crashing for them because they were using a third gen Intel CPU that didn't have a SIMD instruction set the x64 command line portion used (particularly the BMI instruction set.) It was a bug in the mango image library anyway because I had disabled that particular instruction set when I built it, but goes to show that when you're doing a retro game hacking project, a lot of gamers are keen to use older hardware for them and I'm quite aware of this fact
lbj 2y ago
My hat is off to this, I really appreciate how he documented every step he took. It's lengthy but definitely worth the read.
tomovo 2y ago
STB image didn't get used in the end because some other library was faster but I think the author missed the possibility of #defining their own allocator using STBI_MALLOC (which could just return a pointer to an existing memory block).
- tomysshadow 2y ago
  No, actually, I did see this. The problem with using STBI_MALLOC in that way is that it is used for _all_ allocations by STB, not just the main image buffer. The image buffer I need to put the data into is passed in as an argument to Gfx Tools. It is already existing, and I couldn't touch the code where it was created, that code lived in yet another DLL, the one calling into Gfx Tools. So if I overrode STBI_MALLOC to just return that same buffer every time, then any time STB calls malloc, each malloc call would return the same buffer, that same buffer would be used for different allocations with entirely different purposes. So, it's close, but it wouldn't work. I would need to have done some hack like checking the requested buffer size to malloc matches the expected size of the image buffer, and only return it then, but that's of course quite fragile and error prone. Or, you know, just go into the STB source and find the one malloc I need to replace, but that's kind of dirty.
  - tomovo 2y ago
    Thanks for the detailed explanation, good to know!
feintruled 2y ago
I think any software engineer can identify with the feeling you get at the moment you do the first run of the solution you have implemented that you are 100% sure has to fix it only to find nothing has changed.
- tomysshadow 2y ago
  I was genuinely concerned that everything I was doing with mango and Pixman was going to turn out to be pointless. It wasn't, thankfully, there was a noticeable difference after introducing them. But it was a gamble for sure, because there was no smaller test I could really do to know it was worth it in advance - if I wanted to replace that DLL, I was going to have to replace the whole DLL because it was C++, the DLL exports were all mangled names for classes that all kind of interacted with each other, so I couldn't just cleanly replace one call and see that it was a good idea. I try to gather as much evidence as I can to back the idea it'll work before I make the leap, but I've learned that if you really want to get stuff done sometimes you just have to go for it and assume there is a way to salvage it if it fails
- finnh 2y ago
  This has happened to me so many times. Especially in the distributed database I work on ... "hmm maybe I need to let the experiment run for longer, this data is noisy so it probably needs more time to show a trend line".
- ramon156 2y ago
  This reminds me of when I was trying to do Minecraft style chunking in Bevy. I was in a situation where (instead of doing the not-so-obvious fix) I threw parallelization, compiler optimization, caching, release flags etc. at my project and nothing made it go faster. I could not figure out why it was so slow. Turns out what I was doing was so unoptimized that I might've as well loaded the whole world per frame. You live and you learn :)
- danudey 2y ago
  Corollary: the relief/anguish when you discover that the reason none of your fixes have worked, nor your debugging print statements produced output, is because you were editing a different copy of the file than was getting built/run because you moved or renamed something and your editor didn't notice.
shiomiru 2y ago
> As any good programmer knows, division is slow, it’s a serializing instruction, and we want to avoid it as much as possible. The favourite programmer tricks to avoid division are to use bit shifts (for division by multiples of two) or flip it into a multiplication — for example, to multiply by 0.333 instead of dividing by 3. In this case though, we are dividing by the alpha, so we can’t know what number we will be dividing by in advance. > However, because the channels are 8-bit, we will only ever be dividing numbers from 1 to 255 (yes, some values will be zero — but we sure won’t be dividing by them then!) That means there are only about 65K possible combinations, so we can use another classic solution: a lookup table! This is a perfect place to use constexpr to bake the array directly into the compiled result. Interestingly, when I benchmarked this same problem, three integer divisions would easily beat the LUT on my computer. Maybe because the it's easier on the cache? (Or I did something wrong.)
- Palomides 2y ago
  I think, on a modern processor, a lookup table of 65k is way too big to be worthwhile for something as simple as a division memory access is relatively very slow; OP probably should have benchmarked it
  - Jerrrry 2y ago
    Depends on the use and context, benchmarking can hint at the "truth", that it is faster to just divide: ultimately the benchmark would have to have the two implementations and run them thru all possible inputs to know for sure. It may clearly state that memoization is slower, until you plop it into a benchmark that inlines division explicitly without using a given hardware accelerate. division by a constant input can be solved faster still, so there can be optimizations on top of memoization that would beat raw division on most peocessors/runtime environments.
  - wongarsu 2y ago
    Chances are only a small portion of the lookup table is used. It's conceivable that this is almost entirely L1 access. But I'm also very skeptical that this is actually faster. Would have been nice to see some numbers
Cthulhu_ 2y ago
Love seeing how the optimization parameters were different back then, that is, size constraints were more important than loading speeds, even though both drives and CPUs were much slower back then. Ideally companies like this that make games keep all the original assets and make things like image format a build switch, for when the parameters change in the future. That said, back then they released on a DVD (I'm reading it would've taken 12 CDs otherwise), I don't believe any higher capacity storage devices were in the pipeline yet at that point. That said, hard drives back then were around the 100 GB mark, so a multi-dvd release would've been doable. Ironically nowadays, some games (like the FFVII Remakes) are on two disks again, an install and a run disk, despite them having a 50 or 100 GB capacity nowadays.
- tomysshadow 2y ago
  Someone on Reddit pointed out to me after, DDS is DirectX specific and the DVD was for Win/Mac, so it may have been more of a multiplatform issue than a space one. In an ideal world you'd use DDS on Windows because it's fastest there, and whatever the OpenGL equivalent is on Mac, but that would've been well, well outside of space constraints, at that point
- tobr 2y ago
  It was released on 2 DVDs as far as I remember.
- Uvix 2y ago
  It was already on two discs. You could choose whether to copy one or both to the hard drive. The game ran on machines as old as late 1999, so the typical disk size would’ve been more in the 10-20 GB range. Even the existing 3.4 GB minimum requirement (installing just one disc and streaming content off the other) was a pretty hefty ask.
- hirako2000 2y ago
  I remember on PS1 it sold with 3* CDs. It was beautiful as they had to make a special double edges holding box. Stood nicely aligned with all the other games but could be spotted from afar. We see physical media as a burden today, that's sad as they used to be pieces of arts. Edit: 3, not 4.
mananaysiempre 2y ago
I’ve just read both parts of the article and I still feel like I’m left with more questions than answers. The game is bottlenecked on memcpy so hard it takes two seconds to load each time? On a modern machine with double-digit GB/s RAM bandwidth and single-digit GB/s SSD bandwidth, when the game was released on two DVDs and thus can’t have more than couple dozen GB of assets total[1]. How? OK, they’re doing a memcpy per image row, that’s not nice and can probably cost you an order of magnitude or so, and the assets are JPEG-compressed so it’s another order of magnitude to copy around uncompressed pixels, but still, how? Furthermore, if it really is bottlenecked on memcpy, why does running on a modern machine not improve things? I almost want to think there’s a fixed amount of per-frame work hardcoded somewhere, and loading DDS is just accounted for incorrectly. [1] In fact, a screenshot in part 1 shows data.m4b taking up 1.4GB, and the rest of the files shown are either video, sound, or small.
- tomysshadow 2y ago
  To be completely honest, it's surprising to me as well. I would expect it to be bad, but not as bad as it was. I entirely expected that the slow part would be decoding, not copying. In fact, my initial plan was to convert the remaining images that couldn't be DDS to Targa, on the assumption it would decode faster. However, when I investigated the slow functions and found they were only copying, I changed tactic because then in theory that would not make a difference. There is no fixed amount of per-frame work. After the 550ms hardcoded timer is up, it is blocking during the loading of those images, and during this phase all animations on screen are completely still. I thought to check for this, because it did occur to me that if it tried to render a frame inbetween loading each image to keep the app responsive, that would push it to be significantly longer, and that would be a pretty normal thing to want to do! But I found no evidence of this happening. Furthermore, I never changed anything but the actual image loading related code - if it tried to push out a frame after every image load or every x number of image loads, those x number of frames wouldn't go away only by making the images load faster, so it'd have never gotten as instant as it did without even more change. The only explanation I can really fathom is the one I provided. The L_GetBitmapRow function has a bunch of branches at the start of it, it's a DLL export so the actual loop happens in a different DLL, and that happens row by row for 500+ images per node... I can only guess it must be because of a lack of CPU caching, it's the only thing that makes sense given the data I got. Probably doesn't help that the images are loaded in single threaded fashion, either. That said, there have been plenty of criticisms of my profiling methodology here in these comments, so it would be nice to perhaps have someone more experienced in low level optimizations back me up. At the end of the day, I'm pretty sure I'm close enough to right, at least close enough to have created a satisfactory solution :)
jobbr 2y ago
This guy Mysts.
SideQuark 2y ago
Unfortunately the author and the paper he links apply alpha premultiply to the gamma compressed image. To be correct, this should be done in a linear colorspace. His solution will make some color edge combos get halos. Basically, alpha in all formats I’ve seen is stored linear, but colors are gamma compressed (sRGB, HDR stuff, etc.). If you apply alpha premultiply, then linearize, you’ve misapplied alpha. If you ignore linearizing (as even this author shows), you get immediate black halos since your blend is effectively multiplying colors, not adding them.
- tomysshadow 2y ago
  This is something I'd love to get right. Pixman does appear to support sRGB input, in the form of the PIXMAN_a8r8g8b8_sRGB format, which might work well enough for the premultiply step. It's the unpremultiply that I'm struggling to wrap my head around - I'm guessing I'd need Pixman to output to 16-bit channels in the destination, otherwise I wouldn't be able to convert back to sRGB? That's kind of a massive pain though, I'd have to allocate a whole other temporary buffer that's double the size, for something that is imperceptible enough I never noticed it with my test images or in my playthrough. So I'm unsure what the cheapest way to do it would be. This is all well outside of my area of expertise which is primarily hacking and reverse engineering, but I'm always open to learn. I tried my hardest to create something that was as "technically correct" as I could approximate given my lack of graphics experience and the performance constraints I was under, but I kind of knew it was likely I could mess up some small detail. Maybe since it's open source someone will eventually come along to correct it? One can dream :P
  - tomysshadow 2y ago
    right, looking at it again, I think I get it now. You'd need: the 8-bit sRGB source, to the premultiplied image as floating point (Pixman can't do to 16-bit channels it seems,) then to the resized image as floating point, then unpremultiply that, and then go back to 8-bit sRGB. It makes sense in my head, I just don't know if it's really worth all that tradeoff, it's a lot of extra steps... I don't even know that the original resize algorithm would've even done it either given its age, and my goal is to replicate that. But maybe I'll test and see how it goes eventually
deleted 2y ago
[deleted]
ada1981 2y ago
This was very impressive to read and while I don’t have the technical Knowledge to do this, it reminded me of “fixing” my mental health when Stanford Psychiatrists diagnosed me and said I’d be on pills the rest of my life, incurable. Years later, after rebuilding my psyche from scratch, happy to report they were wrong. But striking similarities, where the “professionals” just didn’t bother to solve a solvable problem.
- 01HNNWZ0MV43FF 2y ago
  You might feel that your mind is a computer program you can simply rewrite, but I feel that mine is a horse that does not listen to me Pills work for a lot of things (ADHD for instance) and they're a lot faster than years
  - ada1981 2y ago
    Trade offs for sure. Short term vs. long term impacts. Having fully healed from so called bipolar, schizoaffective, anxiety and suicidal depression, I’m quite grateful I read the primary research and didn’t listen to the pharma-industrial complex. Wild that things like dancing have proven to be more effective (and with no side effects) than SSRIs. And sure, you can always tranquillized a horse, or you can take the time to learn to ride.
withinrafael 2y ago
Tangentially related, previous releases of the game were also hit by a DirectInput device enumeration regression that Microsoft (behind the scenes) refused to fix. (I haven't checked the latest re-release.) https://github.com/riverar/IndirectInput https://github.com/riverar/IndirectInput
brcmthrowaway 2y ago
What is this weird game?
- evanmoran 2y ago
  Myst is a very old game where you walk by tapping a series of pre-rendered 3d images. This is back when each image would take minutes to hours to render (like Pixar did with Toy Story 1), so graphically it looks amazing for its time, but it actually existed at the same time when Super Nintendo was popular (1990s)
  - MrDOS 2y ago
    The first game was unimaginably popular after its release in 1993. It quickly became the best-selling computer game of all time, and stayed there for nine years until The Sims unseated it in 2002. It's still the 25th highest-selling computer game ever[0]. Kids these days! [0]: https://en.wikipedia.org/wiki/List_of_best-selling_PC_games https://en.wikipedia.org/wiki/List_of_best-selling_PC_games
- d_tr 2y ago
  Why not just do a search and get an answer in five seconds?
deleted 2y ago
[deleted]
nitwit005 2y ago
> In this profile, we can see that approximately 50% of the time is spent on WaitForSingleObject, but we know that is a part of the game’s normal rendering loop so we can dismiss it as background noise. That's not an entirely safe assumption. Even a single threaded game could wait on different handles at different points in its logic.
account42 2y ago
> So we know that WaitForSingleObject is where the majority of CPU time should be spent during normal operation, and we can dismiss anything that appears in this first list as not the source of the problem. This heuristic might have worked this time but I don't think it's great in general. System functions can be used for many different purposes and even the same use might be fine in one place and a bug in another. For example the game could have been unintentionally vsyncing many times during the loading process, i.e. to update a progress bar. And no, that's not a purely hypothetical scenario.

264 points by davikr 2y ago

> the author explains they used a tool called Luke Stackwalker to profile the game Can anyone confirm my memory that Microsoft had a tool called Luke Heapwalker in the mid-1980s, and that Lucasfilms demanded they change the name?

keyle 2y ago
I can't find an exact story but this pdf [1] has a foot note about the naming being changed (search for Luke). [1] https://libros.metabiblioteca.org/server/api/core/bitstreams/405db7a0-020f-4460-807a-7d7c9bc146b4/content https://libros.metabiblioteca.org/server/api/core/bitstreams... [pdf]
- tomcam 2y ago
  Many thanks. I love the whole book.

EDEdDNEdDYFaN 2y ago

Very good read! love detailed explanations on the "bad" original code and steps taken toward improving it. a lot of it comes down to personal preference and the author did a good job at respecting what might have been an intentional design decision with their optimizations by making it all configurable

zetafunction 2y ago

Great read! Though there is an unnecessary double map lookup in part 2: https://github.com/tomysshadow/M4Revolution/blob/094764c87aa4e3d5b822d18a23e6729b04b14236/M4Revolution/Ubi.cpp#L1341 https://github.com/tomysshadow/M4Revolution/blob/094764c87aa...

rkagerer 2y ago

This is awesome (and very impressive)! Two questions: 1. What tool was used to generate that "Ange Albertini-inspired file format diagram"? 2. Is there an emulator that would make this easy to play under Android?

tomysshadow 2y ago
1. There are probably better tools to do it, but I just used Google Drawings. 2. Not for Myst IV currently. All of the prior games are supported by ScummVM, which would work on an Android device, but Myst IV is not in there yet. Maybe someday though

kubb 2y ago

My manager takes one look at this and asks: so, in the end the effort was unsuccessful? No impact? That’s OK, let’s get you refocused on something productive :)

throwaway284534 2y ago

I really enjoyed the author's technical deep-dive and approach to debugging performance issues. Mild spoilers for anyone who hasn't played Riven, but the method for fixing Gehn's faulty linking books is a perfect analogy for the author's more counterintuitive performance optimizations. While I don’t have a write-up as detailed as this one, I spent a month on a similar journey optimizing an animated ASCII art rasterizer. What started as an excuse to learn more about browser performance became a deep dive into image processing, WebGL, and the intricacies of the Canvas API. I’m proud of the results but I’ve annotated the source for a greater mind to squeeze another 5 or 10 FPS out of the browser. Maybe it’s time to brush up on those WebGL docs again… - [1] https://asciify.sister.software/ https://asciify.sister.software/ - [2] https://github.com/sister-software/asciify/blob/main/Asciify.mts https://github.com/sister-software/asciify/blob/main/Asciify...

iforgotpassword 2y ago

Great writeup. A typical "this shouldn't be too hard" story with yet another surprise around every corner. Seems familiar... :) One thing I wondered is whether with that optimized loader library, is it even still necessary to do the DXT conversion at all? Sounds like mango and pixman could be fast enough already....

tomysshadow 2y ago
For me at least, with the optimized loader library, yes, the impact of the DDS conversion is almost unnoticeable. However, I have a pretty fast CPU so I don't want to assume that it'd be the case for everyone, and the DDS conversion was done first, so even if it is overkill it costs me nothing to leave in and will better serve anyone with a slow CPU where mango and Pixman aren't enough. Shortly after I released my tool, I had someone report that it was crashing for them because they were using a third gen Intel CPU that didn't have a SIMD instruction set the x64 command line portion used (particularly the BMI instruction set.) It was a bug in the mango image library anyway because I had disabled that particular instruction set when I built it, but goes to show that when you're doing a retro game hacking project, a lot of gamers are keen to use older hardware for them and I'm quite aware of this fact

lbj 2y ago

My hat is off to this, I really appreciate how he documented every step he took. It's lengthy but definitely worth the read.

tomovo 2y ago

STB image didn't get used in the end because some other library was faster but I think the author missed the possibility of #defining their own allocator using STBI_MALLOC (which could just return a pointer to an existing memory block).

tomysshadow 2y ago
No, actually, I did see this. The problem with using STBI_MALLOC in that way is that it is used for _all_ allocations by STB, not just the main image buffer. The image buffer I need to put the data into is passed in as an argument to Gfx Tools. It is already existing, and I couldn't touch the code where it was created, that code lived in yet another DLL, the one calling into Gfx Tools. So if I overrode STBI_MALLOC to just return that same buffer every time, then any time STB calls malloc, each malloc call would return the same buffer, that same buffer would be used for different allocations with entirely different purposes. So, it's close, but it wouldn't work. I would need to have done some hack like checking the requested buffer size to malloc matches the expected size of the image buffer, and only return it then, but that's of course quite fragile and error prone. Or, you know, just go into the STB source and find the one malloc I need to replace, but that's kind of dirty.
- tomovo 2y ago
  Thanks for the detailed explanation, good to know!

feintruled 2y ago

I think any software engineer can identify with the feeling you get at the moment you do the first run of the solution you have implemented that you are 100% sure has to fix it only to find nothing has changed.

tomysshadow 2y ago
I was genuinely concerned that everything I was doing with mango and Pixman was going to turn out to be pointless. It wasn't, thankfully, there was a noticeable difference after introducing them. But it was a gamble for sure, because there was no smaller test I could really do to know it was worth it in advance - if I wanted to replace that DLL, I was going to have to replace the whole DLL because it was C++, the DLL exports were all mangled names for classes that all kind of interacted with each other, so I couldn't just cleanly replace one call and see that it was a good idea. I try to gather as much evidence as I can to back the idea it'll work before I make the leap, but I've learned that if you really want to get stuff done sometimes you just have to go for it and assume there is a way to salvage it if it fails
finnh 2y ago
This has happened to me so many times. Especially in the distributed database I work on ... "hmm maybe I need to let the experiment run for longer, this data is noisy so it probably needs more time to show a trend line".
ramon156 2y ago
This reminds me of when I was trying to do Minecraft style chunking in Bevy. I was in a situation where (instead of doing the not-so-obvious fix) I threw parallelization, compiler optimization, caching, release flags etc. at my project and nothing made it go faster. I could not figure out why it was so slow. Turns out what I was doing was so unoptimized that I might've as well loaded the whole world per frame. You live and you learn :)
danudey 2y ago
Corollary: the relief/anguish when you discover that the reason none of your fixes have worked, nor your debugging print statements produced output, is because you were editing a different copy of the file than was getting built/run because you moved or renamed something and your editor didn't notice.

shiomiru 2y ago

> As any good programmer knows, division is slow, it’s a serializing instruction, and we want to avoid it as much as possible. The favourite programmer tricks to avoid division are to use bit shifts (for division by multiples of two) or flip it into a multiplication — for example, to multiply by 0.333 instead of dividing by 3. In this case though, we are dividing by the alpha, so we can’t know what number we will be dividing by in advance. > However, because the channels are 8-bit, we will only ever be dividing numbers from 1 to 255 (yes, some values will be zero — but we sure won’t be dividing by them then!) That means there are only about 65K possible combinations, so we can use another classic solution: a lookup table! This is a perfect place to use constexpr to bake the array directly into the compiled result. Interestingly, when I benchmarked this same problem, three integer divisions would easily beat the LUT on my computer. Maybe because the it's easier on the cache? (Or I did something wrong.)

Palomides 2y ago
I think, on a modern processor, a lookup table of 65k is way too big to be worthwhile for something as simple as a division memory access is relatively very slow; OP probably should have benchmarked it
- Jerrrry 2y ago
  Depends on the use and context, benchmarking can hint at the "truth", that it is faster to just divide: ultimately the benchmark would have to have the two implementations and run them thru all possible inputs to know for sure. It may clearly state that memoization is slower, until you plop it into a benchmark that inlines division explicitly without using a given hardware accelerate. division by a constant input can be solved faster still, so there can be optimizations on top of memoization that would beat raw division on most peocessors/runtime environments.
- wongarsu 2y ago
  Chances are only a small portion of the lookup table is used. It's conceivable that this is almost entirely L1 access. But I'm also very skeptical that this is actually faster. Would have been nice to see some numbers

Cthulhu_ 2y ago

Love seeing how the optimization parameters were different back then, that is, size constraints were more important than loading speeds, even though both drives and CPUs were much slower back then. Ideally companies like this that make games keep all the original assets and make things like image format a build switch, for when the parameters change in the future. That said, back then they released on a DVD (I'm reading it would've taken 12 CDs otherwise), I don't believe any higher capacity storage devices were in the pipeline yet at that point. That said, hard drives back then were around the 100 GB mark, so a multi-dvd release would've been doable. Ironically nowadays, some games (like the FFVII Remakes) are on two disks again, an install and a run disk, despite them having a 50 or 100 GB capacity nowadays.

tomysshadow 2y ago
Someone on Reddit pointed out to me after, DDS is DirectX specific and the DVD was for Win/Mac, so it may have been more of a multiplatform issue than a space one. In an ideal world you'd use DDS on Windows because it's fastest there, and whatever the OpenGL equivalent is on Mac, but that would've been well, well outside of space constraints, at that point
tobr 2y ago
It was released on 2 DVDs as far as I remember.
Uvix 2y ago
It was already on two discs. You could choose whether to copy one or both to the hard drive. The game ran on machines as old as late 1999, so the typical disk size would’ve been more in the 10-20 GB range. Even the existing 3.4 GB minimum requirement (installing just one disc and streaming content off the other) was a pretty hefty ask.
hirako2000 2y ago
I remember on PS1 it sold with 3* CDs. It was beautiful as they had to make a special double edges holding box. Stood nicely aligned with all the other games but could be spotted from afar. We see physical media as a burden today, that's sad as they used to be pieces of arts. Edit: 3, not 4.

mananaysiempre 2y ago

I’ve just read both parts of the article and I still feel like I’m left with more questions than answers. The game is bottlenecked on memcpy so hard it takes two seconds to load each time? On a modern machine with double-digit GB/s RAM bandwidth and single-digit GB/s SSD bandwidth, when the game was released on two DVDs and thus can’t have more than couple dozen GB of assets total[1]. How? OK, they’re doing a memcpy per image row, that’s not nice and can probably cost you an order of magnitude or so, and the assets are JPEG-compressed so it’s another order of magnitude to copy around uncompressed pixels, but still, how? Furthermore, if it really is bottlenecked on memcpy, why does running on a modern machine not improve things? I almost want to think there’s a fixed amount of per-frame work hardcoded somewhere, and loading DDS is just accounted for incorrectly. [1] In fact, a screenshot in part 1 shows data.m4b taking up 1.4GB, and the rest of the files shown are either video, sound, or small.

tomysshadow 2y ago
To be completely honest, it's surprising to me as well. I would expect it to be bad, but not as bad as it was. I entirely expected that the slow part would be decoding, not copying. In fact, my initial plan was to convert the remaining images that couldn't be DDS to Targa, on the assumption it would decode faster. However, when I investigated the slow functions and found they were only copying, I changed tactic because then in theory that would not make a difference. There is no fixed amount of per-frame work. After the 550ms hardcoded timer is up, it is blocking during the loading of those images, and during this phase all animations on screen are completely still. I thought to check for this, because it did occur to me that if it tried to render a frame inbetween loading each image to keep the app responsive, that would push it to be significantly longer, and that would be a pretty normal thing to want to do! But I found no evidence of this happening. Furthermore, I never changed anything but the actual image loading related code - if it tried to push out a frame after every image load or every x number of image loads, those x number of frames wouldn't go away only by making the images load faster, so it'd have never gotten as instant as it did without even more change. The only explanation I can really fathom is the one I provided. The L_GetBitmapRow function has a bunch of branches at the start of it, it's a DLL export so the actual loop happens in a different DLL, and that happens row by row for 500+ images per node... I can only guess it must be because of a lack of CPU caching, it's the only thing that makes sense given the data I got. Probably doesn't help that the images are loaded in single threaded fashion, either. That said, there have been plenty of criticisms of my profiling methodology here in these comments, so it would be nice to perhaps have someone more experienced in low level optimizations back me up. At the end of the day, I'm pretty sure I'm close enough to right, at least close enough to have created a satisfactory solution :)

jobbr 2y ago

This guy Mysts.

SideQuark 2y ago

Unfortunately the author and the paper he links apply alpha premultiply to the gamma compressed image. To be correct, this should be done in a linear colorspace. His solution will make some color edge combos get halos. Basically, alpha in all formats I’ve seen is stored linear, but colors are gamma compressed (sRGB, HDR stuff, etc.). If you apply alpha premultiply, then linearize, you’ve misapplied alpha. If you ignore linearizing (as even this author shows), you get immediate black halos since your blend is effectively multiplying colors, not adding them.

tomysshadow 2y ago
This is something I'd love to get right. Pixman does appear to support sRGB input, in the form of the PIXMAN_a8r8g8b8_sRGB format, which might work well enough for the premultiply step. It's the unpremultiply that I'm struggling to wrap my head around - I'm guessing I'd need Pixman to output to 16-bit channels in the destination, otherwise I wouldn't be able to convert back to sRGB? That's kind of a massive pain though, I'd have to allocate a whole other temporary buffer that's double the size, for something that is imperceptible enough I never noticed it with my test images or in my playthrough. So I'm unsure what the cheapest way to do it would be. This is all well outside of my area of expertise which is primarily hacking and reverse engineering, but I'm always open to learn. I tried my hardest to create something that was as "technically correct" as I could approximate given my lack of graphics experience and the performance constraints I was under, but I kind of knew it was likely I could mess up some small detail. Maybe since it's open source someone will eventually come along to correct it? One can dream :P
- tomysshadow 2y ago
  right, looking at it again, I think I get it now. You'd need: the 8-bit sRGB source, to the premultiplied image as floating point (Pixman can't do to 16-bit channels it seems,) then to the resized image as floating point, then unpremultiply that, and then go back to 8-bit sRGB. It makes sense in my head, I just don't know if it's really worth all that tradeoff, it's a lot of extra steps... I don't even know that the original resize algorithm would've even done it either given its age, and my goal is to replicate that. But maybe I'll test and see how it goes eventually

deleted 2y ago

[deleted]

ada1981 2y ago

This was very impressive to read and while I don’t have the technical Knowledge to do this, it reminded me of “fixing” my mental health when Stanford Psychiatrists diagnosed me and said I’d be on pills the rest of my life, incurable. Years later, after rebuilding my psyche from scratch, happy to report they were wrong. But striking similarities, where the “professionals” just didn’t bother to solve a solvable problem.

01HNNWZ0MV43FF 2y ago
You might feel that your mind is a computer program you can simply rewrite, but I feel that mine is a horse that does not listen to me Pills work for a lot of things (ADHD for instance) and they're a lot faster than years
- ada1981 2y ago
  Trade offs for sure. Short term vs. long term impacts. Having fully healed from so called bipolar, schizoaffective, anxiety and suicidal depression, I’m quite grateful I read the primary research and didn’t listen to the pharma-industrial complex. Wild that things like dancing have proven to be more effective (and with no side effects) than SSRIs. And sure, you can always tranquillized a horse, or you can take the time to learn to ride.

withinrafael 2y ago

Tangentially related, previous releases of the game were also hit by a DirectInput device enumeration regression that Microsoft (behind the scenes) refused to fix. (I haven't checked the latest re-release.) https://github.com/riverar/IndirectInput https://github.com/riverar/IndirectInput

brcmthrowaway 2y ago

What is this weird game?

evanmoran 2y ago
Myst is a very old game where you walk by tapping a series of pre-rendered 3d images. This is back when each image would take minutes to hours to render (like Pixar did with Toy Story 1), so graphically it looks amazing for its time, but it actually existed at the same time when Super Nintendo was popular (1990s)
- MrDOS 2y ago
  The first game was unimaginably popular after its release in 1993. It quickly became the best-selling computer game of all time, and stayed there for nine years until The Sims unseated it in 2002. It's still the 25th highest-selling computer game ever[0]. Kids these days! [0]: https://en.wikipedia.org/wiki/List_of_best-selling_PC_games https://en.wikipedia.org/wiki/List_of_best-selling_PC_games
d_tr 2y ago
Why not just do a search and get an answer in five seconds?

deleted 2y ago

[deleted]

nitwit005 2y ago

> In this profile, we can see that approximately 50% of the time is spent on WaitForSingleObject, but we know that is a part of the game’s normal rendering loop so we can dismiss it as background noise. That's not an entirely safe assumption. Even a single threaded game could wait on different handles at different points in its logic.

account42 2y ago

> So we know that WaitForSingleObject is where the majority of CPU time should be spent during normal operation, and we can dismiss anything that appears in this first list as not the source of the problem. This heuristic might have worked this time but I don't think it's great in general. System functions can be used for many different purposes and even the same use might be fine in one place and a bug in another. For example the game could have been unintentionally vsyncing many times during the loading process, i.e. to update a progress bar. And no, that's not a purely hypothetical scenario.