Unrolling the Loops - Computerphile

Key Takeaways

back in the early 1980s John warau the founder of adobe had invented postcript he had pioneered all their work of getting a postcript interpreter embedded into Laser Printers he persuaded Steve Jobs at the time to say when your new Macintosh comes out we want it to be almost a dual announcement at the same time but they didn't quite make it the Macintosh did come out first of all a little 9in one which we've done videos on but alongside it fairly shortly afterwards was the Apple laser printer John had got the killer app he thought to show off the skills and wonder of his laser printer driving with postcript the output and that killer example was a United States income tax form for supplementary income so he programmed this up in his postcript language you sent it down to the Apple laser writer which was so fast you couldn't believe it but it took a minute and a quarter to image it and the wondrous jobs of course said John I know how to present but I cannot hold them for one minute and a quarter while we press the button and we wait for it to come out the light at the frontage is going to blink blink blink so John being a very good computer scientist and knowing all about his own language postcript said yeah what we've got to do Steve is remove all the procedures just get them automatically removed and unroll the the loops and make sure that every if statement that we know what data goes into that if statement so we know which way it's going to go through the program so we're going to flatten the program as it sometimes called we're going to linearize it we're going to bind in the data and say we want the fastest route to the final visual effect so that's what he did and the unrolled version imaged in 20 seconds not a minute and a quarter so it really did work we teach our students very carefully good programming principles we teach them to use if statements for Loops blocks structured programming oh and above all else um Isn't it nice to Hive stuff off into procedures or sub routines whatever you want to call them and to uh call them up with superable arguments and it's it's clean and nice and structured and gets you very good grades in your coursework under the good you always have to remember that there is a bit of a penalty performance-wise to be paid for doing all this if you just consider the humble for Loop for example every time you go round that Loop the compiler is building in a checking mechanism at the top saying you said start at one and in steps of one go on until you get to six and do it around the loop like that and every time you go around that Loop it has to say what's my Loop counter at the moment oh I'm on three now let me take a look at how far I'm supposed to oh six is oh is three less than six yes it is oh I think we better go around again is that I exaggerate but you know what I'm getting at equally if you dive into a procedure you call it up with arguments do remember from what we've done already that that causes stack frames to be set up to propel your arguments to that function and to post them into the function and then when the function's finished doing its job it has to clear down that stack frame and if the function's recursive there might be zillions of Stack frames be cleared down it's all overhead but it's overhead that you're probably prepared to pay because it helps you think about the problem and do it neatly and elegantly but if you're concerned with performance of your program to the nth degree these overheads can begin to tell and sometimes to get Optimum maximum performance under specialist conditions you might want to say rather than going around this for Loop six times and doing pretty well exactly the same thing I will write it out by hand six times and forget the forward Loop would that be quicker the answer is very often yes what I thought I'd do in the true Spirit of computer file this little example that we'll do now we want to print out six computer file banners look at that correct font and everything as you all know it's called OC I'm afraid that my uh printer is a bit deficient it's knocked off the corner of the pointy bracket but please forgive okay so how do we do it just using a a postcript for Loop well very briefly I'll go through this with you more details available on the specialist postcript video if you need it every postcript program has to start with percent exclamation mark this says I am postcript from now on comments in postcript programs begin with percent in column one so program for six computer file banners Define the variable end to be six here is the postcript command called select font which says what font do you want and what point size do you want to do it at we're saying find the font called OC and at Point size 30 make me a copy of that ready for use in postcript here postcript does everything backwards in Reverse polish notation but effectively it is very simple it's a for Loop so it's basically saying four starting at one and in steps of one up to n but we know n is six do the following code inside these curly braces now the next line is saying we want six computer files and they should all be at 10 points in from the margin and they should be 100 points apart when you look at this carefully I'm doing them upwards not downwards now you can see what happens when you start printing out stuff probably designed for us letter onto A4 paper you're 10 point almost an what is it 72 points an inch I tried to do a 17th of an inch indent and it didn't work it's all to do with paper sizes but anyway going up the page at 100 Point increments which is just a bit more than an inch 16 instances of computer file all beautifully printed out and there's the end of your for Loop and finally it has as it were virtually imaged this for you inside its own graphic memory but if you want it to show up on your screen or ultimately your piece of paper you say show page now some postcript interpreters if it gets to end of file and you haven't said show page we'll put a show page in for you there's the show page here's the thing done not in a for Loop but writing out six separate calls of the command to print out computer file at 30 point when you might say well you used things like show and move to and show page and here on this copy you're not no I'm trying to show you something which will be of used to as later on that postcript enables you to redefine operators and to abbreviate their names if you want to so up at the top here I say look Define just the letter s to be the operator show Define m to be the same as move to now the word bind just means remember I've done this definition and don't permit any other redefinitions that might mess things up don't let anybody else or don't let even yourself making mistakes try and change it again this is binding solidly M to being moved to select font I've abbreviated as SF show page as SP and look the very first one is there that's 10200 move to I'm there and then another then another and finally SP which is the abbreviation for show page but I didn't write it out by hand I got a transform program to do it for me because it's all right doing six of these with a bit of fancy abbreviation definitions at the top but if it was 10,000 times out I don't want to rep at something 10,000 in an editor or by hand here's a transform script which we'll leave there for in the notes if you get it working write us a comment will you and say yeah wow it worked for me you should be able to work out how to use it and I should say this is a much much much simplified version of the unrolled transform script that John waro used back in 1984 to get his income tax form which was far more complicated than six computer files to print out in a reasonable amount of time on the Apple laser writer just one final comment what John did and what this is echoing here in this abbreviation so why are you bothering to abbreviate the answer is well if you unroll the loops and replicate things you're making files bigger and bigger and bigger lots more printing isn't there in the file and that's not necessarily a good thing can we keep file size down yes by doing abbreviations and that realization made by John in 1984 was the very earliest glimmerings of what we now know as PDF this particular server has four Titan X graphics cards in it a Titan X is one of the four most graphics cards there are new generation 10 Nvidia Graphics cars coming out and some AMD cars