[MUSIC]. The last part of this section is to discuss alignment of our data structures in memory. let's see what we mean by that. A structure contains multiple elements. In this case, we have a struct that has a single byte first element. then two ints in an array as the second element. And finally, a double floating point number as its third element. So, what we would see and expect to see in memory is a starting address for our struct, the first byte being that character C. Then the next 8 bytes being the two ints in the array I. And then, the third part, the next 8 bytes, the double floating point number. And we would expect this struct to occupy 17 bytes of of memory. In reality we have to align this structure. And what we mean by alignment, is taking a data type that's of K bytes, like an int is of size 4 bytes and making sure that it starts at an address divisible by that by that number. So what we want to do is make sure ints start at addresses divisible by four. And double started addresses divisible by eight. So you'll see that, in fact, our struct will end up looking more like this in memory. where we have to pad an extra three wasted bytes that we're not going to use just in order to get the integer to line up at an address divisible by four. Similarly, we're going to have to pad an extra four bytes here to get the to get the the double float to be at an address, start at an address divisible by eight. Okay, and those are totally wasted space. that's called internal fragmentation uh,unused fragments of memory at the inside of our struct that we don't see in the declaration at all but that the compiler puts in, in order to meet this alignment requirement. why what is the basic alignment principle? as I said, it that data type of size that requires K bytes start at an address that is in fact a multiple of K. this is an absolute requirement on some machines. it's comple It's very much advised on the IA32, although not requ not required all the time there. we're going to assume it is, and always do things that way. But what is the motivation for this alignment? well the reason for the alignment is because we want to access physical memory and be able to get an entire piece of data in one access. So for example, imagine that we had a 4 bytes int, and the first two bytes were in one worded memory, and the next 2 bytes were in a separate word. We wouldn't want to have to read two words and then shuffle bytes around in order to get our int. so we'd like to make that be an efficient single memory read that would read the 4 bytes directly. We're going to see this alignment issue come up also in virtual memory which would be discussing a little bit later in the course. But for now the thing to remember is that the program it doesn't worry about this. The compiler takes care of this alignment, and that's why we're provided with the special function in C called size of which returns the, the size, given a data type as an argument returns the size of that data type and bytes in the number of bytes of memory. And that's important because depending on the architecture we're on, we'll have slightly different alignment requirements, and the size of the struct might actually vary, because we have to insert different amounts of unused bytes in different places. So, size of lets us get to the size of the struct as the compiler decided it had to be. So in the case of IA32 a single byte, a c a char eh, of course has no restriction on where it's placed in the memory, because a char is a single byte. And we can always have an address to any byte. a two byte short int, on the other hand, the a addresses lowered a bit must be a zero, meaning that that address is divisible by two. For things that are 4 bytes in size like ints and floats, and pointers, pointers to any type of data any address well then the lower 2 bits have to both be zero, because those addresses have to be divisible by four. Similarly for doubles the address has to be divisible by eight or have end in three zeros. Now it turns out that on some IA32 architectures doubles can only only have required to align to 4 bytes But for our part, we'll always kind of consider that perfect alignment eight byte things on eight byte multiples. Okay, how do we satisfy alignment with structures? Here's our example from before, remember? The, the one byte character, two ints in an array, followed by a double float. in our 64-bit architectures the value K, the alignment requirement that we have to meet, is eight. Because that, it goes for the largest element in the struct. In this case, that double float is eight bytes. so everything m, must be aligned to those eight byte boundaries. So our struct must start at a multiple of eight byte address. we can put that initial character there but then have to waste 3 bytes, so we can start our int at a multiple of four. then again those four wasted bytes, so we can start our float at a multiple of eight for its address. So, in 64-bit architectures we end up with this. What would happen in a 32-bit architecture? Well in this case, the double is only 4 bytes, so K is equal to 4. That is the largest data type that we use. And we can actually arrange things a little bit differently, because you notice that now we do not need to add the extra 4 bytes there to move the float to an 8-byte boundary. We can leave it on a 4-byte boundary without wasting those 4 bytes. So you'll see, you see here why sizeof is an important function. In this case sizeof would return 24. In this case sizeof would return 20 as the size of the struct. In neither case is it 17 however. We always need these 3 bytes here in order to make our integers line up. Let's take a look at another example that shuttles around the elements of the struct. again here is our original struct, and we can do a different definition where we put the largest element first, the double first, then the ints and then the smallest elements last the, the single byte character in this case. So, that instead of having this 24 byte struct, we can actually arrange for something that looks like this. You notice it loo, that it appears to be much more compact. We don't have those wasted bytes, and in fact, we don't have that internal fragmentation in this case. However, as we think about maybe having an array of these structs and having them follow each other, well they all have to start at boundaries that are divisible by eight. so to do that we end up having to add some padding at the end of the struct in fact we will have to add 7 bytes at the end of the struct. So, we end up having the same size struct anyway in this case, but in general we'll do better if we put the largest elements first. Okay but you can see here in the array, since we have to hit addresses that are divisible by eight, we end up with an extra 7 bytes of external fragmentation, some extra bytes at the end of the struct. All right, let's take a look at how elements of the array of structs are accessed. in this case we want to access an element 'I' of the array and then the J of or the J element of that particular struct. so first we're going to need an offset that gets us to the right array element, the right struct. That'll be 12 times I the index to get us to the right struct, and then we need an offset within the struct. and that offset is going to be an additional eight, because in this case that's where J will fall. Remember, in this case we have a 2-byte integer to start. some 2 bytes of padding in order to make sure that our float that is only four bytes now starts at an address divisible by four. which puts J at plus eight from the starting address. And of course, we end up having to put an extra 2 bytes to the next, between that and the next struck so that the next struct can start on a four byte boundary. That's how we can an overall size of 12, alright, and why we multiply the index by 12. The code for the, the summary code we might see for some functions for accessing these arrays. here we have a function get_j, which given an index goes to that element of the array and gets the J element of the, the struct at that position. the way this is computed is using just two instructions. You'll notice that the first one, this LEAL, is simply used to get three times the index. So that we can then multiply it by four to get 12 times the index. remember we can't just do that multiply by 12 directly. Those multipliers have to be powers of two. so we first compose a partial result that's three times the index, then multiply that further by four and add the offset from the start of the array A. That's the starting point of the, the entire array. And then, an additional eight to get us to the J element of the struct the offset within the struct.