5 ms·

> additional computational overhead at compile time, not runtime.

saalweachter 4y ago
For constant addressing; for arr[i] = 2, you'll still need to subtract 1 from i with 1-based addressing when converting to machine instructions.
- vukgr 4y ago
  Can't say I've really thought this through, but couldn't you just subtract 1 (*sizeof(X)) from the arr address?
  - saalweachter 4y ago
    Hmm, maybe? You'd still have the odd subtract here or there, but for many use patterns you could probably ignore the overhead.
  - tremon 4y ago
    What would memset(arr, 0, sizeof(arr)) do in that case? I can see myriad problems with having arr itself point outside the memory range allocated to arr[min..max].
- deleted 4y ago
  [deleted]
- nousermane 4y ago
  > for arr[i] = 2, you'll still need to subtract 1 You can, but don't need to. Just have compiler store array pointer constant as (arr-1) instead of arr, et voila, zero runtime overhead. Or, for modern(-ish) ISAs, often you can add/substract a small constant at runtime, with no extra cycles taken. For example, for x86_64: # rbp contains "true" pointer to arr # rax contains 1-based array index mov rax, QWORD PTR [rbp-8+rax*8]
  - shpx 4y ago
    What if the variable is used for array indexing and something else, like displayed to the user?
  - murderfs 4y ago
    It's basically only x86 among modern ISAs that lets you do base + literal + register * literal, aarch64 only gives you base + register shifted by a literal, and I believe RISC-V is similar: https://gcc.godbolt.org/z/dz768768z https://gcc.godbolt.org/z/dz768768z
    - snvzz 4y ago
      >and I believe RISC-V is similar Yes it is. It was evaluated, carefully weighted and discarded, as it was not worth it.
    - kaba0 4y ago
      But it will still execute with likely no extra time at all due to OOE and how fast arithmetics are.
      - NohatCoder 4y ago
        If it is not on the hot path, it is likely free, but not guaranteed. If it is on the hot path then it is wasting a whole cycle. And of course in highly ALU-dependent code it is another instruction, so a fraction of a clock.
        kaba0 4y ago
        What do you mean it wastes a whole cycle? It may indeed have worse performance due to blowing the instruction cache, but I don’t see why would out-of-order execution be slower on the hot path - I doubt there would be too many hot paths without any dependence on memory fetches outside specific benchmarks - the memory loads will take significantly more time even if they hit cache.
      - murderfs 4y ago
- joaonmatos 4y ago
  For most cases you could get away with some index transformation logic in the compiler (but probably your language would need special types for indices, so I do agree with you that it is not worth the trouble).

For constant addressing; for arr[i] = 2, you'll still need to subtract 1 from i with 1-based addressing when converting to machine instructions.

vukgr 4y ago
Can't say I've really thought this through, but couldn't you just subtract 1 (*sizeof(X)) from the arr address?
- saalweachter 4y ago
  Hmm, maybe? You'd still have the odd subtract here or there, but for many use patterns you could probably ignore the overhead.
- tremon 4y ago
  What would memset(arr, 0, sizeof(arr)) do in that case? I can see myriad problems with having arr itself point outside the memory range allocated to arr[min..max].
deleted 4y ago
[deleted]
nousermane 4y ago
> for arr[i] = 2, you'll still need to subtract 1 You can, but don't need to. Just have compiler store array pointer constant as (arr-1) instead of arr, et voila, zero runtime overhead. Or, for modern(-ish) ISAs, often you can add/substract a small constant at runtime, with no extra cycles taken. For example, for x86_64: # rbp contains "true" pointer to arr # rax contains 1-based array index mov rax, QWORD PTR [rbp-8+rax*8]
- shpx 4y ago
  What if the variable is used for array indexing and something else, like displayed to the user?
- murderfs 4y ago
  It's basically only x86 among modern ISAs that lets you do base + literal + register * literal, aarch64 only gives you base + register shifted by a literal, and I believe RISC-V is similar: https://gcc.godbolt.org/z/dz768768z https://gcc.godbolt.org/z/dz768768z
  - snvzz 4y ago
    >and I believe RISC-V is similar Yes it is. It was evaluated, carefully weighted and discarded, as it was not worth it.
  - kaba0 4y ago
    But it will still execute with likely no extra time at all due to OOE and how fast arithmetics are.
    - NohatCoder 4y ago
      If it is not on the hot path, it is likely free, but not guaranteed. If it is on the hot path then it is wasting a whole cycle. And of course in highly ALU-dependent code it is another instruction, so a fraction of a clock.
      - kaba0 4y ago
        What do you mean it wastes a whole cycle? It may indeed have worse performance due to blowing the instruction cache, but I don’t see why would out-of-order execution be slower on the hot path - I doubt there would be too many hot paths without any dependence on memory fetches outside specific benchmarks - the memory loads will take significantly more time even if they hit cache.
    - murderfs 4y ago
joaonmatos 4y ago
For most cases you could get away with some index transformation logic in the compiler (but probably your language would need special types for indices, so I do agree with you that it is not worth the trouble).