3 ms·

In some cases (especially user land code), using array indexing can be better than using pointers. It allows to re-use data between GPU and CPU, use fewer bits

In some cases (especially user land code), using array indexing can be better than using pointers. It allows to re-use data between GPU and CPU, use fewer bits for indices and simplify serialization. For example Flatbuffers is a very nice example: https://google.github.io/flatbuffers/ https://google.github.io/flatbuffers/

uvdn7 5y ago
And not to mention better CPU cacheline hits!
- KMag 5y ago
  I used to sit next to a guy who previously professionally wrote compilers for both DEC Alpha and Itanium (http://robert.muth.org/ http://robert.muth.org/), who mentioned that programs often ran faster on Alpha (which only supported 64-bit addressing) when modified to use 32-bit array indexes instead of pointers, due to reduced memory bandwidth/cache usage. Of course, one had to first determine if one needs to use any arrays larger than 2^32 elements.
  - mmastrac 5y ago
    Linux used to have the x32 ABI for similar improvements: https://en.wikipedia.org/wiki/X32_ABI https://en.wikipedia.org/wiki/X32_ABI
rayiner 5y ago
The issue addressed in the article with pointer tagging applies whether you use array indexing or pointers. Both are converted to pointer operations under the hood, which on X86 are some form of ADDR = BASE + SCALE*INDEX + OFFSET. Such an operation is still considered a pointer dereference (of BASE) from the view of the hardware, and will trap if tags are stored in the unused upper bits of the pointer. Depending on the size of the array elements, you won't even be able to use the built-in index addressing mode, because the index can only be up to 8 bytes. For that reason, LLVM doesn't even have array indexing. Loads/stores can only be done against pointers, and pointers to items in arrays must be expressly computed using a get-element-pointer instruction: https://llvm.org/docs/GetElementPtr.html https://llvm.org/docs/GetElementPtr.html.
- erwincoumans 5y ago
  Thanks for the insightful reply. I didn't realize array indexing gets converted to pointers in the CPU. I expected the array indexing assembly instructions to be plumbed all the way down without converting to pointers until the very end. LLVM not supporting array indexing means all those instructions go unused, on both x86 and arm? How about gcc or other compilers?
  - saagarjha 5y ago
    This is less about "array indexing" and more about arrays being located at a specific memory address. At some point you're going to have a buffer at address 0x1000 and want to access the 42nd element, and you can't just use a tagged address (e.g. 0x1000000001000) and 42 together without stripping the tag somewhere.
  - clord 5y ago
    The compiler can convert small known-size known-offset array accesses into registers or direct static stores and loads, but array indexing is usually on large chunks through a dynamic index via a ref or pointer, which will be via pointer math.
  - rayiner 5y ago
    They don’t go unused. Typically the separate address calculation and load will get merged back together during instruction selection is there is an applicable instruction. (Although that may not happen either—the compiler might transform the code to get rid of the array indexing. Keeping around the base pointer takes an additional register.) But on x86 and ARM these instructions are limited. On x86, a load instruction can have a prefix that treats one operand as the array base pointer, and another operand as the index. But the size of the array element is limited to 8 bytes so if your array elements are say 16 byte structs, you can’t use those instructions. As to ARM, I think it doesn’t have an array indexing instruction at all, just base + offset.

uvdn7 5y ago

And not to mention better CPU cacheline hits!

KMag 5y ago
I used to sit next to a guy who previously professionally wrote compilers for both DEC Alpha and Itanium (http://robert.muth.org/ http://robert.muth.org/), who mentioned that programs often ran faster on Alpha (which only supported 64-bit addressing) when modified to use 32-bit array indexes instead of pointers, due to reduced memory bandwidth/cache usage. Of course, one had to first determine if one needs to use any arrays larger than 2^32 elements.
- mmastrac 5y ago
  Linux used to have the x32 ABI for similar improvements: https://en.wikipedia.org/wiki/X32_ABI https://en.wikipedia.org/wiki/X32_ABI

rayiner 5y ago

The issue addressed in the article with pointer tagging applies whether you use array indexing or pointers. Both are converted to pointer operations under the hood, which on X86 are some form of ADDR = BASE + SCALE*INDEX + OFFSET. Such an operation is still considered a pointer dereference (of BASE) from the view of the hardware, and will trap if tags are stored in the unused upper bits of the pointer. Depending on the size of the array elements, you won't even be able to use the built-in index addressing mode, because the index can only be up to 8 bytes. For that reason, LLVM doesn't even have array indexing. Loads/stores can only be done against pointers, and pointers to items in arrays must be expressly computed using a get-element-pointer instruction: https://llvm.org/docs/GetElementPtr.html https://llvm.org/docs/GetElementPtr.html.

erwincoumans 5y ago
Thanks for the insightful reply. I didn't realize array indexing gets converted to pointers in the CPU. I expected the array indexing assembly instructions to be plumbed all the way down without converting to pointers until the very end. LLVM not supporting array indexing means all those instructions go unused, on both x86 and arm? How about gcc or other compilers?
- saagarjha 5y ago
  This is less about "array indexing" and more about arrays being located at a specific memory address. At some point you're going to have a buffer at address 0x1000 and want to access the 42nd element, and you can't just use a tagged address (e.g. 0x1000000001000) and 42 together without stripping the tag somewhere.
- clord 5y ago
  The compiler can convert small known-size known-offset array accesses into registers or direct static stores and loads, but array indexing is usually on large chunks through a dynamic index via a ref or pointer, which will be via pointer math.
- rayiner 5y ago
  They don’t go unused. Typically the separate address calculation and load will get merged back together during instruction selection is there is an applicable instruction. (Although that may not happen either—the compiler might transform the code to get rid of the array indexing. Keeping around the base pointer takes an additional register.) But on x86 and ARM these instructions are limited. On x86, a load instruction can have a prefix that treats one operand as the array base pointer, and another operand as the index. But the size of the array element is limited to 8 bytes so if your array elements are say 16 byte structs, you can’t use those instructions. As to ARM, I think it doesn’t have an array indexing instruction at all, just base + offset.