# Array Blocking

# Array Blocking

Array blocking divides an array into contiguous chunks and processes one chunk at a time. This can improve cache locality because nearby elements are reused before moving to the next block.

You use it when large arrays exceed cache capacity or when work should be processed in batches.

## Problem

Given an array $A$ of length $n$ and a block size $b$, process the array in ranges:

$$
[0, b), [b, 2b), [2b, 3b), \dots
$$

until all elements are processed.

## Algorithm

Scan the array by blocks.

```id="array-blocking"
block_scan(A, b):
    if b <= 0:
        error "block size must be positive"

    n = length(A)

    for start from 0 to n - 1 step b:
        end = min(start + b, n)

        for i from start to end - 1:
            process A[i]
```

## Example

Let

$$
A = [8, 3, 5, 1, 9, 4, 2]
$$

and

$$
b = 3
$$

| block | range    | values    |
| ----- | -------- | --------- |
| 1     | $[0, 3)$ | [8, 3, 5] |
| 2     | $[3, 6)$ | [1, 9, 4] |
| 3     | $[6, 7)$ | [2]       |

Each block is processed before moving to the next one.

## Correctness

The outer loop chooses block starts at multiples of $b$. For each start, the end index is capped at $n$, so the last block handles the remaining elements safely.

The inner loop visits every index in the current block. Since the blocks are contiguous, non-overlapping, and cover the range $[0, n)$, every element is processed exactly once.

## Complexity

| operation  |   time |
| ---------- | -----: |
| block scan | $O(n)$ |

Space usage:

$$
O(1)
$$

for simple block scanning.

## When to Use

Array blocking is appropriate when:

* arrays are large
* cache locality matters
* processing can be batched
* each block can be handled independently

It is less suitable when:

* the algorithm needs global random access at each step
* the best block size is hard to estimate
* overhead from nested loops dominates small inputs

## Implementation

```python id="array-blocking-python"
def block_scan(a, block_size, process):
    if block_size <= 0:
        raise ValueError("block size must be positive")

    n = len(a)

    for start in range(0, n, block_size):
        end = min(start + block_size, n)

        for i in range(start, end):
            process(a[i])
```

```go id="array-blocking-go"
func BlockScan[T any](a []T, blockSize int, process func(T)) bool {
    if blockSize <= 0 {
        return false
    }

    for start := 0; start < len(a); start += blockSize {
        end := start + blockSize
        if end > len(a) {
            end = len(a)
        }

        for i := start; i < end; i++ {
            process(a[i])
        }
    }

    return true
}
```