Session 3

The following is the comment I had left on YouTube, before comments were disabled:

This was supposed to be "Data Structures for Boxes and Glue", but it's mostly about "memory words", with just a bit about boxes at the end.

This video in playlist: https://www.youtube.com/watch?v=_dYdPE2_WZM&index=14&list=PL94E35692EB9D36F3

Preliminary remark in the first 2 minutes:

“During lunch I thought of something that I wanted to mention in session number 1… just a little bit of my personal feelings about what I hope publishing this whole program will achieve. I learned programming myself by reading listings of software when I was a college student. Some of that software was very good for me because it was badly written, and gave me a lot of motivation: I said “This was written by a professional and I could do better than that so I must have a special talent for it, so I’m going to become interested in computers”. And others of it was very beautifully written and I thought “This is a pleasure to read; I’d like to do something like that someday”. Now I’m not sure which category this particular program is going to fall into, but either way it seems to be winning and you could reach the right person. So I’m hoping that some young people might see this program and learn from it at least one aspect of software writing. I’m not sure exactly if this could be used in a curriculum or if it is just something that people would do during the summer or on their own to pick up, but somehow one of my goals has been to provide a picture of software here in a way that might inspire some people out there to write their best software.”

Most of TeX’s memory is dynamically allocated, made of an (in-program) unit (a variant record, think “struct” or whatever) called a “memory word”. This is either • a single 32-bit integer (understood either as an integer or a scaled quantity i.e. fixed-point fraction), or • a glue ratio (think: 32-bit floating point number), or • two half-words (think: 16 bits each), or • four quarter-words (think: 8 bits i.e. a byte each), or • two quarter words and a half-word. (TeX program Part 8: Packed data.)

Demonstrates the debugging routines from TeX for printing a memory word. All of this done by 35:00. Then the memory layout (high part for one-word records, and low part for multiple-word records), freeing and allocating memory, etc.

At around 36:00:

Here again, I didn’t use Pascal’s heap or something; I programmed something from scratch so that I could control exactly how much memory was getting used… and so that it would be more portable. And we could do a lot of other things with it… same kind of reasons as for strings but even more so now.

(TeX program Part 9: Dynamic memory allocation.)

Note: he talks of “hi_mem_base” but this was removed later: see errorlog entry 819 of 25 Nov 1984 (also comment on 540 from 22 Oct 1982).

At 51:08:

Now to free_avail – again, I just wrote a macro for it; I didn’t want a procedure call overhead particularly… it was only needed about 5 places in TeX, so why not repeat the code each time instead of calling procedures.

At around 58:00 there’s a trick of saving a bit (the type of some field) by looking at its value: if it’s a “pointer” to high memory it’s one type else another, etc.

BTW a linguistic oddity: he uses “program” where we would use something like “function” or “code” or something else. (See also e.g. sections 37, 354, 391 in the TeX program.)

The transcript below is autogenerated from YouTube, and needs to be cleaned up.

hi so here we are again it is a session number three and during lunch I thought of something that I wanted to mention in session number one and uh and it’s just a little bit of the my personal feelings about how what I hope publishing this whole program will will achieve I learn programming myself by reading other people’s software reading listings of software when I was a costume and some of the software I was very good for me because it was badly written and gave me a lot of motivation that I I said this was written by professional and I could do better than that so I must we have a special talent for it so I’m going to major I’m going to be coming to ested in computers and others of it was was very beautifully written and I thought this is a pleasure to read I like to do something like that someday now I’m not sure which category this particular program is going to fall into but either way it seemed to be winning and you could reach the the right the right person you know and so I’m hoping that some some people young people might see this program and learn learn from it at least one aspect of software writing and I’m not sure exactly how if this could be used in in curriculum or if it or if it’s just something that people would would do during the summer or you know to on their own to to pick up but somehow one of my goals has been to provide a picture of software here you know in a way that might inspire some some people out there to to write to write their best software now the agenda for our afternoon the next thing is called data structures for boxes and glue and this is one of the key things that that I used over and over in tech the way the way boxes lists of things are are represented there so as I mentioned in the last lecture a large part of the memory a large part of the core memory that that’s going on while Tech is running more memory than in fact the whole program itself is is this dynamic memory area this is where we’re going to store things about boxes and glue really horizontal lists and vertical lists and the elements of horizontal listen vertical lists can be can include boxes blue and a variety of other things so now the the first thing we have to understand is is the way that memory array works and and so step number one is is to is to see that every item that you address in the array is is what we call a memory word it’s a Pascal record called memory word and this is uh starting on its in module 105 on page 37 now a memory word is is something that it that ought to be represented well by your pascal compiler if you don’t have a pascal compiler that’s going to do this memory word correctly you can be wasting incredible amount of memory well factor for probably so you’d like to have a Pascal compiler that tax things properly to a memory word now when we when I have a something of type memory word I it’s a variant record the definition is actually on page 38 so let’s look at the at the whole definition that’s in module 108 it’s where let’s see we might get on the screen so we have memory word is made up of four quarter words is one of the options or two half words and so we have a definition there that says two choices for choices this is just because of the way pascal ism I needed this particular type but a memory word then is a pact record and it’s and then it’s a case for choices of this in Pascal means that there’s four possibilities and would you store something under under any one of these you should retrieve it under the same one so if I set X dot int to something it ought to be an integer and then then I shouldn’t try to read out X dot gr I should if I’m unless unless i’m using dirty Pascal 30 Pascal would allow me to read out x dot gr and this is called a variant record and it’s a special case of a variant record where I don’t store the the particular variant something some people would put in their store an integer 124 with the record with with with X telling what kind it is but that way space and time and there’s no point in it the way we were using it so we have four choices int gr HH and qqqq of four different types so this memory word is support for all four different types they’re all supposed to come out to be approximately one word then of memory and talk about these types a little bit there’s actually fifth type that I use in the program called SC and when I and that’s because I i also have scaled quantities this is a section that I didn’t discuss it’s the previous section of the program scaled quantity is an integer but it doesn’t represent an integer it represents a unit of it represents a physical distance so it has units and the units are scaled points namely 22 to the 16th scaled points makes one point that’s a scale point then is it so for the scale that means that the decimal point is is 16 bits from the right-hand edge and when I when something is an integer but it’s really representing scaled i call it SC instead of int or i say that it’s type is scaled instead of integer in order to provide a comment to the reader about that pascal never sees this but the person reading this program gets to see the difference between SC and editor now all of these are supposed to take up the same space I worked it out so the tech will never allow the user to give it an integer constant greater than 2 to the 31 minus 1 so the orange or less than negative of that so the so this means that that text should be able to work with 32-bit integers that have signed that have signs and if you have a machine that has more bits than that well it still run tech and those other bits of goop presumably be zero however you could get actually larger integers in there through some arithmetic operations and they just would overflow on machines that are smaller but we would prefer that people write tech programs that are going to work on all on all the 32-bit machines if you have a larger machine what you should do with it is make your quarter words and half words bigger so that gives you a chance of making the mem alright bigger then you can address more more words but not actually work with bigger integers or scale values you don’t really need anything more any dimensions that large inside the typesetting job who’s going to typeset something more than 19 feet one console so so we’re where I you know at least if you wanted to you could probably break it into two parts and or say that it was and or magnified up from something else and have the magnification to done in the DVI file so so 32 bits is plenty for these images now glue ratio is the next case and that is something that you could define any way you want to is defined here is real now a glue ratio is is used only to when we’re setting a box and we have to stretch or shrink to glue then the glue ratio is the proportion by which the thing will stretch or shrink so for stretching for example in the glue ratio is point 333 then one third of the stretch component gets gets added and it and I distinguish between that and scale the scale values are kept as integers and the arithmetic is defined very precisely on all the scale values because it’s important that every implementation of tech compute exactly the same numbers when it works with scale values scale values will affect the performance of tech as far as how many lines get put onto a page and how many pages there will be in a manuscript and so on if you stick with the calculations as they’re given here you can be sure that you will get the same type setting information on a cdc machine as you would get on an IBM machine even though their arithmetic is done quite differently they at least agree on integers but when you try at it and tell them to do floating-point arithmetic you’re liable to get all kinds of different results and this would lead to different type setting different pages and not and people’s sending tech job from one place to another would find that it that it doesn’t work out so this is a major change that I that I made in tech 82 that was at first was going to be the only major change but we felt quite strongly about it as being one of the first first noticeable defects and technically we weren’t machine dependent because we were depending on floating point arithmetic so I went to scaled however for glue ratio it was a big pain to to work with scaled numbers and doing multiplication by so many ratios which you had to do in multi simulating multiple precision in order to get a decent result in all the cases and really it wasn’t necessary because the result of a GU ratio never participates upfront intex decision making it only comes out when you’re setting the final box in a putting to a DVI file does it actually ever compute this this number from the glue ratio so so i can i can use real arithmetic floating-point arithmetic in other words even though it’s not it’s not machine independent because that’s that will only affect the positioning of the final boxes in something that the I couldn’t possibly detect so so you can use that there if you want however to do a fixed-point arithmetic instead of floating point for example you’re implementing this on some kind of a micro that doesn’t have floating point or it has horrible floating point software then there’s a suggestion for how to do all the computations you need with glue ratio in a in something that would pack into a into a word 32-bit word and I wrote that up in tugboat and that appeared in the you know I think the februari issue of tugboat I have a reference to it actually in the program somewhere blue ratio here it is tugboat three nineteen eighty two pages ten to twenty seven it’s the reference on in module 104 so that’s the that’s the that’s a type glue ratio which I’ve made real in this case now if you change it to some other type then you just need to find a few places where i’ve used glue ratios I have to print a glue ratio i have to multiply by a glue ratio and one or two other things and and then you could you could substitute something there that would be probably better than a bad floating-point implementation if you if you had to do it on a micro now on I BM Pascal at least the way it was a some time ago if you said real that would give you 64 bits so you’d have to say short real in order to get a 32-bit floating point number and the person should be careful to declare memory word so that this will work out if glue ratio is real and then integer will be 32 bit but you’d still be wasting 64 bits for every memory word because the because it picks the worst case of these now what about two halves here’s another comment commenting or we’re going to break up this word impact two different two different things in the word so two halves is we find up above that and it’s a packed record also that has a rh which you might realize is right half and then the other part of it is either LH another half word or two quarter words the RH is always a half word but with an Rh you don’t necessarily have an LH you might have to core towards b0 and b1 so that’s the two halves type and and that two halves type is is quite commonly used especially in well the whole upper part of mem is entirely two halves as we’ll see now the the other possibility is four quarters and that I think you could guess it’s be 0 V 1 B 2 B 3 all quarter words now some machines will pack a quarter word if it goes in the range 0 to 255 say and and if you have a 32-bit machine you’ll be able to get four quarter words in one word and will be treated as from zero to 255 but on other machines the only type only way they would pack is if it was like minus 128 to plus 127 what’s happening here we’re losing were losing the screen I think you better leave that down because I might get back to it again it’s fun to watch that it isn’t a knob so Anna I’m micro on a Pascal implementation that if you give it to 0 to 255 if it considers that a 9 bit position then then I you wouldn’t be able to put four of those in a word and on the other hand on our past call if you ask if you say minus hundred twenty-eight 2 plus hundred twenty-seven it takes up a whole word for that it considers that a sign position has to want to go there so pastels are quite different from each other and I didn’t want to make tech unusable just for that fact so I was so i define quarter word in a in a very general way where it’s a sub range from min quarter word to max quarter work and similarly half words go from in half word to max effort and you can redefine these and chances are tech will still work now I’m going to have to debug it with min quarter word non zero to make sure that I’ve not forgotten to add it in the right place and subtract it in the right place who will I do is if I want to represent a number from 0 to 255 in a quarter word i subtract min quarter word from it or no I admin quarter word to it excuse me and then when i read it out i subtract min quarter word from it now the conditions that those constants have to satisfy are all listed there in 106 so all the program is supposed to work provided these conditions are true and the program actually runs through and checks those conditions in any tech does anyway check these conditions and gives you a stop at the beginning saying I’m sorry but you set up your no you set this thing up wrong so that I can’t handle it the conditions are first of all that your min quarter word has to be zero or negative you can’t have min court or equal to 1 because I’m storing zero sometimes in a quarter words okay similarly max quarter word has to be at least 127 because sometimes I’m storing 127 in there and okay men half word has to be again zero or negative and the maximum half word has to be at least two other the largest 15 bit number then we also have to be have a relation between quarters and half words that any quarter work can be storable and a half word so that the next line says that the minimum quarter word has to be greater than or equal to minimum half word and similarly for the Maxis the next line says that the memory base that’s the lowest address in memory has to be greater than or equal to a minimum half word and the largest address in memory man max has to be strictly less than max half where these are the cases the relations here are not the ones that must be true but the ones that must be false so men max cannot agree on or equal to max effort the max half word itself was used as a flag so the largest location addressable in memory has to be strictly less than your maximum half work so for example if your men have word is minus to the 15th your max half word is to 15th minus 1 is 32 767 then your mem max had better not be any larger than 32 766 if you have a 36 bit machine you see you could make your max half word to the 18th minus 1 and then you can your memory max could be four times as large as on a 32-bit machine similarly for fonts that so the gist of that line there are says that any memory address can fit in a half word so I keep pointer data pointers to memory locations in a half work the next line says essentially that any font internal font number can fit in a quarter word my internal font numbers are the numbers that is that I assigned to fonts not the users number but about the one that tech the tech keeps the user might have several fronts 10 and 11 and 12 that all turn out to to boil down to the exactly the same font and I’ll map those into the same number inside so so I have an internal front number and besides his numbers might range from 0 to a very high case but I want to pack them all tightly so I internally we have numbers running from fonte base to font max in those numbers internal font numbers must all be representable in a quarter word the next thing is similarly things I want to represent and a half word and the same size that’s usually very small only a few hundred but i but but if it were larger than a maximum half word I’d be in trouble so I put all those restrictions that would conceivably ever cause tech any problem I think I listed them here and so they you’re not allowed to have more than say 32 k strings now that’s not the size of the string pool that’s the size of the string start already that says that you shouldn’t have that many strings well it’s rare to have more than ten thousand strings who’d 130 thousand me because each one of those things would be pretty long too so so if you can’t get that and a half word you in trouble i doubt if anybody would ever set next things that high but if you did they say bad with 16 and later we get an error message saying this is case 16 of what you can’t do this error message is expected see these events that are expected to come along so so rarely and seen only by person running any any tech that they have just been left as numeric codes the last one is a buffer size your input buffer which I have at 500 now and that’s been more than enough if that gets larger than 32,000 then we’ve bad because I’m storing a buffer pointer somewhere and a half word in released one place in fact okay so those are the constraints there and you want to design those so that it all gets packed together now Pascal compilers don’t always optimize adding 0 and subtracting 0 and my program is careful to admin quarter word and subtract mint mac i subtract min quarter word and half words and so on especially this quarter word every time that I’m packing something that might might go past 127 into a quarter word and well this is in the inner loop I mean like every character go this happens to every character and so I’d be adding 0 and subtracting 0 rather needlessly and in the part of tech that’s supposed to run real fast if I believe the we’ve made memory counts before and I think it’ll still happen in New Tech that a small very small part of tech maybe one percent or so is executed a large number of times I call that the inner loop and we make pain so that that the inner loop doesn’t have a lot of wasted emotion in it so because if the inner loop is fast I can do just about anything everywhere else and it won’t make much difference so one of the things we’re doing in the inner loop is adding subtracting min quarter word so i define macros for this purpose is the QI macro for into a quarter word and qo macro for out of a quarter word and they just add and subtract min quarter words this is in section 107 here you see now of course it might change file at sale min quarter were 20 so I just really find Qi of hash to be hash and because this Pascal wouldn’t optimize the way that’s 0 that’ll save that will make tech run maybe five percent faster so it’s changing that one Mac or not now if I have it if I’ve missed it somewhere in the probe in the program saying Qi where I should have I won’t notice it right now because Qi of something is you know leaving it out would have been the same so I’m going to run some tests where I where I have min quarter word negative and that means that my memory words are going to knock pack into one into one word but that will be ok because i can run tests on a small memory size to check that but you won’t have to worry about i’ll be the one has to worry about this this kind of testing any questions on this part now i think to understand what a memory word is I’m some y’all question please use the mic this piece of code then DJ change those macros in other words that are compile time yeah in your in your change pot yeah see y’all I’ll put that up on it I’ll put that up on the screen let’s see if we can switch to the computer file here and I’ll search for Qi left bracket okay here’s the change that I made it at sale for this and so you see that you with all changes to start the top line is common to the two and then I added this other sentence here so they have been simplified here in the obvious way and you see how I how did it you can you read the can you read a web source file instead of a web output file is it sufficiently enough contrast there you see you put up the app sign d for a definition so that’s the that’s what you do ok now while i’m at this like guess i could explain it the that i have a last resort thing for debugging it built into the into the tech debugger and let me see if i can activate that let’s see i’ll run or run a pre-loaded version of tech this is this is tech that’s been preloaded with a format from from the trip file yesterday we played around with the trip file it has the Pascal debugger in it so I have to do this to get out of the Pascal debugger and now it’s it’s running this tech and it says format equals trip 82 7 25 which is probably last Sunday and and now to get into my debugger I have a tech debugger built-in also that will do things intact so technically bugger I can for example give an undefined control sequence and it will stop on undefined control sequence now why compiled tech with the debug switch debugging and view bed or whatever that debug backwards is if I if I have not commented out the debug code and I have a special secret option that I can type to an undefined control sequence’ however I better get out of scroll mode before I do that because I mean scroll mode that doesn’t allow me to respond to undefined control sequence’ i go to my error stop mode and give another undefined control sequence’ got it now I got a question mark prompt and and so i can say d this is the secret thing that I can do and that gets me into my debugger now the debugger is written at the very end of your program it’s module oh gosh maybe not the very end but near the near the very end and I see it here page 3 95 96 module 12 07 and 1208 and this is a cryptic thing that I use only in emergencies but it gives me as prompt of a hash marks and it and then the number of options that i can type are described on page 3 96 and there are various things that I can do for example 11 will check the memory to see if all the links are okay if there is any weak links if there’s a if the lists have been clobbered somehow it will we will have checked that well there it didn’t find any problems oh I guess they would like some of the house lights in the audience so that they can look at their own copy is it getting brighter out there can you give them some house lights in the audience please okay thanks now the the option number one will print memory word of a location and in memory and well I should find a location that’s not 0 let me just try let me try 5 580 and hope that it’s not 0 and see what it is it’s not been pre know it’s been preloaded 20 I should be coming well 580 102 let’s see excuse me a sec here I’m going to what’s going on well let’s see going to try to find out which locations are are are not free so 527 25 70 are not free so i should try i should be able to get 570 or something like that 527 so let me try 527 okay so if I say one and then 527 one is my debugging command says print out memory word 527 oh that’s 02 done it well here’s one that wasn’t 0 okay now print memory word is something that I can use that will print out of memory word in all of its possible forms so location memory location 528 is a memory word that can be interpreted it as an integer as minus 260 to 144 on this particular machine or if it’s interpreted as a glue ratio it would be minus 4.0 okay and if its internal I’m sorry I as a scale if it’s interpreted as a scale that would be minus 4.0 because I / 2 to the 16th if it’s interpreted as a glue ratio would be 0 because it has a zero mantissa essentially now the next line print out that memory word as if it was two halves and so to the left of the semicolon it says 4915 2 equals 192 colon zero so the left half it’s either an LH field and in this to have since either left half of 49 152 or it’s a b0 of 192 and a b 10 0 and the right half is 65535 and that is that sort of clear know if this word memory word was packed two halves then the right drh part would be 65535 and with the two halves you have either L which would be 49 152 or you have b0 and b1 which we’ve been 190 20 and then the last thing on that second line is 255 255 192 0 that’s b0 b1 b2 b3 in case you call it four quarters now this particular shows that this particular pascal compiler packs these words the one that I call right half actually is in the left half of the word just end they will think that I call be zero in the case in case two halves is 192 would be zero if it’s four quarters is 255 that’s I think it’s the left half anyway you must be or it comes in somehow that way so but doesn’t matter how podcast I’ll compiler does that since I’m never going to make any assumptions about the way past called as the packing I’m always going when I store something in with with two halves or if I start something in the b0 field I’m never going to read out and LH field ok I but when i’m debugging i might want to to take a look at memory and have it printed out in this way to see what it would be like in different fields here’s one of the places than when i did dirty pascal this is one of the few places in the code where it does read a memory word in a different format from the way it was stored but i only use this as a last resort i just built this in something so that i could do so without having to do a lot of kind of pencil and paper calculations on the on the thing if i had to otherwise my final afterwards there wasn’t that bad because if i go back by type 0 and now i get back into pascal debugger and pascal debugger i could look I could talk about mem 527 and I could talk to a dot int and it and this debugger whoa 528 sorry tells me what it is and then if I wanted it with the HH rh it would have given me 65535 and and I could also ask for the dot qqqq and dot B to field and it would have told me what it is so I didn’t really need this print memory word very much because I have it in the past golly bugger it does illustrate however the idea of a memory word with a little bit of redundancy so I think by now everybody knows so much about memory words they want me to move on to something else right okay the format file that you dumped out is all full of memory words so so the the format that contains all of your strings your macros font information for quick preloading the dot FMT file that is a file of memory word that’s one of the reasons why we wouldn’t expect it to be readable from one machine to another now inside that memory this was for several arrays in the program are of our type memory word but the big one is this mem mmm and that’s the one that goes from embase up to mem max inclusive and inside of that we do dynamic location up until a point called high mem base and as Hyman base and low man base and the layout of memory is explained in modules starting a 156 and then of the next few pages after that where 156 gives really the layout of memory that that’s on page 51 so the the key the key place there is hi mmmm base because memory is divided once and for all into two areas the the the low part of it and the high part of it and the hard part of it is used only for one word records and the low part all is used only for records that are more than one word long now here again I didn’t use past heap something I programmed something from scratch so that I could control exactly how much memory with getting used here and so that it would be more portable now we and we could do a lot of other things with it and it’s same same kind of reasons as for strings but even more so now the area of less than hi ma’am then as I said is it always has nodes of two words or more and those above my men are done in the simple one one word at a time reservation if you set if you have a job that has lots of macros macro gets stored in one word one word items the item actually consists of the RH part is a link and the LH part is divided to b0 b1 no it’s it’s the LH part which is a token or a 16-bit representation of one token of your macro definition so if you have a if you are running something with large macro packages you want a lot of space above high mem base the thing that put in the present are the old version of tech the thing that put big big demands on things less than high man base were boxes and also the in the notes that were made up intermediate to making paragraphs for example when I ran this tech job on Sunday to print this this book for you I got I overflowed my memory below I’m m-base when i got to the index and here i was 430 pages into this thing and it and it crashed that memory capacity exceeded and the reason was that there was the word type had been used so often and it came right at the end of a page so tech memory was already fairly full and then along comes a paragraph that sells all the places where i used type in this program and it and for each of those had built a very large break node so that it could optimize the index entry for type which was also a trivial optimization if you looked at it because all the three-digit numbers that would five of them fit on a line and there was nothing else to do but it to know this because it’s doing a fancy ragged right margin and everything so so the memory crashed because it was overloaded there with with with boxes and and things for the cut for the paragraph shape well in tech 82 the paragraph nodes are reduced in size from 10 words to three words and they aren’t generated as often so this that so you won’t need quite so much space there however if there are still if you had an application was doing things with real long paragraphs there you’d want there you would need a lot of space below hi mam base but there’s there’s important reasons for fixing it once and for all at compile time what this time I’m base is as you’ll see as you get into it so so this is the way we you have to make a decision when you when you compile tech as to what hyman base is going to be hyman base is not listed in that list of compile time constants in the module 11 because if you change hi man base at compile time then you can’t run a format but you have to also change your FMT file see the fmt file is going to start loading macros at high man base or and compute some other some other things that go in to the to the memory there and but you’re allowed to change mem max at compile time and it won’t affect your format file so somebody can you can increase the size of the memory up in the macro region up in the up in the upper area just we just change it in a in the constant section attack recompile and you’ve got more memory up there but if you’re going to if you have to change hi mam base then you’re going to have to also run any tech again and make another format file the the process that you’re not supposed to change at compile time are listed in mark in module 12 so the constants in 11 are given as Pascal Co NS t type constants in module 12 the the the constants of mem base and high man base are defined as web map growth also hash size is another one is defined there so if you want to change the size of the hash table certainly you can’t preload your your hash codes unless if you change the size of the hash table many of the other things though can be just changed and the fmt file will still work even though the size has been different so you can increase the number of fonts you can increase the number of parameters that priests the size of your buffer crees the side of your string pool most of those things can all be changed without recompiling unitec now that’s the high men base then separates the dynamic variable size memory from from the other part now that the variable size memory starts out with a few words that are in fixed locations and I guess here I get to try out this pad and see what happens or should I try the blackboard I think the blackboard might be better because everybody feels so on here’s the dynamic memory and here’s your here I got you I got you okay but I better light there but it’s okay so here’s your dynamic memory this is mem and and I put mem base here and mem max is it is the largest and then it’s high mem base somewhere where you decide is a good place you can compile with the stat option then it tells you exactly what the maximum amount of memory you’ve used to both kinds is for each job and also within a particular page so you can get a feeling for what would be good for the kinds of jobs you’re running now there’s another location defined in this section on the memory allocation called first mem and second ma’am and these are where we actually do the dynamic locations in between here we have fixed locations set up set aside for things that I can refer to by fix the dresses I know they want to be somewhere in them and I also know that I’ll always always need them there so i always put them that so right here for example we put the definition the specifications for glue that like Phil glue or zero glue things that are that are people can say when they say H Phil and it will refer to one of these words we know we will always want an H built to be present in this area I have one word nodes that I always want to be present these are typically the heads of lists so that they’ll they’ll be they’ll have a link field and and this will be starting to point to to the first item on a list and then it’s good to have another word that starts that list it makes a lot of the algorithms simpler if they don’t have to consider the empty case of the special case so this is the high mmmm base to second man and then all of these other air from first men to Hyneman base this is 20 up to hi mmmm base and then this is about I don’t know a dozen locations in here all the way up to mem max this is all dynamically allocated now the easiest thing to describe is how we allocate memory in this part in this part of it all of these words are of type two halves remember the type two halves had an RH part and either b0 b1 or HH or LH n 0 now the 2 so the two halves here are the right with rh part is always called link and so typically our one word nose will be linked together in a list that we draw this way the link field i call it link and so there’s a definition that link is the same rh now there’s a pointer there’s a there’s a global variable called mem end which tells the largest location in this memory that you’ve ever that you’ve ever seen as you ever asked for so you never told tech never bothers to initialize this part of it this might be gobs and gobs of memory to sit you know mm n is the largest one you ever need it and it points to the and there’s another one called a veil which points to the first one that’s that’s not being used right now so if a veil ever gets to to be empty of a null pointer then we increase mem end by one and and get the new location otherwise we never look at men and if the sort of but otherwise a veil is pointing to a two to one and that one is pointing to the next one that’s available and so on a typical way of keeping track of which things aren’t currently in use so when something is recycled instead of doing a garbage collection we have a the algorithm that makes it available and then when the veil becomes null and and we need another one then we try to move from MN at that time if men equals min max work out of luck we’ve run out okay now those algorithms then are described just before the discussion of memory layout dynamic memory allocation starting at module 110 that’s right after the description of memory words and in that section it talks about the the way a veil is is is handled so let’s see that’s the bottom of page 39 and and we you might see my finger here vail link avail link of link of avail these are the available locations terminated by no now I never say 0 for a null link I always say no and I defined no to be named base so it’s the same as the address here of the first word in memory which is turns out to be also the same as the word 0 glue is stored I never make use of these of this fact but it’s it’s true and in order to but when I say no this means i’m thinking of it as a null pointer if I say 0 glue that means I’m thinking of that as the address where zero point plus zero point minus zero point is stored and if I say zero that means I’m not talking about a memory address at all in my program okay now so global for a veil in mem and are defined at the bottom of page 39 there are in module hundred thirteen to get a new word I say get a veil and we have a function says that returns a pointer and the word pointer is is is synonym for half word however it’s only used when I intended to be a pointer into either men or are one of the techs other big tables could you show that on the screen possibly or here is the get avail function you know your camera is pretty good we get a veil function that allocates a single word node and so that’s the simple algorithm that I mentioned except that you see we have to also always care be careful of errors and so p is set to avail if it’s not know that’s good then we just set avail to link of a veil now avail is pointing to the next available one and we’ve reserved it otherwise we look at them and and we hope it’s less than men max and going the virgin territory so if it was less than man max that’s great we increase ma’am end and that’s the value P that we’re going to get for this pointer otherwise we call a procedure called run away now this is a procedure that will come in and give them error message saying do you have a runaway argument because that’s one of the most common reasons for for running out of memory at this point as if somebody forgot a right brace and it might be a parameter to a long macro that doesn’t have any protection against against right braces missing and here we would like the at least as long as we’re going to kind of abort the job for running out of memory we’re going to at least one a point to where that where the error was so it won’t happen again so there’s a runaway procedure that will left i will give a essentially appropriate error message directly then we reset link of p to know before we return a get avail whenever we get something from that procedure it’s going to it’s going to have its link field no because if you ever want it to be something you want it to be null and you almost always want it to be know when you’re getting a new word out of this memory then there’s something that would be commented out unless we were maintaining statistics and here’s what would slow it down because we have to get available things they’re often so increasing this counter seeing how many words are currently in use and that and then get a veil is the full value of the function is as return at this point not to free avail put something of it again I guess wrote a macro for it i didn’t want the procedure call overhead particularly so it was only needed about five places in tech and so why not repeat the code each time instead of crawling a procedure so i have free avail of that pointer and so you just do the opposite process we we put me plan a link field to the previously available one avail now points to the new newly wat available one and we decrease the number of things dynamically used there’s no other way to get available one word knows you have to call one you have to say get a veil or free avail it’s not allowed to do this yourself and okay come through the next procedure is something that will take a whole list and free amount and free em all now so that’s simple in the one word part of memory in the variable word part of memory there’s a kind of interesting method views and I I’ll go to the blackboard again switching this multimedia show here does somebody have the time by the way I want to try to pace myself to fit actually I have it on my screen here if the computer isn’t done yeah 255 you’re right okay so in this area of memory I’m sorry in this area of memory they every time I get out of a variable size cluster of nodes I make sure that I that the link field in the first word is something unequal to mmm max it’s never equal to men max remember the mmmm we never I’m sorry never equal to it max half word because we made sure that mm max was strictly less than max half words so this this is something would never occur as a link field or a pointer if this was equally but the ones that are available are going to be flagged by having their first word in a Link field here as Max half word now if is long so we can store any data here except that one that one bad one and then the rest of the format is completely free but going to this is a in use but if it’s free then we put max half word here which I can just indicate by all once or something like that and binary and then we put the size here of the free area and then I have an el link in our link in the next word and this is a this size a doubly linked list of free cells that’s that goes around in a circle and then the rest of the words are are unknown now if I want to free something up I simply stamp its size field here I have to know how big it is when I’m freeing it and then I linked it into the circular list there’s a list of all these of all these notes that are free and when I’m well I need to find a new place in this memory I go around this list until I find one that’s big enough by looking at the size fields but before I check to see if it’s if I found a place big enough I I also look at the one right after it to see if it’s also free if it’s also free then it will have ones that finish in this field here and then I can come then I can combine these two at that point I keep doing that until i get to a place that’s followed by a non-free one might be preceded by a free when I don’t care i’ll get to that one later if I if I if I really need it but I look ahead and collapse it at this point and and dynamically this works out very nicely and then I and then I get a then I see if the size is right if it’s big enough that means that it might fit perfectly then i can just allocate it and take it out of its list if it’s if it’s one too big I can’t do anything with it because I’m not allowed nodes of size two of size one in this area but so it has to be at least two to larger if it’s at least two larger then i allocate the top part and I decrease the size of this one so that’s the algorithm that’s explained there in the next part for a variable for getting variable size records important thing to remember is if you’re implementing any extensions to it make sure that you put some kind of a link field or something in the first word here that could never possibly be all once that’s a mild restriction but it it could certainly be violated if somebody because somebody didn’t know okay well how the I’m running a little bit short though because I wanted to tell you what goes into these lists and but I got I got through most of the main ideas because we talked about the info i guess in one word section of memory i always call the left hand the LH part the info fields and the right rh part the link field then something that’s also rather commonly used in the program is an l link in our link field but these always refer to the info and Link parts of the second of the second word of a multi-word known so if somebody if i ever in my program say el link i’m talking about the left-hand part of word to of something that’s at least two words long now all of these things that can go on and in a horizontal list are indicated a somehow and linked together yes so if I have a list has a hundred items in it they’re going I’m going to have a pointer to the first one somehow it’s linked field will link to the second one it’s linked field will point to the third and the final one will point to know I use a circular linking like this only in the list of available cells for the variable size memory but the other lists are always well there’s only one or two exceptions almost always end with no and I have to tell what kind of a what kind of a thing I what kind of thing I’m doing so there’s a little bit of a problem because I want to pack a link field in a word and I also typically have a font and a character font is 256 possibility that’s a quarter word a character is 256 possibility there’s another quarter word and my link is a half word I’ve used up my 32 bits well here we have a great solution due to lowest reporter Anunnaki I don’t know who what combination of the two of you but they realize that just by looking at the address of the word I could tell whether it was in the one word part of memory or the other variable part of memory so it is up in the one word part of memory I know it’s a character node and I don’t need to look at it any further I know that it that it contains five and character information so up here anything up above high mmmm base is going to have a link in this park and then it’s going to have a font and a character and it’s b0 and b1 part so it’s called the front character feels so as I’m going through a list I can check to see whether the pointer is high then I know that it’s a font and character saved a bit that way you know if it’s not then we have a type field and so we have a type field and a subtype field the type field tells what kind of a thing it is is a box horizontal made out of horizontal is is it a turn or whatever the subtype is a is further information relating to the type so the type field then is something that we have room for 256 different types i’m only using about 30 of them subtype field is often not used at all if i was implementing this on a microcomputer i could do something different about the organization of the memory I since all these words up above high man base are half words I could allocate them as 16-bit as two 16-bit arrays whose which go from Hyneman base up two men Max and and then I could implement from from men base up the first member 16-bit words and make instead of a memory word I could use I could devise something so that if this would ever come out to a some other number of bytes then I wouldn’t I save a little bit of space in here I don’t think it would save a great deal but it’s the possibility for a change you know is if you change some of these macros you would be able to run the rest of tech just by changing in the way it refers to nodes in memory with with some other memory organizations that would be equivalent or I don’t think like a typical use you’d gain a great deal over over over what we have right now now each each type so i i’m looking at something anything i look at the t feel that tells me what type it is and the type will be one of these things listed starting on on module 129 and there’s just a great number of definitions they’re following all of the English language words that it says ageless note is 0 and so the type field will be 0 in such a case box node sizes 7 this is a declared as a macro so that when I free a box know if somebody chose another way of storing this and boxes were some other number of words then then you would only have to change this macro in this one place the width offset depth the this the second word of a box notice its width as a scaled number that’s defined here width of something is ma’am of that plus width offset dot SC okay that’s the width of a box and depth of a box height of a box shift amount of a box these things are explained in words above it now the different things we can have is our ageless node V list known rule note turn the page we get new we get in snowed insertion nodes mark nodes adjustment notes for the via just operation ligature node discretionary node all of these have subfields that are explained what they what the function is there I might go into that a little more next hour the whatsit node i mentioned in the lecture yesterday that’s not type 8 and that’s for extensions and the subtype you look at the subtype of what’s at node and it would tell you what kind of oh what’s that you have there is a math know that begins and ends math formulas glue nodes which are pointers to to the actual specification of glue current nodes and penalty nodes and some more coming up later unset nodes and things like that so the various different types of nodes and I describe this all in words as two so that you know what they represent in order to reinforce that whenever I in this program whenever I define a complicated data type I usually follow that by a bunch of programs that printout that data type in symbolic form so at least you can you can get an idea as to some programs that use this data structure and how a safe way to refer to the data structure is because if you’re going to have a program that’s going to print out what’s in a node you’ve got to be able to you know it’s not only this printout is not only explain what’s than a note but the program is going to use the right protocols for accessing your node so this whole section called displaying boxes is really worth reading when if you ever want to know what you what’s in a box we looked at one of those examples before display a node p it says if is charno then print font and charity so but if you look at these codes you’ll see that this is the way you’re supposed to to look at the data structure by using the macros in the discipline these routines that display boxes and glue and so on so so the programs not only will give printouts then when you have to find out what’s inside attack it’s so looking at all those bits and and and checking against the macro definition saying what was type 3 not only does this give you a program that does it symbolically but it also the program itself shows you is a paradigm of how to write other programs that access the data structure any questions on that before we adjourn okay thanks very much and I’ll see you at in 24 minutes