2 ms·

A `Vec<Option<QueryInfo>>` would be unable to elid the bounds checks because the optimizer will never remember that the Vec was created with 65536 `None`s. `Box

A `Vec<Option<QueryInfo>>` would be unable to elid the bounds checks because the optimizer will never remember that the Vec was created with 65536 `None`s. `Box<[Option<QueryInfo>; 65536]>` would be better, though slightly annoying to create without accidentally creating an intermediate `[Option<QueryInfo>; 65536]` on the stack. (`vec![None; 65536].into_boxed_slice().try_into().expect("size is hard-coded to match")` is the easiest way in stable, AFAICT.)

tialaramex 5y ago
> the optimizer will never remember that the Vec was created with 65536 `None`s. I mean, probably today, but: 1. If you're worried about bounds checks you are likely not thinking about this problem in the right way. The bounds check is a couple of CPU instructions, a register compare and a conditional jump. The jump is never taken, the CPU will remember that if we do this often, and everything is in registers or instruction cache. Then, having discerned that we're in bounds, we do a memory dereference. Actually no modern CPU waits until then, the CPU has concluded that we probably aren't going to branch, so it will emit the memory read, and while that takes its sweet time the CPU can do the comparison, and as anticipated decide not to take the branch it never takes. So we're actually waiting on the memory read, which is why we care about not using a hash map, because the hash map might incur two memory reads if we get unlucky. But on the other hand, if the hash map was small enough to fit in cache at least it arrives before the CPU goes into a coma because of how slow memory reads are to main memory. 2. Optimizers get smarter. It's clearly not impossible to do the analysis and decide this check isn't necessary. So I think that means you shouldn't rule it out.
- Arnavion 5y ago
  Yes, you could trust in the CPU's branch prediction and the optimizer getting smarter in the future, or you could do the thing that's not only more self-documenting (Vec == need to read the code to notice it never grows, array == obviously fixed size) but also guaranteed to work already.

tialaramex 5y ago

> the optimizer will never remember that the Vec was created with 65536 `None`s. I mean, probably today, but: 1. If you're worried about bounds checks you are likely not thinking about this problem in the right way. The bounds check is a couple of CPU instructions, a register compare and a conditional jump. The jump is never taken, the CPU will remember that if we do this often, and everything is in registers or instruction cache. Then, having discerned that we're in bounds, we do a memory dereference. Actually no modern CPU waits until then, the CPU has concluded that we probably aren't going to branch, so it will emit the memory read, and while that takes its sweet time the CPU can do the comparison, and as anticipated decide not to take the branch it never takes. So we're actually waiting on the memory read, which is why we care about not using a hash map, because the hash map might incur two memory reads if we get unlucky. But on the other hand, if the hash map was small enough to fit in cache at least it arrives before the CPU goes into a coma because of how slow memory reads are to main memory. 2. Optimizers get smarter. It's clearly not impossible to do the analysis and decide this check isn't necessary. So I think that means you shouldn't rule it out.

Arnavion 5y ago
Yes, you could trust in the CPU's branch prediction and the optimizer getting smarter in the future, or you could do the thing that's not only more self-documenting (Vec == need to read the code to notice it never grows, array == obviously fixed size) but also guaranteed to work already.