| 1 |
<html> |
| 2 |
<head> |
| 3 |
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8" /> |
| 4 |
<title>High Performance Primitive Collections (HPPC)</title> |
| 5 |
</head> |
| 6 |
|
| 7 |
<body> |
| 8 |
<link rel="stylesheet" type="text/css" href="resources/overview.css"> |
| 9 |
|
| 10 |
High Performance Primitive Collections (HPPC) library provides |
| 11 |
typical data structures (lists, stacks, sets and maps) |
| 12 |
that are generated for all Java primitive types |
| 13 |
(<code>byte</code>, <code>int</code>, etc.) from a single template |
| 14 |
to conserve memory and boost performance. |
| 15 |
|
| 16 |
<h2>Why HPPC?</h2> |
| 17 |
|
| 18 |
<p>The Java Collections package is in many ways excellent, but it cannot |
| 19 |
be used for primitive types without autoboxing (which kills the |
| 20 |
runtime performance due to increased memory use and garbage collector overhead).</p> |
| 21 |
|
| 22 |
<p>This library has slightly different design goals than Java Collections (and many other |
| 23 |
collection packages). For example, the internals of each class are open |
| 24 |
and subject to free hacking and tuning up to one's wishes.</p> |
| 25 |
|
| 26 |
|
| 27 |
<h2>Why not other primitive collection libraries?</h2> |
| 28 |
|
| 29 |
<p>There are a few projects implementing collections over primitive types: |
| 30 |
<a href="http://fastutil.dsi.unimi.it/">fastutil</a>, |
| 31 |
<a href="https://github.com/OpenHFT/Koloboke">Koloboke</a>, |
| 32 |
<a href="http://pcj.sourceforge.net/">PCJ</a>, |
| 33 |
<a href="http://trove4j.sourceforge.net/">GNU Trove</a>, |
| 34 |
<a href="http://commons.apache.org/primitives/">Apache Primitive Collections</a>.</p> |
| 35 |
|
| 36 |
<p>Historically, some of these libraries were released on commercially forbidding licenses |
| 37 |
(fastutil) and others appeared to be abandoned (PCJ), so HPPC was created to fill this |
| 38 |
gap. Since then things have changed quite a lot (fastutil is now Apache-licensed, |
| 39 |
Koloboke has been released), but HPPC still remains a small memory footprint and |
| 40 |
does the job. If you require full Java collections compliance, try |
| 41 |
<a href="http://fastutil.dsi.unimi.it/">fastutil</a>, or Koloboke, they are both |
| 42 |
very, very good.</p> |
| 43 |
|
| 44 |
|
| 45 |
<h2>Assumptions and goals of HPPC</h2> |
| 46 |
|
| 47 |
<p>We assume that:</p> |
| 48 |
<ul> |
| 49 |
<li>The programmer knows what he's doing and may wish to access internal |
| 50 |
storage of a given collection's class directly (not using predefined |
| 51 |
iterators, for example).</li> |
| 52 |
|
| 53 |
<li>Vast majority of scenarios use single-threaded access. There is little |
| 54 |
point in repeated verification for concurrent modifications, for example.</li> |
| 55 |
|
| 56 |
<li>The programs (algorithms) that use HPPC are unit-tested |
| 57 |
and regression-tested during development with assertions enabled, so their |
| 58 |
behavior in production systems does not have to be restrictively verified |
| 59 |
(we can assume the code should break during testing/ development when |
| 60 |
assertions are enabled).</li> |
| 61 |
</ul> |
| 62 |
|
| 63 |
<p>From these assumptions stem the following design drivers:</p> |
| 64 |
<ul> |
| 65 |
<li>Data types in the HPPC are as simple as possible and expose |
| 66 |
internal storage for any optimisations one may wish to do from within the |
| 67 |
end-application code.</li> |
| 68 |
|
| 69 |
<li>Verification of parameter and state validity is done <b>optionally</b> |
| 70 |
using assertions. This means that contracts are only checked if requested at |
| 71 |
runtime (using Java 1.4+ <code>-ea</code> switch). When the algorithm is |
| 72 |
tested and verified, it can run with no additional overhead from |
| 73 |
contract checks.</li> |
| 74 |
|
| 75 |
<li>We tried to avoid complex interface hierarchies, although certain |
| 76 |
interfaces are defined for clarity. The programmer should still choose |
| 77 |
a proper data structure at design-time and should know what he's doing.</li> |
| 78 |
|
| 79 |
<li>HPPC provides utilities for the most common tasks like filtering, iterating |
| 80 |
or joining collections, but these utilities are usually more expensive than implementing |
| 81 |
a low-level direct access to the data storage (which may be done if needed).</li> |
| 82 |
|
| 83 |
<li>There is no special support for data serialization.</li> |
| 84 |
|
| 85 |
<li>The implementation is not thread safe and does not attempt to provide |
| 86 |
fast-failing concurrency problems detection.</li> |
| 87 |
</ul> |
| 88 |
|
| 89 |
|
| 90 |
<h2>Design and implementation assumptions</h2> |
| 91 |
|
| 92 |
<ul> |
| 93 |
<li>We want HPPC class templates to be implemented as <b>regular Java classes (with generics)</b> |
| 94 |
so that typical programming tools can be used for development, testing, etc.</li> |
| 95 |
|
| 96 |
<li>We want HPPC class templates to be usable as generic-collection classes (for boxed |
| 97 |
numeric types or any other <code>Object</code> types), but at the same time we want |
| 98 |
specialized classes to be automatically-generated for primitive-types |
| 99 |
(to limit memory consumption and boost performance due to JIT optimisations).</li> |
| 100 |
</ul> |
| 101 |
|
| 102 |
|
| 103 |
<h2>Interfaces and their relation to Java Collections API</h2> |
| 104 |
|
| 105 |
<p>HPPC is not strictly modeled after Java Collections API, although we did |
| 106 |
try to make the APIs look similar enough for comfortable use. |
| 107 |
One particular thing largely missing in HPPC are "view" projections |
| 108 |
(sublists or views over the collection of keys or values). Certain classes provide such views |
| 109 |
(like {@linkplain com.carrotsearch.hppc.ObjectObjectHashMap |
| 110 |
<code>ObjectObjectHashMap</code>}), but for the most part, specific methods are |
| 111 |
provided that accept ranges or closure-like filters. If performance is still unsatisfactory, |
| 112 |
the internals of each class are available for direct manipulation.</p> |
| 113 |
|
| 114 |
<p>Rough relationships between Java Collections classes and HPPC classes are |
| 115 |
presented in the table below.</p> |
| 116 |
|
| 117 |
<table class="nice" summary="Relationships between HPPC and Java Collections."> |
| 118 |
<caption>Relationships between HPPC and Java Collections.</caption> |
| 119 |
<thead> |
| 120 |
<tr class="odd"> |
| 121 |
<th class="empty"></th> |
| 122 |
<th scope="col">Java Collections</th> |
| 123 |
<th scope="col">HPPC (primitives)</th> |
| 124 |
<th scope="col">HPPC (generics)</th> |
| 125 |
</tr> |
| 126 |
</thead> |
| 127 |
<tbody> |
| 128 |
<tr> |
| 129 |
<th scope="row" class="column1">bit sets</th> |
| 130 |
<td><code>java.util.BitSet</code></td> |
| 131 |
<td><code>BitSet</code></td> |
| 132 |
<td>n/a</td> |
| 133 |
</tr> |
| 134 |
|
| 135 |
<tr class="odd"> |
| 136 |
<th scope="row" class="column1">array-backed lists</th> |
| 137 |
<td><code>java.util.ArrayList</code>, <code>java.util.Vector</code></td> |
| 138 |
<td><code><span class="red nobr">[type]</span>ArrayList</code></td> |
| 139 |
<td>{@linkplain com.carrotsearch.hppc.ObjectArrayList |
| 140 |
<code>ObjectArrayList<<span class="red nobr">T</span>></code>}</td> |
| 141 |
</tr> |
| 142 |
|
| 143 |
<tr> |
| 144 |
<th scope="row" class="column1">stacks</th> |
| 145 |
<td><code>java.util.Stack</code></td> |
| 146 |
<td><code><span class="red nobr">[type]</span>Stack</code></td> |
| 147 |
<td>{@linkplain com.carrotsearch.hppc.ObjectStack |
| 148 |
<code>ObjectStack<<span class="red nobr">T</span>></code>}</td> |
| 149 |
</tr> |
| 150 |
|
| 151 |
<tr class="odd"> |
| 152 |
<th scope="row" class="column1">deques</th> |
| 153 |
<td><code>java.util.ArrayDeque</code></td> |
| 154 |
<td><code><span class="red nobr">[type]</span>ArrayDeque</code></td> |
| 155 |
<td>{@linkplain com.carrotsearch.hppc.ObjectArrayDeque |
| 156 |
<code>ObjectArrayDeque<<span class="red nobr">T</span>></code>}</td> |
| 157 |
</tr> |
| 158 |
|
| 159 |
<tr> |
| 160 |
<th scope="row" class="column1">hash sets</th> |
| 161 |
<td><code>java.util.HashSet</code></td> |
| 162 |
<td><code><span class="red nobr">[keyType]</span>HashSet</code><br/> |
| 163 |
<code><span class="red nobr">[keyType]</span>ScatterSet</code><br/> |
| 164 |
</td> |
| 165 |
<td> |
| 166 |
{@linkplain com.carrotsearch.hppc.ObjectHashSet |
| 167 |
<code>ObjectHashSet<<span class="red nobr">K</span>></code>}<br/> |
| 168 |
<code><span class="red nobr">[keyType]</span>HashSet</code><br/><br/> |
| 169 |
{@linkplain com.carrotsearch.hppc.ObjectScatterSet |
| 170 |
<code>ObjectScatterSet<<span class="red nobr">K</span>></code>}<br/> |
| 171 |
<code><span class="red nobr">[keyType]</span>ScatterSet</code><br/> |
| 172 |
</td> |
| 173 |
</tr> |
| 174 |
|
| 175 |
<tr> |
| 176 |
<th scope="row" class="column1">hash maps</th> |
| 177 |
<td><code>java.util.HashMap</code></td> |
| 178 |
<td><code><span class="red nobr">[keyType][valueType]</span>HashMap</code></td> |
| 179 |
<td> |
| 180 |
{@linkplain com.carrotsearch.hppc.ObjectObjectHashMap |
| 181 |
<code>ObjectObjectHashMap<<span class="red nobr">K, V</span>></code>}<br/> |
| 182 |
<code><span class="red nobr">[keyType]</span>ObjectHashMap<<span class="red nobr">V</span>></code><br/> |
| 183 |
<code>Object<span class="red nobr">[valueType]</span>HashMap<<span class="red nobr">K</span>></code><br/><br/> |
| 184 |
{@linkplain com.carrotsearch.hppc.ObjectObjectScatterMap |
| 185 |
<code>ObjectObjectScatterMap<<span class="red nobr">K, V</span>></code>}<br/> |
| 186 |
<code><span class="red nobr">[keyType]</span>ObjectScatterMap<<span class="red nobr">V</span>></code><br/> |
| 187 |
<code>Object<span class="red nobr">[valueType]</span>ScatterMap<<span class="red nobr">K</span>></code> |
| 188 |
</td> |
| 189 |
</tr> |
| 190 |
</tbody> |
| 191 |
</table> |
| 192 |
|
| 193 |
<p>The method-level API of the corresponding types is also similar, but distinct |
| 194 |
differences exist (consult the JavaDoc of each class).</p> |
| 195 |
|
| 196 |
<a name="scattervshash"><h2>Scatter or hash (sets and maps)</h2></a> |
| 197 |
|
| 198 |
<p> |
| 199 |
All key-redistribution containers (maps and sets) implemented in HPPC use |
| 200 |
<a href="http://en.wikipedia.org/wiki/Open_addressing">open addressing</a> |
| 201 |
with <a href="http://en.wikipedia.org/wiki/Linear_probing">linear probing</a>. Given |
| 202 |
the speed of access to CPU caches on modern processors this type of key lookup |
| 203 |
is the fastest one in practice. However, there is a potential problem with this approach: |
| 204 |
because keys are distributed in the underlying array at approximately their hash value, |
| 205 |
when they are copied to another hash container, the number of conflicts to find an empty |
| 206 |
slot may quickly increase. In the worst case this may lead to an exponential cost |
| 207 |
of any operation that requires a slot-lookup (adding, removal of a key). The "worst" case |
| 208 |
is, unfortunately, not as unlikely as it may seem; it's enough that keys are just copied |
| 209 |
from one container to another, in particular with load factors higher than 0.5. |
| 210 |
</p> |
| 211 |
|
| 212 |
<p> |
| 213 |
In HPPC there is a distinction between "hash" and "scatter" sets and maps. Any hash-based |
| 214 |
structure will try to redistribute keys differently on a per-object basis. So the likelihood |
| 215 |
of the worst case (described above) is minimized to nearly zero at the cost of slightly |
| 216 |
increased slot lookup cost and lower CPU cache utilization when keys are copied from one |
| 217 |
container to another. The "scatter" sets and maps will use a very simple hashing strategy |
| 218 |
to be as fast as possible, but this can lead to conflict avalanches if scatter container's |
| 219 |
keys are copied to another scatter container. So when are scatter sets (or maps) useful? In short, |
| 220 |
whenever there is a need to check for existence of a key or for collecting (aggregating) |
| 221 |
some value for an existing key but assuming the content of the scatter container is |
| 222 |
not later propagated to some other (scatter) set or map. |
| 223 |
</p> |
| 224 |
|
| 225 |
<p>Check out <a href="https://github.com/carrotsearch/hppc/wiki/Scatter-Or-Hash">this example</a>, it provides in-depth information and explanation of the phenomenon.</p> |
| 226 |
|
| 227 |
<p> |
| 228 |
If you're unsure which one to use, use regular hash containers. The difference shows |
| 229 |
only for large data sets (measured in millions of elements) anyway. |
| 230 |
</p> |
| 231 |
|
| 232 |
|
| 233 |
<a name="interfaces"><h2>Interfaces and container inheritance</h2></a> |
| 234 |
|
| 235 |
<p>HPPC's interfaces are modeled to encapsulate |
| 236 |
the common functionality enforced from <i>all</i> the classes that |
| 237 |
implement a given interface. The interface hierarchy is loosely inspired by STL.</p> |
| 238 |
|
| 239 |
<p>An overview of interfaces and their relationship to data structures implemented |
| 240 |
in HPPC is depicted graphically below.</p> |
| 241 |
|
| 242 |
<p><img src="resources/interfaces.png" alt="HPPC interfaces"></p> |
| 243 |
</body> |
| 244 |
</html> |