Hacker News Reader

Comment by IlliOnato | Hacker News Reader

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

View on HN

> Your (1) only affects compilation time, [...]

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.

> No, it mostly affects execution 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.

> No, it mostly affects execution time.

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]

compiles into an access at address

    (arr - 1) + x

Since the address of arr is statically known, arr - 1 is, too, and the address of "one before the first element" will be what's written as the base for the memory access.

> Since the address of arr is statically known [...]

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.

At some point I would like to write up a story about this team in my University Object-Oriented Programming class who decided to use 1-based 1ndexes in Java while making a 2-D array for a board game.

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 ]

>When you're writing web services? Probably not so much.

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.

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

Circular buffers?

Nah, it doesn't matter if you do (prev + 1) % len, or (prev % len) + 1.

Hash tables matter more though.

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

This is entirely orthogonal to whether you do "prev+1 & len-1" or "(prev & len-1) + 1". (In fact, the latter gives a more natural construction if you fill downward.)

Adding/advancing is indeed easier. What about going backwards (insert before head or remove from tail), i.e when 0, then length. One way to do it is something like that, assume 2 compliment and there is negative shift left available. Not straightforward:

  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

Of course, it can implemented via branching but that would be a major downside for 1-based idx.

>on array offsets? How often you do it?

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.

Reply on news.ycombinator.com