Tracking down the SSB Dynarec Bug

Yesterday I said I'd provide some more details about the Super Smash Bros. dynarec fix. The actual fix is fairly straightforward, but I thought the process of tracking down the issue was quite interesting and worthy of a couple of blog posts.

When I first started looking at SSB I noted that although the game ran fine without dynarec, it would always hang when trying to enter the main entry with dynarec enabled.

I've been programming professionally for around 6 years now and I can safely say that debugging dynarec bugs is one of the hardest categories of problems I've ever had to work on. For a start, because the code is generated on the fly, you don't have the luxury of source level debugging, and without spending time reverse engineering the original rom image, you don't even know what the generated dynarec code is meant to be doing. It's very much like working blindfolded.

And it gets even worse. I've fixed dynarec problems in the past which were the result of generating incorrect code for a fragment over 500 million instructions into emulation. This would be bad enough, but it can be many thousands of instructions later before this causes emulation finally diverges from the correct path. Just identifying the exact point at which the emulation starts to diverge from the correct sequence of instructions can be like finding a needle in particularly large haystack. While blindfolded :)

Over the years of trying to debug problems like these I've built up a set of tools and learned a few tricks along the way which you might find quite interesting. Although I'm going to talk about them in the context of tracking down this dynarec issue, I've found some of the techniques useful in solving other problems so you might find other ways of applying them too.

One of the first things I do when trying to identify a dynarec issue with Daedalus is to see if the problem is reproducible on the PC build of the emulator. Although it is possible to use GDB with PSPLink, I've never got this up and running and I'm much more comfortable debugging with Visual Studio. Also, working with the PC build is usually much faster than working with the PSP build (debug builds run around 10x faster on the PC, and build times are much quicker.)

Not all dynarec issues can be debugged in this way - the PSP and PC builds have different code generation back-ends (i.e. MIPS and x86 code generation respectively) so bugs in the MIPS code generation won't usually be reproducible in the PC build. The dynarec system in Daedalus shares a common frontend (trace selection and recording) between the two platforms, which means that if I can reproduce the problem on both platforms, I can narrow down the likely location of the bug to this area.

Fortunately this particular bug manifested itself in both the PC and the PSP builds, so I knew that if I fixed the bug on the PC build, it should fix the PSP build too. What I needed to find out next is what the emulator was doing differently when dynarec was enabled compared to when it was disabled.

If dynarec is running without errors, then the sequence of executed instructions should exactly match that executed with dynarec disabled. If I could log details about all the instructions executed with dynarec disabled, and again with dynarec enabled, I should be able to compare the two logs to figure out the exact point at which dynarec is going out of sync. This all relies on the fact that the emulator is totally deterministic, i.e. that running the emulator twice in succession with the same settings should give exactly the same results.

Unfortunately, for a variety of reasons my dynarec solution doesn't produce identical results to interpretation, the main reason being that for performance reasons I can only handle vertical blank and timer interrupts on the boundaries between fragments. For example, with dynarec disabled, the first vertical blank interrupt might occur exactly on the 625,000th instruction, but with dynarec enabled with might not occur until the 625,015th instruction. This means that the logs diverge at the instant the first VBL fires, and never regain synchronisation.

When I was originally developing the new dynarec system I put a lot of effort into writing a fragment simulator, the idea being that rather than executing the native assembly code for a given trace, I could keep track of the instructions making up the trace and interpret these individually instead. Theoretically fragment simulation is identical to dynarec code execution, even down to the way I handle VBLs and timer interrupts, and it's been very useful at identifying bugs in the dynarec code generation. What's particularly useful about fragment simulation however is that I can enable a setting which makes it handle interrupts exactly in the same way as the non-dynarec core, i.e. interrupts are handled precisely rather than on fragment boundaries.

Essentially Daedalus has four modes of operation:

• Dynarec + fragment execution
  
• Dynarec + fragment simulation (imprecise interrupt handling)
  
• Dynarec + fragment simulation (precise interrupt handling)
  
• Interpretative core
  

This tool is particularly powerful, because if I can ensure that dynarec+fragment execution is equivalent to dynarec+fragment simulation, and that dynarec+fragment simulation is equivalent to running the interpretative core, then I can use the transitive properties of these relations to ensure that dynarec+fragment execution is equivalent to running the interpretative core. Fragment simulation allows me to bridge the gap between these two modes of operation which would otherwise be very difficult to compare.

I think that's long enough for one post. Tomorrow I'll talk about how I used this technique to help track down the SSB dynarec bug.

-StrmnNrmn

Super Smash Bros - Dynarec Update

This is just a quick update to let everyone know I've finally figured out why the dynarec wasn't working in Super Smash Bros. The problem has taken a lot longer to identify than I'd hoped - in part because it was a particularly tricky bug but also because I've not had as much time to work on Daedalus recently as I would have liked.

Anyway, I managed to spend a few hours this weekend isolating the problem, and after a little experimentation I've been able to come up with a temporary workaround. With the fix in place SSB is running at around 30-40fps in game on the PSP, which is very exciting.

Now that I've identified the problem my next job is to come up with a permanent, robust solution to help fix similar problems in other roms. I also want to add some improved checks in the debug build to help spot other situations where this problem arises.

For those that are interested I'll post an update shortly (within the next day or so) with some of the technical details.

-StrmnNrmn

Status Update

It's been a couple of weeks since the last update. As people tend to get a bit nervous when I don't update regularly, I just wanted to let everyone know that I'm ok and still thinking about getting R12 ready :)

I'm still in the middle of looking at fixing the various dynarec bugs which are keeping Super Smash Bros from working with Dynarec enabled. I've not made as much progress as I would have liked since the last post, as I've been very busy with work and various other commitments. Hopefully I should get a bit more time to work on R12 from the end of this week. I'll post an update as soon as I have more news to report on.

-StrmnNrmn

Dynarec Fixes

In the previous update I mentioned that the dynarec wasn't working with Goldeneye:

...I can still only get the rom running with dynarec disabled on the PSP, so the framerate is currently just 6-7 fps. Interestingly it runs fine with dynarec on the PC with the same set of changes, so this indicates a bug somewhere in the PSP dynarec implementation.

I've spent a couple of evenings investigating this problem, and I've finally had a bit of luck in determining the root cause. As I suspected it was due to a bug in the PSP dynarec implementation - it turns out that I was fiddling addresses to compensate for the different endianness of the PSP twice (essentially having the same effect as not compensating in the first place).

The fix was very easy to implement (just a single line of code). It's quite a significant bug, so I'm hoping that it will fix dynarec issues with a few other roms too. Unfortunately it looks like the bug which is preventing dynarec working with Super Smash Bros. is a different issue, so I'll have to spend some more time investigating that.

I'm pleased to say that Goldeneye is now running fine with dynarec, so it now boots and runs the intro sequence very quickly. Although the intro and menu run at around 30-60fps, in-game is still very slow (around 5-8fps) so I need to profile this and see what's going on.

As I've hinted above, the next job is to have a look why dynarec is causing Super Smash Bros to hang. A cursory look revealed that it's still broken even when I disable most of the native code generation and directly call the interpretive instruction handlers from the compiled fragment. Because of this I think the problem has something to do with how traces are selected and the resulting fragments are linked together. I'll know more later in the week.

-StrmnNrmn

Goldeneye Update!

Ok, I know the last thing I said yesterday was:

Anyway, given the work involved Goldeneye isn't an immediate priority, but I am thinking about it.

I couldn't quite resist having a quick hack to see if I could get Goldeneye working using the third method I outlined. It turned out to be relatively painless to crowbar in the required changes, and I'm pleased to say that I've managed to get Goldeneye booting again! :)

With the changes, Daedalus now dynamically pages the Goldeneye ROM into the PSP's RAM so that it no longer requires a free 12 MiB. I now check the instruction pointer on every instruction fetch in the interpretive core*, and raise a TLB Read Miss exception if required. If this happens, it causes Goldeneye's exception handler to realise that the required code isn't in memory, and to load it in from ROM before continuing execution.

So here are the first screenshots of Goldeneye running under Daedalus R12 - you can see there are a handful of graphical glitches to sort out, particularly on the main menu:







Not bad for an hour's work!

There's still quite a long way to go though. Firstly, I can still only get the rom running with dynarec disabled on the PSP, so the framerate is currently just 6-7 fps. Interestingly it runs fine with dynarec on the PC with the same set of changes, so this indicates a bug somewhere in the PSP dynarec implementation. Secondly, I've not been able to get in-game yet - it just seems to hang with a black screen shortly after starting to load the level. I've not figured out whether this is just running very slowly without dynarec and taking its time, or if there's another bug to be fixed somewhere.

Getting the rom booting is a great first step though - it can only continue to improve from here :)

-StrmnNrmn

*I probably want to tidy things up to avoid doing this for most other roms as it can be quite expensive - especially if dynarec is disabled.

Goldeneye

While I'm at it with the blog updates, I also invesitgated why Goldeneye no longer works in Daedalus (it did run with some of the very early releases, but stopped working some time ago.)

Goldeneye is quite an unusual game in that it's one of the few titles that executes code from virtual memory. I'm not sure exactly why it does this, but I suspect that it's to allow it to free up as much RAM as possible. It sets up a virtual memory range for the code, and pages in chunks of data to physical RAM as required (i.e. on TLB miss exceptions). I guess this means that it can just keep a few dozen KiB of code in RAM at a time, rather than the entire code segment.

Anway, emulating this accurately is incredibly slow - for every instruction that is executed, the emulator needs to check whether the instruction fetch would cause a TLB miss exception, and if so invoke the N64's exception handler. This is quite a time consuming process, so I tend to cheat and assume that the instruction pointer is in physical memory.

To get around this problem with Goldenye, I set up a couple of bogus entries in Daedalus' memory map that point directly to the correct region in the ROM image. In a way it's as if the N64 has a much larger TLB, and all the pages are permenantly mapped.

Normally (i.e. on the PC version of Daedalus) this all works fine. The problem as far as the PSP version is concerned is that the rom (all 12 MiB for Goldeneye) must be permenantly loaded into memory, and there just isn't enough memory left to do this anymore. As most N64 roms are simply far too large to fit in the PSP's RAM, I have to page chunks in from the memory stick on demand (pretty similar to what Goldeneye was doing on the N64 really :D)

So, there are a few possibilities for getting Goldeneye to work:

• Permenantly disable dynarec for Goldeneye, and reuse the dynarec buffers (6MiB) the expansion pak (unneeded anyway, 4MiB) and anything else I can scavenge, to fit the rom in a contiguous block in memory.
  
• Investigate a way of getting the memory-mapping hack to work with rom caching.
  
• Re-examine how I handle TLB miss exceptions for instruction fetches, and implement them correctly.
  

Of all of these, the first solution is probably the easiest, but it's a bit hacky (I'd have to allocate a 12 MiB for Goldeneye at startup, and carve this up for different subsystems if other roms were run).

The second solution is a bit less horrible, but I'm still not sure it's possible without checking the instruction pointer for every instruction that's executed (and paging in chunks of ROM as required).

That leaves the third solution which is probably the most work, but I think will be the most stable solution in the long run. It may also help a few other roms that are using similar techniques to Goldeneye to run correctly. If I can get it to work in conjunction with the current dynarec implementation, it shouldn't even be any slower than the current hack that's in place.

Anyway, given the work involved Goldeneye isn't an immediate priority, but I am thinking about it.

-StrmnNrmn

R11 Mario HUD Issue

As a few people have pointed out on the R11 release comments page, I broke the HUD in Mario 64 in R11 :(

I investigated a little, and it turns out it was due to a tiny change I made sometime on Saturday. Basically I changed the alpha threshold test from >= to >, and so nothing with an alpha of 0 is ever rendered. This shouldn't be an issue, except for the bizarre render states that Mario sets up to render its HUD.

I don't think this is a too significant issue as Mario is just as playable in R10. I'd rather release R12 a little early to fix this than mess around releasing an R11b version or whatnot. We'll see how things go with the SSB work.

-StrmnNrmn

Early SSB Progress

As I mentioned on Sunday, my main focus for R12 is to fix whatever's causing the dynarec to hang with SSB, but to start with I've spent a little time looking into fixing some of the graphical issues plaguing Super Smash Bros.

In the end I fixed four or five separate problems which were all causing quite significant glitches.

The first bug was that I was assuming that the fixed-point texture coordinates specified in the TexRect (i.e. 2d textured rectangle) commands were unsigned. It turns out that they're actually signed - SSB just happens to be one of the few roms that ever specifies negative values.

The next issue was that I was ignoring the RDP tile* mask parameters, and assuming that the tile width and height always defined the extents for both wrapping and clamping. As it turns out, the mask values (if set) define how many bits from the texture coordinate to accept - all the other bits from the texture coordinate are ignored. This means that if a tile defines a mask of 5, the texture will wrap every 2^5, or 32 texels. What's quite interesting about the N64 is that it lets you define different limit for clamping than for wrapping. For instance, you can wrap every 32 texels, but clamp the texture to a coordinate of 100 (i.e. after the texture has repeated 3 and a bit times.) It turns out this is exactly what SSB was doing.

A related issue was that as the PSP only supports textures with power-of-2 dimensions, I have to pad out non-power-of-2 textures from the n64 with empty space. As I was assuming that the n64 always clamped at power of 2 boundaries, it meant that the PSP occasionally displayed texels from bits of the texture that I hadn't initialised. To get around this I just manually repeat the last column/row of the texture when converting it on the PSP.

Another issue I fixed was relating to how I handled 'swizzled'** textures that were not an even number of texels. In the second screenshot on the left below, you can see a fringe of corrupt pixels down the right-hand side of each character's icon. This was due to me not correctly handling all of the texels the swizzled rows, but it only happened when the rows were not a multiple of 8 bytes (in the example below, the textures were 30x32 texels at 16bpp). Again, this is something SSB does that I've not seen in other roms.

I fixed a bug relating to how I was recolouring textures. In order to support some of the N64's more complex combiner modes on the PSP, I need to replace the RGB channels of a texture while maintaining the existing alpha channel. As it turns out, I wasn't handling this correctly for textures that weren't a power of 2. This is what is messing up the black background behind the 'Super Smash Bros' text on the first screenshot. Whoops.

Wow! That's quite a few bugs! Here's a few screenshots, with SSB running in R11 on the left, and the R12 work-in-progress on the right:







What's quite nice is that even though I've been fixing these with SSB in mind, there are likely to be lots of other roms which I've not tested that are relying on the same behaviour.

Graphically SSB is looking pretty slick, so now it's on to chasing down that dynarec bug :)

-StrmnNrmn

* The RDP has 8 tile attribute descriptors, which are used to tell the RDP how to interpret the data loaded into it's 4KiB of texture memory. They define properties such as the tile's format, width, height and whether to clamp or wrap and so on.

** On the N64, all odd rows in a texture have pairs of texels alternated (or more precisely pairs of 4-bytes of data.) The reason for this is that the N64's texture memory is composed of two separate banks of 2KiB, and organising texels like this allows for multiple texels to be accessed simultaneously when sampling from the texture. I use the term 'swizzled' loosely as it's quite a different process than swizzled textures on modern consoles (such as the PSP and the Xbox (see page 28)), even if it is performed for similar reasons.

Daedalus R11

Daedalus R11 is finally here. It took a little longer than I expected to merge the changes across to the sourceforge subversion repository but I got there in the end :)

Anyway, here are the latest files:

Daedalus PSP R11 for v1.00 Firmware
Daedalus PSP R11 for v1.50+ Firmware
Daedalus PSP R11 Source

Here's the changelist:

• [*] Large overhaul of rom settings and preferences. All settings should now be persistant.
  
• [+] Native support for palettised textures for faster rendering and less memory usage.
  
• [+] Provided a fixed size pool for all texture memory, to limit memory usage.
  
• [+] Expansion Pak enabled by default.
  
• [!] Updated rom info database to include save mechanism for many roms.
  
• [!] Fix memory leak in texture cache.
  
• [!] Fixed conversion of RGBA/32bpp textures with odd alignments.
  
• [!] Fix crash which occurred when recolouring textures in low memory situations.
  
• [^] Large rewrite of texture cache to reduce memory usage and improve performance.
  
• [^] Various optimisations to the way textures are looked up in the cache and installed.
  
• [^] Optimise offsetting/scaling of texture coordinates.
  
• [^] Improve performance of dynarec fragment cache and reduce memory fragmentation.
  

As always, let me know your thoughts on the comments pages. I don't always have time to reply to all of the comments, but I do read every one of them.

-StrmnNrmn

R11 Sometime on Sunday

I'm very close to having R11 ready for release, and I'm aiming to have everything finished some time tomorrow morning (that's Sunday morning, UK time.)

I've spent the day putting in number of changes to the way that Daedalus allocates memory for various lookup tables. Namely, I've replaced a couple of stl maps I was using to keep track of cached textures and dynarec fragments with sorted vectors, which should help reduce fragmentation and improve cache usage. Basically it should make things even more stable and give another small speedup.

I've also been through and updated the rom.ini file I talked about a couple of weeks ago to make sure that it contains accurate information for the save type. I noticed that many of the entries for European roms were undefined, which can cause various compatibility problems. Hopefully this should mean that a few more European roms are working in R11.

Finally I realised that there was a dynarec issue which was preventing Super Smash Bros from going in-game. Although that's not fixed (that's something for R12) I have disabled dynarec for SSB by default. With my various texture cache fixes SSB is now running in-game, albeit with messed up graphics and at just 15 fps. Here's a teaser screenshot of SSB running in R11:



Given how many people have been asking for SSB compatibility to be improved, I'm pretty sure this is going to be my main focus for R12. If I can fix the dynarec issue it looks like this is going to run at a solid 25-30fps or more.

Anyway, check back sometime over the next 12 hours for R11 (I'm off to bed for now, let's hope I don't lie in :)

-StrmnNrmn

R11 almost ready

Following on from last week's work, I've been busy fixing a few more issues relating to the way Daedalus handles textures.

To start with, I refactored the way that n64-format textures are converted to psp-format textures. Previously, I was converting the textures at the point at which they were loaded into texture memory on the n64. A result of this was that in order to support mirroring, I needed to keep a copy of the converted pixels in RAM. By moving the conversion process closer to the point that the textures are actually used on the psp, I've been able to remove this buffer and perform conversion and mirroring in the same step. This has approximately halved the memory needed for each texture, and is slightly faster than the previous approach.

The most significant change I've made is to fix a memory leak in the texture cache. I mentioned last week that I'd discovered that the texture cache was the biggest culprit for soaking up memory. It turned out that despite my fixes and support for 4-bit and 8-bit palettised textures, I was still running out of memory in certain situations. I did a bit more investigating, and discovered a resource leak that had been in the texture cache since it was first written (probably 7 or 8 years ago now!)

It turned out that in certain situations, several textures would hash to the same bucket in the hash table that I was using. This wasn't normally a problem, but occasionally the process which purges old textures from the cache was accidentally leaking textures. This was wasting video memory and causing the leaked textures to be re-converted on next frame.

The fix ended up being a very simple one-line change, and as a result the texture cache is now 100% leak-free. As an added bonus, it seems that the change has resulted in a nice 4-5% speedup - I suspect this is because the leaked textures are now no-longer being unnecessarily reconverted.

The final bit of work I've been doing is setting up a fixed-size pool for allocating textures from (well, there are actually two pools - one for fast VRAM and another of standard RAM for when this runs out). Despite the various improvements and fixes I've made to reduce the amount of memory being consumed by the texture cache, I wanted to put a hard limit on how much memory can ever be used. This change means that if the limit is ever reached, I just display white textures until some texture memory is freed up a little later. Previously Daedalus would just keep allocating RAM until it ran out of memory and crashed, so the new solution is much nicer :)

All in all I'm very happy with the state of R11. The changes I've made mean that I can permanently allocate 8MB for the Expansion Pak, and not worry about running out of memory. A welcome side-effect to all the texture changes I've made is an approximate 5-10% speedup over R11. On top of this Daedalus now remembers your preferences for each rom, so it's a little nicer to use.

I've still got a few small things to polish, but I'm hoping to release R11 by the weekend.

-StrmnNrmn

R11 Update

Wow, it's been far longer than I'd intended to give this update. I had a great time in Spain, and came back and spent a few evenings playing through Crackdown. It was quite nice to take a break for a few days :)

Since then I've been working on the various features I promised for R11.

I talked a bit about the texture cache being the main culprit for gobbling up memory while the emulator is running. When I started profiling this in detail, I realised that one of the worst offenders for memory consumption was mirrored texture support for 4 or 8-bit palettised textures. There were actually two main problems which were exacerbating the problem.

Firstly, I've never handled palettised textures directly in Daedalus. By that, I mean that rather than converting the palettised texture on the n64 to a palettised texture on the PSP, I've been converting it to a 32-bit RGBA texture. This means that on the n64, a 64x64 pixel 4-bit palettised texture would take up 2KiB. By converting this up to a 32-bit RGBA texture on the PSP, it takes 16KiB - an eightfold increase in memory usage.

The second issue which was compounding the problem was that the PSP doesn't have support for mirrored textures. In order to support this feature I have to manually duplicate and mirror the texture. This means that a 64x64 texture mirrored along the S and T axes on the n64 will become a 128x128 texture on the PSP.

The main problem I was getting due to running out of memory was due to the heavy use of mirrored 4-bit palettised textures in some games. A 64x64 4-bit palettised texture that took up 2KiB on the n64 would consume a huge 64KiB on the PSP - a 32-fold increase! The problem was that certain games were using dozens of such textures in a single display list, and the available memory was rapidly being exhausted.

So over the past couple of weeks I've been working on rewriting Daedalus's texture handling so that it supports 4-bit and 8-bit palettised textures directly. This has taken a lot more time than I'd anticipated because of the number of places in the codebase which have to fiddle around with texture data directly. I also spent a week trying to track down two horrible bugs (both of which turned out to be brain-dead logic errors on my part).

The great thing about this work is that not only does supporting palettised textures directly save a lot of memory, it also has a number of small performance benefits. Generating less texture data generally means a bit less work for the CPU (well, less cache usage), so converting palettised textures is now a bit quicker. Palettised textures are also a lot more efficient to render with (mostly due to the fact that they consume less bus bandwidth and can make better use of the PSP's texture cache.)

The other big chunk of work I've been bashing away at is improving the way that I handle preferences for individual roms. One of the big problems with the current setup with Daedalus is that the main daedalus.ini file consists of both global rom-specific details (such as the rom's name, save type, comments etc) and local user-defined preferences (such as whether to enable speed sync, disable dynarec etc). This means that I can't ship a new version of daedalus.ini without wiping out people's local preferences.

What I've done now is split daedalus.ini into two files. roms.ini will contain global rom-specific details, and an updated version will be distributed with every version of Daedalus from now on. If I know dynarec causes a certain rom to fail to run, I can add a setting for this in roms.ini, and everyone will be able to pick up the change in the next release. Another good example is the SaveType field; every version of Super Mario 64 uses a 4k EEPROM, and so once this is set up in roms.ini it should never need tweaking.

The other file I created is called preferences.ini. This file won't ship with Daedalus - the emulator will create this the first time you change some settings when playing a rom, and update it with any further changes that you make. This means that when you copy a fresh build of Daedalus across to your memory stick, the new build will pick up your existing preferences.ini file and so remember all of your settings.

The settings that Daedalus will currently remember for each rom are:

• Texture Update Check
  
• Frameskip
  
• Limit Framerate
  
• Dynamic Recompilation (used to override the setting in roms.ini if you're having problems with dynarec)
  
• Audio
  
• Adjust Frequency
  
• Controller
  

I'll be adding to this list over the coming months, as more options become configurable.

One other thing that will be stored in preferences.ini (which I've not coded yet) is all of the options from the 'Global Settings' page - stuff like the viewport size, stick deadzone, whether to display the framerate or not, etc.

So R11 is shaping up pretty nicely, even if it's taken a bit longer than I'd hoped. I have a few more things to work on, but I'll try to keep you all updated a bit more frequently as I work towards the next release.

-StrmnNrmn

R11 Plans

I had planned on posting this update on Monday, but I've spent the last couple of nights catching up on a few games that I've not had chance to play since they were released (Crackdown on the 360 and Afterburner : Black Falcon on the PSP for the curious :)

For R11 I'm hoping to fix the Expansion Pak support for once and for all. Memory is currently very tight, so I need to look at shaving off a few hundered KB here and there. Almost all the memory Daedalus uses is allocated up front - there are very few dynamic allocations at runtime, with the biggest culprit being the texture cache. So for R11 I want to introduce a pooled allocator for the texture cache, which will mean that when it runs out of memory, you just get white textures appearing rather than a hard crash.

The other feature I want to improve in R11 is the way that global settings and per-rom settings are handled. At the moment Daedalus discards any changes to settings that you make when you restart your PSP, and it can be incredibly tedious setting things up every time you run a game. This is quite a small feature to add, but I think it will make the emulator much nicer to use.

Behind the scenes, I want to spend a short while working on some scripts to handle packaging new releases for distribution. Current I do all of this by hand, and it's one of the things I least enjoy about the project. Hopefully, the more automated I can make this, the more frequently I'm likely to release builds :)

I'd like to get all these changes done and release R11 within a couple of weeks. I have a couple of busy weekends coming up, so I'm not going to specify an exact date. You can expect it before May though (I'll try not to be a couple of days late this time :)

R11 is essentially going to be a compatibility release - hopefully the Expansion Pak support will lead to a few more roms running (Majora's Mask being one I've already verified). Looking further ahead, R12 will be back to concentrating on speed (as it happened, R10 achieved a 10-15% speedup without having implemented the majority of the optimisations I had planned :)

-StrmnNrmn

PS Off to Spain again over the Easter bank holiday weekend. Back on Tuesday :)

R10 Reception

I just wanted to say a quick thank you for all the feedback I've received on the R10 release. I'd been looking at it as quite a small update, but people seem to be very happy about the incremental speedup and new features such as frameskip and so on. I found releasing R10 within 4-5 weeks of R9 was really hard work, but I'm now convinced that releasing smaller updates more regularly is the right way to go. I'll be following this post with some details about the plans for R11.

Finally, it turns out that this blog had over 40,000 visits over Sunday/Monday, which is incredible - thanks for continuing to read :)

-StrmnNrmn

Daedalus R10

This is a few hours later than I'd hoped, but here's R10:

Daedalus PSP R10 for v1.00 Firmware
Daedalus PSP R10 for v1.50+ Firmware
Daedalus PSP R10 Source

This is the changelist:

[+] Added frameskip option.
[+] Added framerate limiting option.
[+] Added adjustable stick deadzone.
[+] Allow pause menu to be activated even when rom emulation has hung.
[!] Fix crash when no roms found, added explanatory message.
[!] Fix flickering when small number of roms found.
[^] Fix texture hash frequency check.
[^] Finally got code compiling with -O3 optimisation flag in GCC.
[^] Use VFPU for InvSqrt (thanks hlide!)
[^] Improved VFPU code for clipping and tnl (thanks Raphael!)
[^] Improved inlining of AddTri.
[^] Reduced time spent searching for overridden blend modes.
[~] Remove debug console in public release builds (smaller footprint and slight speedup.)

I'll post tomorrow with details on what I want to work on for R11. In the meantime, enjoy!

-StrmnNrmn

R10 Countdown

I'm in the process of tidying up my current build so that I can release R10 over the next few days.

There are a number of features/optimisations still on my TODO list, but as I promised last month, I'd like to release R10 by the end of March. I think frequent, small updates are better than keeping everyone waiting months between releases.

Although R10 will be a smaller update than R9, there are some great improvements (most of which I've already talked about):

• An approximate 10-15% speedup
  
• Frameskip, framerate limiting and stick deadzone tuning
  
• Various small bugfixes
  

I'm hoping to have everything ready by Sunday afternoon at the latest.

One feature which might not make it is the Expansion Pak support. I mentioned that I'd finally fixed the bug that was preventing this from working, but I've been having difficulty resolving the various memory issues that it causes when enabled. Rather than delay R10, I'd prefer to disable the Expansion Pak support for now and release R11 early - as soon as I've fixed the underlying problem. I'll keep you posted.

-StrmnNrmn

Frameskip

A couple of people have been commenting about the mysterious frameskip version of Daedalus R9 which appeared a short while ago. I'm not going to link to it because I can't verify where it came from. That said, I've not checked my email for a week so maybe the author has emailed me about it :)

Anyway, it just so happens that I implemented frameskip in R10 on Sunday, so expect this to be a supported feature in the next official release. I had been planning to add this to R9, but I forgot :) It's no big deal - it's about 20 lines of code.

It does give a slight speedup, but not always as much as you'd expect. For instance, skipping every other frame won't double the framerate, as not all the time is spent rendering. Paradoxically, it tends to have more of an effect on roms that are already running fairly fast. Hopefully for some roms it will make the different between them being barely playable and playable though.

There are a few other things people have been asking about which I will implement for R10 too:

• A configurable deadzone for the stick
  
• A configurable framerate limiter
  

-StrmnNrmn

A look inside Daedalus

(This is quite technical post, probably only of interest to other C++/PSP developers.)

Since I fixed the issue stopping the Expansion Pak support from working, I've been testing daedalus with the feature enabled to see if the added pressure on available RAM causes any new issues. Most roms that I've been tested have been running perfectly, but I've been experiencing occasional crashes through running out of memory. I believe this is due to a small leak somewhere, so in an effort to track it down I've been improving the tools I use to track memory usage.

In the improved tracker I override the global new and delete operators, which lets me perform some logging on every allocation/deallocation made during the course of executing the emulator (this isn't quite true, as I don't currently log calls to malloc etc, but it's good enough for my purposes). At the start of each overriden implementation, I keep track of the calling function's return address with the following snippet of code:


u32 ra;
asm volatile
(
"sw $ra, %0\n"
: "+m"(ra) : : "memory"
);


I log this return address along with the allocation size and the returned pointer for every call to new and new[]. For calls to delete and delete[], I just log the address of the memory being freed and the caller's address. This data is all logged to disk across the USB connection using PSPLink.

The logfiles look a little like this:


Allocating 36 bytes - 09c40620 - RA is 08953a94
Allocating[] 8192 bytes - 09c40a00 - RA is 0895e8bc
Allocating 12 bytes - 09c3fce0 - RA is 08964898
Allocating 12 bytes - 09c40970 - RA is 089648b0
Allocating 12 bytes - 09c409d0 - RA is 089648c8
Allocating 12 bytes - 09c408e0 - RA is 089648e0
Allocating 20 bytes - 091ceb20 - RA is 089645e8
Freeing 09c3fce0 - RA is 08962374
Freeing 09c40970 - RA is 089621fc


In order to analyse the results I've written a PC tool which scans through the logfile one line at a time 'replaying' the allocations and deallocations in the same order that they occured on the PSP. The analyser keeps track of the current state of allocations at any point in time, matching up any calls to delete with the corresponding call to new. This means that at any given time the tool has a complete list of all outstanding allocations.

I can discover any memory leaks by shutting down the emulator and continuing to record the logfile while it frees up all allocated resources. By replaying the logfile the analyser can identify any leaks, as these are (mostly) the only remaining allocations at the end of the logfile. I can then run the corresponding return addresses through psp-addr2line to discover where the leaked memory is being allocated from.

The other cool feature of the tool is that it builds up a graphical representation of the state of memory allocations at any point in time. This is really useful for figuring out where all the available RAM is going.

Here's a picture showing where most of the PSP's memory is being used while emulating Mario 64 (I've added the labels on by hand, the tool doesn't do that :)



Each pixel corresponds to 16 bytes of RAM. The smallest blocks are 64x64x16 bytes = 64KB. 1MB chunks are formed from 4x4 64KB blocks. The black space corresponds to both unallocated memory, and also memory allocated outside of the tracker (e.g. calls to malloc, memory used by PSPLink, the CRT, static data areas etc.) You can see that the "Emulated RAM" accounts for just over 8MB - this is because I enabled the Expansion Pak while testing. Dynarec currently uses about 6MB - Ideally I'd like to reduce this down to around 4MB soon.

You'll notice that almost all the memory Daedalus uses is for these big fixed-size allocations. What little dynamic allocation it does at runtime is limited to:

• Keeping track of hot-trace hit counts in the Dynamo implementation
  
• Textures and texture caching
  

As it turns out, the out-of-memory issues I've been having have been due to the texture cache going crazy and chewing up around 3MB of memory (typically it just uses 200-300KB or so). I've not figured out the root cause yet, but the tool has helped point me in the right direction.

All in all I think this is a pretty nifty utility as it stands, but I've been thinking about a few features that would make it even better:

• Log the time and current frame alongside each allocation/deallocation. The analyser can then use this information to see how much 'churn' there is over time. Minimising this should help improve performance and reduce fragmentation.
  
• Every memory allocation has a small housekeeping overhead (for alignment, keeping track of the allocation size etc). The tool could generate a histogram of allocation sizes to demonstrate how much memory is being wasted through tiny allocations, and give some indication of where pooling or freelists might help.
  

These are probably features for some point down the line however :)

That pretty much sums up the tool. If this code (either for the tracker or the logfile analyser) would be useful to anyone, let me know and I'll add it to Subversion alongside the rest of the Daedalus code with R10.

StrmnNrmn

Daedalus R10 Optimisation Progress

I didn't mean to leave it quite so long since last weekend's update, but I've been working hard on a number of optmisations for R10. Oddly enough these are mostly new issues that I've found - most of them don't exist in the list of tasks I came up with a couple of weeks ago. I think that shows how much scope there is for optimising Daedalus!

Firstly, I finally managed to get Daedalus compiling with GCC's '-O3' setting. This flag turns on all of the optimisations that GCC provides. When I've tried to enable this flag in the past I've had numerous strange crashes and odd behaviour, so all releases of Daedalus to date have been compiled with -O1.

I updated my local installation of the PSPSDK last weekend and decided to try the -O3 setting again. I was pleased to find that Daedalus ran without crashing, but there was still some odd behaviour which I eventually tracked down to my use of the famous InvSqrt function. You can read a bit more about my findings on the pspdev forums.

Enabling -O3 tends to slightly increase the code size (the EBOOT.PBP has increased from around 850KB to 900KB), but the speedup is quite noticable - my estimate is that Daedalus runs around 5% faster with -O3 over -O1.

As a result of the thread I started on the pspdev forums, hlide and Raphael both came up with some great suggestions for how I could optimise my use of the VFPU.

When I originally wrote the VFPU code for TnL and clipping there were still many undocumented/unsupported functions. A few months down the line and hlide and co have discovered a couple of instructions which are perfect for my needs - namely vuc2i and vc2i. These two functions take a 32-bit value comprising of 4 (un)signed 8-bit chars and unpack them into a vector of 4 32-bit fixed point numbers. It turns out that these instructions are perfect for converting the N64's packed colour and normal values into a format I can use in the VFPU code.

The various VFPU tweaks I've made have given Daedalus another 5% or so speedup.

The final set of changes I've been working on this week have been to do with how I handle certain blend modes. Some of the N64 blend modes are too complex for the PSP to deal with precisely, so I have a large table of 'override' blend modes which allow me to make as good an approximation of the N64 mode as possible. It turned out that looking up these blend modes was very expensive, so I've rewritten how this is handled to make it more efficient. The end result is another small speedup.

Overall these three changes give a combined 10-15% speedup on the various games I've tested, although there are roms that lie outside this range (some show an even greater speedup while others are more or less unaffected by the changes).

There's still quite a lot more in the way of optimisations that I want to get in for Daedalus R10 (mostly stuff I mentioned earlier) so hopefully these numbers will improve even further over the next couple of weeks.

-StrmnNrmn

Weekend update

It's been a busy week at work, what with catching up after my week off and GDC, so I've not managed to post as many updates as I'd have liked.

On Daedalus I've been starting to take a look at the list of potential optimisations I listed and working out what to tackle first. To help me do this my first job is to do some work on Daedalus's profiler, to try and figure out where the biggest wins are going to come from. Hopefully I'll be able to report back with some interesting findings this weekend.

On a related note, I've spent the morning looking at converting the source control I'm using at sourceforge from CVS to Subversion. I've been meaning to do this for some time. I've never really been a fan of CVS, and as I'm using Subversion for other projects at work and at home I thought it made sense to migrate Daedalus over too.

So you can now access the latest Daedalus source* through Subversion:


svn co https://daedalus-n64.svn.sourceforge.net/svnroot/daedalus-n64/trunk daedalus-n64


With CVS I usually only updated the source alongside every release. Ideally the repository would contain an up-to-date copy of my local build, but I've had problems in the past where people have distributed 'intermediate' builds of Daedalus PSP, bugs and all. I only ever release new builds when I think there are enough new features and its stable enough to make it worthwhile for people to download and install; updating a source a bit less frequently gives me a bit more control and helps prevent everyone's time being wasted with intermediate builds. I think that I'm going to continue with this policy for the time being. We'll see how it goes.

-StrmnNrmn

*This is still just the R8 source which I lifted from CVS today. I'm in the process of testing whether this compiles OK, then I'll refresh the repository with all the changes from R9. I'll update this post when the R9 source is available.

Edit: R9 source commited to Subversion, all seems to be compiling OK.