nesdev.comhttps://forums.nesdev.com/ Techniques for bigger jump tables?https://forums.nesdev.com/viewtopic.php?f=2&t=16671 Page 1 of 2

 Author: Drakim [ Mon Nov 06, 2017 2:37 am ] Post subject: Techniques for bigger jump tables? I usually employ the jump table/split jump table technique, running as many parallel tables as I need values for my structs. However, this creates a hard cap of 256 entries/indexes. So what I'm wondering, what are the various techniques for creating "structs" that can accommodate more than 256 entries?The wiki unfortunately doesn't have (that I could find) a page on techniques for this. I'm especially interested in techniques that have some advantage over the others (cycles, complexity, etc). Right tool for the problem, right? I'm also curious if these techniques have any "name" like we have for "split jump table" or "rts trick", so I can google up more information.The one I already know about is the classic LDA (address),Y trick, where you store the address to a blobish struct and read out it's values by adjusting Y.But I imagine there must be more. Maybe using the carry to switch between table1 and table2, or jump tables of jump tables, or MMC5's multiplication register, or using some self-modifying code, etc.

 Author: Quietust [ Mon Nov 06, 2017 4:59 am ] Post subject: Re: Techniques for bigger jump tables? The most straightforward method would be to simply have multiple levels of jump tables - one for each byte of your index, since the 6502 only has 8-bit registers to begin with. In other words, something like this:Code:switch (highbyte){case 0: switch (lowbyte) { case 0: ... case 255: } break;case 1: switch (lowbyte) { case 0: ... case 255: } break;case 2: switch (lowbyte) { case 0: ... case 255: } break;...}I also can't help but wonder exactly what it is you're doing that requires a jump table longer than 256 entries...

 Author: dougeff [ Mon Nov 06, 2017 5:28 am ] Post subject: Re: Techniques for bigger jump tables? I've never heard this term, apparently it's a real term."The BLOB structure, derived from Binary Large Object, contains information about a block of data."

 Author: tokumaru [ Mon Nov 06, 2017 7:28 am ] Post subject: Re: Techniques for bigger jump tables? Well, regardless of the method you use, there's no way you'll achieve the same level of performance if you need to address more than 256 of anything... This is an 8-bit CPU after all.

 Author: Sumez [ Mon Nov 06, 2017 9:34 am ] Post subject: Re: Techniques for bigger jump tables? I'm genuinely interested in knowing what practical use such a big jump table could possibly have?

 Author: pubby [ Mon Nov 06, 2017 9:52 am ] Post subject: Re: Techniques for bigger jump tables? Sumez wrote:I'm genuinely interested in knowing what practical use such a big jump table could possibly have?Compiler-compilers like Flex (and probably Yacc) output huge jump tables. Probably irrelevant for NES games though

 Author: Bregalad [ Mon Nov 06, 2017 11:37 am ] Post subject: Re: Techniques for bigger jump tables? Quietust wrote:I also can't help but wonder exactly what it is you're doing that requires a jump table longer than 256 entries...That. You didn't give details but if you need a jump table larger than 256 entries I can almost guarantee you're doing something wrong. This is why there is no "techniques" mentionned in the wiki - because nobody needs that.

 Author: rainwarrior [ Mon Nov 06, 2017 1:56 pm ] Post subject: Re: Techniques for bigger jump tables? The techniques for storing/using jump tables really apply to any tables, for the most part? Like really the only specific tricks I can think of for jump tables are stuff like using RTS or RTI, which are not really about the table or its size but just about how you use the data once retrieved.So, some ideas:1. Split multi-byte structures into parallel 1-byte tables ("stripes", "structure of arrays"). This gets you up to 256 entries pretty well.2. LDA (indirect), Y is a straightforward generic solution. Tables of arbitrary size are easy to implement. As a jump-table specific option, you could also put a JMP (indirect) instruction in RAM (ZP?) ahead of time, update its operand with the computed lookup address, and run that directly instead of fetching it with LDA.3. Multiple layers works too. Quietust suggested a jump table to select a second set of jump tables. Not sure whether the naive way of doing this is any better than just computing a pointer like in #2, but the subdivision idea itself has a lot of potential. Getting those subdivisions down to <= 256 entries lets you use the striping (#1) concept at the same time.If you've got <= 512 entries or <= 1024 entries you might just branch to select from a couple of parallel LDA abs, X lookups? You can build a small binary tree search in code with a few ROR / BCS nodes.If you've got an appropriate mapper with enough banks, you might even use banking to select pages of your table quickly. Put each 256-entry table in a different bank, and then a quick STA \$8000 could be faster than doing any branching/indirection. (You can still use the rest of the bank for other data.) If your table is really large you're probably already dealing with banks anyway.

 Author: Quietust [ Tue Nov 07, 2017 4:54 am ] Post subject: Re: Techniques for bigger jump tables? Drakim wrote:Does switching banks incur any cycle cost? If not, I might reconsider it. All each entry would need would be a bank number and the usual object id, and looking up the data would be ultra cheap, provided that the only cost to switching the bank would be the LDA/STA to the register.The only "cost" behind switching banks is the amount of time required to write to the bank register[s] - in hardware, the "bank bits" are updated every cycle based on the address you're currently accessing.

 Author: Drakim [ Tue Nov 07, 2017 5:02 am ] Post subject: Re: Techniques for bigger jump tables? That's great. Although it's a bit messy (especially since you gotta ensure the data is perfectly aligned between banks), that's gotta be the most performant big jump table remotely possible on the NES.

 Author: White Flame [ Tue Nov 07, 2017 10:24 am ] Post subject: Re: Techniques for bigger jump tables? Stepping back a bit, if you have more than 256 items to dispatch on, then your identifier will be at least 2 bytes. It can make sense then to just use address pointers for IDs instead of enums & dispatch tables at all.Whether or not those pointers point to code to jump to, point to a data structure for LDA (zp),y addressing, or are larger than 16-bit to accommodate banking information (or encode banking in various bits of the 16-bit word to be extracted before use to save space) is up to you. But it's big enough that you can use the identifier itself directly.