12 ms·

I don't quite understand the argument "0-based being easier for pointer arithmetic is nonsense because the language doesn't have pointers". Whether or not the

• Uptrenda 4y ago
  This is far easier and clearer than the entire article. Good stuff.
• bluetomcat 4y ago
  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?
  • 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.
• blueflow 4y ago
  That so people in this thread argue about the higher-level language (missing the point) shows that few people found access to the underlying machine code. Which is sad, because all code is still executed as machine instructions even when the developer does not see it or does not want to care.
  • Blikkentrekker 4y ago
    “machine code” isn't really the zero point that's special nowadays. The code the programmer wrote is compiled to something such as LLVM IR, LLVM IR is further compiled by LLVM to Assembly, this is further compiled by an assembler into machine code, and then the c.p.u. further compiles this to it's internal code as it executes it. “machine code” really is no more special in this chain of events than, say, LLVM IR.
    • blueflow 4y ago
      Machine code is special because its the only thing the CPU can actually execute.
      • clhodapp 4y ago
        ... then the c.p.u. further compiles this to it's internal code as it executes it. “machine code” really is no more special in this chain of events than, say, LLVM IR. I think this is the core point. Even though you are mechanically feeding machine code into the CPU, modern CPUs deeply transform your program before (or even while) running it, with potentially deep performance implications. With modern CPUs, the only choice we truly have is which compiler we trust to optimize our program.
        • iopq 4y ago
          Sometimes it executes it exactly how you think it will execute. But it's still slower because the "less optimized code" fit in its cache.
      • pjmlp 4y ago
• lupire 4y ago
  Implementation matters for performance, but even beyond that, the interface matters for users. 0-based offsets are convenient for users doing math on indexes. A pointer is just one kind of array-like indexing scheme. Good pointery languages will distinguish Address from Offset from Integer.
  • deleted 4y ago
    [deleted]
• vbezhenar 4y ago
  Waste 0th element or reuse it for something like length (hello, pascal strings). Another option is using base_address - element_size as your array value. Another option is using +element_size for all array accesses, assembly languages usually have this instruction. There’re many options to use 1-based indexing without sacrificing performance.
  • xg15 4y ago
    > assembly languages usually have this instruction Is that so? I wasn't aware of that.
    • vbezhenar 4y ago
      At least x86_64 can put something like `ptr[index * 4 + 4]` in one instruction (assuming that variable values are in registers). Not completely sure about ARM.
  • chinabot 4y ago
    newer pascal strings are #0 terminated, original pascal strings were 255 chars max with string[0] being the string length, they were also not Unicode friendly, newer pascal compilers still support this as the shortstring type. I use pascal style strings in my embedded C library I wrote in 1989 much more efficient on 8/16-bit systems
• turboponyy 4y ago
  Nats start at 0, end of discussion - it's only logical to index by the naturals.
  • JadeNB 4y ago
    > Nats start at 0, end of discussion - it's only logical to index by the naturals. Now you'll just bring out the people who start the naturals at 1.
    • ajg36 4y ago
      Starting the naturals at 1 is quite onerous.
      • colejohnson66 4y ago
        That’s why I compromise and start at -1
  • topaz0 4y ago
    If there were any justice in the world, they'd start at 2, as a handicap. They might even make it out of the bottom of the NL east if that was the case.
  • salty_biscuits 4y ago
    Where 0 is the cardinality of the empty set, i.e. some empty collection. Not a convincing argument.
    • JadeNB 4y ago
      > Where 0 is the cardinality of the empty set, i.e. some empty collection. Not a convincing argument. Why not? "Every cardinality, except of the empty set, is a natural number" isn't very convincing to me, if we're making cardinal-based arguments.
      • thaumasiotes 4y ago
• iib 4y ago
  0 for offsets, 1 for ordinals, that's usually the rule. Of course, both are conventions.
• Someone 4y ago
  > To get the address of a particular item, this layout naturally leads to the formula "base address + index * element size", with "index" being 0-based. If you want to expose other indexing schemes in your language, you'll have to add more logic to convert the user-visible index back to 0-based before you can obtain the address. The easy way to do that is by shifting the base address. In pseudo-C (I think that computing the b pointer is non-conforming, even if the code never tries to access b[0], but compilers can do this without problems): int a[100]; // array of 100 integers, zero-based int * b = a - 1; // array of 100 integers, one-based Things only get costly when you want to check array bounds or when you have multi-dimensional arrays. There also may be non-standard architectures where this kind of stuff isn’t possible.
  • twobitshifter 4y ago
    Should work 99.99999% of the time until someone tries to put an array at 0x000001 :)
    • alexcosan 4y ago
      I think, in theory, it would work regardless of the starting address. As long as you don't try to access the invalid address (which you wouldn't assuming that it's starting in the index 1, you would always be accessing the first valid address)
      • Someone 4y ago
        In theory, it’s not guaranteed to work at all. https://www.open-std.org/jtc1/sc22/wg14/www/docs/n2310.pdf#page80 https://www.open-std.org/jtc1/sc22/wg14/www/docs/n2310.pdf#p... (emphasis added): “In other words, if the expression P points to the i-th element of an array object, the expressions (P)+N (equivalently, N+(P)) and (P)-N (where N has the value n) point to, respectively, the i + n-th and i − n-th elements of the array object, _provided_they_exist” […] If both the pointer operand and the result point to elements of the same array object, or one past the last element of the array object, the evaluation shall not produce an overflow; _otherwise,_the_behavior_is_undefined. In this case, the minus-one-th element doesn’t exist, so the expression int * b = a - 1; triggers undefined behavior. I think some compilers use this in practice to produce faster code (that, often, will not do what the programmer expects it to do). Start reading at https://stackoverflow.com/questions/56360316/c-standard-regarding-pointer-arithmetic-outside-arrays https://stackoverflow.com/questions/56360316/c-standard-rega... if you’re sure they don’t. I expect that will change your opinion.
• matthewmcg 4y ago
  Amusing but probably irrelevant: the sailing yacht racing handicapping calculations mentioned are almost certainly under the Performance Handicap Racing Fleet (PHRF) system[0]. This system is "zero based" in its own way. A sailboat's performance is assessed and handicapped against a standard yacht with a zero rating. Your time to complete the race course is adjusted by your handicap to determine your final standing. This lets you race slower and faster types of boats in a "fair" way. [0] https://en.wikipedia.org/wiki/Performance_Handicap_Racing_Fleet#:~:text=7%20External%20links-,The%20Rating%20System,experience%20in%20handicapping%20similar%20boats https://en.wikipedia.org/wiki/Performance_Handicap_Racing_Fl....
• tuatoru 4y ago
  I would be fine with it all if 0-based was called "offset", with "index" reserved for 1-based. The element at offset 0 is the first element. Precision in naming is important.
  • dathinab 4y ago
    Defining index as the element wise offset is a precise well formed definition/name. It's also a definition commonly used in math, through not always. It depends a lot of the area of mathematics and even the cultural context. The only reason we sometimes feel 0-index is wrong IMHO is because the english language describes entities in a sequence as 1st, 2nd, 3rd etc. But I wouldn't be surprised if there is some human language somewhere which does it differently. Like something which roughly matches to english like "head, head+1, head+2, ...".
    • biztos 4y ago
      Which floor is the first floor in your building? Depends which country your building is in, and more! My apartment building is 1,2… but my mall is G,M,1,2… (same country different architects). For many years I lived in Europe where it’s usually G,1,2… (where G can also be E or Fsz or whatever) and when I was in the US I had to remember that 1 is G, though L,2,3… is also common. City people live with index ambiguity all the time and our brains manage just fine.
      • joaonmatos 4y ago
        Quick complement. Where I’m from (Portugal) we use the literal number 0 for the ground floor.
        • avereveard 4y ago
          In Europe is common for elevator to use zero for ground, even if language/culture has a specific name for it (piano terra/piano rialzato here)
        • fjkdlsjflkds 4y ago
• cm2187 4y ago
  I always assumed it started at zero otherwise you don’t use the full range of an unsigned integer and you can only have an odd number as your capacity (for whatever you use indexing for, not just RAM addressing).