pixelpedant Posted May 18, 2022 Share Posted May 18, 2022 I was puzzling lately over the most memory-efficient and time-efficient means of storing and retrieving sets of boolean values in TI BASIC (not Extended BASIC, so no bitwise operators). Say you've got a game where levels have switches/doors/toggles, and you need to store (and efficiently check) the on/off value for sets of up to 10 of them, as needed. The best approach I've been able to come up with so far, offering a balance of memory-efficiency and (importantly, as this is TI BASIC) time-efficiency is as an integer which is a multiple of primes. So 10 boolean values are stored in an integer with a value of up to 2*3*5*7*11*13*17*19*23*29 = 6469693230 (when all 10 bits are "on"). And to set values, starting from X=1, "bit 3" can be set by X=X*5, "bit 9" by X=X*23, etc. And zeroing values, if necessary, would of course be achieved by division. Then, to retrieve values, the truth value of, say, bit 7, is tested with (X/17=INT(X/17)), which is likewise quite fast, in TI BASIC terms. This is the sort of very elementary business that I'm sure has been trod a thousand times, over the years. But I decided to attack TI BASIC type-in/cassette game development full force, recently, so I'm kind of exploring all these nooks and crannies for solutions. Does anyone have a better solution? Within the domain of TI BASIC itself. Not interested in jailbreak-based solutions, for present purposes. Keeping in mind that speed is the top priority here, and memory use the secondary one. This solution is very fast at storing values (a LET with a multiplication) and fairly fast at retrieving them (since an INT() and two divisions take a little longer). If you just need to store a few boolean values, sure, just making them regular numerical variables with values of 1 and 0 is fine. But given how big TI BASIC numerical variables are, that solution doesn't really scale. So it became apparent to me I needed something better, which isn't as slow as packing and unpacking data stored in strings. 2 Quote Link to comment Share on other sites More sharing options...
+OLD CS1 Posted May 18, 2022 Share Posted May 18, 2022 In TI BASIC, I found straight arrays were faster to use as simple flags rather than trying to store bit flags in a variable. I have used bit flags in Extended BASIC using OR to set, AND to unset and detect, and it is faster than the equivalent math routines in TI BASIC. You need eight bit flags? F({0..7}) works just fine. You can test for value or test for truth (0=false, anything else is true.) It is more memory hungry than storing eight bits in a single variable, but faster to work with. In terms of memory, since TI BASIC has no concept of integer storage, unlike CBM BASIC which uses six bytes (two for the name, two for the memory pointer, and two for the value,) for the % integer operator (F%, for instance,) TI BASIC will store your flag as a floating point number. In terms of ease-of-use and speed, a straight variable for each flag, in my experience, is superior in TI BASIC. 1 Quote Link to comment Share on other sites More sharing options...
pixelpedant Posted May 18, 2022 Author Share Posted May 18, 2022 Yes, as I had said, if you just need to store a few boolean values (or for that matter, your problem isn't one which is likely to butt up against memory limitations regardless), then storing them as 1s and 0s in regular numerical variables (probably as arrays so you can iterate over them easily) is fine and dandy. The problem I'm confronting is just that in a complex game context where I am wrangling every spare byte and trying to control the size of very large arrays, this solution does not scale sufficiently well. Storing a two-dimensional array of boolean values in eight bytes per bit is some crazy pants nonsense when you're fighting for spare bytes. Using this solution, a 10x8 array of boolean values consists of 64 bytes of numerical data, instead of 640 bytes. Which does make a major difference, in a 16K world. 1 Quote Link to comment Share on other sites More sharing options...
pixelpedant Posted May 18, 2022 Author Share Posted May 18, 2022 I will say, this sort of struggle does have something of the quality of the solution in search of a problem. After all, why develop any big or complex project for a TI BASIC 16K/Cassette use case, in a world where Extended BASIC and easy, cheap disk solutions are pervasively available? Well, the same reason I'm using a 43 year old computer in the first place, I figure. But in a broader context, I do feel like TI BASIC was oddly underexploited. It's somewhat shocking just how few high quality, thoughtfully developed TI BASIC programs were developed in its time. Programs that actually looked at what it can do and the speed at which it can do it, and used those (albeit limited) capabilities to their fullest, within their own means. Flooraway and Maze of Grog and Lord of Serpents are some examples. But at the same time, it's not shocking, given how utterly necessary Extended BASIC was, and how completely straightforward and impossible to ignore or put aside its advantages are. Even if it had added no features at all, the huge performance advantage would still be impossible to pass up. 3 Quote Link to comment Share on other sites More sharing options...
+TheBF Posted May 18, 2022 Share Posted May 18, 2022 One downside I can think of with your method is if you wanted to compile the program it would fail because you are using floats. I have been noodling on strings as an alternative but I can't think of a fast way to set/change a char in the middle of a string. I suspect a bunch of nested string functions could do it however. It might still be the same speed as a lot of floating point math. (?) POS(BIT$,"1",N) would let you read a "bit" pretty fast or you could use SEG$() If you accessed a bunch of "bits" as a string ( ie: "10101010") with SEG$ you can compared them all at once with the equal operator. So there is that. 1 Quote Link to comment Share on other sites More sharing options...
pixelpedant Posted May 18, 2022 Author Share Posted May 18, 2022 1 hour ago, TheBF said: POS(BIT$,"1",N) would let you read a "bit" pretty fast or you could use SEG$() If you accessed a bunch of "bits" as a string ( ie: "10101010") with SEG$ you can compared them all at once with the equal operator. So there is that. Yeah, there definitely is a use case for strings as non-text data storage in TI BASIC, and there are a fair number of programs out there that use them in such ways. For example, I've seen entire songs stored in string format, which extract all their CALL SOUND values via ASC and SEG$. But it is very slow. A POS takes 40ms in TI BASIC to find character 1 of a 1 character string, and search duration grows at about 3ms per character. And SEG$ takes 35ms to segment character 1 of a 1 character string. Plus, string concatenation is quite slow, in BASIC. Concatenating three single-character strings and assigning them to a variable takes over 50ms. So potentially a tool for downtime extraction or storage of data, but not something I'd use for general purpose gameplay variables that need to be accessed and modified regularly and on the fly, sadly. I did use strings for storage of integer values in one case in the program that motivated this thread, precisely because I needed something that behaved like a stack, which strings obviously can very easily. But not for data actively used during gameplay, in that case. Quote Link to comment Share on other sites More sharing options...
+OLD CS1 Posted May 18, 2022 Share Posted May 18, 2022 2 hours ago, pixelpedant said: Yes, as I had said, if you just need to store a few boolean values (or for that matter, your problem isn't one which is likely to butt up against memory limitations regardless), then storing them as 1s and 0s in regular numerical variables (probably as arrays so you can iterate over them easily) is fine and dandy. I thought I was being supportive, though I did not go so far as to say directly, but alluded, that TI BASIC may not be the proper environment for complex scenarios. Certainly should not be a discouragement: we climb the mountain because it is there. A lot has been squeezed out of TI BASIC over the decades, so getting a little more out of its native environment (no sandbox jailbreak or other special external tricks) would be neat to see, as well as the cost-benefits analysis. 3 Quote Link to comment Share on other sites More sharing options...
RXB Posted May 19, 2022 Share Posted May 19, 2022 19 hours ago, TheBF said: One downside I can think of with your method is if you wanted to compile the program it would fail because you are using floats. I have been noodling on strings as an alternative but I can't think of a fast way to set/change a char in the middle of a string. I suspect a bunch of nested string functions could do it however. It might still be the same speed as a lot of floating point math. (?) POS(BIT$,"1",N) would let you read a "bit" pretty fast or you could use SEG$() If you accessed a bunch of "bits" as a string ( ie: "10101010") with SEG$ you can compared them all at once with the equal operator. So there is that. Hmm if we turn this into an Assembly program I could incorporate it into RXB ROMs. Quote Link to comment Share on other sites More sharing options...
RXB Posted May 19, 2022 Share Posted May 19, 2022 18 hours ago, OLD CS1 said: I thought I was being supportive, though I did not go so far as to say directly, but alluded, that TI BASIC may not be the proper environment for complex scenarios. Certainly should not be a discouragement: we climb the mountain because it is there. A lot has been squeezed out of TI BASIC over the decades, so getting a little more out of its native environment (no sandbox jailbreak or other special external tricks) would be neat to see, as well as the cost-benefits analysis. To bad we can not do like I did with RXB and turn much of TI BASIC into Assembly. Quote Link to comment Share on other sites More sharing options...
senior_falcon Posted May 19, 2022 Share Posted May 19, 2022 22 hours ago, TheBF said: I have been noodling on strings as an alternative but I can't think of a fast way to set/change a char in the middle of a string. I suspect a bunch of nested string functions could do it however. It might still be the same speed as a lot of floating point math. (?) POS(BIT$,"1",N) would let you read a "bit" pretty fast or you could use SEG$() If you accessed a bunch of "bits" as a string ( ie: "10101010") with SEG$ you can compared them all at once with the equal operator. So there is that. I haven't thought this through 100%, but here's another way that might work using strings: For your 10 values you could have ABCDEFGHIJ for each of the 10 values. Start out with A$="" To see if "C" is there you could 50 P=POS(A$,"C",1) 51 IF P THEN 100 ELSE 200 100 REM C IS THERE, GET RID OF IT 110 A$=SEG$(A$,1,P-1)&SEG$(A$,P+1,255) 200 REM C NOT THERE, ADD IT 210 A$=A$&"C" Adding a letter is easy, as the order does not matter. A$ could be "CGDA" But with two SEG$, removing a letter might be too slow. (can't remember if you need parentheses around the POS(A$,"C",1)) 3 Quote Link to comment Share on other sites More sharing options...
+OLD CS1 Posted May 19, 2022 Share Posted May 19, 2022 Caveat to using strings as a stack is the inevitable garbage collection as strings are not re-used in BASIC's string stack. 1 2 Quote Link to comment Share on other sites More sharing options...
senior_falcon Posted May 20, 2022 Share Posted May 20, 2022 Another possible way to use strings would be to have an array. This would be considerably smaller than using a numeric array. To set the 3rd element: A$(3)="1" 1166 loops in 30 seconds To reset: A$(3)="" 1243 loops in 30 seconds To test: IF A$(3)="1" THEN 200 1090 loops in 30 seconds The prime method: To set: X=X*5 2285 loops in 30 seconds To reset: X=X/5 2211 loops in 30 seconds To test: IF X/17=INT(X/17) THEN 200 677 loops in 30 seconds These are approximate times done with a stop watch. Plus I did not time empty loops which would let you determine how long each instruction takes. Setting/resetting is faster using the prime method. However, testing is faster using the string method. So if you are mostly testing then the string method might be better. If you are mostly setting/resetting then the prime method would be better. Arrays take time. If you have, say, 10 things to keep track of, maybe A$,B$,C$ etc. would be faster. OLD CS1 has a good point about the garbage collection. But if you are not setting/resetting a lot it would not happen too often. 3 Quote Link to comment Share on other sites More sharing options...
senior_falcon Posted May 20, 2022 Share Posted May 20, 2022 Here's another thing that is easy to overlook. Besides the overhead of a numeric variable or string variable or array, there is also the overhead of actually using the variable. 10 IF X/17=INT(X/17) THEN 100 takes 26 bytes 10 IF A$(3)="" THEN 100 takes 20 bytes 10 IF A$="" THEN 100 takes 16 bytes 10 X=X*17 takes 14 bytes 10 A$(3)="" takes 16 bytes 10 A$="" takes 11 bytes So the answer to your original question is.......complicated. 2 1 Quote Link to comment Share on other sites More sharing options...
RXB Posted May 20, 2022 Share Posted May 20, 2022 3 hours ago, senior_falcon said: Here's another thing that is easy to overlook. Besides the overhead of a numeric variable or string variable or array, there is also the overhead of actually using the variable. 10 IF X/17=INT(X/17) THEN 100 takes 26 bytes 10 IF A$(3)="" THEN 100 takes 20 bytes 10 IF A$="" THEN 100 takes 16 bytes 10 X=X*17 takes 14 bytes 10 A$(3)="" takes 16 bytes 10 A$="" takes 11 bytes So the answer to your original question is.......complicated. Gets even more complicated when you consider speed and types of memory. Numeric values like 17 takes 8 bytes in memory as Floating Point and the longer the variable name the more memory used. String values only take length and characters, but ONLY reside in VDP Slower memory in XB, in BASIC everything is in Slower VDP memory. RAM memory is way faster than VDP memory and everything in BASIC is in VDP. BASIC is slow for many reasons and I have not even mentioned GPL yet. Quote Link to comment Share on other sites More sharing options...
pixelpedant Posted May 20, 2022 Author Share Posted May 20, 2022 4 hours ago, senior_falcon said: So the answer to your original question is.......complicated. Indeed! And thank you for engaging with this question and producing these results. The significant memory cost of numeric constants is definitely something one has to keep in mind. One big takeaway from that reality being just that, given a large program with a lot of math in it, replacing every single instance of "1" with a variable "A" which is permanently set to the value 1 is very nearly always going to save a meaningful chunk of memory. And look stupid and nonsensical, but c'est la vie, if you actually need that memory. Just another reason to effectively write two versions of any given TI BASIC program - one which is readable and unoptimised, and another which is a goddamn unreadable hodgepodge, but optimised. The limitation of this approach for very large programs being that if you're making it an unreadable hodgepodge to fit inside memory limitations and you're butting right up against said limitations, the "unoptimised" version is not actually going to be testable/usable code. It's effectively no better than pseudocode, if it can't actually run. So arguably, you may as well just write pseudocode instead. 1 Quote Link to comment Share on other sites More sharing options...
+TheBF Posted May 20, 2022 Share Posted May 20, 2022 23 minutes ago, pixelpedant said: So arguably, you may as well just write pseudocode instead. ... and then use a programmable language that turns your pseudocode into runnable code and so forth. (Sorry. I couldn't resist the tempation) 1 Quote Link to comment Share on other sites More sharing options...
+OLD CS1 Posted May 20, 2022 Share Posted May 20, 2022 5 hours ago, senior_falcon said: So the answer to your original question is.......complicated. 2 1 Quote Link to comment Share on other sites More sharing options...
+TheBF Posted May 20, 2022 Share Posted May 20, 2022 2 hours ago, RXB said: RAM memory is way faster than VDP memory and everything in BASIC is in VDP. VDP RAM is slower but not as much as I thought it was if you use an interpreted language where the interpreter has already slowed down the operations of the machine. I did some experiments in Forth with strings and variables in VDP RAM and expansion RAM. I don't have the results handy but I was surprised. I need to find that code again. Quote Link to comment Share on other sites More sharing options...
+OLD CS1 Posted May 20, 2022 Share Posted May 20, 2022 30 minutes ago, pixelpedant said: The limitation of this approach for very large programs being that if you're making it an unreadable hodgepodge to fit inside memory limitations and you're butting right up against said limitations, the "unoptimised" version is not actually going to be testable/usable code. It's effectively no better than pseudocode, if it can't actually run. So arguably, you may as well just write pseudocode instead. Not necessarily. The advantage of pseudocode would be writing geared toward your final goal, but with the lacking of testability. I have written some BASIC programs which come close to consuming TI BASIC's program memory, and I have maintained two code bases of the same program. Individual unoptimized parts can be tested in smaller chunks, feeding it useful information and checking expected output (or fuzzing it with nonsense to see if it breaks.) You will definitely run into a problem of translating between your unoptimized source and your optimized running program. Moving between my code bases sometimes introduced a little quirk here and there which had to be addressed, mostly because of the differences between AND and OR in XB and the equivalent mathematic formula in TI BASIC, but also simple transcription errors which change values or alter program flow unexpectedly. 2 Quote Link to comment Share on other sites More sharing options...
senior_falcon Posted May 20, 2022 Share Posted May 20, 2022 (edited) 7 hours ago, pixelpedant said: One big takeaway from that reality being just that, given a large program with a lot of math in it, replacing every single instance of "1" with a variable "A" which is permanently set to the value 1 is very nearly always going to save a meaningful chunk of memory. And look stupid and nonsensical, but c'est la vie, if you actually need that memory. I don't think there is any savings. In the program line, "1" is not kept as a floating point number using 8 bytes. It is kept as a string with a token denoting a string, a length byte and "1", and converted to floating point when it is needed by the program. "A" is kept the same way, with a length byte and "A" Just the A with no length byte and no token denoting a string. I may be remembering wrong, but this is easy to check in Classic99. Do a cold reset to clear the VDP memory, goto BASIC and enter a program line. In vdp ram the program line ends at >37D7 and you can use the debugger to see how many bytes are in the crunched line. Remember that program lines are 2 bytes, so line 10 becomes >000A. Edited May 21, 2022 by senior_falcon 2 Quote Link to comment Share on other sites More sharing options...
pixelpedant Posted May 20, 2022 Author Share Posted May 20, 2022 Ahah! You make an excellent point (and have excellent knowledge of these things, as always). My hypothesis had been tested simply by dumping a giant program of mine into XB with all "1s" replaced with a variable "A" and comparing the SIZE result, which had improved meaningfully. But looking at the tokenised BASIC, it looks like where this is coming from is not where I'd expected. Specifically, ZZZ=A in tokenised TI BASIC appears to consist of five bytes, those being: >5A >5A >5A >BE >42 Z Z Z = A While ZZZ=1 in tokenised TI BASIC appears to consist of seven bytes, those being: >5A >5A >5A >BE >C8 >01 >31 Z Z Z = Str Len 1 So the memory footprint of any given reference to a numeric constant (in bytes) appears to be its decimal character length + 2. While the memory footprint of any given reference to a numeric variable appears to be its character length outright. So if I dump a program like this into Classic99, it grows upwards to >3757 or so. 10 ZZZ=1 20 ZZZ=1 30 ZZZ=1 40 ZZZ=1 50 ZZZ=1 60 ZZZ=1 70 ZZZ=1 80 ZZZ=1 90 ZZZ=1 100 ZZZ=1 While if I dump a program like this into Classic 99, it grows upwards to >376B or so: 10 ZZZ=A 20 ZZZ=A 30 ZZZ=A 40 ZZZ=A 50 ZZZ=A 60 ZZZ=A 70 ZZZ=A 80 ZZZ=A 90 ZZZ=A 100 ZZZ=A 2 Quote Link to comment Share on other sites More sharing options...
senior_falcon Posted May 21, 2022 Share Posted May 21, 2022 (edited) You are right! I stand corrected. These days, this is what happens when I rely on my memory. Now if you have two ways to do something, you can check to see which is most compact. Edited May 21, 2022 by senior_falcon Quote Link to comment Share on other sites More sharing options...
RXB Posted May 21, 2022 Share Posted May 21, 2022 23 hours ago, TheBF said: VDP RAM is slower but not as much as I thought it was if you use an interpreted language where the interpreter has already slowed down the operations of the machine. I did some experiments in Forth with strings and variables in VDP RAM and expansion RAM. I don't have the results handy but I was surprised. I need to find that code again. I spend all day for last 30 years working with GPL Interpreter and XB. By changing VDP routines from GPL to Assembly I have increased routines in XB accessing VDP by 9 times like in CALL HCHAR or CALL VCHAR Quote Link to comment Share on other sites More sharing options...
RXB Posted May 21, 2022 Share Posted May 21, 2022 18 hours ago, pixelpedant said: Ahah! You make an excellent point (and have excellent knowledge of these things, as always). My hypothesis had been tested simply by dumping a giant program of mine into XB with all "1s" replaced with a variable "A" and comparing the SIZE result, which had improved meaningfully. But looking at the tokenised BASIC, it looks like where this is coming from is not where I'd expected. Specifically, ZZZ=A in tokenised TI BASIC appears to consist of five bytes, those being: >5A >5A >5A >BE >42 Z Z Z = A While ZZZ=1 in tokenised TI BASIC appears to consist of seven bytes, those being: >5A >5A >5A >BE >C8 >01 >31 Z Z Z = Str Len 1 So the memory footprint of any given reference to a numeric constant (in bytes) appears to be its decimal character length + 2. While the memory footprint of any given reference to a numeric variable appears to be its character length outright. So if I dump a program like this into Classic99, it grows upwards to >3757 or so. 10 ZZZ=1 20 ZZZ=1 30 ZZZ=1 40 ZZZ=1 50 ZZZ=1 60 ZZZ=1 70 ZZZ=1 80 ZZZ=1 90 ZZZ=1 100 ZZZ=1 While if I dump a program like this into Classic 99, it grows upwards to >376B or so: 10 ZZZ=A 20 ZZZ=A 30 ZZZ=A 40 ZZZ=A 50 ZZZ=A 60 ZZZ=A 70 ZZZ=A 80 ZZZ=A 90 ZZZ=A 100 ZZZ=A This shows only the TOKENs used not the speed of execution, there will be more routines to run to interpret the A vs a constant 1 Interpreter has to look up symbol A find it's address where stored and then use that value this takes more time especially in VDP. Do this in RAM with XB vs Consol and you will see a large difference in number of executions. I have been fighting the fight on this for many years now. 100 CALL CLEAR 110 OPEN #1:"CLOCK" 120 INPUT #1:A$,B$,C$ 130 FOR C=1 TO 10000 140 Z=1 150 NEXT C 160 INPUT #1:D$,E$,F$ 170 PRINT A$,D$:B$,E$,C$,F$ 180 END 100 CALL CLEAR :: A=1 110 OPEN #1:"CLOCK" 120 INPUT #1:A$,B$,C$ 130 FOR C=1 TO 10000 140 Z=A 150 NEXT C 160 INPUT #1:D$,E$,F$ 170 PRINT A$,D$:B$,E$,C$,F$ 180 END Run each to see the results. TOP TEST Z=1 is 1 minute 17 seconds BOTTOM TEST Z=A is 1 minute 23 seconds 1 Quote Link to comment Share on other sites More sharing options...
senior_falcon Posted May 21, 2022 Share Posted May 21, 2022 I see the opposite. Looping 4000 times: Z=A 32 seconds Z=1 37 seconds Bottom line is that it is pretty close either way. Of course, I don't trust the times that my computer gives, and after seeing the results you posted in "BYTE MAGAZINE SIEVE BENCHMARK" or in "BENCHMARKING LANGUAGES", I definitely would not trust your times. Unless you have determined what was causing the anomalous results in the video and are getting results that agree with a real TI99. (As I noted in my post #219 in benchmarking languages "Here's the thing. As far as I can tell, your video shows a test that should yield valid results." Yet the video in your post #216 clearly shows that it does not.) Quote Link to comment Share on other sites More sharing options...
Recommended Posts
Join the conversation
You can post now and register later. If you have an account, sign in now to post with your account.
Note: Your post will require moderator approval before it will be visible.