Hacker News Reader

Comment by muragekibicho | Hacker News Reader

I saw something similar in Bit Twiddling hacks. Out of utter curiosity, when would you need to interleave bits in prod? Is it something a Saas dev would be doing or maybe sb in embedded programming?

View on HN

To expand on azornathogron's answer, when you are working with 2d data (it generalises to 3d too!) you often want to filter pixels in a rectangular area. This is commonly for bilinear filtering or some kind of convolution kernel.

If you don't interleave the bits and have large textures (think 4096 pixels wide) where each pixel is 4bytes big, that means there is a distance of 16kb between a pixel and the pixel below it.

This is super bad for caches (really important for the TLB in the MMU which is usually way smaller than data caches).

In GPU literature you'll see this called "tiling" (again like azornathogron said it's not always pure morton order), Intel document their tiling layout, here's an older layout doc:

https://docs.mesa3d.org/isl/tiling.html

If you're doing low level graphics programming (processing pixel data) or in some other way dealing with 2D raster type data, you might want to work with data in Morton order or with Morton order tiles or something similar. Interleaving the bits of the x & y coordinate values helps to put pixels that are close together in your 2D space also close together in memory, which can help with making best use of caches.

See for example https://fgiesen.wordpress.com/2011/01/17/texture-tiling-and-... (search "Morton" in the page)

There are probably other use-cases that I'm unaware of.

Keccak (and other ciphers only using bit rotation and bitwise ops) can use bit interleaving to avoid slow 64-bit rotations on 32-bit hardware, by replacing 1 64-bit rotation by 2 independent 32-bit rotations on the interleaved words [1, §2.1].

[1] https://keccak.team/files/Keccak-implementation-3.2.pdf

Two-bit values are common in bioinformatics, and I’ve found the ability to efficiently convert between packed arrays of 1- and 2-bit values to be valuable in that domain.

https://en.wikipedia.org/wiki/Z-order_curve

Reply on news.ycombinator.com