7 ms·

The "language" that has a 0-based indexing scheme is assembly. An HLL with 1-based counting that compiles to assembly will introduce additional computational ov

The "language" that has a 0-based indexing scheme is assembly. An HLL with 1-based counting that compiles to assembly will introduce additional computational overhead for the translation of the index. If 1-based indexing was used in assembly, then "mov 1(%ebx),%eax" would be the equivalent of "mov (%ebx),%eax".

jiveturkey 4y ago
> 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.
        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).
unilynx 4y ago
Not sure if assembly/machine code is that relevant. If one based indexing was more prevalent, the LEA instruction on x86 would just subtract one during execution
- cryptonector 4y ago
  u/blutomcat's point clearly (I think) was that instruction sets didn't do what you suggest, so zero-based index is (was and still is) what you'd do if you wrote in assembly (which was not uncommon!), and on any given platform, assembly was the main language 50-60 years ago. It follows that it's easier to carry that over to higher level programming languages. Whether that's what actually happened in the cases of HLLs that adopted zero-based arrays or not, I don't know. But today, to me, zero-based array indexing feels very natural, and the idea that zero-based arrays being simpler in assembly carrying over to HLLs seems at the very least plausible.
- dboreham 4y ago
  "just subtract one" would take a long time 50-60 years ago.
  - Jtsummers 4y ago
    If you did this, you'd subtract one once at array creation. Or subtract whatever the offset is (really, you'd subtract 1 * data type size). Under the hood, using C syntax instead of assembly: int foo[n]; // what the user wrote // what happens behind the scenes, after a fashion int* foo = malloc(n * sizeof(int); // or sp - n * sizeof(int) if stack allocated; subtraction since stacks usually grow "down" foo = foo - 1; All references into foo will now work just fine so long as they are within the [1,n] range (same issues as with 0-based there since C doesn't carry size information for checking array bounds access). This adds one extra instruction per allocation (which includes allocation on the stack) for all non-0 offsets, but then all access will have the same cost whether 0-based, 1-based, or arbitrary-based. That's a non-zero cost, but it's not exorbitant since you'll be accessing much more often than allocating (and if it's reversed, something weird is happening).
lucas_membrane 4y ago
> An HLL with 1-based counting that compiles to assembly will introduce additional computational overhead for the translation of the index Not necessarily so for translation of an index that is evaluated at run time. PL1 (back in the 1960's) compiled arrays into 'dope vectors'. Each array's dope vector included highest and lowest valid subscripts for each dimension of the array and the address where the element with all zero subscripts would be found, if it existed.

jiveturkey 4y ago

> 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.
        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).

unilynx 4y ago

Not sure if assembly/machine code is that relevant. If one based indexing was more prevalent, the LEA instruction on x86 would just subtract one during execution

cryptonector 4y ago
u/blutomcat's point clearly (I think) was that instruction sets didn't do what you suggest, so zero-based index is (was and still is) what you'd do if you wrote in assembly (which was not uncommon!), and on any given platform, assembly was the main language 50-60 years ago. It follows that it's easier to carry that over to higher level programming languages. Whether that's what actually happened in the cases of HLLs that adopted zero-based arrays or not, I don't know. But today, to me, zero-based array indexing feels very natural, and the idea that zero-based arrays being simpler in assembly carrying over to HLLs seems at the very least plausible.
dboreham 4y ago
"just subtract one" would take a long time 50-60 years ago.
- Jtsummers 4y ago
  If you did this, you'd subtract one once at array creation. Or subtract whatever the offset is (really, you'd subtract 1 * data type size). Under the hood, using C syntax instead of assembly: int foo[n]; // what the user wrote // what happens behind the scenes, after a fashion int* foo = malloc(n * sizeof(int); // or sp - n * sizeof(int) if stack allocated; subtraction since stacks usually grow "down" foo = foo - 1; All references into foo will now work just fine so long as they are within the [1,n] range (same issues as with 0-based there since C doesn't carry size information for checking array bounds access). This adds one extra instruction per allocation (which includes allocation on the stack) for all non-0 offsets, but then all access will have the same cost whether 0-based, 1-based, or arbitrary-based. That's a non-zero cost, but it's not exorbitant since you'll be accessing much more often than allocating (and if it's reversed, something weird is happening).

lucas_membrane 4y ago

> An HLL with 1-based counting that compiles to assembly will introduce additional computational overhead for the translation of the index Not necessarily so for translation of an index that is evaluated at run time. PL1 (back in the 1960's) compiled arrays into 'dope vectors'. Each array's dope vector included highest and lowest valid subscripts for each dimension of the array and the address where the element with all zero subscripts would be found, if it existed.