3 ms·

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, usin

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
    Counter-example: You have to remove all desks from #20 to #30, how many desks are there? Oh, it's 11 desks, I see. This is because we used INCLUSIVE indexing, instead of semi-open interval. If we use semi-open intervals, we don't include the last item, so that we can write match index { 0..10 => println!("first ten"), 10..20 => println!("next ten"), _ => println!("something else"), } but this forces us to start our intervals at 0, otherwise we would have to write 1..11 which would be awkward
    - maxdamantus 4y ago
      Indeed. End exclusion is advantageous because we don't need to add or subtract 1 when constructing or interpreting ranges. Forgetting to add or subtract 1 is basically why off-by-one errors exist (and doing add rather than subtract or vice versa is probably why off-by-two errors exist). `a..(a+n)` is an n-length range, not an (n + 1)-length range (oh look, an "add 1" operation!). And an empty range is denoted by `a..a`, not `a..(a-1)` (oh look, a "subtract 1" operation!).
    - gernb 4y ago
      doesn't swift use inclusive indexing? 1...10 includes 10
      - maxdamantus 4y ago
        Haven't used Swift, but looking at the documentation, it seems to support `...` for end-inclusive and `..<` for end-exclusive. Looking at the Swift standard library, end-exclusive ranges seem to be far more commonly used: ~/build/swift$ git grep -e '\.\.< *[a-zA-Z0-9_(]' --and --not -e '^ *//' -- stdlib/\*.swift | wc -l 599 ~/build/swift$ git grep -e '\.\.\. *[a-zA-Z0-9_(]' --and --not -e '^ *//' -- stdlib/\*.swift | wc -l 112

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
  Counter-example: You have to remove all desks from #20 to #30, how many desks are there? Oh, it's 11 desks, I see. This is because we used INCLUSIVE indexing, instead of semi-open interval. If we use semi-open intervals, we don't include the last item, so that we can write match index { 0..10 => println!("first ten"), 10..20 => println!("next ten"), _ => println!("something else"), } but this forces us to start our intervals at 0, otherwise we would have to write 1..11 which would be awkward
  - maxdamantus 4y ago
    Indeed. End exclusion is advantageous because we don't need to add or subtract 1 when constructing or interpreting ranges. Forgetting to add or subtract 1 is basically why off-by-one errors exist (and doing add rather than subtract or vice versa is probably why off-by-two errors exist). `a..(a+n)` is an n-length range, not an (n + 1)-length range (oh look, an "add 1" operation!). And an empty range is denoted by `a..a`, not `a..(a-1)` (oh look, a "subtract 1" operation!).
  - gernb 4y ago
    doesn't swift use inclusive indexing? 1...10 includes 10
    - maxdamantus 4y ago
      Haven't used Swift, but looking at the documentation, it seems to support `...` for end-inclusive and `..<` for end-exclusive. Looking at the Swift standard library, end-exclusive ranges seem to be far more commonly used: ~/build/swift$ git grep -e '\.\.< *[a-zA-Z0-9_(]' --and --not -e '^ *//' -- stdlib/\*.swift | wc -l 599 ~/build/swift$ git grep -e '\.\.\. *[a-zA-Z0-9_(]' --and --not -e '^ *//' -- stdlib/\*.swift | wc -l 112