Optimization on ImmutableList and ConcatList

[ikarienator]

Benchmarks added but not enforced.

[michaelficarra]

You should probably move the benchmarks out of the tests into something with a main method. If they don't make assertions, they aren't tests.

[ikarienator]

Can I actually start to assert on the performance numbers?

[ikarienator]

It looks like the job is killed due to time out? Can we lift the time out?

[michaelficarra]

I don't think we should make perf assertions. I just think the benchmarking files should not be marked as tests. This will also fix the timeout issue. We don't need to run benchmarks every time we run tests, especially if there's no assertions.

[ikarienator]

I was intended to post the numbers here. Unfortunately, some of the benchmarks can not finish in 20 minutes before optimization. I had to reduce the scale of benchmarks to get some numbers.

ConcatList

Old x0.01 scale (numbers below should x100)	New
Balanced tree	Balanced tree
ForeachIndexUpdate: 0.569µs	ForeachIndexUpdate: 1.193µs
Foreach: 31.990µs	Foreach: 120.339µs
ForLoop: 28.406µs	ForLoop: 197.553µs
Find: 11.245µs	Find: 133.512µs
Left-leaning tree	Left-leaning tree
ForeachIndexUpdate: 0.269µs	ForeachIndexUpdate: 21.149µs
Foreach: 60.615µs	Foreach: 106.369µs
ForLoop: 59.074µs	ForLoop: 176.883µs
Find: 0.852µs	Find: 99.922µs
Right-leaning tree	Right-leaning tree
ForeachIndexUpdate: 0.184µs	ForeachIndexUpdate: 376.171µs
Foreach: could not finish	Foreach: 125.026µs
ForLoop: could not finish	ForLoop: 181.210µs
Find: could not finish	Find: 122.133µs

ImmutableList

Old	New
Equals: 171.921µs	Equals: 66.200µs
Foreach: 864.418µs	Foreach: 70.119µs
Append: 1354.331µs	Append: 359.650µs
Reverse: 558.842µs	Reverse: 244.184µs
ToArray: 1098.376µs	ToArray: 80.166µs

Maybe

Old	New
0.763µs	0.503µs

[michaelficarra]

LGTM. Thanks, @ikarienator.