Garbage going crazy

Questions about the LÖVE API, installing LÖVE and other support related questions go here.
Forum rules
Before you make a thread asking for help, read this.
grump
Party member
Posts: 947
Joined: Sat Jul 22, 2017 7:43 pm

Re: Garbage going crazy

Post by grump »

pgimeno wrote: Sat Jun 05, 2021 8:35 pm Was that a private conversation, or a public one?
I raised an issue in the Github project with the same code from this thread.
I'm not familiar with that terminology, so I may easily be wrong. From my reading of this: https://en.wikipedia.org/wiki/Inline_ca ... ne_caching it appears that the term "megamorphic" refers to a state in which in a certain code path, a certain variable (or several of them) adopts values of multiple types during a trace.
I think it just means that the function that is called in a specific location is chosen from a large set of possible functions, and the function that is chosen varies a lot.

The only thing thats truly dynamic in my code is the selection of functions. There are no dynamic allocations, or changing types. There are no dynamic tables or types, not even a single key that gets added or removed at runtime. The number of tables, the keys and the number of values in those tables are constant after initialization. All logic is based on selecting a function based on global state. I thought I was being so clever when I wrote almost branchless code that uses zero runtime allocations.
Shouldn't that be

Code: Select all

    return tick()
to be a proper tail call? Or is LuaJIT clever enough to figure out that there's no difference and use a tail call in that case? I doubt it.
Yeah, that's just me confusing Lua with MoonScript which adds the return implicitely. The return is there in the actual code. It's not much different from yours. I'm trying to pass as few arguments as possible though, because I fear that the compiler runs out of registers and starts spilling onto the stack, which seems like a thing that should be avoided. The code has gone from nice and clean to a pile of shit because of that.

At least I can play Super Mario Bros. at 1800 fps on my computer. No other emulator I've tried is that fast. It's just those pesky slowdowns to 15 fps in the middle of the game that kind of suck. ;)
User avatar
pgimeno
Party member
Posts: 3544
Joined: Sun Oct 18, 2015 2:58 pm

Re: Garbage going crazy

Post by pgimeno »

From Pall's explanation in context (thanks) and the Wikipedia article I linked, my understanding is that what he calls "unpredictable megamorphic dispatch" is this:

Code: Select all

ops[state2.fn]()
I don't think that a "branchful" version would be any better, though. If I had to try, I'd do it with a tree of branches, rather than linearly, of course.

Looking at the article he linked, I found that it linked this other one in turn, which explains Pall's use of the word "dispatch", and can help shed some light: http://lua-users.org/lists/lua-l/2011-02/msg00742.html

It provides insight and food for thought. From that, it's clear that a "branchful" version is just the same dog with a different collar, as we say here.
grump
Party member
Posts: 947
Joined: Sat Jul 22, 2017 7:43 pm

Re: Garbage going crazy

Post by grump »

Oh, I've read all this so many times, heh. I sure do have the diamond pattern in my code, but I'm still not sure why tailcalls eliminate the issues.

I'll try some more ideas I have to reduce traces before I either ditch the project, or try to rewrite it with branching, ugh.
grump
Party member
Posts: 947
Joined: Sat Jul 22, 2017 7:43 pm

Re: Garbage going crazy

Post by grump »

I think I've found a working solution at last. It's a bit crazy though. I now use the FFI to create a fresh Lua state and run the system's PPU in its own space, isolated from the CPU, to "untangle" their traces. Basically cooperative multithreading that doesn't require synchronization, and that allows one state to call functions in the other state directly via the Lua C API instead of going through a Channel.

This reduces complexity for the compiler, and it seems to be working well. The trace counts for the emulated components stabilize quickly, and the churn rate remains low. Frame rate is of course lower now on average due to more overhead, but it's also much more stable.

The ability to set different compiler options for each component is another benefit of this approach. The CPU has a relatively small state space that can be heavily JITed, while the PPU with its huge number of state permutations can use more suitable settings that avoid constant recompilation, without it affecting the other components.

I gotta rewrite major parts of the code before I can test the more complex games, but it's looking good so far. At least not as bad as before. Writing a complex emulator in a trace compiled language does not seem like it's the best idea ever tbh.
User avatar
pgimeno
Party member
Posts: 3544
Joined: Sun Oct 18, 2015 2:58 pm

Re: Garbage going crazy

Post by pgimeno »

I now use the FFI to create a fresh Lua state and run the system's PPU in its own space, isolated from the CPU, to "untangle" their traces.
Whoa, head-spinning!

You don't easily give up do you? :D

That's a very imaginative solution. Kudos.
grump
Party member
Posts: 947
Joined: Sat Jul 22, 2017 7:43 pm

Re: Garbage going crazy

Post by grump »

pgimeno wrote: Wed Jun 09, 2021 9:15 pm You don't easily give up do you? :D
Nope. I want to be able to say "I wrote an NES emulator in Lua" and have something to show for it that doesn't croak when you throw some random game at it.
yal2du
Prole
Posts: 42
Joined: Wed Oct 13, 2021 5:41 pm

Re: Garbage going crazy

Post by yal2du »

But this array of functions is an important part of the project and can't really be changed to something else.
interesting thread. necroing to mention a quick edit that made original garbage.love run the same regardless of function order (mode 1 or 2).

1) initialize the contiguous op array beginning with index 1 (not 0)
2) initialize the start1 counter values with 1, initialize the state2 fn value with 1
3) change the conditional assignments to match the new array range
Running the components in separate threads would solve the problem, but I don't see how I can synchronize a bunch of threads several million times per second using Channels
saw later where you "use the FFI to create a fresh Lua state" but isn't that the same as using love.Thread() ? in any event, you can use ffi to allocate a memory mapped file to use as shared memory to avoid Channel overhead on windows and linux. post below has some posix example code that can be adapted

https://nullprogram.com/blog/2016/04/10/
Post Reply

Who is online

Users browsing this forum: No registered users and 41 guests