vigna / fastutil Goto Github PK
View Code? Open in Web Editor NEWfastutil extends the Java™ Collections Framework by providing type-specific maps, sets, lists and queues.
License: Apache License 2.0
fastutil extends the Java™ Collections Framework by providing type-specific maps, sets, lists and queues.
License: Apache License 2.0
I was looking for the source of IntArrayList, and cannot find it in the repo. I did a repository search and found references to it, but there is no IntArrayList.java file. Is this a temporary thing, or am i missing something? Thank you. Love this library, btw.
LongArrayList.removeAll(LongCollection) only removes the first match, while ArrayList.removeAll(Collection) removes all matches.
List<Long> list = new ArrayList<>(Arrays.asList(1L, 2L, 3L, 4L, 1L, 2L, 3L, 4L));
list.removeAll(Arrays.asList(2L, 4L));
System.out.println(list);
returns [1, 3, 1, 3]
while
LongList list = new LongArrayList(new long[] { 1, 2, 3, 4, 1, 2, 3, 4 });
list.removeAll(Arrays.asList(2L, 4L));
System.out.println(list);
returns [1, 3, 1, 2, 3, 4]
The documentation doesn't really say if that is an expected behaviour (e.g. "removes first occurence")
This is the same issue as in #18 (When calling toArray(T[]) the element after the last one should be null), but now it's for YYYEmptyMap.entrySet().toArray(T[])
. See failing unit test here: https://github.com/gpanther/fastutil-guava-tests/blob/master/src/test/java/net/greypanther/fastutil/tests/Int2IntMapTest.java#L72
I think this is similar to issue #19:
@Test
public void testAddWithIterator() {
IntBigList list = new IntBigArrayBigList();
list.iterator().add(1);
assertEquals(IntBigLists.singleton(1), list);
}
This fails with an IllegalStateException in AbstractIntBigList line 151 (this is for fastutil 7.0.10).
From the documentation: https://docs.oracle.com/javase/8/docs/api/java/util/Collection.html#removeAll-java.util.Collection- (emphasis added):
"Removes all of this collection's elements that are also contained in the specified collection (optional operation). After this call returns, this collection will contain no elements in common with the specified collection."
This currently doesn't work for Lists where they only remove the first occurrences (the same seems to be true for BigLists). See tests at https://github.com/gpanther/fastutil-guava-tests/blob/37b76e/src/test/java/net/greypanther/fastutil/tests/IntArrayListTest.java#L68
A quick glance seems to indicate that the problem is that the method is implemented at AbstractXXXCollection level where it calls "rem" in a loop. Probably the solution would be to add "remAll" methods (both boxed and unboxed versions) at the collection level and call those from AbstractXXXCollection (for sets for example rem and remAll can contain identical implementations).
Regards,
Attila
This is just one example, but it will throw on all calls of remove / removeAll since *ArrayMap.EntrySet inherits from AbstractObjectSet which implements remove as throwing UnsupportedOperationException
.
@Test
public void testEntrySetSupportsRemoveAll() {
Int2IntMap map = new Int2IntArrayMap();
assertFalse(map.entrySet().removeAll(Collections.singleton("TEST")));
}
Hi! I decided to try modifying the makefile so to generate classes with different naming scheme, like this:
# The capitalized types used to build class and method names; boolean and object types are not listed.
TYPE_NOBOOL_NOOBJ=Byte Short Int Long Char Float Double
# The capitalized types used to build class and method names; boolean and reference are not listed.
TYPE_NOBOOL_NOREF=$(TYPE_NOBOOL_NOOBJ) Obj
# The capitalized types used to build class and method names; object types are not listed.
TYPE_NOOBJ=Boolean $(TYPE_NOBOOL_NOOBJ)
# The capitalized types used to build class and method names; references are not listed.
TYPE_NOREF=$(TYPE_NOOBJ) Obj
# The capitalized types used to build class and method names; boolean is not listed.
TYPE_NOBOOL=$(TYPE_NOBOOL_NOREF) Ref
# The capitalized types used to build class and method names; now references appear as Reference.
TYPE=$(TYPE_NOREF) Ref
# The capitalized types used to build class and method names; only types for which big structures are built are listed.
TYPE_BIG=Int Long Float Double Obj Ref
So you'd get something like Ref2ObjMap. Ideally I wanted it to be RefObjMap for example, removing the '2', names which are described in the same file.
The thing is that it seems to break code generation, for instance I get class definitions like:
public abstract class Abstract2BooleanFunction implements 2BooleanFunction , java.io.Serializable {
That ought to be AbstractSomething2BooleanFunction and Something2BooleanFunction, so compilation fails.
Also if I change TYPE_NOOBJ from Boolean to Bool, I get an error for a missing file:
./drv/BinIO.drv:157:63: fatal error: src/it/unimi/dsi/fastutil/io/BooleanBinIOFragment.h: No such file or directory
Since it seems the full name "BooleanBinIOFragment" is hardcoded in the BinIO.drv file. The generator instead creates BoolBinIOFragment, thus why it cant find it.
Any ideas on what might be wrong or what I am missing?
At 16 MB, fastutil is a pretty large package.
It would be nice to have a modularized version. For example, many users may not need the Big variants. I imagine that the Big variants add a considerable amount of size to fastutil.
I can also imagine that a lot of users only need double, int and long; but it seems difficult on where to draw a line for a "core" subset that most people use.
Right now, I'm still using Trove which is just 2.5 MB. I like trove iterators more than Java-compatible iterators (in particular for iterating over primitive maps, it.key()+it.value() are both readable and avoid boxing "Entry" objects), and whenever I tried to switch to fastutil, gsc, Koloboke/HFT I found a lot of code to be less elegant because of Java-style iterators. The other thing that is holding me back is the size. Fastutil for example would double the size of our project instantly.
As per the documentation:
ListIterator listIterator(int index) ... Throws: IndexOutOfBoundsException - if the index is out of range (index < 0 || index > size())
However the following tests fail:
@Test(expected=IndexOutOfBoundsException.class)
public void testListIterator_tooLow() {
new IntBigArrayBigList().listIterator(-1L);
}
@Test(expected=IndexOutOfBoundsException.class)
public void testListIterator_tooHigh() {
new IntBigArrayBigList().listIterator(1L);
}
Note that they pass in longs not ints. This calls listIterator( final long index )
from AbstractIntBigList
which does not have bounds checking (as opposed to the int version - listIterator( final int index )
on IntBigArrayBigList
which does). While the fix is simple (adding ensureIndex( index );
to the former), perhaps some kind of code reuse can be achieved here (why isn't the method with int just calling the long method? why does it need a different implementation?)
Hi,
i need to use fastutil in my thesys project, but i need to use a jar of it that will be imported; i try with the usual command mvn package but it is still empty. Can someone help me with this issue?
Thanks in advance
dequeue???
should throw NoSuchElementException if there is no element in the queue like dequeueLast???
. ???
is the primitive type name.
Alternatively have 2 methods like in Java where on rentuns a special value and another throws an exception. (https://docs.oracle.com/javase/7/docs/api/java/util/Queue.html)
map.putIfAbsent(k, v): v
map.replace(k): v
map.replace(k, v): boolean
map.remove(k, v): boolean
Even not talking about lambda-accepting methods, putIfAbsent()
is a painfully missing part.
Hello!
I use fastutil
in several projects with the types often appearing as part of published APIs. As fastutil
is a healthy project with frequent releases, I often have to update version numbers. Is it safe to assume that fastutil
is using semantic versioning? It seems like it is, given how the version numbers have changed over time, but I don't see an explicit policy written down anywhere. With an explicit policy in place, I can use version ranges in dependencies to make it easier to stay up-to-date.
Seems this website is down. I am unable to access javadocs online
I would like to introduce the idea that fastutil should support recyclable iterators. That is, when calling the iterator()
method, the same iterator object should be returned but reset to the start.
When trying to avoid allocations, it's clear that escape analysis can remove these allocations, but that means nothing when trying to profile the application, all I can see is these iterators because escape analysis is turned off by the profiler so I just fallback to using elements()
where I can.
As long as the collections are not being paired with a lock, it seems like this is pretty straightforward. For the synchronized collections, this might be complicated. Although a lock must be held for the duration of the iteration, the iterator itself might be retained beyond the scope of the lock, and then be used again when the lock is re-acquired
I have been unable to build the latest code on Windows 7 64-bit. My terminal is Cygwin bash, the latest Apache Ant is the main tool being used, and Maven is installed but doesn't seem to be involved with the build. I don't have Ivy installed and I'm not sure if I need it. I put jUnit and Emma (which seems to no longer be needed) in my ~/.ant/lib/ directory, though I have no idea what file names they should have, or what versions to use. I just downloaded a fresh copy of the fastutil sources that incorporate the changes made a few hours ago, and ran make sources
without errors or warnings. Running ant jar
from Cygwin bash in the root of the downloaded sources gives me a large list of errors.
$ /cygdrive/c/dev/ant/bin/ant jar
Buildfile: C:\Users\User\Downloads\fastutil-master\fastutil-master\build.xml
init:
[mkdir] Created dir: C:\Users\User\Downloads\fastutil-master\fastutil-master\build
[mkdir] Created dir: C:\Users\User\Downloads\fastutil-master\fastutil-master\dist\lib
compile:
[javac] Compiling 1878 source files to C:\Users\User\Downloads\fastutil-master\fastutil-master\build
[javac] warning: [options] bootstrap class path not set in conjunction with -source 1.7
[javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\bytes\Byte2BooleanLinkedOpenHashMap.java:24: error: class, interface, or enum expected
[javac] OpenHashMap.drv
[javac] ^
[javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\bytes\Byte2BooleanOpenCustomHashMap.java:28: error: class, interface, or enum expected
[javac] OpenHashMap.drv
[javac] ^
[javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\bytes\Byte2ByteLinkedOpenHashMap.java:24: error: class, interface, or enum expected
[javac] OpenHashMap.drv
[javac] ^
[javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\bytes\Byte2ByteOpenCustomHashMap.java:28: error: class, interface, or enum expected
[javac] OpenHashMap.drv
[javac] ^
[javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\bytes\Byte2CharLinkedOpenHashMap.java:24: error: class, interface, or enum expected
[javac] OpenHashMap.drv
[javac] ^
[javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\bytes\Byte2CharOpenCustomHashMap.java:28: error: class, interface, or enum expected
[javac] OpenHashMap.drv
[javac] ^
[javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\bytes\Byte2DoubleLinkedOpenHashMap.java:24: error: class, interface, or enum expected
[javac] OpenHashMap.drv
[javac] ^
[javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\bytes\Byte2DoubleOpenCustomHashMap.java:28: error: class, interface, or enum expected
[javac] OpenHashMap.drv
[javac] ^
[javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\bytes\Byte2FloatLinkedOpenHashMap.java:24: error: class, interface, or enum expected
[javac] OpenHashMap.drv
[javac] ^
[javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\bytes\Byte2FloatOpenCustomHashMap.java:28: error: class, interface, or enum expected
[javac] OpenHashMap.drv
[javac] ^
[javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\bytes\Byte2IntLinkedOpenHashMap.java:24: error: class, interface, or enum expected
[javac] OpenHashMap.drv
[javac] ^
[javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\bytes\Byte2IntOpenCustomHashMap.java:28: error: class, interface, or enum expected
[javac] OpenHashMap.drv
[javac] ^
[javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\bytes\Byte2LongLinkedOpenHashMap.java:24: error: class, interface, or enum expected
[javac] OpenHashMap.drv
[javac] ^
[javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\bytes\Byte2LongOpenCustomHashMap.java:28: error: class, interface, or enum expected
[javac] OpenHashMap.drv
[javac] ^
[javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\bytes\Byte2ObjectLinkedOpenHashMap.java:23: error: class, interface, or enum expected
[javac] OpenHashMap.drv
[javac] ^
[javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\bytes\Byte2ObjectOpenCustomHashMap.java:27: error: class, interface, or enum expected
[javac] OpenHashMap.drv
[javac] ^
[javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\bytes\Byte2ReferenceLinkedOpenHashMap.java:23: error: class, interface, or enum expected
[javac] OpenHashMap.drv
[javac] ^
[javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\bytes\Byte2ReferenceOpenCustomHashMap.java:27: error: class, interface, or enum expected
[javac] OpenHashMap.drv
[javac] ^
[javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\bytes\Byte2ShortLinkedOpenHashMap.java:24: error: class, interface, or enum expected
[javac] OpenHashMap.drv
[javac] ^
[javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\bytes\Byte2ShortOpenCustomHashMap.java:28: error: class, interface, or enum expected
[javac] OpenHashMap.drv
[javac] ^
[javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\bytes\ByteLinkedOpenCustomHashSet.java:23: error: class, interface, or enum expected
[javac] OpenHashSet.drv
[javac] ^
[javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\bytes\ByteLinkedOpenHashSet.java:23: error: class, interface, or enum expected
[javac] OpenHashSet.drv
[javac] ^
[javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\bytes\ByteOpenCustomHashSet.java:27: error: class, interface, or enum expected
[javac] OpenHashSet.drv
[javac] ^
[javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\chars\Char2BooleanLinkedOpenHashMap.java:24: error: class, interface, or enum expected
[javac] OpenHashMap.drv
[javac] ^
[javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\chars\Char2BooleanOpenCustomHashMap.java:28: error: class, interface, or enum expected
[javac] OpenHashMap.drv
[javac] ^
[javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\chars\Char2ByteLinkedOpenHashMap.java:24: error: class, interface, or enum expected
[javac] OpenHashMap.drv
[javac] ^
[javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\chars\Char2ByteOpenCustomHashMap.java:28: error: class, interface, or enum expected
[javac] OpenHashMap.drv
[javac] ^
[javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\chars\Char2CharLinkedOpenHashMap.java:24: error: class, interface, or enum expected
[javac] OpenHashMap.drv
[javac] ^
[javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\chars\Char2CharOpenCustomHashMap.java:28: error: class, interface, or enum expected
[javac] OpenHashMap.drv
[javac] ^
[javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\chars\Char2DoubleLinkedOpenHashMap.java:24: error: class, interface, or enum expected
[javac] OpenHashMap.drv
[javac] ^
[javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\chars\Char2DoubleOpenCustomHashMap.java:28: error: class, interface, or enum expected
[javac] OpenHashMap.drv
[javac] ^
[javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\chars\Char2FloatLinkedOpenHashMap.java:24: error: class, interface, or enum expected
[javac] OpenHashMap.drv
[javac] ^
[javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\chars\Char2FloatOpenCustomHashMap.java:28: error: class, interface, or enum expected
[javac] OpenHashMap.drv
[javac] ^
[javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\chars\Char2IntLinkedOpenHashMap.java:24: error: class, interface, or enum expected
[javac] OpenHashMap.drv
[javac] ^
[javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\chars\Char2IntOpenCustomHashMap.java:28: error: class, interface, or enum expected
[javac] OpenHashMap.drv
[javac] ^
[javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\chars\Char2LongLinkedOpenHashMap.java:24: error: class, interface, or enum expected
[javac] OpenHashMap.drv
[javac] ^
[javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\chars\Char2LongOpenCustomHashMap.java:28: error: class, interface, or enum expected
[javac] OpenHashMap.drv
[javac] ^
[javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\chars\Char2ObjectLinkedOpenHashMap.java:23: error: class, interface, or enum expected
[javac] OpenHashMap.drv
[javac] ^
[javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\chars\Char2ObjectOpenCustomHashMap.java:27: error: class, interface, or enum expected
[javac] OpenHashMap.drv
[javac] ^
[javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\chars\Char2ReferenceLinkedOpenHashMap.java:23: error: class, interface, or enum expected
[javac] OpenHashMap.drv
[javac] ^
[javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\chars\Char2ReferenceOpenCustomHashMap.java:27: error: class, interface, or enum expected
[javac] OpenHashMap.drv
[javac] ^
[javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\chars\Char2ShortLinkedOpenHashMap.java:24: error: class, interface, or enum expected
[javac] OpenHashMap.drv
[javac] ^
[javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\chars\Char2ShortOpenCustomHashMap.java:28: error: class, interface, or enum expected
[javac] OpenHashMap.drv
[javac] ^
[javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\chars\CharLinkedOpenCustomHashSet.java:23: error: class, interface, or enum expected
[javac] OpenHashSet.drv
[javac] ^
[javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\chars\CharLinkedOpenHashSet.java:23: error: class, interface, or enum expected
[javac] OpenHashSet.drv
[javac] ^
[javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\chars\CharOpenCustomHashSet.java:27: error: class, interface, or enum expected
[javac] OpenHashSet.drv
[javac] ^
[javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\doubles\Double2BooleanLinkedOpenHashMap.java:24: error: class, interface, or enum expected
[javac] OpenHashMap.drv
[javac] ^
[javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\doubles\Double2BooleanOpenCustomHashMap.java:28: error: class, interface, or enum expected
[javac] OpenHashMap.drv
[javac] ^
[javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\doubles\Double2ByteLinkedOpenHashMap.java:24: error: class, interface, or enum expected
[javac] OpenHashMap.drv
[javac] ^
[javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\doubles\Double2ByteOpenCustomHashMap.java:28: error: class, interface, or enum expected
[javac] OpenHashMap.drv
[javac] ^
[javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\doubles\Double2CharLinkedOpenHashMap.java:24: error: class, interface, or enum expected
[javac] OpenHashMap.drv
[javac] ^
[javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\doubles\Double2CharOpenCustomHashMap.java:28: error: class, interface, or enum expected
[javac] OpenHashMap.drv
[javac] ^
[javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\doubles\Double2DoubleLinkedOpenHashMap.java:24: error: class, interface, or enum expected
[javac] OpenHashMap.drv
[javac] ^
[javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\doubles\Double2DoubleOpenCustomHashMap.java:28: error: class, interface, or enum expected
[javac] OpenHashMap.drv
[javac] ^
[javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\doubles\Double2FloatLinkedOpenHashMap.java:24: error: class, interface, or enum expected
[javac] OpenHashMap.drv
[javac] ^
[javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\doubles\Double2FloatOpenCustomHashMap.java:28: error: class, interface, or enum expected
[javac] OpenHashMap.drv
[javac] ^
[javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\doubles\Double2IntLinkedOpenHashMap.java:24: error: class, interface, or enum expected
[javac] OpenHashMap.drv
[javac] ^
[javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\doubles\Double2IntOpenCustomHashMap.java:28: error: class, interface, or enum expected
[javac] OpenHashMap.drv
[javac] ^
[javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\doubles\Double2LongLinkedOpenHashMap.java:24: error: class, interface, or enum expected
[javac] OpenHashMap.drv
[javac] ^
[javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\doubles\Double2LongOpenCustomHashMap.java:28: error: class, interface, or enum expected
[javac] OpenHashMap.drv
[javac] ^
[javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\doubles\Double2ObjectLinkedOpenHashMap.java:23: error: class, interface, or enum expected
[javac] OpenHashMap.drv
[javac] ^
[javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\doubles\Double2ObjectOpenCustomHashMap.java:27: error: class, interface, or enum expected
[javac] OpenHashMap.drv
[javac] ^
[javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\doubles\Double2ReferenceLinkedOpenHashMap.java:23: error: class, interface, or enum expected
[javac] OpenHashMap.drv
[javac] ^
[javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\doubles\Double2ReferenceOpenCustomHashMap.java:27: error: class, interface, or enum expected
[javac] OpenHashMap.drv
[javac] ^
[javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\doubles\Double2ShortLinkedOpenHashMap.java:24: error: class, interface, or enum expected
[javac] OpenHashMap.drv
[javac] ^
[javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\doubles\Double2ShortOpenCustomHashMap.java:28: error: class, interface, or enum expected
[javac] OpenHashMap.drv
[javac] ^
[javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\doubles\DoubleLinkedOpenCustomHashSet.java:23: error: class, interface, or enum expected
[javac] OpenHashSet.drv
[javac] ^
[javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\doubles\DoubleLinkedOpenHashSet.java:23: error: class, interface, or enum expected
[javac] OpenHashSet.drv
[javac] ^
[javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\doubles\DoubleOpenCustomHashSet.java:27: error: class, interface, or enum expected
[javac] OpenHashSet.drv
[javac] ^
[javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\floats\Float2BooleanLinkedOpenHashMap.java:24: error: class, interface, or enum expected
[javac] OpenHashMap.drv
[javac] ^
[javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\floats\Float2BooleanOpenCustomHashMap.java:28: error: class, interface, or enum expected
[javac] OpenHashMap.drv
[javac] ^
[javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\floats\Float2ByteLinkedOpenHashMap.java:24: error: class, interface, or enum expected
[javac] OpenHashMap.drv
[javac] ^
[javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\floats\Float2ByteOpenCustomHashMap.java:28: error: class, interface, or enum expected
[javac] OpenHashMap.drv
[javac] ^
[javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\floats\Float2CharLinkedOpenHashMap.java:24: error: class, interface, or enum expected
[javac] OpenHashMap.drv
[javac] ^
[javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\floats\Float2CharOpenCustomHashMap.java:28: error: class, interface, or enum expected
[javac] OpenHashMap.drv
[javac] ^
[javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\floats\Float2DoubleLinkedOpenHashMap.java:24: error: class, interface, or enum expected
[javac] OpenHashMap.drv
[javac] ^
[javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\floats\Float2DoubleOpenCustomHashMap.java:28: error: class, interface, or enum expected
[javac] OpenHashMap.drv
[javac] ^
[javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\floats\Float2FloatLinkedOpenHashMap.java:24: error: class, interface, or enum expected
[javac] OpenHashMap.drv
[javac] ^
[javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\floats\Float2FloatOpenCustomHashMap.java:28: error: class, interface, or enum expected
[javac] OpenHashMap.drv
[javac] ^
[javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\floats\Float2IntLinkedOpenHashMap.java:24: error: class, interface, or enum expected
[javac] OpenHashMap.drv
[javac] ^
[javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\floats\Float2IntOpenCustomHashMap.java:28: error: class, interface, or enum expected
[javac] OpenHashMap.drv
[javac] ^
[javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\floats\Float2LongLinkedOpenHashMap.java:24: error: class, interface, or enum expected
[javac] OpenHashMap.drv
[javac] ^
[javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\floats\Float2LongOpenCustomHashMap.java:28: error: class, interface, or enum expected
[javac] OpenHashMap.drv
[javac] ^
[javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\floats\Float2ObjectLinkedOpenHashMap.java:23: error: class, interface, or enum expected
[javac] OpenHashMap.drv
[javac] ^
[javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\floats\Float2ObjectOpenCustomHashMap.java:27: error: class, interface, or enum expected
[javac] OpenHashMap.drv
[javac] ^
[javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\floats\Float2ReferenceLinkedOpenHashMap.java:23: error: class, interface, or enum expected
[javac] OpenHashMap.drv
[javac] ^
[javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\floats\Float2ReferenceOpenCustomHashMap.java:27: error: class, interface, or enum expected
[javac] OpenHashMap.drv
[javac] ^
[javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\floats\Float2ShortLinkedOpenHashMap.java:24: error: class, interface, or enum expected
[javac] OpenHashMap.drv
[javac] ^
[javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\floats\Float2ShortOpenCustomHashMap.java:28: error: class, interface, or enum expected
[javac] OpenHashMap.drv
[javac] ^
[javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\floats\FloatLinkedOpenCustomHashSet.java:23: error: class, interface, or enum expected
[javac] OpenHashSet.drv
[javac] ^
[javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\floats\FloatLinkedOpenHashSet.java:23: error: class, interface, or enum expected
[javac] OpenHashSet.drv
[javac] ^
[javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\floats\FloatOpenCustomHashSet.java:27: error: class, interface, or enum expected
[javac] OpenHashSet.drv
[javac] ^
[javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\ints\Int2BooleanLinkedOpenHashMap.java:24: error: class, interface, or enum expected
[javac] OpenHashMap.drv
[javac] ^
[javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\ints\Int2BooleanOpenCustomHashMap.java:28: error: class, interface, or enum expected
[javac] OpenHashMap.drv
[javac] ^
[javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\ints\Int2ByteLinkedOpenHashMap.java:24: error: class, interface, or enum expected
[javac] OpenHashMap.drv
[javac] ^
[javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\ints\Int2ByteOpenCustomHashMap.java:28: error: class, interface, or enum expected
[javac] OpenHashMap.drv
[javac] ^
[javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\ints\Int2CharLinkedOpenHashMap.java:24: error: class, interface, or enum expected
[javac] OpenHashMap.drv
[javac] ^
[javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\ints\Int2CharOpenCustomHashMap.java:28: error: class, interface, or enum expected
[javac] OpenHashMap.drv
[javac] ^
[javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\ints\Int2DoubleLinkedOpenHashMap.java:24: error: class, interface, or enum expected
[javac] OpenHashMap.drv
[javac] ^
[javac] C:\Users\User\Downloads\fastutil-master\fastutil-master\src\it\unimi\dsi\fastutil\ints\Int2DoubleOpenCustomHashMap.java:28: error: class, interface, or enum expected
[javac] OpenHashMap.drv
[javac] ^
[javac] 100 errors
[javac] 1 warning
BUILD FAILED
C:\Users\User\Downloads\fastutil-master\fastutil-master\build.xml:136: Compile failed; see the compiler error output for details.
Total time: 3 seconds
The last file in that list of errors has unusual contents, and doesn't appear to be valid Java.
/* Generic definitions */
/* Assertions (useful to generate conditional code) */
/* Current type and class (and size, if applicable) */
/* Value methods */
/* Interfaces (keys) */
/* Interfaces (values) */
/* Abstract implementations (keys) */
/* Abstract implementations (values) */
/* Static containers (keys) */
/* Static containers (values) */
/* Implementations */
/* Synchronized wrappers */
/* Unmodifiable wrappers */
/* Other wrappers */
/* Methods (keys) */
/* Methods (values) */
/* Methods (keys/values) */
/* Methods that have special names depending on keys (but the special names depend on values) */
/* Equality */
/* Object/Reference-only definitions (keys) */
/* Primitive-type-only definitions (keys) */
/* Object/Reference-only definitions (values) */
/* Primitive-type-only definitions (values) */
OpenHashMap.drv
This only appears to affect LinkedOpenHashMap and OpenCustomHashMap implementations, though ant may be cutting the build short at 100 errors and more files may be missing implementations.
I suspect this has something to do with the literal string "OpenHashMap.drv" being inserted on Windows, instead of doing what the build should be doing and inserting the contents of that file, probably with preprocessing applied. I'd be happy to try different configurations of toolchain to get this to work.
I'm currently working around this by using the extracted sources jar from Maven for the latest release ( 7.0.10 ). I'm only using a fraction of the classes, so I've semi-manually moved any classes I don't use into an unused directory and copied the used classes into the source tree of my main library. Thanks for all your hard work on fastutil, and for the xorshift benchmarks and algorithms!
See unittest here: https://github.com/gpanther/fastutil-guava-tests/blob/b154514cbaee3c06353d2c50a9babe77a21ddc6b/src/test/java/net/greypanther/fastutil/tests/Int2IntMapTest.java#L63
The problem seems to be that Maps.Singleton does not check the types of the Map.Entry it gets (IMHO it should do an instanceof check on both key and value which would also weed out null values):
Line 166 in 0740dcd
The following simple program doesn't compile in JDK8 with eclipse:
import java.util.HashMap;
import java.util.Map;
public class Test {
public static void main(String[] args) {
Map<Long, Double> map = new HashMap();
System.out.println(Long2DoubleArrayMap(map));
}
}
As the documentation states there should be a constructor for Long2DoubleArrayMap(Map<? extends Long,? extends Double> m)
.
I am probably missing something very basic. Newbe here.
Thanks
Does parallel Quicksort require extra memory? And if so, how much?
There is a note on sequential Quicksort indicating that it does not. However parallel Quicksort does not have this note.
Looking forward to a reply!
Since the collections declare that they implement the corresponding java.util.Collection interface (ie. IntSet implements Set), they should handle nulls gracefully. See tests here:
https://github.com/gpanther/fastutil-guava-tests/blob/c16625d/src/test/java/net/greypanther/fastutil/tests/IntArrayListTest.java#L46
https://github.com/gpanther/fastutil-guava-tests/blob/c16625d/src/test/java/net/greypanther/fastutil/tests/IntArraySetTest.java
Ie. don't throw exception when .contains(null) is called (rather return false).
Note: throwing null for contains / containsAll / removeAll / retainAll IS allowed by the wording on collections (see https://docs.oracle.com/javase/8/docs/api/java/util/Collection.html#retainAll-java.util.Collection- - "NullPointerException - if this collection contains one or more null elements and the specified collection does not permit null elements (optional), or if the specified collection is null") so perhaps the only thing needs fixing here is the equals method for sets (the second link in the above case). I only gave the example for IntArraySet but the same problem is exhibited by the other set implementations also.
Regards,
Attila
Is it possible to add this interface to existing fastutil (AVL,RB)TreeSet implementations? The lower
and ceiling
methods can be mimicked with calls to headSet().last()
and tailSet().first()
respectively, but they probably wouldn't be as fast, and the higher
and floor
methods cannot be mimicked easily at all.
@Test
public void testMapValuesShouldSupportClear() {
Int2IntMap map = new Int2IntArrayMap(Int2IntMaps.singleton(42, 24));
map.values().clear();
assertTrue(map.isEmpty());
}
@Test
public void testMapValuesShouldSupportRemove() {
Int2IntMap map = new Int2IntArrayMap(Int2IntMaps.singleton(42, 24));
map.values().remove(24);
assertTrue(map.isEmpty());
}
@Test
public void testMapValuesShouldSupportRemoveAll() {
Int2IntMap map = new Int2IntArrayMap(Int2IntMaps.singleton(42, 24));
map.values().removeAll(Collections.singleton(24));
assertTrue(map.isEmpty());
}
(note that it is ok to throw on add / addAll).
This also works as expected on OpenHashMaps, so the issue seems limited to ArrayMaps.
`
@test
public void testSubSet() {
final Long2LongAVLTreeMap long2LongAVLTreeMap = new Long2LongAVLTreeMap();
final Long2ObjectAVLTreeMap long2ObjectAVLTreeMap = new Long2ObjectAVLTreeMap<>();
testSubSet(long2LongAVLTreeMap, long2ObjectAVLTreeMap);
}
void testSubSet(AbstractLong2LongSortedMap long2LongAVLTreeMap, AbstractLong2ObjectSortedMap long2ObjectAVLTreeMap) {
final TreeMap<Long, Long> treeMap = new TreeMap<>();
final long[] input = {1, 2, 3, 4, 5};
for (long l : input) {
treeMap.put(l, l);
long2LongAVLTreeMap.put(l, l);
long2ObjectAVLTreeMap.put(l, (Long) l);
}
for (long fromKey = 0; fromKey < 7; fromKey++) {
for (long toKey = fromKey; toKey < 8; toKey++) {
// SubMap
final Long2LongSortedMap long2LongSubmap = long2LongAVLTreeMap.subMap(fromKey, toKey);
final Long2ObjectSortedMap<Long> long2ObjectSubmap = long2ObjectAVLTreeMap.subMap(fromKey, toKey);
final NavigableMap<Long, Long> treeSubmap = treeMap.subMap(fromKey, true, toKey, false);
compare(long2LongSubmap, long2ObjectSubmap, treeSubmap);
// Head
final Long2LongSortedMap long2LongHead = long2LongAVLTreeMap.headMap(fromKey);
final Long2ObjectSortedMap<Long> long2ObjectHead = long2ObjectAVLTreeMap.headMap(fromKey);
final NavigableMap<Long, Long> treeHead = treeMap.headMap(fromKey, false);
compare(long2LongHead, long2ObjectHead, treeHead);
// Tail
final Long2LongSortedMap long2LongTail = long2LongAVLTreeMap.tailMap(toKey);
final Long2ObjectSortedMap<Long> long2ObjectTail = long2ObjectAVLTreeMap.tailMap(toKey);
final NavigableMap<Long, Long> treeTail = treeMap.tailMap(toKey, true);
compare(long2LongTail, long2ObjectTail, treeTail);
// Subset Subset/Had/Tail
if (treeSubmap.isEmpty()) continue;
final ObjectSortedSet<Map.Entry<Long, Long>> long2LongEntries = long2LongSubmap.entrySet();
final ObjectSortedSet<Map.Entry<Long, Long>> long2ObjectEntries = long2ObjectSubmap.entrySet();
final Map.Entry<Long, Long> firstL = long2LongEntries.first();
final Map.Entry<Long, Long> lastL = long2LongEntries.last();
assertNotNull(firstL);
assertNotNull(lastL);
final Map.Entry<Long, Long> firstO = long2ObjectEntries.first();
final Map.Entry<Long, Long> lastO = long2ObjectEntries.last();
assertNotNull(firstL);
assertNotNull(lastL);
// Subset
final List<Long> ss1 = long2LongEntries.subSet(firstL, lastL)
.stream().map(kv -> kv.getKey()).collect(Collectors.toList());
final List<Long> ss2 = long2ObjectEntries.subSet(firstO, lastO)
.stream().map(kv -> kv.getKey()).collect(Collectors.toList());
assertEquals(ss1, ss2);
// Head
final List<Long> h1 = long2LongEntries.headSet(firstL)
.stream().map(kv -> kv.getKey()).collect(Collectors.toList());
final List<Long> h2 = long2ObjectEntries.headSet(firstO)
.stream().map(kv -> kv.getKey()).collect(Collectors.toList());
assertEquals(h1, h2);
// Tail
final List<Long> t1 = long2LongEntries.tailSet(firstL)
.stream().map(kv -> kv.getKey()).collect(Collectors.toList());
final List<Long> t2 = long2ObjectEntries.tailSet(lastO)
.stream().map(kv -> kv.getKey()).collect(Collectors.toList());
assertEquals(t1, t2);
}
}
void compare(
Long2LongSortedMap long2LongAVLTreeMap,
SortedMap<Long, Long> long2ObjectAVLTreeMap,
NavigableMap<Long, Long> treeMap) {
List list1 = new ArrayList<>(long2LongAVLTreeMap.keySet());
List list2 = new ArrayList<>(long2ObjectAVLTreeMap.keySet());
List list3 = new ArrayList<>(treeMap.keySet());
assertEquals(list1, list2);
assertEquals(list2, list3);
}
`
Fails on tail result comparison:
Expected :[1, 2]
Actual :[2]
I am seeing a lot of allocations from the open hash set and map classes. For this use case I am using the ACT pattern to keep track of information for requests.
ACT
by inserting into a Int2ObjectOpenHashMap
This is causing a massive amount of allocations because the map is constantly being halved and then moments later is doubled in size. This behavior is indeed documented:
If the table is emptied below one fourth of the load factor, it is halved in size
but I still feel this behavior is unwarranted because:
Int2IntOpenHashMap m = new Int2IntOpenHashMap(4_096);
m.put(1, 1);
m.remove(1);
This has the following impact on my code:
fastutil
7.0.11, this is causing several hundreds of GiBs worth of allocations per second with pauses ranging in the 200-400 milliseconds per second. In this case I am fortunate because I can work around it using clear
fastutil
6.6.3. This application I thought was allocation free once it reached the steady state but because of this it makes about 1 MiB/s worth of allocations resulting in about 2 pauses of 8 ms each per minute.The following code reproduces the issue in case I am not being clear:
import it.unimi.dsi.fastutil.ints.Int2IntOpenHashMap;
import org.junit.Test;
import static org.junit.Assert.*;
public class RehashTest {
@Test
public void test() {
Int2IntOpenHashMap m = new Int2IntOpenHashMap();
for (int i = 0; i < 100_000_000; i++) {
for (int j = 0; j < 1_000; j++) {
m.put(j, j);
}
for (int j = 0; j < 1_000; j++) {
m.remove(j, j);
}
}
}
}
I am willing to provide the patch for this myself if there is interest. The solution is just not to rehash on remove
, e.g., replace this
private V removeEntry(final int pos) {
final V oldValue = value[pos];
value[pos] = null;
size--;
shiftKeys(pos);
if (size < maxFill / 4 && n > DEFAULT_INITIAL_SIZE) rehash(n / 2);
return oldValue;
}
with
private V removeEntry(final int pos) {
final V oldValue = value[pos];
value[pos] = null;
size--;
shiftKeys(pos);
return oldValue;
}
For completeness, I also looked at Agrona
, its maps do not rehash on removal
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:
Object2ObjectOpenHashMap
in "random" order requires some amount of calls to equals()
in the inserted Objects.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, WrappedString
s 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.
I see this in in the IterableCollection of DoubleCollections and IntCollections, didnt check any further:
public boolean isEmpty() {
return iterable.iterator().hasNext();
}
I think, there is a missing negation. Because this actually tells me, the iterable is not empty. Or am i missing something? :)
Java 8 introduced support for primitive iterators to avoid costs for boxing and unboxing values during iteration: Documentation. This is very similar to the existing IntIterator
, LongIterator
, and DoubleIterator
. In order to improve compatibility with the standard Java Collection Framework I propose changing the IntIterator
declaration from
public interface IntIterator extends Iterator<Integer>
to
public interface IntIterator extends PrimitiveIterator.OfInt
and analogously the two other interfaces. The obvious drawback of this is that the minimum requirement for fastutil gets bumped up to Java 8.
if there is enough space in the passed-in array. Documented here: https://docs.oracle.com/javase/8/docs/api/java/util/Collection.html#toArray-T:A-
"If this collection fits in the specified array with room to spare (i.e., the array has more elements than this collection), the element in the array immediately following the end of the collection is set to null. (This is useful in determining the length of this collection only if the caller knows that this collection does not contain any null elements.)"
Test showing that fastutil does not respect this: https://github.com/gpanther/fastutil-guava-tests/blob/bea3e/src/test/java/net/greypanther/fastutil/tests/IntArrayListTest.java#L30
Regards,
Attila
Hi,
I'm trying to sort a set of integers that represents row indexes in a 'table' object, according to the values in the table, with the sorting logic provided by a comparator.
I have run a side-by-side test using java.util.Collections and it.unimi.dsi.fastutil.Arrays. A visual inspection confirms that the Collections#sort produces the expected order. Here is the code from the test:
table1 = StorageManager.readTable("bigdata/airlines");
table2 = StorageManager.readTable("bigdata/airlines");
// This is just used to create a comparator below
Sort key = Table.getSort("ORIGIN");
// first try, with Collections.sort.
IntComparator rowComparator = table1.getComparator(key);
IntArrayList t1rows = table1.rows();
Collections.sort(t1rows, rowComparator);
// second try, with Arrays.quicksort()
IntComparator rowComparator2 = table2.getComparator(key);
IntArrayList t2rows = table2.rows();
int[] values = t2rows.elements();
Arrays.quickSort(0, t2rows.size(), rowComparator2, new Swapper() {
@Override
public void swap(int a, int b) {
int temp = values[a];
values[a] = values[b];
values[b] = temp;
}
});
// This assert fails. The arrays are sorted in a completely different order.
assertTrue(java.util.Arrays.equals(values, t1rows.elements()));
My first thought was that there is a bug in my swap routine, but I can't see it.
This is the comparator being used:
public final IntComparator rowComparator = new IntComparator() {
@Override
public int compare(int i, int i1) {
return getString(i).compareTo(getString(i1));
}
@Override
public int compare(Integer i, Integer i1) {
return getString(i).compareTo(getString(i1));
}
};
The method is defined such that the row indexes from the sort column ("ORIGIN") are compared according to the standard lexicographical sort on the string values of that column.
Any suggestions would be very much appreciated. If you agree that this seems like a bug, I can try to provide a simple executable test case to recreate.
I've looked into source code for SynchronizedMap and I'm not sure it's implemented correctly:
public LongSet keySet() {
if ( keys == null ) keys = LongSets.synchronize( map.keySet(), sync );
return keys;
}
}
If multiple threads call this method at the same time, than mutliple LongSet
instances might be created. They are thread-safe, so nothing bad will happen, but still it feels not right.
Moreover another method never sets the values
variable:
public ObjectCollection<V> values() {
if ( values == null ) return ObjectCollections.synchronize( map.values(), sync );
return values;
}
Java's implementation in java.util.Collections.SynchronizedMap
synchronizes the whole method:
public Set<K> keySet() {
synchronized (mutex) {
if (keySet==null)
keySet = new SynchronizedSet<>(m.keySet(), mutex);
return keySet;
}
}
A tiny issue: build.xml references the missing emma_ant.properties
around line 124 which prints the warning:
[taskdef] Could not load definitions from resource emma_ant.properties. It could not be found.
YYYLinkedOpenHashSet
declares that it implements SortedSet
, however it breaks [the contract for the comparator
method|https://docs.oracle.com/javase/8/docs/api/java/util/SortedSet.html#comparator--] which states that:
Returns the comparator used to order the elements in this set, or null if this set uses the natural ordering of its elements.
However YYYLinkedOpenHashSet
always returns null, even though it should return a comparator which does something like: "if element A was inserted before B then return -1, if B was inserted before A return 1 else return 0" (ie. don't use the "natural order" but rather use the "insertion order").
See a failing unittest [here|https://github.com/gpanther/fastutil-guava-tests/blob/master/src/test/java/net/greypanther/fastutil/tests/Int2IntSortedSetTest.java#L13].
An other option to implementing the above comparator (which is not-very-fast) is for YYYLinkedOpenHashSet
to just not implement SortedSet
(as java.util.LinkedHashSet
does it).
@Test
public void testRemoveAllModifiesCollection() {
IntBigList list = new IntBigArrayBigList();
assertFalse(list.removeAll(Collections.emptySet()));
assertEquals(IntBigLists.EMPTY_BIG_LIST, list);
}
The first assertion fails because removeAll return true (even though it should return false since the collection was not modified). But even if we ignore that assertion, it errors out at the second assert since "removing nothing" suddenly populated the BitList with [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
😄.
When installing from sources on OS X, make sources fails with the following errors:
`./gencsource.sh drv/Iterable.drv src/it/unimi/dsi/fastutil/booleans/BooleanIterable.c >src/it/unimi/dsi/fastutil/booleans/BooleanIterable.c
gcc -w -I. -ftabstop=4 -DASSERTS_VALUE=false -E -C -P src/it/unimi/dsi/fastutil/booleans/BooleanIterable.c >src/it/unimi/dsi/fastutil/booleans/BooleanIterable.java
src/it/unimi/dsi/fastutil/booleans/BooleanIterable.c:7:2: error: invalid preprocessing directive
^
src/it/unimi/dsi/fastutil/booleans/BooleanIterable.c:8:2: error: invalid preprocessing directive
^
src/it/unimi/dsi/fastutil/booleans/BooleanIterable.c:9:2: error: invalid preprocessing directive
^
src/it/unimi/dsi/fastutil/booleans/BooleanIterable.c:10:3: error: invalid preprocessing directive
#assert keys(primitive)
^
src/it/unimi/dsi/fastutil/booleans/BooleanIterable.c:11:2: error: invalid preprocessing directive
^
src/it/unimi/dsi/fastutil/booleans/BooleanIterable.c:12:2: error: invalid preprocessing directive
^
src/it/unimi/dsi/fastutil/booleans/BooleanIterable.c:13:2: error: invalid preprocessing directive
^
src/it/unimi/dsi/fastutil/booleans/BooleanIterable.c:14:3: error: invalid preprocessing directive
#assert values(reference)
^
src/it/unimi/dsi/fastutil/booleans/BooleanIterable.c:20:5: error: invalid token at start of a preprocessor expression
^
src/it/unimi/dsi/fastutil/booleans/BooleanIterable.c:53:5: error: invalid token at start of a preprocessor expression
^
src/it/unimi/dsi/fastutil/booleans/BooleanIterable.c:72:5: error: invalid token at start of a preprocessor expression
^
src/it/unimi/dsi/fastutil/booleans/BooleanIterable.c:81:5: error: invalid token at start of a preprocessor expression
^
src/it/unimi/dsi/fastutil/booleans/BooleanIterable.c:89:5: error: invalid token at start of a preprocessor expression
^
src/it/unimi/dsi/fastutil/booleans/BooleanIterable.c:113:5: error: invalid token at start of a preprocessor expression
^
src/it/unimi/dsi/fastutil/booleans/BooleanIterable.c:187:5: error: invalid token at start of a preprocessor expression
^
src/it/unimi/dsi/fastutil/booleans/BooleanIterable.c:380:5: error: invalid token at start of a preprocessor expression
^
src/it/unimi/dsi/fastutil/booleans/BooleanIterable.c:391:5: error: invalid token at start of a preprocessor expression
^
src/it/unimi/dsi/fastutil/booleans/BooleanIterable.c:395:7: error: invalid token at start of a preprocessor expression
^
src/it/unimi/dsi/fastutil/booleans/BooleanIterable.c:399:7: error: invalid token at start of a preprocessor expression
^
fatal error: too many errors emitted, stopping now [-ferror-limit=]
20 errors generated.
make: *** [src/it/unimi/dsi/fastutil/booleans/BooleanIterable.java] Error 1
`
@Test(expected = IllegalStateException.class)
public void testArrayMapEmptyEntrySetThrowsExceptionOnIteratorRemove() {
ObjectIterator<Entry<Integer, Integer>> iterator = new Int2IntArrayMap().entrySet().iterator();
assertFalse(iterator.hasNext());
iterator.remove();
}
According to the documentation this should throw IllegalStateException (but at least it throws an exception 😄).
From reviewing the source code I would expect some methods not to be synchronized correctly if xxxxMaps.synchronize(xxxxMap<K, V>)
is called.
That would be probably every method being defined as default in java.util.Map
, such as compute
, computeIfAbsent
or computeIfPresent
.
See test here: https://github.com/gpanther/fastutil-guava-tests/blob/97fda/src/test/java/net/greypanther/fastutil/tests/IntArrayListTest.java#L88
This is again caused by the fact that IntLists.EMPTY_LIST inherits equals from AbstractIntCollection.
Regards,
Attila
Currently it looks like
public int skip(final int n) {
int i = n;
while (i-- != 0 && hasNext())
nextInt();
return n - i - 1;
}
So it will iterate ~ 2 billion times
When installing from sources on OS X, make sources fails with the following errors:
./gencsource.sh drv/Iterable.drv src/it/unimi/dsi/fastutil/booleans/BooleanIterable.c >src/it/unimi/dsi/fastutil/booleans/BooleanIterable.c
gcc -w -I. -ftabstop=4 -DASSERTS_VALUE=false -E -C -P src/it/unimi/dsi/fastutil/booleans/BooleanIterable.c >src/it/unimi/dsi/fastutil/booleans/BooleanIterable.java
src/it/unimi/dsi/fastutil/booleans/BooleanIterable.c:7:2: error: invalid preprocessing directive
#unassert keyclass
^
src/it/unimi/dsi/fastutil/booleans/BooleanIterable.c:8:2: error: invalid preprocessing directive
#assert keyclass(Boolean)
^
src/it/unimi/dsi/fastutil/booleans/BooleanIterable.c:9:2: error: invalid preprocessing directive
#unassert keys
^
src/it/unimi/dsi/fastutil/booleans/BooleanIterable.c:10:3: error: invalid preprocessing directive
#assert keys(primitive)
^
src/it/unimi/dsi/fastutil/booleans/BooleanIterable.c:11:2: error: invalid preprocessing directive
#unassert valueclass
^
src/it/unimi/dsi/fastutil/booleans/BooleanIterable.c:12:2: error: invalid preprocessing directive
#assert valueclass(Object)
^
src/it/unimi/dsi/fastutil/booleans/BooleanIterable.c:13:2: error: invalid preprocessing directive
#unassert values
^
src/it/unimi/dsi/fastutil/booleans/BooleanIterable.c:14:3: error: invalid preprocessing directive
#assert values(reference)
^
src/it/unimi/dsi/fastutil/booleans/BooleanIterable.c:20:5: error: invalid token at start of a preprocessor expression
#if #keyclass(Object) || #keyclass(Reference)
^
src/it/unimi/dsi/fastutil/booleans/BooleanIterable.c:53:5: error: invalid token at start of a preprocessor expression
#if #valueclass(Object) || #valueclass(Reference)
^
src/it/unimi/dsi/fastutil/booleans/BooleanIterable.c:72:5: error: invalid token at start of a preprocessor expression
#if #keyclass(Object) || #keyclass(Reference)
^
src/it/unimi/dsi/fastutil/booleans/BooleanIterable.c:81:5: error: invalid token at start of a preprocessor expression
#if #valueclass(Object) || #valueclass(Reference)
^
src/it/unimi/dsi/fastutil/booleans/BooleanIterable.c:89:5: error: invalid token at start of a preprocessor expression
#if #keyclass(Object) || #keyclass(Reference) || #valueclass(Object) || #valueclass(Reference)
^
src/it/unimi/dsi/fastutil/booleans/BooleanIterable.c:113:5: error: invalid token at start of a preprocessor expression
#if #keyclass(Object) || #keyclass(Reference)
^
src/it/unimi/dsi/fastutil/booleans/BooleanIterable.c:187:5: error: invalid token at start of a preprocessor expression
#if #keyclass(Object)
^
src/it/unimi/dsi/fastutil/booleans/BooleanIterable.c:380:5: error: invalid token at start of a preprocessor expression
#if #keyclass(Object) || #keyclass(Reference)
^
src/it/unimi/dsi/fastutil/booleans/BooleanIterable.c:391:5: error: invalid token at start of a preprocessor expression
#if #keyclass(Object)
^
src/it/unimi/dsi/fastutil/booleans/BooleanIterable.c:395:7: error: invalid token at start of a preprocessor expression
#elif #keyclass(Float)
^
src/it/unimi/dsi/fastutil/booleans/BooleanIterable.c:399:7: error: invalid token at start of a preprocessor expression
#elif #keyclass(Double)
^
fatal error: too many errors emitted, stopping now [-ferror-limit=]
20 errors generated.
make: *** [src/it/unimi/dsi/fastutil/booleans/BooleanIterable.java] Error 1
This code produces infinite loop:
IntOpenHashSet set = new IntOpenHashSet();
set.add(1);
set.add(2);
set.add(3);
set.trim(1);
while it shouldn't rehash the set at all.
Because it inherits toString from AbstractIntCollection it returns "{}" instead.
Regards,
Attila
Standard packaging of sources makes the .java file names match the .class file names in the corresponding binary JAR file. This allows the IDEs, static analysis tools, etc to discover them.
fastutil packages sources under src/ and test/ which means that they are essentially useless in any automated environment, and can only be handled manually.
Please can you publish a more standard -sources.jar and either merge the test sources at the root of the sources JAR or publish a separate test sources JAR?
Thank you.
This is the same as issue #16 (RemoveAll should remove all occurrences of a given element from the collection), but it also needs fixing for ?BigArrayBigList.
The following code throws an UnsupportedOperationException, even though it should remove the element (or should it? Is IntArraySet considered to be immutable? then again, it implements add/remove on the class level):
IntSet set = new IntArraySet(Arrays.asList(42));
IntIterator iterator = set.iterator();
assertTrue(iterator.hasNext());
iterator.next();
iterator.remove();
The stacktrace of the exception (with fastutil 7.0.10) is:
java.lang.UnsupportedOperationException
at it.unimi.dsi.fastutil.ints.AbstractIntIterator.remove(AbstractIntIterator.java:66)
at net.greypanther.fastutil.tests.IntArraySetTest.testRemoveFromIterator(IntArraySetTest.java:27)
...
Here is how to reproduce with fastutil-7.0.8:
import it.unimi.dsi.fastutil.longs.LongOpenHashSet;
public class LongOpenHashSetInfiniteLoopInRemove {
public static void main(String[] args) {
LongOpenHashSet set = new LongOpenHashSet(4, 1.0f); // Changing load factor to 0.9f makes this work
set.add(1);
set.add(2);
set.add(3);
set.remove(2);
set.trim(); // Removing this trim makes this work
System.out.println("Remove 1 starts...");
set.remove(1); // Will hang inside this call
System.out.println("Remove 1 done!");
}
}
Running:
javac -cp fastutil-7.0.8.jar LongOpenHashSetInfiniteLoopInRemove.java
java -cp ".:./fastutil-7.0.8.jar" LongOpenHashSetInfiniteLoopInRemove
As per the documentation: https://docs.oracle.com/javase/8/docs/api/java/util/List.html#hashCode--
Again, the issue is that IntLists.EMPTY_LIST inherits the hashCode implementation from AbstractIntCollection
Regards,
Attila
I'm trying to add the battery of tests from Google Guava's testlib [1] to FastUtils and found the following discrepancy between ArrayList and (Byte)ArrayList (though I suspect that it's present in all of the *ArrayLists since they share the common template):
@Test
public void testAddUsingIteratorToTheFirstPosition() {
testAddUsingIteratorToTheFirstPosition_internal(new ArrayList<>());
testAddUsingIteratorToTheFirstPosition_internal(new ByteArrayList());
}
private void testAddUsingIteratorToTheFirstPosition_internal(List<Byte> list) {
list.add((byte)24);
ListIterator<Byte> it = list.listIterator();
it.add((byte)42);
assertTrue(it.hasNext());
assertEquals(Arrays.asList((byte)42, (byte)24), list);
}
Ie. adding an element using the list iterator on the first position fails with IllegalStateException. The test also demonstrates that using ArrayList works as expected.
Regards,
Attila
PS. I will post other bugs I discover as I debug them.
I think there is some left-over benchmark code here:
Version 7.0.6
Getting this
java.lang.ArrayIndexOutOfBoundsException: -1 at it.unimi.dsi.fastutil.objects.ObjectOpenCustomHashSet.rehash(ObjectOpenCustomHashSet.java:536) at it.unimi.dsi.fastutil.objects.ObjectOpenCustomHashSet.add(ObjectOpenCustomHashSet.java:255)
The set is created like
ObjectOpenCustomHashSet<byte[]> set = new ObjectOpenCustomHashSet<>(ByteArrays.HASH_STRATEGY);
And the only method that is ever called is
ObjectOpenCustomHashSet.add(byte[])
I don't have an exact path to reproduce but I am getting the error fairly often.
$ java -version
java version "1.7.0_80"
Java(TM) SE Runtime Environment (build 1.7.0_80-b15)
Java HotSpot(TM) 64-Bit Server VM (build 24.80-b11, mixed mode)
$ uname -r
2.6.32-573.12.1.el6.x86_64
If I call LongOpenHashSet.removeAll(LongCollection), then AbstractLongCollection.removeAll(LongCollection) ist called.
For each long of the given collection, this method iterates over the whole Set until it finds a match. If a match is found, it's removed.
That may be useful for Lists, but for Sets it doesn't make sense, because it's extremely slow on large Sets.
For Sets it should just call remove for each given collection element.
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.