at compile time, not runtime.
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]A benefit is that you can then use 0 as a sentinel value; for instance if you have a find() routine that surely can fail, it can just return 0 instead of having e.g. -1 (which can introduce minor issues).
In my experience, though, I am so used to 0-based index that switching schemes can cause stupid off-by-one bugs. I guess that's the main reason behind complains about Lua. It's not that "natural" arrays are thought of as bad, but mixing both schemes (often C an Lua) is error-prone.
Yes it is. It was evaluated, carefully weighted and discarded, as it was not worth it.
You'd still have the odd subtract here or there, but for many use patterns you could probably ignore the overhead.
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.
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.
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;
// 11 arrays are created here
int foo[10][10];
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
year(x) = (x - 1)%100 + 1
century(x) = floor((x - 1)/100) + 1
year(x) = x%100
century(x) = floor(x/100)
or how would you count, say, 3 Apples? or three legionaries?
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"),
}
`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!).
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
112I don't think it's inherently more natural to start from 1, just conventional. Disregarding history/convention, I think it would be more natural to use the lowest available natural number.
Back in Roman times, the lowest natural number that people were aware of was "1", so obviously they started counting from that number.
Our understanding of and use of mathematics has evolved since then, and accordingly there are fields such as computer science and combinatorics where there are clear advantages to starting from the smallest number (zero). In virtually all other cases, the reason "1" seems more natural is because that's the way it's been done historically.
It seems that when labelling those apples using a 1-based count, the logic is basically: each apple is identified by the number of apples that precede it, plus 1. The reason for the "plus 1" is that that was your starting number, but it could have easily been 2 or 3. If you instead start from 0, you can omit the "plus X" logic, just as I omitted the "+ 1" and "- 1" logic in my year/century formulae when moving from 1-based to 0-based counting.
> It seems that when labeling ... number ... that precede it, plus one.
I don't think so. It's the number that you have counted once you've counted that one.
It was introduced into western mathematics through Fibonacci in the 1200s at the same time that Hindu-Arabic numerals were adopted, which use "0" as a placeholder (compare this to earlier Greek numerals which work similarly to the system we use today but without placeholders and using different sets of symbols for the different places—and of course no way of representing zero).
I agree with you the subtraction instruction is not exorbitant, especially considering malloc is much more expensive and always has been.
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.
No, you misunderstood. You subtract one from the pointer at allocation time. You don’t add an instruction every time you access.
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! ;)
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.
If 1-based indexing was used in assembly, then "mov 1(%ebx),%eax" would be the equivalent of "mov (%ebx),%eax".