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

[hershel-theodore-layton]

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.

hhvm/hphp/hsl/src/vec/select.php

Line 225 in e81b014

* Time complexity: O(n), where n is the size of the slice

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.

hhvm/hphp/runtime/ext/array/ext_array.cpp

Lines 948 to 958 in e81b014

	int pos = 0;
	ArrayIter iter(cell_input);
	for (; pos < offset && iter; ++pos, ++iter) {}
	if (input_is_packed && (offset == 0 || !preserve_keys)) {
	VecInit ret(len);
	for (; pos < (offset + len) && iter; ++pos, ++iter) {
	ret.append(iter.secondValPlus());
	}
	return tvReturn(ret.toVariant());
	}

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 hershel-theodore-layton@b983bd5 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.

  public function cutSourceOrder(
    NodeId $from,
    NodeId $to_inclusive,
  )[]: vec<Node> {
    $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×