Here it is, spliterators and primitive stream methods for collections. Also fill in some other Java 8 methods.

Overview of the change: https://docs.google.com/document/d/1yMf5LSajEQ4i4odnwWrXDPPl7OmjX1Fj2MpHzhCAB5c/edit?usp=sharing

This change addresses https://github.com/vigna/fastutil/issues/116, https://github.com/vigna/fastutil/issues/115, and https://github.com/vigna/fastutil/issues/98

IntArrayList.intStream().sum() is about 3.5 times faster then java.util.ArrayList.stream().mapToInt(Integer::intValue).sum() (1ns per element for ArrayList, .28ns per element for IntArrayList)

If you think the changes are substantial enough to warrant a bump to 9.0.0, may I suggest that we require Java 9 for that so that we can take advantage of its high performance methods for arrays and index checks?

I am not content with how the disambiguation methods (such as forEachRemaining(...fastutil.ints.IntConsumer) delegates to forEachRemaining(java.util.function.IntConsumer)) turned out. But without this, calling forEachRemaining(...fastutil.ints.IntConsumer) would cause a compile-time error as it would be ambiguous between java.util.function.IntConsumer and java.util.function.Consumer. If you don't think this disambiguation is worth it (for example, you wanted to deprecate ...fastutil.ints.IntConsumer), then I can remove it and the cruft associated with it.

Apologies for doubling the size of TODO. I do plan on getting to the items I listed in it, but I didn't want to block any longer on this.

Hi,

as you said in #43:

Well, Java 7 hit the end of life. So Java 8 support it's a matter of survival.

Do you plan to migrate to Java 8? I strongly urge you to - I personally need most of these changes :) I identified several "todo"-items for Java 8, which I would be willing to implement:

• Support of the new Map methods like putIfAbsent, computIfAbsent etc. (#57)
• Synchronization support of the newly introduced map methods (#48)
• Support of new Iterator interfaces (#43)
• Support of new Function interfaces, e.g. Int2DoubleMap should implement Java 8's IntToDoubleFunction.

I imagine that one could implement all this in a way which allows you to specify the target Java version. But, while it should be possible, I advice against it; as you pointed out, Java 7 is not the go-to version anymore and future releases should target Java 8.

Would you accept Pair<K,V>, similar to https://docs.oracle.com/javase/9/docs/api/javafx/util/Pair.html and https://developer.android.com/reference/android/util/Pair in your codebase ? I use Pairs in my product and would be interested in PairIntInt and PairIntObject<V>.

If you'd accept such a PR, I would try to create it if I understand the language

If I recall correctly, I already added support for building a reduced jar ("fastutil-min"). It might make sense to actually publish this.

Reasoning: Asides from memory usage due to array packing there is, to my knowledge, no reason to use any key/value types except int, long and double, as essentially all operations are only defined for these types and operations on the other "primitives" even incur a performance penalty due to conversion. One could discuss whether boolean types could be included (XY2BooleanMap and BooleanList have some merit I guess). Advantage are smaller image (not that important), less clutter (autocompletion isn't spammed with 100 different types) and faster to work with (indexing fastutil does take a while).

Maybe the "full" fastutil image could even depend on the "min" image, however I guess this is a bit tricky to work with.

EDIT: floats are also natively supported by the JVM, however they come with many other pitfalls, so I still think that they should not be included in the core image

Here some functions that were really needed. (More the stack then the Priority queue)

Compiled the code to test if it works and added a test to make sure nothing crashes or gives unexpected results.

This is an umbrella issue for discussing two problems that are becoming very visible in these days in the codebase:

• The overlap of different people implementing different conditional features has led to a proliferation of complex assertions—the semantics of which, however, is sometime much simpler than one would expect (e.g., it's just a matter of being int/long/double or any other type). All contributors added stuff to gencsources.sh, resulting in a large collection of #define's without any comment. Ten years ago that would have been OK, but with the amount of subtly convoluted conditional compilation we have now this is no longer acceptable. It has become very difficult (for me) to understand which code is being generated. There must be some documentation for the #define's, and clearly named assertions.

• The strategy for implementing functional interfaces or callers of functional interfaces in the presence of multiple possible implementations (e.g., object-based, JDK-primitive, or fastutil-primitive) is not uniform throughout the codebase. I find myself thinking most of the time "shouldn't this be implemented the other way around?". This is not healthy (oh, of course maybe I'm just old). Once again, ten years ago there were so few cases that looking around in other parts of the code was sufficient to understand what was the best practice, but this is no longer the case.

For the first part, it is mostly a matter of restructuring the file and commenting.

For the second part, I must write somewhere what is the preferred design. I'll keep updating this text, and I invite everybody working on fastutil to comment below.

Now, given the premises, there are things we cannot change:

• We want to benefit from code improvements upstream. This means that anything primitive that has been implemented in the JDK must not be overridden. For example, IntIerator.forEachRemaining() has primitive implementations in the JDK, so we should use those (possibly all of them—also the ones accepting object-based consumers).

• Lambdas will be fastutil-primitive. This is unavoidable because fastutil's types join the object and primitive JDK world, and this is the only possibility to avoid ambiguity while continuing fastutil's tradition of adding primitive-based operation without eliminating the object-based ones. As already implemented by @techsy730 in a number of cases, for methods accepting functional interfaces there must the usual deprecated object-based one, a fastutil-primitive one, and a JDK-primitive one if it is possible. We have by now functions (unary operators), predicates, consumers and binary operators, which should cover everything type-specific presently (except of course for two-argument functions in which the three types involved are not all the same, as in Map.computeIf*()).

The solution chosen is as follows (at present time, for Consumer/Predicate-related methods):

• in the int/long/double case, we inherit from the JDK or implement the overload accepting a JDK type-specific functor. An @apiNote will explain that this is the method to override.

• in the remaining case, the overload accepting a fastutil type-specific functor will be implemented, instead. Again, an @apiNote will explain that this is the method to override.

• in the int/long/double case, the overload accepting a fastutil type-specific functor delegates to the overload accepting a JDK type-specific functor. A WARNING will explain that this method should not be overridden.

• in the remaining cases, the overload accepting a widened JDK type-specific functor checks for the functor being an instance of fastutil type-specific functor, in which cases passes directly the functor with a cast, or generates a new lambda using the only method of the functor. An @apiNote that will explain that this method incurs in a slight overhead.

To make the implementation easy, the functor type associated with the actual implementation is stored in a macro, so the implementation of the first two cases is the same. The other implementations are contained within conditional code, which makes it possible to add appropriate comments. See Consumer.drv for an example.

Another issue is whether to use the JDK-primitive method names, if available, instead of fastutil's names. In principle I'm against this option because fastutil has always avoided adding disambiguating strings to methods if the type of the arguments was sufficient. So a BinaryOperator should have an apply() method. The applyAsInt() coming from the JDK should be delegated with a default method to apply(). This delegation would actually never happen inside fastutil at runtime if we proceed as explained above, because a ready-made JDK-primitive thing would be turned into a new lambda in which the JDK-primitive method is used to implement the fastutil-primitive method.

Harden immutability of ImmutableList.

This closes a few avenues that could have lead to mutating the supposed to be immutable list. In particular, the backing array was non-final and protected (now private and final), and mutations could still happen through the iterator.

Adds the cult-favorite optimization of sharing a single empty instance if given empty arguments to the static constructor.

Also add fast toArray for object based ImmutableList and ArrayList.

Clean up the of methods()

• Make the of methods in the root List and Set interfaces return immutable collections (like the platform does)
• Validate that duplicate entries to the "of" method of sets throws (like the platform does)

Because of this validation, it is now worth it to have overloads of 0 and 1 element, which skip the temporary array and validation (0 and 1 element sets can never have duplication).

In the spirit of ArraySet's "just trust me" API of working raw arrays unvalidated, an it has an offshoot ofUnchecked that takes the elements as is and does no validation, like the array accepting constructors do.

I'm using an Object2ObjectOpenHashMap as an internal data structure. When my program ends, I write out the content to disk (using custom serialization code, iterating over the map). When the program the next time starts, it reads the data back in from disk, inserting the objects again into the map. I realized that reading the data back in is much slower than inserting the objects in the first round. After some testing, I found out the following:

• Inserting objects into an Object2ObjectOpenHashMap in "random" order requires some amount of calls to equals() in the inserted Objects.
• Inserting objects into an Object2ObjectOpenHashMap in the order as they are returned from the iterator from another Object2ObjectOpenHashMap, it requires many more calls to equals() in the inserted Objects (at least one magnitude more calls).

If the equals() method does a bit of logic, it has a huge impact on performance.

I'll attach a short piece of code that demonstrates the problem, inserting Strings into the Map (Actually, WrappedStrings so I'm able to count the number of equals() invocations). Inserting the 2 million Strings the first time requires about 5 million equal() calls, while inserting them the second time requires about 180 million equal() calls.

It reminds me a bit of the problem in Java's HashMap a while ago (Java 7?) where it was said inserting objects in a special order could lead to Denial of Service attacks due to very poor performance in such cases.

InsertTest.java.txt

Hi, NPE while putting into Object2IntOpenHashMap, could anyone help?

java.lang.NullPointerException
 at it.unimi.dsi.fastutil.objects.Object2IntOpenHashMap.rehash(Object2IntOpenHashMap.java:1313) ~[fastutil-8.1.0.jar:?]
 at it.unimi.dsi.fastutil.objects.Object2IntOpenHashMap.insert(Object2IntOpenHashMap.java:322) ~[fastutil-8.1.0.jar:?]
 at it.unimi.dsi.fastutil.objects.Object2IntOpenHashMap.put(Object2IntOpenHashMap.java:331) ~[fastutil-8.1.0.jar:?]

Hello to Everyone who reads this. Maybe even @vigna.

I want to help with this project. Make improvements etc. I have no issue with working with drv files and do all these edits even if there is no compiler help.

What I have an issue with is test the code because there is no real instructions/tutorial on how to actually generate the source code. What this issue is about is very simple. Please provide a instruction list/tutorial how to generate these things. If there is a difference between linux and windows and mac then provide instructions how to do these.

Why am i requesting this help? Very simple. There is some requirements to write tests & test them. Ensure code is actually working. Which has to be done A either in the head or B not at all. This is prone to cause errors or mistakes in the code that may be not found.

The single requirement: Make them easy and simple to understand so that someone who has never worked with sh scripts & make-files before can understand them. Because right now you need actual experience to know what to do to do simple exporting of the source code.

Also the Wikisection is great for such things.

Thanks for reading. Speiger

This is a memory optimization for the case when a user required to modify iterator by moving it to a desire position. This works the same way as iteraotr(fromElement) but doesn't create a new iterator that decreases memory footprint at an algorithms which makes a lot of jumps.

This was shown in a recent Java Collections Puzzlers. The JavaDoc for Map.putIfAbsent states the following.

If the specified key is not already associated with a value (or is mapped to {@code null}) associates it with the given value and returns {@code null}, else returns the current value.

@Test
public void putIfAbsent_nullExistingValue() {
  var map = new Object2ObjectOpenHashMap<Object, Object>();
  map.put("a", null);
  map.putIfAbsent("a", "b");
  assertThat(map).containsEntry("a", "b");
}

FAILED: Test.putIfAbsent_nullExistingValue
key is present but with a different value
value of: map.get(a)
expected: b
but was : null
map was : {a=>null}

The computeIfAbsent method has similar wording and fails in this scenario.

I have requested that this peculiarity of the api be added to Guava's testlib.

I would like to iterate a map's entry set without the need for boxing. I found no equivalent for Map#forEach though.

One could achieve this via iterating over *2*EntrySet() but the code looks less readable then.

Currently there is no way to check dynamically if an BigList implements copy() or not. If all the MappedBigList implemented FlyweightPrototype, it would be easier to make a function that makes a threadsafe copy of any type of BigList.

Unfortunately FlyweightPrototype is in dsiutils, not fastutil, so I don't know what's the best way to proceed here.

It appears many of the classes which implement Serializable allocate memory based on a size value specified in the deserialized data, e.g. read an int as size value and create an array of that size. I assume this is done intentionally for good performance; however, it should be documented. Adversaries can abuse this to cause Denial of Service attacks. For example the Guava library received CVE-2018-10237 for the same issue. (I just want to point out here that this can be considered a security issue; I am not asking for fastutil to get a CVE or to change the implementation.)

It would therefore be good to at least in the README and the Javadoc main page describe that the deserialization implementation is designed for efficiency and should not be used for untrusted data.

This adds collectors for Stream to fastutil Maps.

Future improvements would be to investigate supporting primitive streams (e.g. IntStream) and improving the type signature for collectors where char is the key or value. When char is the key, the functions are for int. When char is the value, the functions are for Object.

~~Also there is boxing that could be avoided using more specialized function types, like Int2IntFunction instead of ToIntFunction<Integer>.~~