Fixed!

I'm very pleased to be able to say that I've finally managed to fix the nasty bug I blogged about on Thursday.

I'll go into more details in a later post, but in essence the problem was due to very rare situations where the trace recorder would exit a trace when there was still a branch delay instruction pending. This caused the fragment generator to inadvertently skip the branch instruction, causing the odd behaviour I was seeing.

For reference, here are some updated figures for Super Mario 64 and Mario Kart (initial results are from a previous post). Generally the current changes seem to indicate an overall speedup of 20%-25%, which is great for a few days work. What's even better is that I've still not implemented all the optimisations that I have planned for R7, so hopefully these numbers will look even better soon.

Scene	R4 Framerate (Hz)	R5 Framerate (Hz)	Current Framerate (Hz)
Mario Head	3	6	8
Mario Main Menu	14	25	30
Mario Peach Letter	6-7	11	13
Mario Flyby (under bridge)	6	10	12
Mario In Game	5-6	9	11
Mario Kart Nintendo logo	10	23	24
Mario Kart Flag	6	11	13
Mario Kart Menu	7	11	13

(I'll update with results from Zelda shortly - I have to go to a BBQ now!)

-StrmnNrmn

Captain Morgan's compatibility results

It looks like Captain Morgan has put a lot of effort into doing compatibility testing with Daedalus R6. Thanks Cap'n! (thanks for your email too - I promise I'll get back to you just as soon as sort this issue out!)

[Update]

Don't miss Wally*Won_Kenobie's R6 compatibility list, which is also excellent. Wally has been collecting missing_mux.txt files for me too, for which I am indebted :)

-StrmnNrmn

A great optimisation/bugfix..

..with a catch.

This week I've been posting about various speedups I've been making by implementing various opcodes in the new dynarec engine. Although I have implemented most of the commonly used opcodes now, after my previous post I decided to add some temporary logging to the emulator to see how often the remaining unhandled opcodes were being used. Two that immediately jumped out at me were JAL (Jump And Link, which is used to perform a function call) and JR (Jump Register, which is used to return from a function call.)

These two instructions are very heavily used, and I was surprised to realise that I'd not implemented them! They're pretty easy to code - in fact, due to the way I construct the instruction traces that are fed into the dynamic recompiler I could effectively ignore the JAL instruction and JR just required a couple of lines of code.

So far so good. I was expecting a modest speedup - maybe another 2-3% on top of all the previous changes I've made this week. After compiling and running the new code, I was amazed to see an improvement of over 10%! Surprised with the figures I was seeing, I did a full rebuild and checked the results again with several different roms. They all showed the same kind of speedup.

I've been programming (and more importantly debugging) long enough now when I should trust my instincts - call it my programming 'Spider-Sense' tingling if you will, but I knew something didn't quite add up :). In situations like this in the past, rather than taking an unexpected speedup for granted I've spent time investigating the root cause to find out exactly what's going on. At the very least I'll simply satisfy my own curiosity, but often I'll find some useful information along the way too (e.g. other related improvements and optimisations etc.)

So I started looking through the code and rerunning a few roms to try and get a handle on what was causing such a significant improvement. After a short while I realised that all the roms were now generating a lot more potential traces for the dynarec engine to consider for recompiling. This confused me even more, because this behaviour should slow the emulator down rather than speed it up. Another puzzling thing was that the only observable behaviour of my changes should be the speed of emulation - but it looked like my change was somehow changing the flow of execution in the rom.

After bit more head scratching and debugging, I finally realised what had happened. In making my changes, I had inadvertently fixed a bug in the dynarec engine that was causing the recompiled code to jump back out to the interpreter whenever a JAL instruction was encountered! This bug had been in the dynarec engine since the first day or so, but because its only side effect was to slow down the emulator rather than something more obvious (i.e. a crash!) it had remained undetected for a couple of months.

So I had figured out what the reason for the 10% speedup was, and I could finally get to bed safe in the knowledge that I had fixed a nasty, subtle bug along the way. Brilliant!

It was only then that I noticed a couple of new problems that I hadn't seen before: The emulator began hanging in places that had previously been fine - such as Peach's letter at the start of Mario 64. On the occasions the emulator managed to get past that point, I found out that Mario wouldn't move or jump (but strangely the c-buttons and pause menu worked fine)

:(

I've spent the last couple of evenings trying to figure out why fixing one bug is causing another. I've finally managed to find a way of reliably reproducing a hang within a few seconds of starting the emulator up. This is important because my best chance of identifying and fixing the problem is to be able to run the PC build of the emulator with my 'fragment simulator' enabled. The simulator is very slow however (about 100x slower than running the emulator normally), which is why it's important to find a way of reliably reproducing the bug very early on in the emulation.

So that's what I've been up to over the past couple of days, and why I haven't been able to reply to people's emails or comments on this blog. Now that I can reproduce the bug in the fragment simulator I'm confident that I can get to the bottom of it. I'll keep you posted with any developments and try to go through emails/comments just as soon as I've cracked it.

-StrmnNrmn

Further dynarec optimisation

I've spent the last couple of evenings working on adding support for additional instructions to the dynamic recompiler. With every instruction I add, the generated code becomes a bit more efficient as I can avoid various bookeeping work (such as flushing all the cached registers out to memory.)

I've added code to handle the following ops:

• MULT, MULTU (multiply, multiply unsigned)


• DIV, DIVU (divide, divide unsigned)


• MFLO, MFHI (move from lo/hi)


• MTLO, MTHI (move to lo/hi)


• LB, LBU (load byte, load byte unsigned)


• LH, LHU (load halfword, load halfword unsigned)

So far I'm seeing around a 5-6% speedup with these changes (on top of the 10-12% speedup I talked about on Sunday). I am generating slightly more code as a result of this work, but given the large savings I made over the weekend this isn't much of an issue.

My next job is to look at optimising the remaining load/store instructions - I just have LWU/SB/SH to do (ignoring the 64 bit instructions for now). Once that's done I'm going to have a look at optimising sequences of load/store operations by caching the base address between uses. I think that should give a significant speed up for memory intensive chunks of code.

-StrmnNrmn

A productive weekend

I've had a fairly productive weekend. I've been working on a few improvements on the dynamic recompiler, and I've managed to both decrease the amount of memory it's using (by approximately 10-12%), and increase the emulator's speed (by around 7-10%).

I don't want to get into too many details just yet, as I'm planning on putting together a more detailed post with all the gory details (and a few graphs :) later in the week.

In a related change, I've also managed to identify and fix an issue (read 'bug') with the dynarec that may have been causing stability problems on v1.0 firmware PSPs. This may explain some of the differences in stability users of the different builds have been seeing.

-StrmnNrmn

Windows CE device emulator source

For anyone reading this blog with an interest in emulator development, Microsoft have just released their Windows CE device emulator as shared source.

As the post mentions, it includes the source for an ARM -> x86 JIT compiler which makes interesting reading, (take a peek at armcpu.cpp)

-StrmnNrmn

R6 Released

I've got to keep this short as blogger.com is going down in 5 minutes :(

Change log:

[+] Added over 50 new combiner modes
[+] Added support for c-buttons
[+] Load roms from ms0:\N64 in addition to local roms directory
[!] Fixed backface culling issues
[!] Correctly implemented flipping to avoid flickering with certain roms
[!] Plugged memory leak in texture handling code, fixing various crashes
[!] Fixed issue which caused screenshot function to hang the emulator

You can grab it here.

For R6 I've mostly been focusing on fixing a number of graphical issues (namely adding combiner modes to popular roms). I've also managed to add a couple of nice usability improvements (in particular mapping the c buttons to the dpad, using the circle button to toggle back to the n64 dpad)*. I've also been able to track down a couple of bugs that affected stability.

I've still not decided what to concentrate my attention on for R7. The main areas are:

• Speed


• Compatibility


• Graphics


• Usability

These are all quite broad areas, but it would be good to get a feeling for what people are most interested in seeing improved. Any comments would be most appreciated.

-StrmnNrmn

* I should point out that I had dozens of people suggest this to me via email and through comments on this blog, so I can't take any credit for this idea :)

R6 up within the hour..

I had to pull a long shift at work (14 hours!) so I've only just got in. I'm in the process of rebuilding a release build, updating docs, zipping things etc and should have a new build uploaded by 1am (BST). It looks like blogger.com is down at 5pm (PST) so if I don't post an update soon, check the SourceForge site for the update.

-StrmnNrmn

R6 Tomorrow (hopefully!)

I don't mean to tease, but I am hoping to release the next build of Daedalus PSP tomorrow. I've spent the last couple of days polishing a number of graphical issues and I need to set myself a target date otherwise I'll just keep tinkering for ages :) I'll have a longer post tomorrow with details of the changes that have made it into R6.

In the meantime, I've answered a few of the most recent questions on the previous comments page.

-StrmnNrmn

Graphical fixes

Here are a few of the significant graphical fixes I've made so far for R6.

Firstly, I managed to fix the horrible flickering that happened when running various roms (Paper Mario was a good example). It turned out that I was making an assumption that roms executed exactly one display list per frame. I assumed that each display list would clear the screen, render everything, and then wait for the screen to flip. As it turns out, some roms execute multiple display lists per frame. In the case of Paper Mario it executes 2 display lists per frame (one which clears the screen, then another which renders everything). By making sure that I only flip after the second display list executes, I avoid the flickering (the actual solution is a little more involved but this is the general idea).

The next significant glitch I've fixed was to do with backface culling of triangles. Basically, when I ported the graphics engine over from the PC version, I forgot to implement the two or three lines of code which handles this. It was a very small fix, but it corrects a number of significant graphical issues (notably all the walls getting in the way in Quest 64).

Finally, I've managed to track down and fix a significant memory leak in the texture handling code. I believe this was causing many of the random crashes that were occuring when leaving the emulator running for several minutes or more (basically through running out of memory). Before applying the fix I found that the Super Mario 64 would crash within 4-5 minutes. After applying the fix I've been able to run Mario with no problems for over 30 minutes.

I'll keep you posted as to when you can expect a new release. I'm quite excited about the memory leak fix, so I'd like to get a new release out as soon as I can implement some of the other things I promised for R6.

-StrmnNrmn

PS I know I've been crap at replying to emails :( I'm hoping to get this release out and then I'll spend a few hours sorting out my mailbox and replying to various comments here.

Congratulations Italy!

Congratulations to Italy on their win tonight!

Just a quick note to apologise for the lack of updates recently. I've been busy with work for the past couple of weeks, but hopefully it should be business as usual now. I'll try to post a more interesting update tomorrow or on Tuesday.

-StrmnNrmn

Deciding what to optimise

Whenever I start to answer questions on the comment pages I always end up going into too much detail for a quick response and end up deciding to put up a new post instead. I hope this isn't too annoying :)

In response to Plans for R6 xiringu and ukcuf16 had a couple of interesting suggestions for performance improvements.

First up, from xiringu:

instead of working with a 300x200 screen, work with only half height 150x200 and then display an empty line every other line to get the final 300x200.

That's an interesting idea - it's a trick that's been used by demo coders for years to get a few extra fps. I'm not sure this is going to provide all that much of a speedup to Daedalus though :( The reason for this is that currently rendering only contributes a small amount to the overall cost of each frame, so even if rendering time was totally eliminated, the framerate wouldn't change much. As an example, let's take something like Zelda which currently runs at around 4 fps. At 4fps it means each frame takes 1000/4 = 250 milliseconds to render each frame, which is broken down something like this:

CPU emulation: 200 ms
Display list parsing: 40 ms
Rendering: 10 ms
Total: 200 + 40 + 10 = 250 ms (i.e. 1000/250 = 4fps)

Assuming that we could totally eliminate the rendering time, this would now look like:

CPU emulation: 200 ms
Display list parsing: 40 ms
Rendering: 0 ms (no cost)
Total: 200 + 40 = 240 ms (i.e. 1000/240 = 4.17fps)

So the very best we could hope for in this case would be a .17fps improvement in the framerate :(

ukcuf16 wrote:

Just wanted to ask if there is ever going to be frame skip in later versions :)

What ukcuf16 is suggesting is that the emulator renders one frame, then skips the next. Alternating frames like this should halve the cost of rendering, at the cost of making the framerate a little less smooth.

Again, this is an interesting idea, but I don't really see this having much impact on the framerate as things stand at the moment. Working out the potential speedup is a little more complicated, as we have to take the average time over two frames. The numbers look something like this:

Frame1 CPU emulation: 200 ms
Frame1 Display list parsing: 40 ms
Frame1 Rendering: 10 ms
Frame2 CPU emulation: 200 ms
Frame2 Display list parsing: 0 ms (skipped)
Frame2 Rendering: 0 ms (skipped)
Total: 200 + 40 + 10 + 200 = 450 ms
Average: 450 / 2 = 225 ms (i.e. 1000/225 = 4.44fps)

So even implementing a frame skip mechanism would only give a tiny 0.5fps speedup.

To take this example to its ultimate conclusion, let's assume that I could somehow eliminate the entire cost of display list parsing and rendering:

CPU emulation: 200 ms
Display list parsing: 0 ms (no cost)
Rendering: 0 ms (no cost)
Total: 200 ms (i.e. 1000/200 = 5fps)

Even if I could somehow (magically) reduce the cost of rendering to 0 milliseconds, we'd still only see a 1fps speedup. However, if I can halve the cost of CPU emulation (which is much more likely given the speedups already seen with the new dynarec engine) this is what the calculations look like:

CPU emulation: 100 ms (now twice as fast)
Display list parsing: 40 ms
Rendering: 10 ms
Total: 100 + 40 + 10 = 150 ms (i.e. 1000/150 = 6.66fps)

At the moment I feel that there are more gains to come from optimising the CPU emulation, which is why I've been concentrating on this area recently. As the cost of CPU emulation falls relative to rendering then the ideas suggested by xiringu and ukcug16 will start to become more attractive.

-StrmnNrmn

Source code rant - update

I was going to post these responses on the comments page, but I was worried that they'd get buried and I have a few important points to make.

From laxer3a:

Now you start to see why the TYL emu source was released shifted by one version from the bin. :-)

I was thinking about doing this, but it's important that people are able to tinker with the source as they please. I usually only ever have the time to refresh the CVS depot when I release anyway, but if other people get involved in the project then this will need to happen more regularly.

gregnoid wrote:

Naa, this pre-release is just a fake !
Becaus PspMonkey had not compiled this.

I need to make it clear I was ranting about PSdonkey, not PSmonkey. I have a lot of respect for PSmonkey and I wouldn't want people to think I was criticising him. It's unfortunate that so many people confuse the two names. Remember: donkey = large four-legged member of the horse family (likes hay, sombreros etc). Monkey = amusing, cheeky primate (likes bananas, mischief, etc) :)

psdonkey said:

About the pre R5 build that I made. Yes I did change a couple of minor things in the source code and things seemed to run a tad bit better. However, after reviewing your updated R5 release, none of the changes that I made in the other build had any effect in this new R5 build that you released. In fact most of what I did was clean up some of the excess code and I can see that you already did this in your R5 release.

I appreciate you clearing up the situation and making your source available - thanks for doing this. I really wasn't expecting to see this happen, so accept my apologies for the criticism I levied in my previous post. I had a bit of a Hulk rage going on and it wasn't really justified.

You make a really good point about having a shared directory for roms between Daedalus and Monkey64 - I'll look at rolling this change into the next official release (R6). If you're really keen on helping contribute to Daedalus then I think you should drop me an email and we can talk about the possibility adding you as a contributor on sourceforge.

-StrmNrmn

Plans for R6

I'm back from Spain now. I had a great time in Barcelona, it's a bit of a shame to be back :)

I'm planning to have quite a quick turnaround on for the next release, i.e. hopefully I'll have something ready by the end of next week, or early July. I want to concentrate on fixing a bunch of graphical issues (adding new combine modes to fix various pink+black textures etc). I'm also going to look at reducing memory requirements - I think the stability problems associated with running the emulator with dynarec for an extended period of time are a result of running out of memory. This should also help to improve the Expansion Pak support. If I get enough time I'll look at adding support for configuring the controls on a rom by rom basis. Finally, I also want to look at improving savegame support.

-StrmnNrmn

PS Congrats Ghana + Australia :D

Away for a few days

I'm going to Spain for a few days to celebrate a friend's birthday. I'll be back on Monday sometime, so I'll try and respond to various questions/issues about the R5 release then.

Buenos nachos! :)

PSdonkey's build

PSdonkey made this comment when releasing a pre-release of R5 last week:

I went ahead and compiled the new source for everyone and also added a couple of minor changes to the source for speed improvements.

As I have no way of getting in touch with him directly, I'd like to ask him publicly if he could forward me a set of diffs for the 'speed improvements' he applied. Not just because this is a requirement of the GPL (the license under which the Daedalus PSP source is made available), but because I think it would be beneficial to the project to apply these changes to the main source tree. Having said that, I suspect PSdonkey might simply have been attempting to take partial credit for several weeks development work. I'll let you know if I receive any diffs...

Daedalus PSP R5

I've just uploaded the R5 release to sourceforge. Here's the changelist:

[+] New DynaRec engine, resulting in significant performance improvements
[+] New front end - ability to toggle a couple of options (more to come)
[+] Save game first pass (eeprom4k, eeprom16k and mempak)
[^] Various interpreting engine optimisations
[~] Use .png fileformat for background images, save ~380KB
[~] Stripped out unnecessary code, save ~250KB

By far the most substantial change was the addition of the new dynarec engine. As detailed in previous posts, this is still some way from completion but is already providing significant benefits (around a 2x increase in speed in many roms).

I've also added the groundwork for a new front end and implemented a first-pass of the savegame system. The savegame support isn't fully tested so I'm expecting a few teething problems - please post any bug reports on the sourceforge site (preferably!), the comments page or email me (check the readme.txt..)

I'm not too sure what I want to concentrate on next. It's been over a month since the last release and I think that it would be a good idea to knock out the next few releases in quick succession, to help me pick up some momentum that I've lost. If I aim to do this I'll probably concentrate on some nice (but quick) improvements such as various graphical fixes, savegame support and per-rom control configuration. Any suggestions welcome :)

Linkage:

R5 Source
R5 for v1.00
R5 for v1.50

Brief Update

This is just a brief update as it's been a while since my last post. I'm hoping to release a new build tomorrow, possibly Thursday at latest. I was planning on making an official release last weekend, but I got sidetracked polishing a few things. I've got a slight bit more to finalise, but there should be a couple of nice little additions since the source drop last week.

Source updated

Earlier this evening I updated the project CVS repository with the latest version of the code. Normally I only do this when I release a new build, but I know people have been playing with the code and have expressed an interest in seeing the latest developments.

I'm not quite ready to release a new binary yet (still a few more optimisations I want to make and various bugs to fix first), but I'll try and do this within the coming week.

Incidentally, updating the source normally only takes 20 minutes or so, but it took a good couple of hours tonight. Sourceforge updated their CVS service recently (May 12th) and as a result I had to spend a couple of hours updating WinCVS, generating new SSH keys and the like. Hopefully it won't be so painful next time around, or I might just lose the will to live.

As a more general update, I cleared a couple of things from my TODO list sorted this weekend. I'm caching floating point registers for most of the single-precision Cop1 instructions, which are now implemented directly in the dynarec code. I've not timed this in depth yet, but it's shaving 10-20ms/frame off the intro to Mario 64 (Mario's Head), which is particularly FPU heavy (i.e. I'm getting ~160ms/frame rather than ~180ms)

Finally I need to have a good think about how to go about optimising the double-precision floating point performance. As the PSP doesn't have hardware support for double precision floating point this is currently very expensive (i.e. adding 2 doubles on the n64 takes just one instruction - on the psp this balloons to several hundred as it all has to be done in software).

Currently I cheat and cast all the double-precision floats to single-precision values before performing the calculations. Although this is much faster it obviously loses a lot of precision, so I need to be careful it's not going to break any roms. Also even the float->double/double->float conversions are pretty expensive so it's still not an ideal solution. Fortunately not many roms seem to use double-precision maths extensively (presumably because it was relatively expensive on the n64), and where they do use it they don't seem to be too sensitive to the fact that I'm throwing most of their mantissa away :)

Some initial benchmarks

I've been really busy working on the new dynarec engine, so I've not been posting as frequently as I'd like. I've made a lot of progress in the following areas:

• Most integer arithmetic and logical instructions now implemented (i.e I'm now generating optimised assembly for these instructions rather than calling a generic function to handle them


• Regsiter caching implemented (although I'm only using a greedy allocation algorithm at the moment, as I've not yet fully implemented the fast linear scan algorithm I talked about in the previous post)


• I'm directly linking all direct branches to compiled fragments


• I'm linking to all indirect branch targets

So far I'd say I'm around 40-50% through the work on the dynarec engine.

Now for some stats :) The following table compares the framerates at various points (previous framerate is for the R4 release of Daedalus, current framerate is for my most recent development build):

Scene	Previous Framerate (Hz)	Current Framerate (Hz)
Mario Head	3	6
Mario Main Menu	14	25
Mario Peach Letter	6-7	11
Mario Flyby (under bridge)	6	10
Mario In Game	5-6	9
Mario Kart Nintendo logo	10	23
Mario Kart Flag	6	11
Mario Kart Menu	7	11
Zelda Nintendo Logo	20	23
Zelda Start Menu	2-3	4
Zelda Main Menu	10	13

Overall I'd say the dynarec is currently achieving up to a 100% speedup in the roms I've tested, which I'm very excited about. Mario is certainly starting to feel a lot more playable, and the Mario Kart menus are a lot more responsive now.

I specifically included Zelda in the results because I'm not seeing the same kind of results there, so I need to take a closer look at what's going on there (it's quite possible it's just using a few of the arithmetic and logical ops I've not spent time optimising yet).

A twofold improvement in framerate is pretty good, but I now think I can do a lot better. Here's the list of things I currently have on my 'TODO' list:

• Fully implement all the remaining integer ops (including all the 64 bit instructions)


• Finalise implementation of the fast linear scan register allocation algorithm


• Keep track of 'known' values for specific registers and use this to optimise the generated code (e.g. most of the time the top half of the N64's 64 bit registers is just sign extended from the lower half)


• Cache the memory location pointer to by the N64 stack pointer (SP) and optimise load/stores using this register as a base pointer


• Optimise all memory access instructions (currently all the cached registers get flushed for all memory accesses other than LW/SW/LWC1 and SWC1)


• Detect and optimise 'busy wait' loops (e.g. many roms sit in a tight loop waiting for the next vertical blank interrupt to fire which is just wasting cycles on the PSP)


• Implement all the branching instructions (I've currently only implemented BNE, BEQ, BLEZ and BGTZ)


• Implement instructions and register caching for all the cop1 (floating point coprocessor) instructions. (I think this will give a huge speedup.)

Although the list is quite short, there's quite a lot of work there. What I'm quite excited about is that I think these changes will start to provide significant speedups as they're implemented. I don't want to get too far ahead of myself, but I'm starting to feel that certain roms are going to be very playable in the not too distant future.

I'm going to try and release a new version of the emulator soon. Unfortunately it's probably not going to be this weekend (due to various social commitments); towards the end of the following week is more likely. I'd certainly like to get a version released before the World Cup starts and all my free time is taken up watching football :)

-StrmnNrmn