search

vigna / fastutil

fastutil extends the Java™ Collections Framework by providing type-specific maps, sets, lists and queues.
Apache License 2.0
1.8k stars 197 forks source link

Make List.of and Set.of bimorphic #185

Closed techsy730 closed 3 years ago

techsy730 commented 3 years ago

Make List.of and Set.of bimorphic, that is, only returns potentially two different types. Three or more tanks performance severely. See https://github.com/vigna/fastutil/issues/183

Now

There is one more case that needs to be looked into, and that is Iterators.asXIterator and its cousin Spliterators.asXSpliterator. However, the performance loss only happens if three or more return types actually happen in a program run, not by merely being possible in the bytecode. And I can't imagine that many programs will trigger all three paths. Still should be looked at but less important.

techsy730 commented 3 years ago

With these final few pull requests (especially this one, the bimorphic call for of), I think I am done for this release. Obviously I can do further work for later releases, but IMHO these gets us in a good spot for a release.

vigna commented 3 years ago

I agree. My only wish was for NavigableSet, we're really late on that, but it's a lot of work.

techsy730 commented 3 years ago

I can try doing that for 8.6. Since I am going to have to break down and understand the tree structure anyways to make an efficient spliterator, it would also get me the knowledge needed to implement the navigable methods.

vigna commented 3 years ago

We can work on it together for 8.6.0, it would be a nice addition (and the last before switching to Java 9 or even 11). For me, the main benefit is upper/lower bound computations—all the reversed view stuff I think is really a red herring (and a lot of work).