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.

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.

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

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

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

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

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.

for(i=N-1; i>=0; i--)

The alternative is to use the so-called goes-to operator: for (i=N; i --> 0;). But this actually relies on the postincrement semantics, which is a huge wart.

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

No, it mostly affects execution time. Whether the effect is meaningful, however, depends on various factors.

> [...] and even this is assuming a particular implementation of arrays (which is not a given).

Eventually, all arrays boil down to pointer+offset memory accesses. Well, if your programming language internally implements "arrays" as hashmaps, then you've already lost performance-wise, of course.

> Why would you need to use "modulo and division into round/ceil/floor" on array offsets?

Whenever you're working with 2D/3D data in manually managed memory.

> How often you do it?

When you're writing web services? Probably not so much. When you're doing image manipulation or 3D graphics? All the time.

Citation needed. Yes, the -1 appears in the source code. It might even appear in the intermediate representation. It'll even show up in the assembly for multidimensional arrays (but it'll all get folded into a single `mov` assembly for vectors).

But I dare you to actually demonstrate a performance difference. Compared to a memory access, a `dec` is free.

That's what I was thinking, too, but most of the time (even if the index is not static) the -1 can be eliminated by just modifying the address at which the array is assumed to start. That is,

    arr[x]

    (arr - 1) + x

No, that's almost never the case – only when accessing a static array. Typically, that restricts it to static look-up tables and very simple embedded systems.

I don't want to spoil it, but the following picture of a how they stored a 3x3 tic-tac-toe board is a hint:

  [ null, null, null, null, null, null,

  null, X, 0, X, null, null,

  null, null, O, X, X, null, 

  null, null, null, X, 0, 0 ]

I bet it's done a lot as a lot of data structures are implemented vid pow2 length arrays. It's just the people who write them are unaware.

Circular buffers?

Hash tables matter more though.

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();
  }

  int h = ( -(--head) >>> 31) ^ 1;//if head was equal to 1 (and only 1), h = 1, otherwise zero    
  head += h * len; //or shift left, if there is log2 len available; still, mul is a fast operation, unlike div

Every =single= hash map worth its salt should be power of 2 length backed array. And the hashing function (for the idx of the array) is not the division (that's slow and cannot be parallelized in the cpu) but a simple bitwise AND.

In short offset 1 doesn't map well to hardware.

  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.

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-perf... , so 1-based indexing is just as fast.

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.