The SimpleMath Behind the Speed of Arrays

Practice low level programming interview question with Assembly

Question:

“We often don’t work with assembly here, we mostly work with low level C but this does not mean you won’t ever have to write assembly here. We may need to benefit from the speed of assembly under certain circumstances. But in C we often use the array data structure, can you explain why arrays have constant time retrieval with indexes? And can you provide short arm assembly code to show the underlying workings of how this works?”

My Answer:

“Arrays are stored under a variable and the variable points to the first element in the array. Given all elements of an array have to be under one type, the compiler will know exactly how much memory that type will need so it can allocate enough space for all elements in the array. In assembly we can store the size of the type for simple arithmetic to retrieve an element at a certain index. Since the address of the variable aliasing the array points to the beginning we can use that for the base arithmetic. The index passed in can be multiplied by the size of the element and added to the base address. That results in the address of a specific element being returned.”

My Simple ARM Assembly code (Not a whole Assembly program, just code that would go in ‘main’):

            AREA seunSuberu, CODE, READONLY
            ENTRY
            ;arr is the variable for an array
            ;index is the value for the requested index
            ;assuming that the element is 4 bytes in size
getElement  ADR R0, arr
            LDR R1, index
            MUL R2, R1, #4
            ADD R2, R2, R0
            ;R2 will have the address for the element, so it will essentially return the ;pointer for the element

Additional Resources:

• https://www.tutorialspoint.com/assembly_programming/assembly_arrays.htm