9 ms·

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 executio

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).
  - dahart 4y ago
    The well known “Numerical Recipes in C 2nd ed.” talks about how the first edition promoted exactly this - offset the pointer after allocation and you can use any indexing origin you want. And they promoted 1-indexing and wrote all the algorithms as such, before switching everything to 0-indexing for the 2nd edition. I agree with you the subtraction instruction is not exorbitant, especially considering malloc is much more expensive and always has been.
  - maxdamantus 4y ago
    Since as you say, C doesn't carry size information, you would actually need to do it each time a pointer is created from an object. In C you can have arrays of arrays (not pointers) or arrays in structs, where there is no pointer on creation: // 11 arrays are created here int foo[10][10]; It doesn't make sense to create pointers for the 10 inner arrays, so the subtraction would presumably happen when referring to each inner array: int *z = foo[x]; // (char *)foo_sub_1 + (sizeof *foo)*x - (sizeof **foo) foo[x][y]; // (char *)foo_sub_1 + (sizeof *foo)*x - (sizeof **foo) + (sizeof **foo)*y In any case, this is more work, both for the computer and for the human. It's analogous to trying to figure out "which year of which century is X in?" (2022 is the 22nd year of the 21st century): year(x) = (x - 1)%100 + 1 century(x) = floor((x - 1)/100) + 1 The above formulae work for the 1-based convention, because they do the necessary 1 subtraction/addition in the right places. If we instead counted from 0, things would be a lot simpler (2021 would be year 21 of century 20): year(x) = x%100 century(x) = floor(x/100) Unfortunately, the Romans started counting years before anyone knew about 0. I think this is basically why we have a convention of counting from 1: 0 simply wasn't discovered until relatively recently in human history. Earlier number systems such as Greek/Roman numerals don't have a way of representing it.
    - froh 4y ago
      when I count apples I happily start with one. it's "natural" to label the first thing "1". or how would you count, say, 3 Apples? or three legionaries?
      - iopq 4y ago
- kitkat_new 4y ago
  would it? or would it be just a differently wired circuit?
  - fsckboy 4y ago
    the "differently wired circuit" would be an extra stage of logic computing a carry all the way from lsb to msb (an ALU outside the ALU?) and would contribute a fair bit of extra time. Easier to just use the ALU to do it, which is inserting an extra instruction, also a time waster.
    - codebje 4y ago
      If you're already doing base index addressing (eg, [SI + DI]) you're already using the ALU to compute your memory address, and it's not _that_ much extra wiring to have the ALU support either a constant power-of-two displacement or even a three-way addition; a constant displacement for a basic ripple adder is a XOR and an AND NOT, eg. The x86 family does three-way addition (and a shift) to support "[ESI] [EBX * scale + displacement]".
      - TuringTest 4y ago
        It's not just the extra wiring, but the extra time; each additional computation layer in an integrated circuit introduced delays that would made the operation noticeably slower.
  - codebje 4y ago
    Well, maybe, if the specific use case of 1-based arrays was all that got supported. It'd be a pretty huge waste of processor design space to do that, though: if an HLL wants to support n-based arrays for n != 0 it can just store the base pointer with the initial index offset already applied. Early 8-bit processors had a pretty poor set of addressing modes: you couldn't even expect [R1 + R2] let alone [R1 + R2 * scale + displacement], so random access into an array would be a multi-instruction task. By the time of the 80386 base scaled index addressing with displacement was in the CPU core, but it's not _free_ - there's an additional byte in the instruction encoding for the displacement, so even if the CPU computes the displacement with no additional clock cycles you'll have a latency cost for fetching the byte.
- dahart 4y ago
  Integer add/subtract never really took a long time. Slower than today’s sub-nanosecond, and it depends on the computer, but there were CPUs in the mid 1960s doing millions of instructions per second. They weren’t crazy slow, they were just crazy expensive.
  - dboreham 4y ago
    A million, perhaps. But you're talking about adding one instruction to every single data access. Plus your code bloats up with all those extra dec instructions. BCPL and C were created for departmental and lab computers like the pdp-9. Note, for example that the mighty 6502 succeeded in the market because its designers had heard from customers that the $100 price for the 6800 was too much, so they removed some instructions and addressing modes to get the die small enough that it could be sold for $20.
    - dahart 4y ago
      > But you're talking about adding one instruction to every single data access. No, you misunderstood. You subtract one from the pointer at allocation time. You don’t add an instruction every time you access.
      - topaz0 4y ago
        And even if it was an instruction for every access, memory access is much more expensive than and add (at least nowadays -- I don't know if that's always been true).
        dahart 4y ago
        Similarly I like to think about it as the add/subtract instruction is very small compared to malloc (and maybe could be included in a custom allocator for free). So the one extra instruction will always be somewhere between relatively minor to negligible and unnoticed. Yeah today memory access on a cache miss is really expensive. I think memory was normally running at a different clock rate than the CPU even 50-60 years ago, so has always been something where you can’t touch memory every instruction. The latency of a cache miss wasn’t nearly as bad in the past. When the data cache was invented, a main memory access was like 4 times slower than register access. Today, main memory access can be more than a hundred time slower, sometimes it can approach a thousand times slower, which is why we always have multi-level caches now. And memory latency is still getting worse. If someone figured out how to make memory faster without increasing the cost or the energy consumption, they’d be rich! ;)

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).
- dahart 4y ago
  The well known “Numerical Recipes in C 2nd ed.” talks about how the first edition promoted exactly this - offset the pointer after allocation and you can use any indexing origin you want. And they promoted 1-indexing and wrote all the algorithms as such, before switching everything to 0-indexing for the 2nd edition. I agree with you the subtraction instruction is not exorbitant, especially considering malloc is much more expensive and always has been.
- maxdamantus 4y ago
  Since as you say, C doesn't carry size information, you would actually need to do it each time a pointer is created from an object. In C you can have arrays of arrays (not pointers) or arrays in structs, where there is no pointer on creation: // 11 arrays are created here int foo[10][10]; It doesn't make sense to create pointers for the 10 inner arrays, so the subtraction would presumably happen when referring to each inner array: int *z = foo[x]; // (char *)foo_sub_1 + (sizeof *foo)*x - (sizeof **foo) foo[x][y]; // (char *)foo_sub_1 + (sizeof *foo)*x - (sizeof **foo) + (sizeof **foo)*y In any case, this is more work, both for the computer and for the human. It's analogous to trying to figure out "which year of which century is X in?" (2022 is the 22nd year of the 21st century): year(x) = (x - 1)%100 + 1 century(x) = floor((x - 1)/100) + 1 The above formulae work for the 1-based convention, because they do the necessary 1 subtraction/addition in the right places. If we instead counted from 0, things would be a lot simpler (2021 would be year 21 of century 20): year(x) = x%100 century(x) = floor(x/100) Unfortunately, the Romans started counting years before anyone knew about 0. I think this is basically why we have a convention of counting from 1: 0 simply wasn't discovered until relatively recently in human history. Earlier number systems such as Greek/Roman numerals don't have a way of representing it.
  - froh 4y ago
    when I count apples I happily start with one. it's "natural" to label the first thing "1". or how would you count, say, 3 Apples? or three legionaries?
    - iopq 4y ago
kitkat_new 4y ago
would it? or would it be just a differently wired circuit?
- fsckboy 4y ago
  the "differently wired circuit" would be an extra stage of logic computing a carry all the way from lsb to msb (an ALU outside the ALU?) and would contribute a fair bit of extra time. Easier to just use the ALU to do it, which is inserting an extra instruction, also a time waster.
  - codebje 4y ago
    If you're already doing base index addressing (eg, [SI + DI]) you're already using the ALU to compute your memory address, and it's not _that_ much extra wiring to have the ALU support either a constant power-of-two displacement or even a three-way addition; a constant displacement for a basic ripple adder is a XOR and an AND NOT, eg. The x86 family does three-way addition (and a shift) to support "[ESI] [EBX * scale + displacement]".
    - TuringTest 4y ago
      It's not just the extra wiring, but the extra time; each additional computation layer in an integrated circuit introduced delays that would made the operation noticeably slower.
- codebje 4y ago
  Well, maybe, if the specific use case of 1-based arrays was all that got supported. It'd be a pretty huge waste of processor design space to do that, though: if an HLL wants to support n-based arrays for n != 0 it can just store the base pointer with the initial index offset already applied. Early 8-bit processors had a pretty poor set of addressing modes: you couldn't even expect [R1 + R2] let alone [R1 + R2 * scale + displacement], so random access into an array would be a multi-instruction task. By the time of the 80386 base scaled index addressing with displacement was in the CPU core, but it's not _free_ - there's an additional byte in the instruction encoding for the displacement, so even if the CPU computes the displacement with no additional clock cycles you'll have a latency cost for fetching the byte.
dahart 4y ago
Integer add/subtract never really took a long time. Slower than today’s sub-nanosecond, and it depends on the computer, but there were CPUs in the mid 1960s doing millions of instructions per second. They weren’t crazy slow, they were just crazy expensive.
- dboreham 4y ago
  A million, perhaps. But you're talking about adding one instruction to every single data access. Plus your code bloats up with all those extra dec instructions. BCPL and C were created for departmental and lab computers like the pdp-9. Note, for example that the mighty 6502 succeeded in the market because its designers had heard from customers that the $100 price for the 6800 was too much, so they removed some instructions and addressing modes to get the die small enough that it could be sold for $20.
  - dahart 4y ago
    > But you're talking about adding one instruction to every single data access. No, you misunderstood. You subtract one from the pointer at allocation time. You don’t add an instruction every time you access.
    - topaz0 4y ago
      And even if it was an instruction for every access, memory access is much more expensive than and add (at least nowadays -- I don't know if that's always been true).
      - dahart 4y ago
        Similarly I like to think about it as the add/subtract instruction is very small compared to malloc (and maybe could be included in a custom allocator for free). So the one extra instruction will always be somewhere between relatively minor to negligible and unnoticed. Yeah today memory access on a cache miss is really expensive. I think memory was normally running at a different clock rate than the CPU even 50-60 years ago, so has always been something where you can’t touch memory every instruction. The latency of a cache miss wasn’t nearly as bad in the past. When the data cache was invented, a main memory access was like 4 times slower than register access. Today, main memory access can be more than a hundred time slower, sometimes it can approach a thousand times slower, which is why we always have multi-level caches now. And memory latency is still getting worse. If someone figured out how to make memory faster without increasing the cost or the energy consumption, they’d be rich! ;)