3 ms·

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 doin

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?

gliptic 2y ago
https://en.wikipedia.org/wiki/Z-order_curve https://en.wikipedia.org/wiki/Z-order_curve
azornathogron 2y ago
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-swizzling/ 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.
tubs 2y ago
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 https://docs.mesa3d.org/isl/tiling.html
pbsd 2y ago
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 https://keccak.team/files/Keccak-implementation-3.2.pdf
chrchang523 2y ago
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.

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?

gliptic 2y ago

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

azornathogron 2y ago

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-swizzling/ 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.

tubs 2y ago

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 https://docs.mesa3d.org/isl/tiling.html

pbsd 2y ago

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 https://keccak.team/files/Keccak-implementation-3.2.pdf

chrchang523 2y ago

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.