6 ms·

Here's two arguments arguments in favor of 0-based 'indexing' (or offsets), that aren't just "because that's how it's done": 1. It is faster. Due to how memory

Here's two arguments arguments in favor of 0-based 'indexing' (or offsets), that aren't just "because that's how it's done": 1. It is faster. Due to how memory works, 1-based languages need to subtract 1 internally every time you access an array[1]. 2. It works mathematically better with some of the most common operations on array offsets, like modulo and division into round/ceil/floor. You'll be peppering your code with +1 or -1 around those a lot if you use 1-based indexing. [1]: This is lua, for instance: https://github.com/lua/lua/blob/master/ltable.c#L702 https://github.com/lua/lua/blob/master/ltable.c#L702

anand-bala 6y ago
(On the phone so forgive the possible typos) I am not sure (1) is a very convincing argument. The subtraction of 1 internally is not necessarily gonna be there once the code gets compiled. I will personally concede with you on (2), but it's still not very convincing considering that Fortran (a 1-index language) is still (arguably) the most popular language for linear algebra. Personally, I feel "The Index Wars" are the same as the "Text Editor Wars": a matter for personal opinion.
- chmod775 6y ago
  >I am not sure (1) is a very convincing argument. The subtraction of 1 internally is not necessarily gonna be there once the code gets compiled. Theoretically one can optimize it - though only when one can statically infer the index and the compiler decides to inline the array access function. If you can't do that, the best you can hope for is a fast CPU instruction like LEA or something. In theory one could make a lot of things fast, in practice they rarely are, and it's always better to avoid problems now than to pray later.
  - stabbles 6y ago
    Oh come one now, don't be silly. Think about vectorization and loop unrolling. It _always_ does a memory load with an offset as a single CPU instruction. As an example a 4 times unrolled sum of doubles on AVX looks like this: L64: vaddpd ymm0, ymm0, ymmword ptr [rcx + 8*rsi] vaddpd ymm1, ymm1, ymmword ptr [rcx + 8*rsi + 32] vaddpd ymm2, ymm2, ymmword ptr [rcx + 8*rsi + 64] vaddpd ymm3, ymm3, ymmword ptr [rcx + 8*rsi + 96] add rsi, 16 cmp rdx, rsi jne L64 The `rcx + 8*rsi + 32` stuff is offsets the compiler generates. Don't even think about worrying about -1 here...
    - chmod775 6y ago
      > Oh come one now, don't be silly. Don't be snarky. I mentioned it's theoretically possible and outlined the specific conditions for optimizations to happen. But I also mentioned that in reality various things often prevent compilers (assuming it's a compiled language, and not interpreted, like that LUA implementation) from applying such optimizations: - you're programming against an API or are compiling an API (i.e. non-static functions). - you have time-constraints for emitting optimized code, like most JITs - you can't afford any deep analysis that would enable such optimizations, you're mostly pattern-matching for lower hanging fruits. Since pictures say more than a thousand words, here's the actual disassembly of that lua function I linked earlier, as shipped by my Linux distribution: https://i.imgur.com/DnqVC8E.png https://i.imgur.com/DnqVC8E.png The green stuff is the "fast path". For 0-based indexing you would completely drop the first LEA and replace those last MOV/SHL/LEA with a (faster?) MOV r,r/SHL/ADD r,m - which is what GCC is likely to generate. So that's Lua (one implementation at least) in practice. No compiler magic making arrays fast here. LuaJIT (from my current reading) goes the different route of just pretending the first array element doesn't exist, meaning that in memory they have an element '0', but they simply don't use it. This trades some memory for speed. From lj_tab.c: ** The array size is non-inclusive. E.g. asize=128 creates array slots ** for 0..127, but not for 128. If you need slots 1..128, pass asize=129 ** (slot 0 is wasted in this case). Personally I quite like this approach. A lot better than hoping compilers will magically fix everything and quite hard to argue with, considering LuaJIT's performance. Though it would be a ludicrous design for a lower-level language.
IlliOnato 6y ago
Your (1) only affects compilation time, and even this is assuming a particular implementation of arrays (which is not a given). Your (2) I don't fully understand. Why would you need to use "modulo and division into round/ceil/floor" on array offsets? How often you do it? For what it's worth, I've written a _ton_ of code in an obscure language called Omnimark, which is 1-based. Much of that code involved using arrays. I've just grepped through a large Omnimark codebase I helped to write, and no, it is _not_ peppered with "+1" or "-1".
- IncRnd 6y ago
  1) It also affects runtime, when addresses need to have a subtraction, and maybe a multiplication, in the offset calculation. 2) You may need this often in certain network or protocol code, for example.
- foxrob92 6y ago
  > Why would you need to use "modulo and division into round/ceil/floor" on array offsets? How often you do it? Circular buffers?
  - tijsvd 6y ago
    Nah, it doesn't matter if you do (prev + 1) % len, or (prev % len) + 1. Hash tables matter more though.
    - xxs 6y ago
      >% len, Modulus (division) is slow and the length should be pow2 and the operation "& (len-1)". If you do %len, you have far greater issues. I have pretty extensive experience writing hashmap/cyclic buffers and the like. If you have auto-grow structs (and you almost always want that), you want pow2 length arrays. e.g. addLast(e) elements[tail++] = e; tail &= elements.length - 1; if (tail == head) doubleCapacity(); }
      - naniwaduni 6y ago
jbverschoor 6y ago
Only one reason exists these days: it prevents bugs because people mix up order, infecting, counting, arrays semantics, implementation, pointer arithmetic
elcomet 6y ago
For 2), in Julia, there is "mod1" function which acts as modulo, with 1 being the smallest value instead of zero. It doesn't really make sense mathematically, but is very useful for looping over circular arrays.
- im3w1l 6y ago
  EDIT: This is actually wrong, because it doesn't correctly describe how negative arguments are handled. It can be phrased mathematically like this: Consider the equivalence relation a ≡ b (mod n). It has n equivalence classes. Use 1..n as the canonical elements for the classes. mod1 takes a number, finds its equivalence class and returns the canonical element.
- user-the-name 6y ago
  Does it have it for any other reason than to work around the limitations of 1-based indexing?
  - naniwaduni 6y ago
    12-hour timekeeping, perhaps ;-)
segfaultbuserr 6y ago
> It works mathematically better with some of the most common operations on array offsets The problem is that for every formula or calculation best suited for 1-based indexing, there is another which is better implemented using 0-based indexing. Regardless of which indexing mode you are using, peppering your code with +1 or -1 is eventually inevitable. It's why I think the choice is a matter of preference and has little to do with technical reasons. Overall I still prefer 0-based indexing - a few bytes of RAM is cheap nowadays, when the calculation can be simplified using 1-based indexing, deliberately not using [0] and pretending that the array begins at [1] is often an acceptable option (the trick was originally invented for porting Fortran code...)
- user-the-name 6y ago
  Not convinced that is the case. I do not pepper my code with +1 and -1 while using 0-based indexing. I can think of a lot of cases where I would do it for 1-based indexing, but very few for 0-based indexing. If you want to make the claim that there similarly many, you're going to have to come up with some substantial examples.
  - tsegers 6y ago
    The -1 with 0-based indexing occurs very frequently when using the amount of elements in some collection to derive boundaries of the indexes, which will range from 0 up to and including n-1. Grepping for "- 1" in my code folder returns mostly expressions that look like 'length/len/size - 1'.
    - user-the-name 6y ago
      This can happen, but it is fairly rare, especially if you favour handling ranges as either (start, length) tuples, or as half-open intervals, with the end index being one past the highest index. This representation simplifies many things, many of them unrelated to 0- or 1-based indexing.
      - tsegers 6y ago
nyanpasu64 6y ago
A while back, I wrote a blog post elaborating on point 2 and inclusive/exclusive indexing and slicing, but it didn't get any traction on HN: https://nyanpasu64.github.io/blog/the-gridline-mental-model-of-indexing-and-slicing/ https://nyanpasu64.github.io/blog/the-gridline-mental-model-...
cbolton 6y ago
Regarding the mathematical advantage: it depends on the subfield, but I think 1-based numbering is more common in mathematical notation and algorithms (linear algebra being a prominent example). Regarding performance: some mentioned that the 1 offset can often be optimized away by the compiler. But even when this is not possible, common CPU architectures include instructions that can apply the offset at no extra cost, see https://stackoverflow.com/questions/28032685/is-there-a-performance-penalty-for-one-based-array-indexing https://stackoverflow.com/questions/28032685/is-there-a-perf... , so 1-based indexing is just as fast.

anand-bala 6y ago

(On the phone so forgive the possible typos) I am not sure (1) is a very convincing argument. The subtraction of 1 internally is not necessarily gonna be there once the code gets compiled. I will personally concede with you on (2), but it's still not very convincing considering that Fortran (a 1-index language) is still (arguably) the most popular language for linear algebra. Personally, I feel "The Index Wars" are the same as the "Text Editor Wars": a matter for personal opinion.

chmod775 6y ago
>I am not sure (1) is a very convincing argument. The subtraction of 1 internally is not necessarily gonna be there once the code gets compiled. Theoretically one can optimize it - though only when one can statically infer the index and the compiler decides to inline the array access function. If you can't do that, the best you can hope for is a fast CPU instruction like LEA or something. In theory one could make a lot of things fast, in practice they rarely are, and it's always better to avoid problems now than to pray later.
- stabbles 6y ago
  Oh come one now, don't be silly. Think about vectorization and loop unrolling. It _always_ does a memory load with an offset as a single CPU instruction. As an example a 4 times unrolled sum of doubles on AVX looks like this: L64: vaddpd ymm0, ymm0, ymmword ptr [rcx + 8*rsi] vaddpd ymm1, ymm1, ymmword ptr [rcx + 8*rsi + 32] vaddpd ymm2, ymm2, ymmword ptr [rcx + 8*rsi + 64] vaddpd ymm3, ymm3, ymmword ptr [rcx + 8*rsi + 96] add rsi, 16 cmp rdx, rsi jne L64 The `rcx + 8*rsi + 32` stuff is offsets the compiler generates. Don't even think about worrying about -1 here...
  - chmod775 6y ago
    > Oh come one now, don't be silly. Don't be snarky. I mentioned it's theoretically possible and outlined the specific conditions for optimizations to happen. But I also mentioned that in reality various things often prevent compilers (assuming it's a compiled language, and not interpreted, like that LUA implementation) from applying such optimizations: - you're programming against an API or are compiling an API (i.e. non-static functions). - you have time-constraints for emitting optimized code, like most JITs - you can't afford any deep analysis that would enable such optimizations, you're mostly pattern-matching for lower hanging fruits. Since pictures say more than a thousand words, here's the actual disassembly of that lua function I linked earlier, as shipped by my Linux distribution: https://i.imgur.com/DnqVC8E.png https://i.imgur.com/DnqVC8E.png The green stuff is the "fast path". For 0-based indexing you would completely drop the first LEA and replace those last MOV/SHL/LEA with a (faster?) MOV r,r/SHL/ADD r,m - which is what GCC is likely to generate. So that's Lua (one implementation at least) in practice. No compiler magic making arrays fast here. LuaJIT (from my current reading) goes the different route of just pretending the first array element doesn't exist, meaning that in memory they have an element '0', but they simply don't use it. This trades some memory for speed. From lj_tab.c: ** The array size is non-inclusive. E.g. asize=128 creates array slots ** for 0..127, but not for 128. If you need slots 1..128, pass asize=129 ** (slot 0 is wasted in this case). Personally I quite like this approach. A lot better than hoping compilers will magically fix everything and quite hard to argue with, considering LuaJIT's performance. Though it would be a ludicrous design for a lower-level language.

IlliOnato 6y ago

Your (1) only affects compilation time, and even this is assuming a particular implementation of arrays (which is not a given). Your (2) I don't fully understand. Why would you need to use "modulo and division into round/ceil/floor" on array offsets? How often you do it? For what it's worth, I've written a _ton_ of code in an obscure language called Omnimark, which is 1-based. Much of that code involved using arrays. I've just grepped through a large Omnimark codebase I helped to write, and no, it is _not_ peppered with "+1" or "-1".

IncRnd 6y ago
1) It also affects runtime, when addresses need to have a subtraction, and maybe a multiplication, in the offset calculation. 2) You may need this often in certain network or protocol code, for example.
foxrob92 6y ago
> Why would you need to use "modulo and division into round/ceil/floor" on array offsets? How often you do it? Circular buffers?
- tijsvd 6y ago
  Nah, it doesn't matter if you do (prev + 1) % len, or (prev % len) + 1. Hash tables matter more though.
  - xxs 6y ago
    >% len, Modulus (division) is slow and the length should be pow2 and the operation "& (len-1)". If you do %len, you have far greater issues. I have pretty extensive experience writing hashmap/cyclic buffers and the like. If you have auto-grow structs (and you almost always want that), you want pow2 length arrays. e.g. addLast(e) elements[tail++] = e; tail &= elements.length - 1; if (tail == head) doubleCapacity(); }
    - naniwaduni 6y ago

jbverschoor 6y ago

Only one reason exists these days: it prevents bugs because people mix up order, infecting, counting, arrays semantics, implementation, pointer arithmetic

elcomet 6y ago

For 2), in Julia, there is "mod1" function which acts as modulo, with 1 being the smallest value instead of zero. It doesn't really make sense mathematically, but is very useful for looping over circular arrays.

im3w1l 6y ago
EDIT: This is actually wrong, because it doesn't correctly describe how negative arguments are handled. It can be phrased mathematically like this: Consider the equivalence relation a ≡ b (mod n). It has n equivalence classes. Use 1..n as the canonical elements for the classes. mod1 takes a number, finds its equivalence class and returns the canonical element.
user-the-name 6y ago
Does it have it for any other reason than to work around the limitations of 1-based indexing?
- naniwaduni 6y ago
  12-hour timekeeping, perhaps ;-)

segfaultbuserr 6y ago

> It works mathematically better with some of the most common operations on array offsets The problem is that for every formula or calculation best suited for 1-based indexing, there is another which is better implemented using 0-based indexing. Regardless of which indexing mode you are using, peppering your code with +1 or -1 is eventually inevitable. It's why I think the choice is a matter of preference and has little to do with technical reasons. Overall I still prefer 0-based indexing - a few bytes of RAM is cheap nowadays, when the calculation can be simplified using 1-based indexing, deliberately not using [0] and pretending that the array begins at [1] is often an acceptable option (the trick was originally invented for porting Fortran code...)

user-the-name 6y ago
Not convinced that is the case. I do not pepper my code with +1 and -1 while using 0-based indexing. I can think of a lot of cases where I would do it for 1-based indexing, but very few for 0-based indexing. If you want to make the claim that there similarly many, you're going to have to come up with some substantial examples.
- tsegers 6y ago
  The -1 with 0-based indexing occurs very frequently when using the amount of elements in some collection to derive boundaries of the indexes, which will range from 0 up to and including n-1. Grepping for "- 1" in my code folder returns mostly expressions that look like 'length/len/size - 1'.
  - user-the-name 6y ago
    This can happen, but it is fairly rare, especially if you favour handling ranges as either (start, length) tuples, or as half-open intervals, with the end index being one past the highest index. This representation simplifies many things, many of them unrelated to 0- or 1-based indexing.
    - tsegers 6y ago

nyanpasu64 6y ago

A while back, I wrote a blog post elaborating on point 2 and inclusive/exclusive indexing and slicing, but it didn't get any traction on HN: https://nyanpasu64.github.io/blog/the-gridline-mental-model-of-indexing-and-slicing/ https://nyanpasu64.github.io/blog/the-gridline-mental-model-...

cbolton 6y ago

Regarding the mathematical advantage: it depends on the subfield, but I think 1-based numbering is more common in mathematical notation and algorithms (linear algebra being a prominent example). Regarding performance: some mentioned that the 1 offset can often be optimized away by the compiler. But even when this is not possible, common CPU architectures include instructions that can apply the offset at no extra cost, see https://stackoverflow.com/questions/28032685/is-there-a-performance-penalty-for-one-based-array-indexing https://stackoverflow.com/questions/28032685/is-there-a-perf... , so 1-based indexing is just as fast.