DS 001, Arrays

What?

A collection of elements, of the same memory size, individually identified by an index (usually starting with 0).

Why?

Best used for sequential and index-based element storage and lookup on a fixed number of elements. This is a very common requirement within applications handling data.

Good

• Access: Sequentially apply f(element_at(i)) to each of n elements:

// unindexed
for each element in array:
	f(e)
// indexed
for i from 0 to length(array) - 1:
	f(array[i])

• Access: Get the element at index i

array[i]

• Update: Update element at i with value y

array[i] = y

Bad

• Search: Find index i of element with value == x (for large values of n)

Ugly

The following operations are unsupported on a fixed-size array.

• Insert: Insert an element x at position i
• Remove: Remove an element x at position i

How?

Arrays are fixed size contiguous blocks of memory (from the perspective the application). With this underlying construction, accessing by index is essentially an efficient O(1) lookup operation in memory where:

element_at(array, index) = address_of(array) + index * size_of(element)

These types of operations are cache-friendly and therefore mechanically sympathetic due to pre-fetching or aligned data fetching in cache lines. Compilers detecting sequential access patterns applying pure functions may also be able to parallelize operations for improved performance.

Note: Since arrays are typically fixed-size on creation performing a lookup outside of the bounds of the array will either lead to undefined behavior, or in memory-safe languages will lead to an exception or panic.

Example(s):

Intermediate

Java: Simple

public class DS001 {
	public static void main(String [] args) {
		var array = new int[]{5, 42, 12, 9, 38};
		for (int element : array) {
			System.out.println(array[i]);
		}
		for (int element : array) {
			array[i] = array[i] + 1;
		}
		for (int element : array) {
			System.out.println(array[i]);
		}
	}
}

Java: Advanced

Java

class DS001 {
    int[] create() {
        var array = new int[]{5, 42, 12, 9, 38};
        return array;
    }
 
    void accessSequentially(int[] array) {
        for (int elem : array) {
            System.out.println(elem);
        }
    }
 
    int accessElement(int[] array) {
        return array[1];
    }
 
    void updateElement(int[] array) {
        array[2] = 13;
    }
 
    void accessAndUpdateElement(int[] array) {
        array[3] = array[3] + 1;
    }
}

Bytecode JDK 23.0.1 godbolt.org

class DS001 {
  DS001();
       0: aload_0
       1: invokespecial #1                  // Method java/lang/Object."<init>":()V
       4: return
 
 
  int[] create();
       0: iconst_5
       1: newarray       int
       3: dup
       4: iconst_0
       5: iconst_5
       6: iastore
       7: dup
       8: iconst_1
       9: bipush        42
      11: iastore
      12: dup
      13: iconst_2
      14: bipush        12
      16: iastore
      17: dup
      18: iconst_3
      19: bipush        9
      21: iastore
      22: dup
      23: iconst_4
      24: bipush        38
      26: iastore
      27: astore_1
      28: aload_1
      29: areturn
 
 
  void accessSequentially(int[]);
       0: aload_1
       1: astore_2
       2: aload_2
       3: arraylength
       4: istore_3
       5: iconst_0
       6: istore        4
       8: iload         4
      10: iload_3
      11: if_icmpge     34
      14: aload_2
      15: iload         4
      17: iaload
      18: istore        5
      20: getstatic     #7                  // Field java/lang/System.out:Ljava/io/PrintStream;
      23: iload         5
      25: invokevirtual #13                 // Method java/io/PrintStream.println:(I)V
      28: iinc          4, 1
      31: goto          8
      34: return
 
 
  int accessElement(int[]);
       0: aload_1
       1: iconst_1
       2: iaload
       3: ireturn
 
 
  void updateElement(int[]);
       0: aload_1
       1: iconst_2
       2: bipush        13
       4: iastore
       5: return
 
 
  void accessAndUpdateElement(int[]);
       0: aload_1
       1: iconst_3
       2: aload_1
       3: iconst_3
       4: iaload
       5: iconst_1
       6: iadd
       7: iastore
       8: return
 
}

Compiled

Rust: Simple

fn main() {
    let mut array = [5, 42, 12, 9, 38];
    for element in array {
        println!("{}", element);
    }
    for i in 0..array.len() {
        array[i] = array[i] + 1;
    }
    for element in array {
        println!("{}", element);
    }
}

Rust: Advanced

#[no_mangle]
pub fn create() -> [u32; 5] {
    [5, 42, 12, 9, 38]
}
 
#[no_mangle]
pub fn access_sequentially(array: &[u32]) {
    for elem in array {
        println!("{}", elem);
    }
}
 
#[no_mangle]
pub fn access_element(array: &[u32]) -> u32 {
    array[1]
}
 
#[no_mangle]
pub fn update_element(array: &mut [u32]) {
    array[2] = 13;
}
 
#[no_mangle]
pub fn access_and_update_element(array: &mut [u32]) {
    array[3] = array[3] + 1;
}
 
// Additional functions with known array size avoids bounds checks and panic code:
#[no_mangle]
pub fn access_element_5(array: &[u32; 5]) -> u32 {
    array[1]
}
 
#[no_mangle]
pub fn update_element_5(array: &mut [u32; 5]) {
    array[2] = 13;
}
// no bounds check but overflow check occurs
#[no_mangle]
pub fn access_and_update_element_5(array: &mut [u32; 5]) {
    array[3] = array[3] + 1;
}

Rust example with #[no_mangle] for the benefit of godbolt.org compiler output

x86 ASM using rustc 1.83.0

<&T as core::fmt::Display>::fmt::hd1455fa1363db9bf:
        push    rax
        mov     rdi, qword ptr [rdi]
        call    qword ptr [rip + core::fmt::num::imp::<impl core::fmt::Display for u32>::fmt::h9a4153c5c33033b1@GOTPCREL]
        and     al, 1
        pop     rcx
        ret
 
core::fmt::Arguments::new_v1::h833399cf78fd70f5:
        mov     rax, rdi
        mov     qword ptr [rdi], rsi
        mov     qword ptr [rdi + 8], 2
        mov     rsi, qword ptr [rip + .L__unnamed_1]
        mov     rcx, qword ptr [rip + .L__unnamed_1+8]
        mov     qword ptr [rdi + 32], rsi
        mov     qword ptr [rdi + 40], rcx
        mov     qword ptr [rdi + 16], rdx
        mov     qword ptr [rdi + 24], 1
        ret
 
core::slice::iter::<impl core::iter::traits::collect::IntoIterator for &[T]>::into_iter::hbf95bf381c6fda3b:
        mov     qword ptr [rsp - 24], rdi
        mov     qword ptr [rsp - 16], rsi
        mov     rax, qword ptr [rsp - 24]
        mov     rcx, qword ptr [rsp - 16]
        shl     rcx, 2
        add     rax, rcx
        mov     qword ptr [rsp - 8], rax
        mov     rax, qword ptr [rsp - 24]
        mov     rdx, qword ptr [rsp - 8]
        ret
 
<core::slice::iter::Iter<T> as core::iter::traits::iterator::Iterator>::next::hd468f210e6c91097:
        mov     qword ptr [rsp - 40], rdi
        mov     rax, qword ptr [rsp - 40]
        mov     rcx, qword ptr [rax + 8]
        mov     qword ptr [rsp - 16], rcx
        mov     rax, qword ptr [rax]
        cmp     rax, qword ptr [rsp - 16]
        sete    al
        and     al, 1
        mov     byte ptr [rsp - 17], al
        test    byte ptr [rsp - 17], 1
        jne     .LBB3_4
        mov     rax, qword ptr [rsp - 40]
        mov     rax, qword ptr [rax]
        mov     qword ptr [rsp - 8], rax
        jmp     .LBB3_5
.LBB3_4:
        mov     qword ptr [rsp - 32], 0
        jmp     .LBB3_7
.LBB3_5:
        mov     rax, qword ptr [rsp - 40]
        mov     rcx, qword ptr [rax]
        add     rcx, 4
        mov     qword ptr [rax], rcx
        mov     rax, qword ptr [rsp - 8]
        mov     qword ptr [rsp - 32], rax
.LBB3_7:
        mov     rax, qword ptr [rsp - 32]
        ret
 
create:
        mov     rax, rdi
        mov     dword ptr [rdi], 5
        mov     dword ptr [rdi + 4], 42
        mov     dword ptr [rdi + 8], 12
        mov     dword ptr [rdi + 12], 9
        mov     dword ptr [rdi + 16], 38
        ret
 
access_sequentially:
        sub     rsp, 136
        call    qword ptr [rip + core::slice::iter::<impl core::iter::traits::collect::IntoIterator for &[T]>::into_iter::hbf95bf381c6fda3b@GOTPCREL]
        mov     qword ptr [rsp + 8], rax
        mov     qword ptr [rsp + 16], rdx
.LBB5_1:
        lea     rdi, [rsp + 8]
        call    qword ptr [rip + <core::slice::iter::Iter<T> as core::iter::traits::iterator::Iterator>::next::hd468f210e6c91097@GOTPCREL]
        mov     qword ptr [rsp + 24], rax
        mov     rdx, qword ptr [rsp + 24]
        mov     eax, 1
        xor     ecx, ecx
        cmp     rdx, 0
        cmove   rax, rcx
        cmp     rax, 0
        jne     .LBB5_3
        add     rsp, 136
        ret
.LBB5_3:
        mov     rax, qword ptr [rsp + 24]
        mov     qword ptr [rsp + 32], rax
        lea     rax, [rsp + 32]
        mov     qword ptr [rsp + 120], rax
        mov     rax, qword ptr [rip + <&T as core::fmt::Display>::fmt::hd1455fa1363db9bf@GOTPCREL]
        mov     qword ptr [rsp + 128], rax
        mov     rax, qword ptr [rsp + 120]
        mov     qword ptr [rsp + 104], rax
        mov     rax, qword ptr [rsp + 128]
        mov     qword ptr [rsp + 112], rax
        mov     rax, qword ptr [rsp + 104]
        mov     qword ptr [rsp + 88], rax
        mov     rax, qword ptr [rsp + 112]
        mov     qword ptr [rsp + 96], rax
        lea     rdi, [rsp + 40]
        lea     rsi, [rip + .L__unnamed_2]
        lea     rdx, [rsp + 88]
        call    qword ptr [rip + core::fmt::Arguments::new_v1::h833399cf78fd70f5@GOTPCREL]
        lea     rdi, [rsp + 40]
        call    qword ptr [rip + std::io::stdio::_print::he7d505d4f02a1803@GOTPCREL]
        jmp     .LBB5_1
 
access_element:
        sub     rsp, 24
        mov     qword ptr [rsp + 8], rdi
        mov     qword ptr [rsp + 16], rsi
        mov     eax, 1
        cmp     rax, rsi
        jae     .LBB6_2
        mov     rax, qword ptr [rsp + 8]
        mov     eax, dword ptr [rax + 4]
        add     rsp, 24
        ret
.LBB6_2:
        mov     rsi, qword ptr [rsp + 16]
        lea     rdx, [rip + .L__unnamed_3]
        mov     rax, qword ptr [rip + core::panicking::panic_bounds_check::h8307ccead484a122@GOTPCREL]
        mov     edi, 1
        call    rax
 
update_element:
        sub     rsp, 24
        mov     qword ptr [rsp + 8], rdi
        mov     qword ptr [rsp + 16], rsi
        mov     eax, 2
        cmp     rax, rsi
        jae     .LBB7_2
        mov     rax, qword ptr [rsp + 8]
        mov     dword ptr [rax + 8], 13
        add     rsp, 24
        ret
.LBB7_2:
        mov     rsi, qword ptr [rsp + 16]
        lea     rdx, [rip + .L__unnamed_4]
        mov     rax, qword ptr [rip + core::panicking::panic_bounds_check::h8307ccead484a122@GOTPCREL]
        mov     edi, 2
        call    rax
 
access_and_update_element:
        sub     rsp, 24
        mov     qword ptr [rsp + 8], rdi
        mov     qword ptr [rsp + 16], rsi
        mov     eax, 3
        cmp     rax, rsi
        jae     .LBB8_2
        mov     rax, qword ptr [rsp + 8]
        mov     eax, dword ptr [rax + 12]
        add     eax, 1
        mov     dword ptr [rsp + 4], eax
        setb    al
        jb      .LBB8_4
        jmp     .LBB8_3
.LBB8_2:
        mov     rsi, qword ptr [rsp + 16]
        lea     rdx, [rip + .L__unnamed_5]
        mov     rax, qword ptr [rip + core::panicking::panic_bounds_check::h8307ccead484a122@GOTPCREL]
        mov     edi, 3
        call    rax
.LBB8_3:
        mov     rcx, qword ptr [rsp + 16]
        mov     eax, 3
        cmp     rax, rcx
        jb      .LBB8_5
        jmp     .LBB8_6
.LBB8_4:
        lea     rdi, [rip + .L__unnamed_5]
        mov     rax, qword ptr [rip + core::panicking::panic_const::panic_const_add_overflow::hf2f4fb688348b3b0@GOTPCREL]
        call    rax
.LBB8_5:
        mov     rax, qword ptr [rsp + 8]
        mov     ecx, dword ptr [rsp + 4]
        mov     dword ptr [rax + 12], ecx
        add     rsp, 24
        ret
.LBB8_6:
        mov     rsi, qword ptr [rsp + 16]
        lea     rdx, [rip + .L__unnamed_6]
        mov     rax, qword ptr [rip + core::panicking::panic_bounds_check::h8307ccead484a122@GOTPCREL]
        mov     edi, 3
        call    rax
 
access_element_5:
        mov     eax, dword ptr [rdi + 4]
        ret
 
update_element_5:
        mov     dword ptr [rdi + 8], 13
        ret
 
access_and_update_element_5:
        sub     rsp, 24
        mov     qword ptr [rsp + 8], rdi
        mov     eax, dword ptr [rdi + 12]
        add     eax, 1
        mov     dword ptr [rsp + 20], eax
        setb    al
        jb      .LBB11_2
        mov     rax, qword ptr [rsp + 8]
        mov     ecx, dword ptr [rsp + 20]
        mov     dword ptr [rax + 12], ecx
        add     rsp, 24
        ret
.LBB11_2:
        lea     rdi, [rip + .L__unnamed_7]
        mov     rax, qword ptr [rip + core::panicking::panic_const::panic_const_add_overflow::hf2f4fb688348b3b0@GOTPCREL]
        call    rax
 
.L__unnamed_1:
        .zero   8
        .zero   8
 
.L__unnamed_8:
        .byte   10
 
.L__unnamed_2:
        .quad   1
        .zero   8
        .quad   .L__unnamed_8
        .asciz  "\001\000\000\000\000\000\000"
 
.L__unnamed_9:
        .ascii  "/app/example.rs"
 
.L__unnamed_3:
        .quad   .L__unnamed_9
        .asciz  "\017\000\000\000\000\000\000\000\027\000\000\000\005\000\000"
 
.L__unnamed_4:
        .quad   .L__unnamed_9
        .asciz  "\017\000\000\000\000\000\000\000\034\000\000\000\005\000\000"
 
.L__unnamed_5:
        .quad   .L__unnamed_9
        .asciz  "\017\000\000\000\000\000\000\000!\000\000\000\020\000\000"
 
.L__unnamed_6:
        .quad   .L__unnamed_9
        .asciz  "\017\000\000\000\000\000\000\000!\000\000\000\005\000\000"
 
.L__unnamed_7:
        .quad   .L__unnamed_9
        .asciz  "\017\000\000\000\000\000\000\0001\000\000\000\020\000\000"

More

Learn and Practice

• Learn: https://www.geeksforgeeks.org/array-data-structure-guide/
• Apply:
  • LeetCode: Problem List - Arrays