Debian Codegraph @

hppc/src/main/javadoc/overview.html

raw
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&lt;<span class="red nobr">T</span>&gt;</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&lt;<span class="red nobr">T</span>&gt;</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&lt;<span class="red nobr">T</span>&gt;</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&lt;<span class="red nobr">K</span>&gt;</code>}<br/>
168 <code><span class="red nobr">[keyType]</span>HashSet</code><br/><br/>
169 {@linkplain com.carrotsearch.hppc.ObjectScatterSet
170 <code>ObjectScatterSet&lt;<span class="red nobr">K</span>&gt;</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&lt;<span class="red nobr">K, V</span>&gt;</code>}<br/>
182 <code><span class="red nobr">[keyType]</span>ObjectHashMap&lt;<span class="red nobr">V</span>&gt;</code><br/>
183 <code>Object<span class="red nobr">[valueType]</span>HashMap&lt;<span class="red nobr">K</span>&gt;</code><br/><br/>
184 {@linkplain com.carrotsearch.hppc.ObjectObjectScatterMap
185 <code>ObjectObjectScatterMap&lt;<span class="red nobr">K, V</span>&gt;</code>}<br/>
186 <code><span class="red nobr">[keyType]</span>ObjectScatterMap&lt;<span class="red nobr">V</span>&gt;</code><br/>
187 <code>Object<span class="red nobr">[valueType]</span>ScatterMap&lt;<span class="red nobr">K</span>&gt;</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>