5 ms·

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 understa

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
      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.)
      - xxs 6y ago
        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.
adwn 6y ago
> 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.
- xxs 6y ago
  >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.
- 3JPLW 6y ago
  > 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.
- nvader 6y ago
  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 ]
- professoretc 6y ago
  > 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.
xxs 6y ago
>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.

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
    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.)
    - xxs 6y ago
      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.

adwn 6y ago

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

xxs 6y ago
>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.
3JPLW 6y ago
> 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.
nvader 6y ago
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 ]
professoretc 6y ago
> 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.

xxs 6y ago

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