Eclipse Collections-Inside Look
Download
Report
Transcript Eclipse Collections-Inside Look
Eclipse Collections
An Inside Look
March 2016
Copyright © 2016 Goldman Sachs. All rights reserved.
AGENDA
Agenda
• What is Eclipse Collections?
• Eclipse Collections vs others
• Eclipse Collections by examples
• UnifiedMap: The memory saver
• UnifiedSet: It is a Set not a Map
2
What is Eclipse Collections?
Copyright © 2016 Goldman Sachs. All rights reserved.
• Eclipse Collections
− Feature rich Java Collections framework
− Project @ Eclipse Foundation
• http://www.eclipse.org/collections/
− Eclipse Collections released under EDL and EPL
• Open for contributions
• Eclipse Collections Kata
− Tutorial developed to learn the framework
• https://github.com/eclipse/eclipse-collections-kata
4
ECLIPSE COLLECTIONS
What is Eclipse Collections
Eclipse Collections vs Others
Copyright © 2016 Goldman Sachs. All rights reserved.
Features
EC 7.0.0
Java 8
Guava
Rich API
Interfaces
Readable, Mutable,
Immutable,
FixedSize, Lazy
Mutable, Stream
Mutable, Fluent
Optimized Set & Map
(+Bag)
Immutable Collections
Primitive Collections
(+Bag,
+Immutable)
Multimaps
(+Bag,
+SortedBag)
(+Linked)
Bags (Multisets)
BiMaps
Iteration Styles
Eager/Lazy,
Serial/Parallel
Trove
Scala
Mutable
Readable, Mutable,
Immutable, Lazy
Lazy,
Serial/Parallel
Lazy,
Serial
(Multimap trait)
Eager,
Serial
Eager/Lazy,
Serial/Parallel (Lazy
Only)
6
ECLIPSE COLLECTIONS VS OTHERS
Eclipse Collections vs Others
ECLIPSE COLLECTIONS VS JAVA 8 STREAMS
Eclipse Collections vs Java 8 Streams
Eclipse Collections 7.0.0
Java 8 Streams
-
Functional APIs
Lazy only
Single use
Serial & Parallel
Primitive streams
(3 types)
Extensible Collectors
Eager & Lazy, Serial &
Parallel
Memory efficient
containers
Primitive containers (all 8)
Immutable containers
More container types
More iteration patterns
“With” method patterns
“target” method patterns
Covariant return types
Java 5+ compatible
7
Eclipse Collections by Example
Copyright © 2016 Goldman Sachs. All rights reserved.
UnifiedMap: The memory saver
Copyright © 2016 Goldman Sachs. All rights reserved.
• JDK HashMap is backed by an Entry
• Entry holds key, value, next and hash
transient Node<K,V>[] table
Node<K,V> implements Map.Entry<K,V>
10
HASHMAP
HashMap
• EC UnifiedMap is backed by an array
protected transient Object[] table
• Key, value in consecutive slots improves
cache locality
11
UNIFIEDMAP
UnifiedMap
/**
* Entry objects are not stored in the table
* like in java.util.HashMap. Instead of trying
* to deal with collisions in the main array
* using Entry objects, we put a special object
* in the key slot and put a regular Object[]
* in the value slot. The array contains the
* key value pairs in consecutive slots, just
* like the main array, but it's a linear list
* with no hashing.
* The final result is a Map implementation
* that's leaner than java.util.HashMap and
* faster than Trove's THashMap. The best of
* both approaches unified together, and thus
* the name UnifiedMap.
*/
12
UNIFIEDMAP
The Unification
public V get(Object key)
{
int index = this.index(key);
Object cur = this.table[index];
if (cur != null)
{
Object val = this.table[index + 1];
if (cur == CHAINED_KEY)
{
return this.getFromChain((Object[])val,(K)key);
}
if (this.nonNullTableObjectEquals(cur, (K) key))
{
return (V) val;
}
}
return null;
}
13
UNIFIEDMAP
UnifiedMap
MEMORY COMPARISON
Comparing Maps
Save half the memory
14
PERFORMANCE COMPARISON
Comparing Maps
Map.get() JMH Tests
ElementOps/sec – higher the better
15
PERFORMANCE COMPARISON
Comparing Maps
Map.put() JMH Tests (non-presized)
ElementOps/sec – higher the better
16
PERFORMANCE COMPARISON
Comparing Maps
Map.put() JMH Tests (presized)
ElementOps/sec – higher the better
17
UnifiedSet: It is a Set not a Map
Copyright © 2016 Goldman Sachs. All rights reserved.
• JDK HashSet is backed by HashMap
private transient HashMap<E,Object> map
• Values in each (key, value) pair are a
waste of space
• Key, value pairs in HashMap are wrapped
in an Entry leading to additional memory
wastage
19
HASHSET
HashSet
• EC UnifiedSet is backed by an array
protected transient Object[] table
• Not backed by Map
20
UNIFIEDSET
UnifiedSet
MEMORY COMPARISON
Comparing Sets
Save 4x the memory
21
Learn more at GS.com/Engineering
© 2016 Goldman Sachs. This presentation should not be relied upon or considered investment advice. Goldman Sachs does not warrant or guarantee to anyone the accuracy, completeness or efficacy of this presentation,
and recipients should not rely on it except at their own risk. This presentation may not be forwarded or disclosed except with this disclaimer intact.
Appendix – More Features
Copyright © 2016 Goldman Sachs. All rights reserved.
MORE FEATURES
The “as” methods (O(1) cost)
24
MORE FEATURES
The “to” methods (O(n) cost)
25
MORE FEATURES
Handling Exceptions
• Using Java Collections
• Using Eclipse Collections
26
Appendix – Primitive Specialization
Copyright © 2016 Goldman Sachs. All rights reserved.
PRIMITIVE SPECIALIZATION
Primitive <-> Object
• Boxing is expensive
− Reference + Header + alignment
− Wrapper classes are immutable
• Unboxing is expensive
28
• From Oracle Java guide
“You can’t put an int (or other primitive value)
into a collection. Collections can only hold
object references, so you have to box primitive
values into the appropriate wrapper class.
An Integer is not a substitute for an int;
autoboxing and unboxing blur the distinction
between primitive types and reference types, but
they do not eliminate it.”
Source: http://docs.oracle.com/javase/1.5.0/docs/guide/language/autoboxing.html
29
PRIMITIVE SPECIALIZATION
Primitive <-> Object
PRIMITIVE SPECIALIZATION
List<Integer>
• Java has object and primitive arrays
• Java 8 has primitive Streams
− They cannot be stored in a field
− They are not reusable
• Java does not have primitive Lists,
Sets, Maps
30
•
•
•
•
•
•
•
•
•
•
intList
longList
shortList
floatList
doubleList
charList
byteList
booleanList
Primitive Sets are similar
Primitive Maps have combination of
primitives
31
PRIMITIVE SPECIALIZATION
Primitive Lists
PRIMITIVE SPECIALIZATION
Primitive Lists – Memory Comparison
32
PRIMITIVE SPECIALIZATION
Primitive Sets – Memory Comparison
33
PRIMITIVE SPECIALIZATION
Primitive Maps – Performance Comparison
34
PRIMITIVE SPECIALIZATION
Primitive Maps – Memory Comparison
35
Appendix – Resources
Copyright © 2016 Goldman Sachs. All rights reserved.
RESOURCES
Resources
• Eclipse Collections Home Page
http://www.eclipse.org/collections/
• Eclipse Collections on GitHub
https://github.com/eclipse/eclipse-collections
https://github.com/eclipse/eclipse-collections/wiki
https://github.com/eclipse/eclipse-collections-kata
• GS Collections Memory Benchmark
http://www.goldmansachs.com/gscollections/presentations/GSC_Memory_Tests.pdf
• Conference Talks and Meetups
https://github.com/eclipse/eclipsecollections/wiki/Conference-talks-and-meetups
37