`HH\Lib\Vec\slice()` gets slower when slicing at larger offsets into a contiguous container

**Describe the bug**
The documentation of `HH\Lib\Vec\slice()` states that the runtime complexity scales with the length of the slice, but slicing `offset=n length=low-number` scales with linearly `offset`.

https://github.com/facebook/hhvm/blob/e81b014b5784b75b0d40360be369ef30f283c130/hphp/hsl/src/vec/select.php#L225

In a real workload (linting with portable-hack-ast-linters), whole run latency (including parsing and linting) can be reduced by 30%. Slicing a small number of elements from the 90,000th offset of a vec is 1500-ish times slower than a naive Hack for loop in repo auth mode.

**Standalone code, or other way to reproduce the problem**

Steps to reproduce the behavior:
1. Create a vec of any sufficiently large length.
2. Call `Vec\slice()` with `($vec, low-number, low-number)`
3. Call `Vec\slice()` with `($vec, high-number, low-number)`
4. Observe that slicing takes longer if the `$offset` argument gets larger

**Expected behavior**

If the argument has contiguous elements, access the elements by offset, rather than walking the length of the input until the offset has been reached.

**Actual behavior**

The input is walked with an `ArrayIter` in an empty loop until the offset has been consumed.
So given `Vec\slice(vec[0,1,2,3,..,99998,99999], 99995)` the `ArrayIter` walks `99995` elements to then consume the remaining 5.

https://github.com/facebook/hhvm/blob/e81b014b5784b75b0d40360be369ef30f283c130/hphp/runtime/ext/array/ext_array.cpp#L948-L958

**Environment**
- Operating system
> Ubuntu 26.04
- Installation method
> docker pull hersheltheodorelayton/hhvm-basic:26.06.05-resolute
- HHVM Version
> HipHop VM 26.6.5 (rel) (non-lowptr)
> Compiler: heads/hhvm-oss-20260605-resolute-raccoon-0-g0a1acba1cb9adf2489535d992f0584a62233ed64
> Repo schema: 97520be2e2a04014a90e9088f1d478f2a46008df

**Additional context**
The following commit https://github.com/hershel-theodore-layton/hhvm/commit/b983bd51b1256cd8c3fed53b2eb9970870723e50 implements an `if is contiguous, for (;offset < stop;++offset) out[] = in[offset];` loop in Hack.

https://github.com/hershel-theodore-layton/hhvm/blob/b983bd51b1256cd8c3fed53b2eb9970870723e50/hphp/hsl/src/vec/select.php#L215-L276

This build of hhvm running portable-hack-ast-linters reduces whole project lint latency by 30%.
portable-hack-ast contains cutSourceOrder. It slices a vec of `Node` (backed by `int`) from a vec width the length of the number of ast nodes in the file. The use case to slice a subset of the ast from the whole ast gets slower when slicing further into the file.

```hack
public function cutSourceOrder(
NodeId $from,
NodeId $to_inclusive,
)[]: vec {
$from = node_id_to_int($from);
$to_inclusive = node_id_to_int($to_inclusive);
return Vec\slice($this->sourceOrder, $from, $to_inclusive - $from + 1);
}
```

Whole run latency of parsing and linting 500 hack files

| Variant | p10 | p25 | p50 | p75 | p90 | p95 | p99 |
| --- | --- | --- | --- | --- | --- | --- | --- |
| Always `\array_slice()` | 1.713 s | 1.735 s | 1.755 s | 1.772 s | 1.792 s | 1.802 s | 1.820 s |
| Use Hack for-loop heuristic | 1.183 s | 1.200 s | 1.220 s | 1.238 s | 1.259 s | 1.276 s | 1.317 s |

The benchmarks below are not steady, since they are the median of 5 hot repo auth requests. Yet, improvements no this order of magnitude do not require full statistical rigor.

With the heuristic that falls back to `\array_slice()` for wide slices, every use case speeds up by doing the loop in Hack. The minimal improvement is the the neighborhood of 10% (slicing the first 4 elements). The improvements rise to 40,000 times when slicing the last elements of a 1 million length vec.

`Vec\slice()` vs naive Hack loop.

| Implementation | Values | Input | Case | Calls | Stock | Indexed | Speedup |
| --- | --- | --- | --- | --- | --- | --- | --- |
| Vec-slice | object | ImmVector | offset 0 length 4 | 20000 | 1.744 ms | 1.662 ms | 1.05× |
| Vec-slice | object | Vector | offset 0 length 4 | 20000 | 1.882 ms | 1.743 ms | 1.08× |
| Vec-slice | string | ImmVector | offset 0 length 4 | 20000 | 1.867 ms | 1.592 ms | 1.17× |
| Vec-slice | string | Vector | offset 0 length 4 | 20000 | 1.915 ms | 1.585 ms | 1.21× |
| Vec-slice | int | ImmVector | offset 0 length 4 | 20000 | 1.847 ms | 1.498 ms | 1.23× |
| Vec-slice | object | vec | offset 0 length 4 | 20000 | 1.691 ms | 1.273 ms | 1.33× |
| Vec-slice | int | Vector | offset 0 length 4 | 20000 | 1.950 ms | 1.448 ms | 1.35× |
| Vec-slice | int | vec | offset 0 length 4 | 20000 | 1.622 ms | 1.126 ms | 1.44× |
| Vec-slice | string | vec | offset 0 length 4 | 20000 | 1.843 ms | 1.066 ms | 1.73× |
| Vec-slice | object | Vector | offset 888889 length 111111 | 30 | 81.959 ms | 23.767 ms | 3.45× |
| Vec-slice | object | vec | offset 888889 length 111111 | 30 | 80.802 ms | 22.919 ms | 3.53× |
| Vec-slice | object | ImmVector | offset 888889 length 111111 | 30 | 82.635 ms | 22.454 ms | 3.68× |
| Vec-slice | string | vec | offset 888889 length 111111 | 30 | 77.218 ms | 16.806 ms | 4.59× |
| Vec-slice | string | Vector | offset 888889 length 111111 | 30 | 75.362 ms | 15.884 ms | 4.74× |
| Vec-slice | int | Vector | offset 888889 length 111111 | 30 | 80.364 ms | 16.886 ms | 4.76× |
| Vec-slice | int | vec | offset 888889 length 111111 | 30 | 75.068 ms | 15.454 ms | 4.86× |
| Vec-slice | string | ImmVector | offset 888889 length 111111 | 30 | 81.589 ms | 16.433 ms | 4.96× |
| Vec-slice | int | ImmVector | offset 888889 length 111111 | 30 | 81.159 ms | 16.169 ms | 5.02× |
| Vec-slice | object | Vector | offset 500000 length 1000 | 500 | 528.031 ms | 2.839 ms | 186× |
| Vec-slice | object | vec | offset 500000 length 1000 | 500 | 523.420 ms | 2.791 ms | 188× |
| Vec-slice | object | ImmVector | offset 500000 length 1000 | 500 | 531.526 ms | 2.797 ms | 190× |
| Vec-slice | string | Vector | offset 500000 length 1000 | 500 | 521.679 ms | 2.087 ms | 250× |
| Vec-slice | string | vec | offset 500000 length 1000 | 500 | 527.391 ms | 1.995 ms | 264× |
| Vec-slice | string | ImmVector | offset 500000 length 1000 | 500 | 566.891 ms | 1.996 ms | 284× |
| Vec-slice | int | vec | offset 500000 length 1000 | 500 | 518.520 ms | 1.816 ms | 286× |
| Vec-slice | int | ImmVector | offset 500000 length 1000 | 500 | 524.060 ms | 1.811 ms | 289× |
| Vec-slice | int | Vector | offset 500000 length 1000 | 500 | 568.746 ms | 1.824 ms | 312× |
| Vec-slice | object | Vector | offset 90000 length 4 | 200 | 38.071 ms | 0.026 ms | 1473× |
| Vec-slice | object | ImmVector | offset 90000 length 4 | 200 | 37.375 ms | 0.024 ms | 1551× |
| Vec-slice | string | Vector | offset 90000 length 4 | 200 | 37.135 ms | 0.024 ms | 1564× |
| Vec-slice | object | vec | offset 90000 length 4 | 200 | 36.810 ms | 0.022 ms | 1700× |
| Vec-slice | string | ImmVector | offset 90000 length 4 | 200 | 40.431 ms | 0.024 ms | 1703× |
| Vec-slice | int | ImmVector | offset 90000 length 4 | 200 | 38.249 ms | 0.021 ms | 1795× |
| Vec-slice | int | Vector | offset 90000 length 4 | 200 | 40.588 ms | 0.022 ms | 1845× |
| Vec-slice | string | vec | offset 90000 length 4 | 200 | 36.803 ms | 0.019 ms | 1952× |
| Vec-slice | int | vec | offset 90000 length 4 | 200 | 37.068 ms | 0.019 ms | 2003× |
| Vec-slice | object | Vector | offset 500000 length 16 | 10000 | 10.762 s | 1.498 ms | 7182× |
| Vec-slice | object | ImmVector | offset 500000 length 16 | 10000 | 10.835 s | 1.454 ms | 7453× |
| Vec-slice | string | Vector | offset 500000 length 16 | 10000 | 10.512 s | 1.323 ms | 7945× |
| Vec-slice | string | ImmVector | offset 500000 length 16 | 10000 | 11.211 s | 1.403 ms | 7992× |
| Vec-slice | int | Vector | offset 500000 length 16 | 10000 | 11.146 s | 1.351 ms | 8247× |
| Vec-slice | object | vec | offset 500000 length 16 | 10000 | 10.452 s | 1.258 ms | 8307× |
| Vec-slice | int | ImmVector | offset 500000 length 16 | 10000 | 10.422 s | 1.181 ms | 8824× |
| Vec-slice | int | vec | offset 500000 length 16 | 10000 | 10.354 s | 1.114 ms | 9292× |
| Vec-slice | string | vec | offset 500000 length 16 | 10000 | 10.615 s | 1.038 ms | 10228× |
| Vec-slice | object | Vector | offset 500000 length 4 | 20000 | 23.022 s | 1.746 ms | 13185× |
| Vec-slice | string | ImmVector | offset 500000 length 4 | 20000 | 21.688 s | 1.634 ms | 13276× |
| Vec-slice | object | ImmVector | offset 500000 length 4 | 20000 | 21.768 s | 1.567 ms | 13889× |
| Vec-slice | string | Vector | offset 500000 length 4 | 20000 | 21.883 s | 1.563 ms | 13997× |
| Vec-slice | int | ImmVector | offset 500000 length 4 | 20000 | 21.197 s | 1.456 ms | 14556× |
| Vec-slice | int | Vector | offset 500000 length 4 | 20000 | 21.665 s | 1.431 ms | 15136× |
| Vec-slice | object | vec | offset 500000 length 4 | 20000 | 21.157 s | 1.387 ms | 15253× |
| Vec-slice | int | vec | offset 500000 length 4 | 20000 | 20.697 s | 1.134 ms | 18247× |
| Vec-slice | string | vec | offset 500000 length 4 | 20000 | 20.831 s | 1.061 ms | 19635× |
| Vec-slice | object | Vector | offset -10 length 4 | 20000 | 43.268 s | 1.797 ms | 24082× |
| Vec-slice | object | Vector | offset 999990 length 4 | 20000 | 42.276 s | 1.732 ms | 24412× |
| Vec-slice | object | ImmVector | offset -10 length 4 | 20000 | 42.860 s | 1.648 ms | 26014× |
| Vec-slice | string | ImmVector | offset 999990 length 4 | 20000 | 43.571 s | 1.586 ms | 27465× |
| Vec-slice | string | Vector | offset 999990 length 4 | 20000 | 43.637 s | 1.552 ms | 28118× |
| Vec-slice | string | ImmVector | offset -10 length 4 | 20000 | 46.609 s | 1.655 ms | 28158× |
| Vec-slice | object | ImmVector | offset 999990 length 4 | 20000 | 45.256 s | 1.605 ms | 28198× |
| Vec-slice | string | Vector | offset -10 length 4 | 20000 | 46.036 s | 1.570 ms | 29328× |
| Vec-slice | int | Vector | offset -10 length 4 | 20000 | 42.826 s | 1.433 ms | 29875× |
| Vec-slice | int | ImmVector | offset -10 length 4 | 20000 | 43.327 s | 1.431 ms | 30269× |
| Vec-slice | int | ImmVector | offset 999990 length 4 | 20000 | 45.822 s | 1.454 ms | 31520× |
| Vec-slice | int | Vector | offset 999990 length 4 | 20000 | 44.783 s | 1.411 ms | 31743× |
| Vec-slice | object | vec | offset -10 length 4 | 20000 | 43.501 s | 1.338 ms | 32516× |
| Vec-slice | object | vec | offset 999990 length 4 | 20000 | 43.178 s | 1.269 ms | 34034× |
| Vec-slice | int | vec | offset -10 length 4 | 20000 | 42.189 s | 1.105 ms | 38184× |
| Vec-slice | int | vec | offset 999990 length 4 | 20000 | 42.554 s | 1.078 ms | 39462× |
| Vec-slice | string | vec | offset 999990 length 4 | 20000 | 43.542 s | 1.067 ms | 40801× |
| Vec-slice | string | vec | offset -10 length 4 | 20000 | 44.376 s | 1.074 ms | 41312× |

After careful measurement, the heuristic is pessimistic about the performance of jitted Hack, arrays of fewer than a million elements can be sliced in a Hack for-loop faster than dropping into cpp.

What if the Hack loop was always used (worst case)

| n | Stock loops | Stock / slice | Index loops | Index / slice | Stock ÷ index |
| --- | --- | --- | --- | --- | --- |
| 32 | 50000000 | 213 ns | 50000000 | 116 ns | 1.84× |
| 64 | 11711781 | 387 ns | 21502712 | 220 ns | 1.76× |
| 128 | 6462081 | 731 ns | 11389123 | 417 ns | 1.75× |
| 256 | 3418720 | 1.440 µs | 5992156 | 824 ns | 1.75× |
| 512 | 1736496 | 2.844 µs | 3035337 | 1.608 µs | 1.77× |
| 1024 | 879096 | 5.638 µs | 1554442 | 3.172 µs | 1.78× |
| 2048 | 443437 | 11.229 µs | 788208 | 6.371 µs | 1.76× |
| 4096 | 222642 | 22.395 µs | 392423 | 12.547 µs | 1.78× |
| 8192 | 111630 | 44.641 µs | 199251 | 25.007 µs | 1.79× |
| 16384 | 56002 | 89.826 µs | 99971 | 49.888 µs | 1.80× |
| 32768 | 27832 | 179.391 µs | 50112 | 100.853 µs | 1.78× |
| 65536 | 13936 | 367.522 µs | 24789 | 204.537 µs | 1.80× |
| 131072 | 6802 | 755.528 µs | 12223 | 467.077 µs | 1.62× |
| 262144 | 3309 | 1.494 ms | 5352 | 1.105 ms | 1.35× |
| 524288 | 1673 | 3.000 ms | 2262 | 2.302 ms | 1.30× |
| 1048576 | 833 | 11.135 ms | 1086 | 9.662 ms | 1.15× |
| 2097152 | 225 | 22.492 ms | 259 | 24.522 ms | 0.92× |
| 4194304 | 111 | 44.011 ms | 102 | 53.768 ms | 0.82× |
| 8388608 | 57 | 92.152 ms | 46 | 113.990 ms | 0.81× |
| 16777216 | 27 | 187.882 ms | 22 | 253.589 ms | 0.74× |
| 33554432 | 13 | 374.294 ms | 10 | 503.222 ms | 0.74× |
| 67108864 | 7 | 727.091 ms | 5 | 967.865 ms | 0.75× |
| 134217728 | 3 | 1.507 s | 3 | 2.035 s | 0.74× |

The verify, this is not unique to monotyped vecs.

Vecs with multiple types inside (string, int, bool, float, null, object, and array)

| n | Stock loops | Stock / slice | Index loops | Index / slice | Stock ÷ index |
| --- | --- | --- | --- | --- | --- |
| 32 | 50000000 | 235 ns | 50000000 | 132 ns | 1.78× |
| 64 | 10637720 | 427 ns | 18929052 | 252 ns | 1.69× |
| 128 | 5859812 | 805 ns | 9904802 | 497 ns | 1.62× |
| 256 | 3105523 | 1.582 µs | 5034191 | 972 ns | 1.63× |
| 512 | 1580148 | 3.105 µs | 2571721 | 1.917 µs | 1.62× |
| 1024 | 805138 | 6.161 µs | 1304338 | 3.815 µs | 1.62× |
| 2048 | 405765 | 12.288 µs | 655374 | 7.507 µs | 1.64× |
| 4096 | 203453 | 24.423 µs | 333015 | 15.126 µs | 1.61× |
| 8192 | 102365 | 48.796 µs | 165278 | 30.434 µs | 1.60× |
| 16384 | 51234 | 100.451 µs | 82146 | 59.732 µs | 1.68× |
| 32768 | 24888 | 203.182 µs | 41853 | 121.401 µs | 1.67× |
| 65536 | 12304 | 408.971 µs | 20593 | 248.430 µs | 1.65× |
| 131072 | 6113 | 824.115 µs | 10063 | 536.273 µs | 1.54× |
| 262144 | 3034 | 1.694 ms | 4662 | 1.316 ms | 1.29× |
| 524288 | 1475 | 3.515 ms | 1900 | 2.795 ms | 1.26× |
| 1048576 | 711 | 12.280 ms | 894 | 10.757 ms | 1.14× |
| 2097152 | 204 | 24.568 ms | 232 | 27.059 ms | 0.91× |
| 4194304 | 102 | 48.517 ms | 92 | 59.234 ms | 0.82× |
| 8388608 | 52 | 96.888 ms | 42 | 116.895 ms | 0.83× |
| 16777216 | 26 | 192.777 ms | 21 | 246.245 ms | 0.78× |
| 33554432 | 13 | 382.625 ms | 10 | 497.974 ms | 0.77× |
| 67108864 | 7 | 771.101 ms | 5 | 984.978 ms | 0.78× |
| 134217728 | 3 | 1.646 s | 3 | 2.090 s | 0.79× |