last day (15 days later) » 

17:27
33
Q: How fast were BASIC interpreters in the 80s? (Is this optimization for speed really necessary?)

GellweilerI have a client who wants me to analyze a BASIC program from Umberto Eco's Foucault's Pendulum. I have never written a line of BASIC in my life as I was born in 1995 and started programming around 2010. The program isn't difficult to understand though, all it does is generate all permutations of ...

Not answering the question: when looking at your version (which I did first) I immediately asked "so why execute the I3 loop at all if nothing is done when I1 = I2". That is, I do not find it easier to read; instead it raises questions because it has unobvious features. The difficulty of the original code is IMO due to the restricted IF/THEN structure of the original BASIC language.
I admit line 100 in the original required some thought to understand, though when I got it, I found it quite clever.
@another-dave yeah the line 100 was the one that tripped me off for the most part. And to me it looked like the kind of "clever" thing a novice programmer would write, instead of using the boring but easy to understand and maintainable option. I admit having the if statements outside of the loop if I just think of the code as indented wouldn't irritate me at all.
If it were possible to write IF I1 != I2 THEN FOR I3 = 1 TO 4 rather than using jumps, as one could write in a richer language, the code would be clearer. But this is BASIC, whose design intent was to be very simple. I note your vefsion uses OR in the IF statement, which as far as I recall was not possible in Dartmouth BASIC.
@another-dave I don’t know, I think I would have used a continue statement here anyway. And the trick on line 100 is a standard interview question.
Readability wasn't so much of an issue back then as it is today. A program used to be one-man's-work and 99% of the cases it was to be read by the guy who wrote it only.
17:27
@tofro Not to mention software used to be treated as more disposable than today.
If anyone is puzzled by the magic "10" in line 100, the point is that you want I1, I2, I3, and I4 to be four different numbers between 1 and 4. Therefore you know I1 + I2 + I3 + I4 = 1 + 2 + 3 + 4 = 10.
@tofro If you want to see some really unreadable code, look at a modern language like C++20 where there is liberal use of templates, concepts, iterators, lambdas, spaceship operators, etc, etc. Just sayin'.
Should your program be introduced in the narrative first, the character could later find it too slow and optimize for a little extra robustness in that 30 minute time frame. Might help with context, move the story along.
@Squd yeah it is not about writing a story tough. It's an existing story and my client just wanted me to analyze the program for him among other more modern programming jobs. I was just trying to understand if this sort of optimization in BASIC would be normal. He is not trying to write a story himself. Would be good plot development tough. It's from Umberto Ecos Foucault's Pendulum by the way. Tough I haven't read the book, so I can't judge if it is any good. I only read the chapter with the program.
@Gellweiler Honestly, I would at least have the short-circuits in the loops if I wrote it myself. Each one in the outer loops saves a lot of work in inner loops. Line 100 is simply a well-known way to avoid having a fourth loop to find the single valid value of I4. In those days, at least a basic understanding of optimisation techniques was a real necessity to make functioning programs.
710 is almost exactly 3x as many instructions as 238. Also, the speed of the BASIC instructions is important. Thus, when CPUs are slow, readability and extensibility are lower on the priority list.
17:27
@Gellweiler Another point which isn't obvious from such a short program is most of a long program can usually be as "readable" as you like, with no effect on the total run time. As a real-world example, I spent most of the 1980s working on software that simulated the behavior of aircraft jet engines. The complete program was maybe 200,000 lines of FORTRAN and a typical calculation ran for a few hours on a Cray supercomputer. But more than 95% of the time was spent in literally just three lines of the 200,000. The rest of the code had a negligible impact on the total run time.
Searching the book and BASIC up, found me this article: academia.edu/41951481/… And this Quora, which says the program's bugged: quora.com/Will-the-BASIC-program-in-Foucaults-Pendulum-work
You're asking about BASIC in a historical/retro context. BASIC is still used in small & large companies and governments worldwide. I started in TRS-80 days - yeah, it was Slow. Now 20+ languages later I mostly use OOP with Java, C#, JavaScript, and PHP. But I still write and work with huge apps in BASIC (not VB). Early BASIC lacked many primitives, GOSUB wasn't available so GOTO was the norm. And many home-schooled developers (like today) had no formal training, so you'll see lots of variation in style and use of features. Optimization was a luxury, just getting stuff to work was joyful. HTH
Really, this question demands other questions. Why does your client care about the quality of BASIC code in a doorstop novel of ideas? Anything you can tell us without violating whatever your contractual obligations might be? (Judging by the cracked spine on the bookshelf, I read Focault's Pendulum but can't remember a damn thing, much less any code).
@Gellweiler: Yes, optimization was normal, at least for skilled programmers. It wasn't that you spent time optimizing a program (unless it was really compute-intensive), it's just that it was the way you thought about things, so whatever you wrote tended to have obvious optimizations built in from the start. The person who wrote the original code probably wrote it that way from the start.
Both versions are extremely naive. See Heap's Algorithm
17:27
@another-dave He's just really an Umberto Eco fan. It's his hobby. He does some text analysis on the books and asked me to write some special text analysis tools for that. He also wants to have the program analyzed, especially he wants to know if contains any easter eggs (which it doesn't) and about the coding style. But I mean there is only so much one can deduct from 15 lines of code. I guess line 100 is the most interesting thing about it. It's not the usual sort of jobs I do, but it was a fun change. Also I really enjoyed learning all these details about the history of home computing here.
@another-dave You haven’t read very far then. It’s in chapter 5.
@user3840170 - probably more like memory cells going offline.
Possibly either Eco, or his character, is just not all that expert a programmer. They've written something that works. Your de-optimised version will run in a few seconds. Expanding it by two more letters will make it exponentially slower, but still tolerable. As a young teen in the 80s I wrote BASIC programs which would take days to render one lo-res frame of Mandelbrot set to the screen.
The original program is not particularly optimized for speed, if it were, for one thing, the lines 120, 130, and 140 would all just read 'NEXT' with no variable after. Assuming MS basic.
@alephzero I’m reading stuff like that and find it easy to read. And yes, I’m also writing it...
17:27
11839 is how many instructions the naive extension of the original program to 6 characters would run, which is 10x fewer than yours. jdoodle.com/ia/eQf
Go try to get some work done with a 1MHz processor and 36k of usable memory - then you'll see how important that 3x speedup is. Seriously - why buy a quad core computer when you could get one core for the same price? Do you really need that extra speed for free? 0_o
This heavily depends on the BASIC you use as well. Taking a mid-to-late-1980s PC as baseline, I’ve did some comparisons with GW-BASIC (as of Schneider EURO PC MS-DOS 3.30A), QBasic (as of MS-DOS 5) and SBasic (a compiler from the DMV Widuch publisher). QBasic came in at over 230s, GW-BASIC at a little over 80s, and SBasic was in the single digits for seconds. I never had QuickBasic or BASIC PDS so couldn’t compare those compilers, and clones had no BASICA, and I know of no other interpreters for this platform I could have compared.
FWIW, I translated both BASIC programs into Python, and got an average run time of 0.008570 (stdev 0.001202) second for the original version, and 0.009150 (stdev 0.001004) second for the “readable” version. That's a 6.8% increase.
I wonder whether the Basic used had boolean expressions, or if Foucault (or his character) knew how to use them? Most people (including me) couldn't code that well in the 80s (and some of the software geniuses of that era like Djikstra and Knuth were reputed to never sully themselves by using an actual computer).
Not an answer to your question, but our code review site might be able to help you optimize even further
17:27
I would say that your version is harder to understand - your added inner loop is looping over 4 values, 3 of which are invalid, and then discarding the invalid ones which seems much harder to understand than merely calculating the single valid value which clearly indicates that only one value is valid... similarly, your version doesn't make clear that some values of I2 and I3 are NEVER valid regardless of what happens in the inner loops... and the single long complicated comparison spanning several (screen) lines for a single (program) line needs breaking down into something easier to read...
... but if you make all of those changes to your version (splitting the long line into simpler lines doing a single comparison, moving the comparisons to the first point they can be done and thereby skipping the inner loop(s), and then replacing the "loop to calculate a single value" with an "expression to calculate a single value", you basically end up back to the original!

last day (15 days later) »