UnmodifiableList doesn't implement RandomAccess

[Peter Burka]

java.util.Collections.unmodifiableList() provides the following guarantee:

The returned list will be serializable if the specified list is serializable. Similarly, the returned list will implement RandomAccess if the specified list does.

It looks like IntLists.unmodifiableList(), LongLists.unmodifiableList(), etc., do not guarantee that the returned list will implement RandomAccess if the underlying list does. This means that operations, like java.util.Collections.binarySearch(), may be slower than expected if they're used on a fastutil UnmodifiableList.

The following program demonstrates this:

import java.util.RandomAccess;

import it.unimi.dsi.fastutil.longs.LongArrayList;

import it.unimi.dsi.fastutil.longs.LongList;

import it.unimi.dsi.fastutil.longs.LongLists;

public class Test

{

    public static void main(String[] args) {

        LongList l = new LongArrayList();

        System.out.println("Random? " + (l instanceof RandomAccess));

        LongList ul = LongLists.unmodifiable(l);

        System.out.println("Random? " + (ul instanceof RandomAccess));

    }

}

This prints:

Random? true
Random? false

(Tested with 7.0.13) 

While the current implementation is consistent with the fastutil documentation, it is inconsistent with java.util.Collections, and can cause unexpected performance problems (see above).

Could the unmodifiableList() implementations be updated so that the returned list implements RandomAccess if the underlying list does?

[seba]

Il giorno mercoledì 1 marzo 2017 22:28:12 UTC+1, Peter Burka ha scritto:

java.util.Collections.unmodifiableList() provides the following guarantee:

The returned list will be serializable if the specified list is serializable. Similarly, the returned list will implement RandomAccess if the specified list does.

It looks like IntLists.unmodifiableList(), LongLists.unmodifiableList(), etc., do not guarantee that the returned list will implement RandomAccess if the underlying list does. This means that operations, like java.util.Collections.binarySearch(), may be slower than expected if they're used on a fastutil UnmodifiableList.

This is so embarassing! It is fixed now--can you check the github current version? 

[Peter Burka]

Thanks! The changes look good.

When reviewing the JDK source, I note that they had to add some special handling to support deserializing UnmodifiableRandomAccessLists in pre-1.4 JDKs (prior to the introduction of RandomAccess). Since fastutil UnmodifiableLists are also serializable, the same issue could affect fastutil if someone serializes an unmodifiable random-access list with a new version of fastutil and tries to deserialize it with an older version. However I suspect that this is a very unlikely scenario.

[Sebastiano Vigna]

Il giorno giovedì 2 marzo 2017 16:47:26 UTC+1, Peter Burka ha scritto:

Thanks! The changes look good.

When reviewing the JDK source, I note that they had to add some special handling to support deserializing UnmodifiableRandomAccessLists in pre-1.4 JDKs (prior to the introduction of RandomAccess). Since fastutil UnmodifiableLists are also serializable, the same issue could affect fastutil if someone serializes an unmodifiable random-access list with a new version of fastutil and tries to deserialize it with an older version. However I suspect that this is a very unlikely scenario.

Yes. We are not so bound to backward compability as the language makers, thanks God. :)