Swizzled Texel Layouts and the Cost of a Bilinear Fetch

A texture fetch is a memory access whose address depends on interpolated geometry, so it is unpredictable at the instruction level and usually far from the last fetch. That combination is the worst case for a cache hierarchy designed around sequential access. The layout decision, which texel sits next to which in memory, therefore has a larger effect on sampling throughput than the filter arithmetic does, and it is invisible in the coordinate space described in texel grids and wrap addressing.

The row-major problem in one number

Suppose an RGBA8 texture of width $W$. Row-major storage puts consecutive texels of a row adjacent, and consecutive rows $4W$ bytes apart. A bilinear fetch reads a 2×2 group: two texels side by side, in two adjacent rows. For $W = 2048$, a row is 8192 bytes, so the two pairs are 8 KiB apart; they never share a cache line of 64 bytes, and each pair may straddle a line boundary if the sample lands near one. The best case is two lines, the worst is four, and the average depends on the alignment of the sample point.

The second row’s line is what matters. Fetches in a shading pass are not one per pixel; they come in quads of 2×2 adjacent fragments, and each fragment fetches its own 2×2 group. Four fragments covering four texels horizontally produce a strip of texels four wide in two rows. In row-major, that strip is two 16-byte pieces separated by 8 KiB. Every one of those pieces is a separate cache line, and a warp of 32 threads sampling a coherent region touches dozens of lines spread across the same number of distant addresses.

The cache does not have to be large to hold the data; it has to hold it in a shape that matches the access. A 32 KiB L1 with 64-byte lines holds 512 lines. Each line covers 16 RGBA8 texels of a row, so 512 lines cover four rows of a 2048-wide texture. A coherent screen-space region that spans more than four rows of the texture therefore exceeds the cache on its own, before any other texture is considered, and a bilinear group at the edge of that region misses on the second row of the pair. That is the shape of the problem: the cache is large enough in bytes and wrong in geometry.

Tiled layouts and the 4×4 block

The standard repair is to store blocks of texels contiguously. A tile of 4×4 texels at 4 bytes each occupies 64 bytes, exactly one cache line on the common architectures. The addressing becomes

$$ \text{offset} = \left(\left\lfloor \frac{y}{4} \right\rfloor \cdot \frac{W}{4} + \left\lfloor \frac{x}{4} \right\rfloor\right) \cdot 16b + \big((y \bmod 4) \cdot 4 + (x \bmod 4)\big) \cdot b $$

with $b$ bytes per texel and $16b$ the size of one tile. Every bilinear group whose four texels lie inside one tile is therefore one cache line, where the row-major layout needed two at best. Across a coherent patch of fragments the difference compounds: a 4×4 block of fragments covers roughly a 5×5 texel neighbourhood, which in row-major spans five rows and therefore at least five lines, and in a tiled layout spans at most four tiles. The reduction is not marginal, because the cost stops scaling with the number of rows the footprint touches.

Two properties of tiles matter. The first is the tile size relative to the line. A 4×4 RGBA8 tile is exactly 64 bytes; a 4×4 R8 tile is 16 bytes, four tiles share a line, and the benefit is smaller. For single-channel and 16-bit formats, tile sizes of 8×4 or 8×8 are used to reach the line size. The layout is chosen per format, so a texture’s physical structure depends on its pixel width, not just on its dimensions.

The second property is that tiles are not transparent to filtering. Bilinear filtering takes four texels that may straddle a tile boundary, and at a tile boundary the four texels come from two or four tiles, which may be far apart in memory. The fraction of fetches that straddle is a geometric constant. A bilinear group crosses a tile edge when its position lies within half a texel of that edge, which is one texel’s worth of the $T$ in a tile, so each axis crosses with probability $1/T$. Either axis crossing has probability $2/T - 1/T^2$: for $T = 4$ that is about 44%, for $T = 8$ about 23%. Nearly half of all fetches still pay two or more lines at the smaller tile size. Larger tiles reduce the straddle fraction but increase the amount of data fetched per miss, and for a 1-texel sample the larger tile is wasted. 4×4 and 8×8 are the practical compromises; 8×8 gives a straddle fraction of about 23% at twice the per-tile bytes.

Morton order and the space-filling argument

A tiled layout is a two-level hierarchy: coarse tiles in row-major, texels within a tile in row-major. Morton order goes further and interleaves the bits of the coordinates at every scale, so that proximity in memory tracks proximity in 2-D at all sizes. Texel $(x, y)$ maps to the index formed by interleaving the bits of $x$ and $y$:

/* Interleave the low bits of x and y: bit 0 of x -> result bit 0,
   bit 0 of y -> bit 1, bit 1 of x -> bit 2, and so on. */
unsigned morton2(unsigned x, unsigned y)
{
    unsigned z = 0;
    for (int i = 0; i < 16; ++i)
        z |= ((x >> i) & 1) << (2 * i) | ((y >> i) & 1) << (2 * i + 1);
    return z;
}

The interleaving has two consequences. A square block of $2^k \times 2^k$ texels maps to a contiguous range of $4^k$ indices, which gives the tiled layout at every level: 2×2 tiles inside 4×4 tiles inside 8×8 tiles. And the memory distance between two texels tracks the product of their 2-D separations, rather than staying constant along a row and jumping by $W$ between rows. For a rotated mapping, where screen-space coherent footprints run diagonally, the improvement is largest: a 45° run of 16 texels in row-major order touches 16 different rows and therefore 16 lines, while in Morton order it stays inside a handful of blocks whose indices are close together.

The cost is address computation. Bit interleaving is several shifts and masks per fetch, which at one fetch per texel is not free. Hardware implements it with a fixed pattern of bit selections, which is a handful of instructions and much cheaper than the general loop above. Software samplers that use Morton order precompute the address of the tile and walk the block, so the interleave happens once per 16 or 64 texels rather than once per texel.

Honest accounting: the benefit of Morton over plain tiling is concentrated in anisotropic and rotated cases, and for axis-aligned coherent access the two are close. Implementations that use Morton order do so because they must handle every case well, not because it dominates in the common case.

Swizzling for bank conflicts

A separate use of “swizzle” refers to the order within a memory system that has banks. If a row of a texture is stored with a stride of $2^k$ bytes and the memory system has $2^k$ banks, every element of a column access hits the same bank. An XOR swizzle permutes the low address bits by the row bits, so that a column access distributes across banks:

$$\text{addr} = \text{base} + \text{row} \cdot \text{stride} + (\text{col} \oplus f(\text{row}))$$

The function $f$ is chosen so that consecutive rows shift the column by different amounts, which spreads a column’s accesses over all banks. This is a distinct concern from cache locality, and the two are usually combined: a tiled layout whose tiles are XOR-swizzled within a larger unit. For a sampler, the effect appears as a change in the shape of the region that fits in the cache, not in the number of texels touched.

Texture samplers are not the only consumers. Render targets and compute shader writes have the same problem, and the tiling mode of a render target determines both whether it can be sampled efficiently and whether it can be written at all. A common division is between a linear layout that both rendering and sampling can use at some cost, and an opaque tiled layout that only the sampler can use efficiently and that requires a resolve step to read back. The resolve copies the whole surface into linear storage, which is why readback of a rendered frame is much more expensive than sampling the same frame.

What the layout cannot fix

The layout optimizes the address pattern of one fetch group. It cannot help when the group itself is spread over a distance larger than a tile, which is the anisotropic case: sixteen taps along a major axis cross sixteen tiles regardless of the order within them. It cannot help when different fragments in a warp sample completely unrelated regions, which happens with incoherent vertex data or with shaders that compute coordinates in a data-dependent way. And it cannot help when the working set genuinely exceeds the cache, which is the case for a large texture minified to a level whose level data is larger than the cache even though each individual fetch is local.

The mip chain interacts here in a way that is easy to overlook. Each level has its own dimensions and its own tiles, and a level whose dimensions are not multiples of the tile size has padding at the edges. The padding is stored and occupies memory but is never sampled. A texture of 1024×1024 with 4×4 tiles needs no padding at all; a 1030×1024 texture needs two more texels per row to complete the last tile column, which costs 0.6% of the level’s storage and repeats at every level whose width is not a multiple of four. Choosing dimensions that are multiples of the tile size, typically powers of two, removes the padding entirely.

Compression interacts too, and in the opposite direction. A block-compressed texture’s 4×4 texel block occupies 64 bits, eight bytes, so eight blocks share one 64-byte cache line. The decode unit’s working set is therefore eight times smaller per texel group than the uncompressed case, and a bilinear group that stays inside one block touches eight bytes rather than 64. That does not make the layout irrelevant: the eight blocks on a line are chosen by the layout, so a tiled or swizzled arrangement determines whether the neighbouring blocks a footprint needs are the ones sharing its line. The two designs are chosen together for that reason, as block compression discusses on the encoding side.

The final constraint is that all of this is invisible to the shading language. A shader writes texture(tex, uv) and the address arithmetic, the tiling, the swizzle, and the block decode all happen inside the unit. That is a benefit for portability and a problem for performance work, because the only knob available at the API level is the texture’s layout when it is created, and that choice is usually made by the loader rather than the person writing the shader.