Hump Algorithms
Posted by Trixter on August 27, 2013
I have the dumbest first-world problems. The current one: I’ve come up with new ideas for a retroprogramming/demoscene project, ideas that nobody on my platform (4.77MHz 8088) has ever attempted. They’re pretty radical, and on par with 8088 Corruption in terms of code cleverness and impact, except this time, I actually know what I’m doing (as opposed to stumbling into it somewhat by accident with Corruption). Every time I think about what is possible, I get really excited and obsess over implementation details. In my head, it’s all coded and running beautifully, bringing shocks of laughter to other retroprogrammers and demosceners alike.
The problem is, even after weeks of design, it’s still in my head.
What I have planned relies heavily on same tricks as the 8-bit democoding scene, namely lots of tables. Generation of those tables, compared to how they are used, is a highly asymmetric process: It can take hours or days to create the table, whereas using it only costs a few cycles for a memory lookup. This very similar to the process of vector quantization, where coming up with the codebook is an NP-hard problem that there is no universal solution for. To bring my ideas to life, I need to write programs that take advantage of gigs of memory and multiple cores to come up with the tables I need. So why not just write them? What’s stopping me is the dumbest of dumb problems: I simply haven’t written any large, modern, multithreaded applications before. All of my programming over the last 30 years has been either in Pascal, or assembler, using dialects and architectures that aren’t applicable to modern resources any more.
“So pick up a new language, ya moron!” is what all of you just screamed at me. I know, I know. But this is what kills me: It would take me at least a month to pick up a new language, learn its IDE, learn its visual form/component system, and the inevitable learning of how to debug my code when it all goes pants. I’ve been putting it off for at least a decade. I can do it… but it would take at least a month to ramp up to full speed! And (said in Veruca Salt cadence) I want to code up my idea NOW!
I’m frozen. What a stupid, stupid first-world problem.
I need an algorithm for getting over the hump that can be solved in polynomial time.
Oldskooler Ramblings 
me said
python dude… (install the latest 3.3.x 64 bit ver)
I picked it up in about 2 weeks. I bought a book. I later realized it just followed the examples from the python website (http://docs.python.org/3/tutorial/). I got to about chapter 7-8 and I was pretty proficient. The examples are really easy for someone who has been playing with pascal like you have. It is one of the better tutorials I have used in a long time. The rest you can get from stackoverflow/google (how do I x in python). It was even kinda fun.
You can create massive tables in very little time. It can even be quite zen when you are optimizing it. Instead of pulling out some clever op code you have to come up with a clever alg to do it.
It is also dead simple to make a table that takes up gigs of memory.
x = [1,2,3]
poof I have a array with 3 items in it. No worries about memory layout or anything. You can even get crazy and nest them. With a bit of clever print statements you can gen out code for other langs.
Half the time it is what I am using python for is generating code in other langs. There are also tons of libraries out there to help you out. Many of them built in.
Also remember this is throw away code. It does not have to be pretty. It just has to work. If it takes 3 days to run? So what. Let it run you have what you need… If you need many threads there are tons of examples out there too. It is pretty easy. You declare a function put your code in it and pass in some params thru a structure/start function for that particular instance of the thread. If you jam stuff into the same place you just need to make sure you have some sort of lock.
IDE? You can use the built in ‘idle’ one (it stinks). Eclipse has a great plugin pydev (I use it for larger projects). But 99% of the time? I use notepad++ (has nice syntax highlighting) and a bit of debug by print. It is that easy.
Python is my *goto* tool for quick and dirty code. Which is exactly like you described.
Trixter said
Python really rubs me the wrong way; I’ve picked it up and put it back down three times that I can remember in the last decade, maybe more. If I gain no traction in the next few weeks, I’ll plant myself at the tutorial and give it a fourth try. Like the xkcd joke, the dynamic typing and formatting restrictions really put me off, especially the former. (I’d like as many bugs caught BEFORE I run my code, thanks.) But I’ll consider it.
I don’t consider my time in Pascal “playing”. I’ve written some fairly sophisticated OOP in it, if you can believe that.
me said
When I say ‘playing’ I mean working. Sorry just the way I talk about my work :) I have seen/worked in very large systems built in pascal. You can do that with any language (I have seen ones done with DOS batch script). I wouldnt recommend it with python though. You quickly run up against what I would call syntax goo. But for quick dirty throw away progs? I love it. The typeless does freak out someone who is more atune with making sure the type is ‘just right’. But it also frees you into not having to worry about it. You can concentrate on the problem and not the syntax. I was like you. But one time I needed something that was 10000 bits wide and do math on it. That would have been a bit of a pain in C was seriously easy in python at a cost of speed.
Someone also suggested the VS IDE. The free one is decent (though I think they went a bit sideways with 2012). You can stand things up pretty quickly with it too. You may feel more at home in a c/c++ enviro depending on what sort of pascal you have been doing. I too made the same switch. The only thing that really threw me was the := too = bit. Took me forever to stop typing it. Keep in mind the free one has all the compiler optimizations turned off.
Also stop waiting, go, do, now… :) So what if the table takes 3 days to run. Let it run over the weekend or while you are at work…
Yann Collet (@Cyan4973) said
I humbly suggest Visual Studio as the IDE, with the Express edition being completely free.
It’s very nice, lot of dynamic, visual and contextual information.
Moreover, the 2012 edition allows the creation of x64 programs,
hence the possibility to play with very big tables (multiple gigabytes).
And for the language, I would suggest C.
I was also a Pascal/Delphi programmer before. The switch wasn’t that hard, really.
Bruno said
I just read your post twice and twice I stumbled in this sentence with a smile:
“The problem is, even after weeks of design, it’s still in my head.”
It’s a very familiar feeling so, i’m not going to suggest you any language or technical solution.
Don’t wait. Just do it!
.. In pascal/asm, whatever you feel comfortable with.
One month of a modern cpu usage is more than enough to render those tables :)
Jeremy said
Just start. Pick a new language, and code hello world. Then write your first custom function. As soon as you start getting feedback in the console, your mind will be off to the races, and the month it takes you to get up to speed will actually be a challenging, fulfilling ride.
Just start. Blank canvases suck.
kirkus said
The higher-level number-crunching packages like MATLAB/Mathematica (or their free equivalents like Octave/SAGE) will do most (if not all) of the concurrency/parallelization for you – have you considered that route?
Trixter said
I have, actually, and have looked at Octave a little.
kklobe said
Also, if you do decide to grit your teeth and go with Python, the NumPy/SciPy combo have some similarly powerful number-crunching goodness.
Asterisk said
Have you looked into Free
Pascal (http://www.freepascal.org/)?
Trixter said
Definitely. For anything that needs a user interface (ie. not command-line) I am thinking of giving Lazarus a try.
Rugxulo said
“Gigs of memory and multiple cores” is something I’ll never ever understand. But just for clarity, if you disdain the slow, dynamic interpreted languages like Python and prefer the statically-typed, compiled Pascal, I would weakly recommend (not in any particular order) Active Oberon/Zonnon/Component Pascal, Modula-3, Ada2012, Go, or C++11. In particular, the latter two have quite good support, even if they aren’t really Pascal-y. These days, it really is (sadly) easier just to go with the crowd and use whatever your friends / coworkers use.
Trixter said
I ended up using Freepascal, and wrote my first 32-bit program a few weeks ago. My project is finished, and I’m relatively satisfied how it turned out. I was doing all console programming, no GUI (neither development environment nor end result) but it did what I needed to and the barrier to entry is now gone. So, alls well that ends well…
VileR said
Nice — so when should we expect to see the aforementioned radical 8088 demo project? ;-)
Trixter said
Various plans are in various stages of progress. A group of people and I are tossing around demo ideas, but it will take a special party with an oldskool compo to probably wring a production out of us.
Optimus6128 said
Hehe yes, I was about to say Freepascal.
I am not familiar with Pascal, I jumped from Basic to C.
But for a long time I was precalculating data in Qbasic or later Freebasic on Windows.
Ok,. not that big data. But I remember I had an unoptimal routine to generate normals for a 3d object (Armadillo, 500000 verices iirc) that took 30 minutes in Qbasic. Haha. Later I wrote the more optimal algorithm and do it fast in C during init.
But ok,. there are precalcs, huge precalcs and impossible precalcs, so I don’t know. Funny though that in order to code a clever effect with precalcs on 8088, one needs gigs of ram and multicore to precalc :)
Trixter said
I did, in fact, complete the work I lamented in the original post with Freepascal. I did not do anything fancy, like a GUI — it’s a console app that takes a few arguments and spits stuff out — but it wasn’t as terrible as I thought it was going to be, and now my oldskool work can continue. Hopefully you’ll see a production from me this year that uses the fruits of this labor.
My “precalc” didn’t need gigs of RAM or multiple cores this time… but it does stress a single core for about 8 minutes.
Unfortunately my next project after that cannot be reliably done on anything other than the target hardware, so I will be writing the compressor ON and FOR the target hardware, so that the decompression timings can be measured accurately. I expect to leave that one running overnight once it is finished…