1 00:00:03,840 --> 00:00:09,038 In this brief video we're going to talk about alignment. A very low level but very 2 00:00:09,038 --> 00:00:14,109 important detail of machine architecture that every compiler writer needs to be 3 00:00:14,109 --> 00:00:22,778 aware of. First, let's review a few properties of Contemporary machines. 4 00:00:22,778 --> 00:00:29,437 Currently, most modern machines are either 32 or 64 bit meaning you have the 32 or 64 5 00:00:29,437 --> 00:00:35,626 bits in a word and the word is actually subdivided into smaller units. We would 6 00:00:35,626 --> 00:00:42,285 say that there are eight bits in a bye and then four or eight byes in word depending 7 00:00:42,285 --> 00:00:48,944 whether it's a 32 or 64 bit machine. And other important property is that machines 8 00:00:48,944 --> 00:00:54,927 can be either byte or word addressable. Meaning that in the native language of the 9 00:00:54,927 --> 00:01:01,939 machine in machine code it may be possible to either name only entire words or it may 10 00:01:01,939 --> 00:01:07,256 be possible to reference memory at the granule area of individual bytes. They say 11 00:01:07,256 --> 00:01:14,250 that data is word aligned if it begins at a word boundary. So if we think about. 12 00:01:14,250 --> 00:01:21,442 Data in memory or the organization in the memory and is laid out into bytes. And 13 00:01:21,442 --> 00:01:28,984 let's say. That this is a 32-bit machines so that four bytes make a word and one 14 00:01:28,984 --> 00:01:34,462 word begins here and the next word begins here and if data is allocated on a word 15 00:01:34,462 --> 00:01:39,606 boundary, say, it needs more bytes then that would be a word a line a piece of 16 00:01:39,606 --> 00:01:44,549 data. If a piece of data begins in the middle of the word, so let's say for 17 00:01:44,549 --> 00:01:50,027 example that begins here, and we have some data that's allocated here, this data is 18 00:01:50,027 --> 00:01:55,531 not [inaudible] doesn't begin on a word boundary And [inaudible]. Property or the 19 00:01:55,531 --> 00:02:01,340 important issue is that most machines have some alignment restrictions. So these 20 00:02:01,340 --> 00:02:06,829 restrictions come in one of two forms. So, on some machines, if the data is not 21 00:02:06,829 --> 00:02:12,497 properly aligned, meaning that you tried to reference data that isn't aligned the 22 00:02:12,497 --> 00:02:17,815 way the machines requires, then the machine may just fail to execute that 23 00:02:17,815 --> 00:02:23,413 instruction. Your program may hang or even the machine may hang and it's, but, the 24 00:02:23,413 --> 00:02:28,801 important thing is that program will not execute correctly. So there's a, it's 25 00:02:28,801 --> 00:02:34,400 incorrect to not have the data aligned properly. Now, there are other machines 26 00:02:34,610 --> 00:02:39,702 that well, actually al low you to put the data anywhere you like but at a 27 00:02:39,702 --> 00:02:44,937 significantly cause And maybe that accessing data that is aligned in word 28 00:02:44,937 --> 00:02:50,383 boundaries is cheaper than accessing that's on non-word boundaries And these 29 00:02:50,383 --> 00:02:58,221 performance penalties Are often dramatic so it can easily be ten times lower to 30 00:02:58,221 --> 00:03:06,564 access missile line data than to access data that has the alignment favored by 31 00:03:06,564 --> 00:03:14,185 that particular machine. So let's take a look at an example where data alignment 32 00:03:14,185 --> 00:03:20,401 issue tend to come up. One of the most common situations where we have to worry 33 00:03:20,401 --> 00:03:26,538 about the alignment is in the allocation of strings. So let's say we have this 34 00:03:26,538 --> 00:03:32,832 string, the string Hello and then we want to put it in memory. So let me draw our 35 00:03:32,832 --> 00:03:40,256 memory as a linear sequence of bytes so I'll mark out some bytes here. And let's 36 00:03:40,256 --> 00:03:46,202 assume this is a 32-bit machine so let me make the word boundaries a little bit 37 00:03:46,202 --> 00:03:53,279 heavier boundaries. So, one, two, three, four. Okay. So, there are the, the word 38 00:03:53,279 --> 00:03:59,200 boundaries And now let's say there were we are trying to have aligned data, a word 39 00:03:59,200 --> 00:04:04,703 aligned data and so allocate this string beginning in the word boundary. So, the 40 00:04:04,703 --> 00:04:10,066 each character will go on the first byte when e, then l, then l, then o. And now, 41 00:04:10,066 --> 00:04:15,848 we may have terminating null depending on how strings are implemented. And let's 42 00:04:15,848 --> 00:04:21,838 assume that we do. And this is fine placement of the strings extremely begins 43 00:04:21,838 --> 00:04:27,382 in the word boundary and. That assess by presumably any alignment restrictions of 44 00:04:27,382 --> 00:04:32,832 the machine and now the question is where does the next data item go? So we could 45 00:04:32,832 --> 00:04:38,646 begin the next data item right in the next available byte and that would be good if 46 00:04:38,646 --> 00:04:43,724 we are very concerned about not wasting memory. But, I noticed that, that data 47 00:04:43,724 --> 00:04:49,338 item will then be were aligned. We may either run into correctness or performance 48 00:04:49,338 --> 00:04:54,951 problems if the machine has restrictions on the alignment. So, the simple solution 49 00:04:54,951 --> 00:05:00,364 here is to simply skip to the next word boundary and allocate the next data item 50 00:05:00,364 --> 00:05:06,094 whenever it is on the next word beginning at the next word boundary. And what 51 00:05:06,094 --> 00:05:11,488 happens to this two bytes here, well these bytes are just junks. T hey're not used at 52 00:05:11,488 --> 00:05:16,687 all, they never reference by the program. It doesn't matter what they're value is 53 00:05:16,687 --> 00:05:21,886 because the program should never refer to them. It's just unused memory. And note 54 00:05:21,886 --> 00:05:27,085 that if we didn't have the terminating zero then there would be the terminating, 55 00:05:27,085 --> 00:05:32,468 no character then and then would be three unused bytes after the [inaudible]. So to 56 00:05:32,468 --> 00:05:37,521 summarize this is the general strategy for dealing with alignment when you have 57 00:05:37,521 --> 00:05:43,015 alignment restrictions. Data begins on the boundaries, typically word boundaries that 58 00:05:43,015 --> 00:05:48,257 are required and if the particular data that you're allocating has a none integral 59 00:05:48,257 --> 00:05:53,183 length. Meaning that it doesn't end directly on the next required boundary and 60 00:05:53,183 --> 00:05:58,172 you just skip over whenever bytes are in between to get the data, the next data 61 00:05:58,172 --> 00:06:01,520 that's going to be allocated on the correct boundary.