Missing Performance Optimization for toArray of size zero

[thespags]

After reading “Arrays of Ancient Wisdom” I was curious as to ImmutableList's and ImmutableSet's performance. It turns out the zero case, listOfStrings.toArray(new String[0]), is not optimized for array backed collections as ImmutableCollection's will create a new array of appropriate size so we don't get the use of Arrays.copyOf(src, size, Foo[].class) mentioned in the article. I ran the same benchmark tests as the post but with ImmutableSet and ImmutableList. Interestingly ImmutableSet is way more performant than HashSet's implementation. Locally, I've added overriding RegularImmutableList to use ArrayList's implementation of toArray to see the performance gain.

ToArrayBenchmark.simple 0 arraylist avgt 15 31.465 ± 4.786 ns/op
ToArrayBenchmark.simple 0 hashset avgt 15 32.851 ± 1.709 ns/op
ToArrayBenchmark.simple 0 immutableset avgt 15 5.016 ± 0.686 ns/op
ToArrayBenchmark.simple 0 immutablelist avgt 15 4.508 ± 1.252 ns/op
ToArrayBenchmark.simple 1 arraylist avgt 15 11.687 ± 0.747 ns/op
ToArrayBenchmark.simple 1 hashset avgt 15 33.714 ± 4.696 ns/op
ToArrayBenchmark.simple 1 immutableset avgt 15 6.244 ± 0.711 ns/op
ToArrayBenchmark.simple 1 immutablelist avgt 15 6.495 ± 0.665 ns/op
ToArrayBenchmark.simple 10 arraylist avgt 15 12.733 ± 0.575 ns/op
ToArrayBenchmark.simple 10 hashset avgt 15 54.044 ± 0.771 ns/op
ToArrayBenchmark.simple 10 immutableset avgt 15 26.258 ± 0.349 ns/op
ToArrayBenchmark.simple 10 immutablelist avgt 15 26.280 ± 0.365 ns/op
ToArrayBenchmark.simple 100 arraylist avgt 15 56.674 ± 0.894 ns/op
ToArrayBenchmark.simple 100 hashset avgt 15 410.268 ± 8.487 ns/op
ToArrayBenchmark.simple 100 immutableset avgt 15 66.360 ± 3.243 ns/op
ToArrayBenchmark.simple 100 immutablelist avgt 15 64.615 ± 0.985 ns/op
ToArrayBenchmark.simple 1000 arraylist avgt 15 542.213 ± 15.957 ns/op
ToArrayBenchmark.simple 1000 hashset avgt 15 5655.338 ± 161.615 ns/op
ToArrayBenchmark.simple 1000 immutableset avgt 15 522.536 ± 13.991 ns/op
ToArrayBenchmark.simple 1000 immutablelist avgt 15 517.339 ± 7.506 ns/op
ToArrayBenchmark.sized 0 arraylist avgt 15 26.663 ± 0.283 ns/op
ToArrayBenchmark.sized 0 hashset avgt 15 28.946 ± 0.704 ns/op
ToArrayBenchmark.sized 0 immutableset avgt 15 26.718 ± 0.277 ns/op
ToArrayBenchmark.sized 0 immutablelist avgt 15 26.685 ± 0.239 ns/op
ToArrayBenchmark.sized 1 arraylist avgt 15 25.376 ± 0.153 ns/op
ToArrayBenchmark.sized 1 hashset avgt 15 31.299 ± 0.461 ns/op
ToArrayBenchmark.sized 1 immutableset avgt 15 6.652 ± 0.134 ns/op
ToArrayBenchmark.sized 1 immutablelist avgt 15 6.416 ± 0.557 ns/op
ToArrayBenchmark.sized 10 arraylist avgt 15 35.730 ± 1.166 ns/op
ToArrayBenchmark.sized 10 hashset avgt 15 62.808 ± 0.399 ns/op
ToArrayBenchmark.sized 10 immutableset avgt 15 36.589 ± 0.233 ns/op
ToArrayBenchmark.sized 10 immutablelist avgt 15 36.588 ± 0.313 ns/op
ToArrayBenchmark.sized 100 arraylist avgt 15 156.417 ± 1.412 ns/op
ToArrayBenchmark.sized 100 hashset avgt 15 457.137 ± 4.642 ns/op
ToArrayBenchmark.sized 100 immutableset avgt 15 163.828 ± 16.155 ns/op
ToArrayBenchmark.sized 100 immutablelist avgt 15 165.102 ± 13.259 ns/op
ToArrayBenchmark.sized 1000 arraylist avgt 15 1622.890 ± 48.077 ns/op
ToArrayBenchmark.sized 1000 hashset avgt 15 6138.110 ± 209.517 ns/op
ToArrayBenchmark.sized 1000 immutableset avgt 15 1594.347 ± 36.467 ns/op
ToArrayBenchmark.sized 1000 immutablelist avgt 15 1576.163 ± 22.306 ns/op
ToArrayBenchmark.zero 0 arraylist avgt 15 6.110 ± 0.520 ns/op
ToArrayBenchmark.zero 0 hashset avgt 15 6.214 ± 0.108 ns/op
ToArrayBenchmark.zero 0 immutableset avgt 15 5.497 ± 0.129 ns/op
ToArrayBenchmark.zero 0 immutablelist avgt 15 5.316 ± 0.109 ns/op
ToArrayBenchmark.zero 1 arraylist avgt 15 14.357 ± 0.734 ns/op
ToArrayBenchmark.zero 1 hashset avgt 15 32.736 ± 1.741 ns/op
ToArrayBenchmark.zero 1 immutableset avgt 15 6.489 ± 0.229 ns/op
ToArrayBenchmark.zero 1 immutablelist avgt 15 7.131 ± 0.587 ns/op
ToArrayBenchmark.zero 10 arraylist avgt 15 24.362 ± 0.407 ns/op
ToArrayBenchmark.zero 10 hashset avgt 15 67.743 ± 3.293 ns/op
ToArrayBenchmark.zero 10 immutableset avgt 15 35.643 ± 0.236 ns/op
ToArrayBenchmark.zero 10 immutablelist avgt 15 35.586 ± 0.290 ns/op
ToArrayBenchmark.zero 100 arraylist avgt 15 139.902 ± 0.979 ns/op
ToArrayBenchmark.zero 100 hashset avgt 15 415.847 ± 10.321 ns/op
ToArrayBenchmark.zero 100 immutableset avgt 15 158.764 ± 2.714 ns/op
ToArrayBenchmark.zero 100 immutablelist avgt 15 163.192 ± 9.697 ns/op
ToArrayBenchmark.zero 1000 arraylist avgt 15 1254.335 ± 58.871 ns/op
ToArrayBenchmark.zero 1000 hashset avgt 15 6237.355 ± 480.110 ns/op
ToArrayBenchmark.zero 1000 immutableset avgt 15 1561.342 ± 27.664 ns/op
ToArrayBenchmark.zero 1000 immutablelist avgt 15 1601.746 ± 52.149 ns/op

The following is with the toArray optimization and we see the performance improvement.

ToArrayBenchmark.simple 0 immutableset avgt 15 3.694 ± 0.092 ns/op
ToArrayBenchmark.simple 0 immutablelist avgt 15 3.681 ± 0.103 ns/op
ToArrayBenchmark.simple 1 immutableset avgt 15 5.883 ± 0.222 ns/op
ToArrayBenchmark.simple 1 immutablelist avgt 15 6.331 ± 0.203 ns/op
ToArrayBenchmark.simple 10 immutableset avgt 15 34.850 ± 17.701 ns/op
ToArrayBenchmark.simple 10 immutablelist avgt 15 28.912 ± 2.927 ns/op
ToArrayBenchmark.simple 100 immutableset avgt 15 68.687 ± 3.175 ns/op
ToArrayBenchmark.simple 100 immutablelist avgt 15 68.712 ± 1.944 ns/op
ToArrayBenchmark.simple 1000 immutableset avgt 15 545.795 ± 19.291 ns/op
ToArrayBenchmark.simple 1000 immutablelist avgt 15 535.887 ± 11.840 ns/op
ToArrayBenchmark.sized 0 immutableset avgt 15 28.366 ± 1.179 ns/op
ToArrayBenchmark.sized 0 immutablelist avgt 15 28.028 ± 0.600 ns/op
ToArrayBenchmark.sized 1 immutableset avgt 15 7.331 ± 0.320 ns/op
ToArrayBenchmark.sized 1 immutablelist avgt 15 6.735 ± 0.257 ns/op
ToArrayBenchmark.sized 10 immutableset avgt 15 42.916 ± 6.048 ns/op
ToArrayBenchmark.sized 10 immutablelist avgt 15 39.424 ± 2.563 ns/op
ToArrayBenchmark.sized 100 immutableset avgt 15 179.566 ± 11.643 ns/op
ToArrayBenchmark.sized 100 immutablelist avgt 15 183.309 ± 17.414 ns/op
ToArrayBenchmark.sized 1000 immutableset avgt 15 1638.464 ± 29.570 ns/op
ToArrayBenchmark.sized 1000 immutablelist avgt 15 1649.259 ± 44.469 ns/op
ToArrayBenchmark.zero 0 immutableset avgt 15 5.927 ± 0.457 ns/op
ToArrayBenchmark.zero 0 immutablelist avgt 15 5.545 ± 0.242 ns/op
ToArrayBenchmark.zero 1 immutableset avgt 15 6.517 ± 0.194 ns/op
ToArrayBenchmark.zero 1 immutablelist avgt 15 6.796 ± 0.150 ns/op
ToArrayBenchmark.zero 10 immutableset avgt 15 36.631 ± 1.714 ns/op
ToArrayBenchmark.zero 10 immutablelist avgt 15 24.109 ± 0.707 ns/op
ToArrayBenchmark.zero 100 immutableset avgt 15 245.963 ± 85.071 ns/op
ToArrayBenchmark.zero 100 immutablelist avgt 15 141.072 ± 2.006 ns/op
ToArrayBenchmark.zero 1000 immutableset avgt 15 1574.395 ± 14.037 ns/op
ToArrayBenchmark.zero 1000 immutablelist avgt 15 1279.353 ± 44.592 ns/op

[lowasser]

Can you send us a pull request with this improvement?

[thespags]

Hi, I can send a pull request, but will there be a problem as I have to remove the final modifier from ImmutableCollection#toArray(T[] other)?

[lowasser]

I think at least a proof of concept would help clarify what approach you have in mind, that we can then figure out how to integrate more fully.

[thespags]

Great. I've added a PR: #3213. The PR doesn't address RegularImmutableAsList implementation which would probably want to defer to the delegateList similarly to copyIntoArray if you were going down that path.

[zugzug90]

Hi all. Is this issue still actual?

[thespags]

Looks like the issue has been addressed, but I haven't rerun the benchmarks with the latest changes.