Pently with all effects on already uses less RAM than FamiTone2 (see size comparison). But now that people are writing NES games in C using cc65, which tends to use more RAM than games written in assembly language, the 2048 bytes of RAM available to the NES CPU have become more precious. In addition, I'd like to be able to add effects to Pently, such as tuning offsets, without having to expand its RAM use for projects that don't use those effects. Currently, disabling effects using PENTLY_USE flags in pentlyconfig.inc saves ROM but not RAM because RAM is statically allocated.
Because of the array-of-structs layout of the NES APU ports, Pently allocates properties of channels and tracks into an array with four columns (n, n+1, n+2, n+3) and a variable number of rows. But various properties apply to various numbers of tracks (3 for pitched channels, 4 for hardware channels, or 5 for all tracks). Minimizing the RAM footprint requires minimizing the number of rows, which equals the length of the longest column.
This sort of allocation resembles the multiprocessor scheduling problem, which in the general case is NP-hard. A greedy algorithm called "first fit decreasing" (FFD) sorts jobs by decreasing size (tracks, then hardware channels, then pitched channels) and then places each in the least full column. FFD has an upper bound of (4m - 1)/3m times the optimal allocation for m columns, or 25% more rows than optimal for 4 columns. But this is an upper bound that I don't expect to see in practice.
BSS is 104 bytes now or 108 bytes after issue #21. If a prototype implementation of FFD results in noticeably suboptimal allocation in BSS, I might have to consider some sort of rearrangement algorithm to shave off a row or two.
Pently with all effects on already uses less RAM than FamiTone2 (see size comparison). But now that people are writing NES games in C using cc65, which tends to use more RAM than games written in assembly language, the 2048 bytes of RAM available to the NES CPU have become more precious. In addition, I'd like to be able to add effects to Pently, such as tuning offsets, without having to expand its RAM use for projects that don't use those effects. Currently, disabling effects using
PENTLY_USEflags in pentlyconfig.inc saves ROM but not RAM because RAM is statically allocated.Because of the array-of-structs layout of the NES APU ports, Pently allocates properties of channels and tracks into an array with four columns (n, n+1, n+2, n+3) and a variable number of rows. But various properties apply to various numbers of tracks (3 for pitched channels, 4 for hardware channels, or 5 for all tracks). Minimizing the RAM footprint requires minimizing the number of rows, which equals the length of the longest column.
This sort of allocation resembles the multiprocessor scheduling problem, which in the general case is NP-hard. A greedy algorithm called "first fit decreasing" (FFD) sorts jobs by decreasing size (tracks, then hardware channels, then pitched channels) and then places each in the least full column. FFD has an upper bound of (4m - 1)/3m times the optimal allocation for m columns, or 25% more rows than optimal for 4 columns. But this is an upper bound that I don't expect to see in practice.
BSS is 104 bytes now or 108 bytes after issue #21. If a prototype implementation of FFD results in noticeably suboptimal allocation in BSS, I might have to consider some sort of rearrangement algorithm to shave off a row or two.