0
# Specialized Histogram Variants
1

2
Memory-optimized histogram implementations designed for specific use cases and constraints. These variants trade off maximum count capacity or other features for reduced memory usage.
3

4
## IntCountsHistogram
5

6
HDR histogram using int arrays for count storage, providing lower memory usage with count limited to Integer.MAX_VALUE per bucket.
7

8
```java { .api }
9
public class IntCountsHistogram extends AbstractHistogram {
10
    
11
    // Constructors
12
    public IntCountsHistogram(int numberOfSignificantValueDigits);
13
    public IntCountsHistogram(long highestTrackableValue, int numberOfSignificantValueDigits);
14
    public IntCountsHistogram(long lowestDiscernibleValue, 
15
                             long highestTrackableValue, 
16
                             int numberOfSignificantValueDigits);
17
    public IntCountsHistogram(AbstractHistogram source);
18
    
19
    // Factory methods
20
    static IntCountsHistogram decodeFromByteBuffer(ByteBuffer buffer, 
21
                                                  long minBarForHighestTrackableValue);
22
    static IntCountsHistogram decodeFromCompressedByteBuffer(ByteBuffer buffer, 
23
                                                            long minBarForHighestTrackableValue);
24
    static IntCountsHistogram fromString(String base64CompressedHistogramString);
25
    
26
    // Implementation methods
27
    public IntCountsHistogram copy();
28
    public IntCountsHistogram copyCorrectedForCoordinatedOmission(long expectedInterval);
29
}
30
```
31

32
### Usage Characteristics
33

34
**Memory Savings**: Approximately 50% memory usage compared to standard Histogram (int vs long arrays).
35

36
**Count Limitations**: Each bucket limited to 2,147,483,647 (Integer.MAX_VALUE) counts.
37

38
**Usage Examples:**
39

40
```java
41
// Create int counts histogram for moderate volume measurements
42
IntCountsHistogram histogram = new IntCountsHistogram(1_000_000, 3);
43

44
// Record values - same API as standard histogram  
45
for (int i = 0; i < 1_000_000; i++) {
46
    histogram.recordValue(ThreadLocalRandom.current().nextInt(1000));
47
}
48

49
// Analysis methods unchanged
50
double mean = histogram.getMean();
51
long p95 = histogram.getValueAtPercentile(95.0);
52
long totalCount = histogram.getTotalCount();
53

54
// Memory usage comparison
55
int intHistMemory = histogram.getEstimatedFootprintInBytes();
56
Histogram standardHist = new Histogram(1_000_000, 3);  
57
int standardMemory = standardHist.getEstimatedFootprintInBytes();
58

59
System.out.printf("IntCountsHistogram: %d bytes%n", intHistMemory);
60
System.out.printf("Standard Histogram: %d bytes%n", standardMemory);
61
System.out.printf("Memory savings: %.1f%%%n", 
62
    100.0 * (standardMemory - intHistMemory) / standardMemory);
63
```
64

65
### When to Use IntCountsHistogram
66

67
**Good For:**
68
- Moderate to high volume measurements (< 2B samples per bucket)
69
- Memory-constrained environments
70
- Batch processing scenarios
71
- Latency measurements in typical applications
72

73
**Avoid When:**
74
- Extremely high-frequency measurements (risk of count overflow)
75
- Long-running cumulative histograms
76
- Situations where count precision is critical
77

78
## ShortCountsHistogram
79

80
HDR histogram using short arrays for count storage, providing minimal memory usage with count limited to Short.MAX_VALUE per bucket.
81

82
```java { .api }
83
public class ShortCountsHistogram extends AbstractHistogram {
84
    
85
    // Constructors
86
    public ShortCountsHistogram(int numberOfSignificantValueDigits);
87
    public ShortCountsHistogram(long highestTrackableValue, int numberOfSignificantValueDigits);
88
    public ShortCountsHistogram(long lowestDiscernibleValue, 
89
                               long highestTrackableValue, 
90
                               int numberOfSignificantValueDigits);
91
    public ShortCountsHistogram(AbstractHistogram source);
92
    
93
    // Factory methods
94
    static ShortCountsHistogram decodeFromByteBuffer(ByteBuffer buffer, 
95
                                                    long minBarForHighestTrackableValue);
96
    static ShortCountsHistogram decodeFromCompressedByteBuffer(ByteBuffer buffer, 
97
                                                              long minBarForHighestTrackableValue);
98
    static ShortCountsHistogram fromString(String base64CompressedHistogramString);
99
    
100
    // Implementation methods
101
    public ShortCountsHistogram copy();
102
    public ShortCountsHistogram copyCorrectedForCoordinatedOmission(long expectedInterval);
103
}
104
```
105

106
### Usage Characteristics
107

108
**Memory Savings**: Approximately 75% memory usage reduction compared to standard Histogram.
109

110
**Count Limitations**: Each bucket limited to 32,767 (Short.MAX_VALUE) counts.
111

112
**Usage Examples:**
113

114
```java
115
// Create short counts histogram for low-volume or sampling scenarios
116
ShortCountsHistogram histogram = new ShortCountsHistogram(10_000, 2);
117

118
// Suitable for sampled data or low-frequency measurements
119
Random random = new Random();
120
for (int i = 0; i < 10000; i++) {
121
    if (random.nextDouble() < 0.1) {  // 10% sampling rate
122
        histogram.recordValue(random.nextInt(10000));
123
    }
124
}
125

126
// Memory efficiency demonstration
127
int shortHistMemory = histogram.getEstimatedFootprintInBytes();
128
System.out.printf("ShortCountsHistogram memory: %d bytes%n", shortHistMemory);
129

130
// Same analysis capabilities
131
histogram.outputPercentileDistribution(System.out, 1.0);
132
```
133

134
### When to Use ShortCountsHistogram
135

136
**Good For:**
137
- Sampled measurements
138
- Proof-of-concept or testing scenarios
139
- Embedded systems with severe memory constraints
140
- Short-duration measurements
141
- Template or placeholder histograms
142

143
**Avoid When:**
144
- Production high-frequency recording
145
- Long-running cumulative measurements
146
- Applications where count accuracy is important
147

148
## PackedHistogram
149

150
Memory-optimized histogram using packed array representation, ideal for sparse value distributions with significant memory savings.
151

152
```java { .api }
153
public class PackedHistogram extends AbstractHistogram {
154
    
155
    // Constructors
156
    public PackedHistogram(int numberOfSignificantValueDigits);
157
    public PackedHistogram(long highestTrackableValue, int numberOfSignificantValueDigits);
158
    public PackedHistogram(long lowestDiscernibleValue, 
159
                          long highestTrackableValue, 
160
                          int numberOfSignificantValueDigits);
161
    public PackedHistogram(AbstractHistogram source);
162
    
163
    // Factory methods
164
    static PackedHistogram decodeFromByteBuffer(ByteBuffer buffer, 
165
                                               long minBarForHighestTrackableValue);
166
    static PackedHistogram decodeFromCompressedByteBuffer(ByteBuffer buffer, 
167
                                                         long minBarForHighestTrackableValue);
168
    static PackedHistogram fromString(String base64CompressedHistogramString);
169
    
170
    // Implementation methods
171
    public PackedHistogram copy();
172
    public PackedHistogram copyCorrectedForCoordinatedOmission(long expectedInterval);
173
}
174
```
175

176
### Packed Array Technology
177

178
PackedHistogram uses dynamic packed arrays that:
179
- Store only non-zero counts
180
- Compress data based on actual usage patterns
181
- Expand dynamically as needed
182
- Provide excellent memory efficiency for sparse data
183

184
### Usage Examples
185

186
```java
187
// Create packed histogram - excellent for sparse distributions
188
PackedHistogram histogram = new PackedHistogram(3);
189

190
// Record sparse data (many values have zero counts)
191
Random random = new Random();
192
for (int i = 0; i < 100000; i++) {
193
    // Sparse distribution - most values between 1000-2000, few outliers
194
    if (random.nextDouble() < 0.95) {
195
        histogram.recordValue(1000 + random.nextInt(1000));  // Dense region
196
    } else {
197
        histogram.recordValue(random.nextInt(1000000));       // Sparse outliers
198
    }
199
}
200

201
// Memory efficiency shines with sparse data
202
System.out.printf("PackedHistogram memory: %d bytes%n", 
203
    histogram.getEstimatedFootprintInBytes());
204

205
// Compare with standard histogram for same data
206
Histogram standard = new Histogram(histogram);  
207
System.out.printf("Standard histogram memory: %d bytes%n",
208
    standard.getEstimatedFootprintInBytes());
209

210
// Full functionality preserved
211
double mean = histogram.getMean();
212
long p50 = histogram.getValueAtPercentile(50.0);
213
long p99 = histogram.getValueAtPercentile(99.0);
214
```
215

216
### Performance Characteristics
217

218
**Memory**: Excellent for sparse distributions, may use more memory for dense distributions.
219

220
**Performance**: Slight CPU overhead due to packing/unpacking operations.
221

222
**Auto-resize**: Supports auto-resizing with efficient memory management.
223

224
### When to Use PackedHistogram
225

226
**Ideal For:**
227
- Sparse value distributions
228
- Wide value ranges with clustered data
229
- Network latency measurements (many low values, few high outliers)
230
- Response time measurements with occasional timeouts
231
- Memory-constrained applications with sparse data
232

233
**Consider Alternatives For:**
234
- Uniformly distributed data
235
- CPU-critical recording paths
236
- Dense value distributions
237

238
## PackedConcurrentHistogram
239

240
Thread-safe version of PackedHistogram combining packed array memory efficiency with concurrent recording support.
241

242
```java { .api }
243
public class PackedConcurrentHistogram extends ConcurrentHistogram {
244
    
245
    // Constructors
246
    public PackedConcurrentHistogram(int numberOfSignificantValueDigits);
247
    public PackedConcurrentHistogram(long highestTrackableValue, int numberOfSignificantValueDigits);
248
    public PackedConcurrentHistogram(long lowestDiscernibleValue, 
249
                                    long highestTrackableValue, 
250
                                    int numberOfSignificantValueDigits);
251
    public PackedConcurrentHistogram(AbstractHistogram source);
252
    
253
    // Factory methods
254
    static PackedConcurrentHistogram decodeFromByteBuffer(ByteBuffer buffer, 
255
                                                         long minBarForHighestTrackableValue);
256
    static PackedConcurrentHistogram decodeFromCompressedByteBuffer(ByteBuffer buffer, 
257
                                                                   long minBarForHighestTrackableValue);
258
    
259
    // Implementation methods
260
    public PackedConcurrentHistogram copy();
261
    public PackedConcurrentHistogram copyCorrectedForCoordinatedOmission(long expectedInterval);
262
}
263
```
264

265
### Usage Examples
266

267
```java
268
// Thread-safe packed histogram for concurrent sparse data recording
269
PackedConcurrentHistogram histogram = new PackedConcurrentHistogram(3);
270

271
// Multiple threads recording sparse latency data
272
ExecutorService executor = Executors.newFixedThreadPool(8);
273
for (int t = 0; t < 8; t++) {
274
    executor.submit(() -> {
275
        Random random = new Random();
276
        for (int i = 0; i < 50000; i++) {
277
            // Simulate network latency: mostly 1-10ms, occasional spikes
278
            long latency = random.nextDouble() < 0.9 
279
                ? 1000 + random.nextInt(9000)    // Normal: 1-10ms
280
                : 50000 + random.nextInt(950000); // Spikes: 50-1000ms
281
                
282
            histogram.recordValue(latency);  // Thread-safe, wait-free
283
        }
284
    });
285
}
286

287
// Coordinated reading (same as ConcurrentHistogram)
288
WriterReaderPhaser phaser = histogram.getWriterReaderPhaser();
289
phaser.readerLock();
290
try {
291
    System.out.printf("Memory usage: %d bytes%n", 
292
        histogram.getEstimatedFootprintInBytes());
293
    histogram.outputPercentileDistribution(System.out, 0.001);  // Scale to ms
294
} finally {
295
    phaser.readerUnlock();
296
}
297

298
executor.shutdown();
299
```
300

301
## Memory Usage Comparison
302

303
Here's a practical comparison of memory usage across variants:
304

305
```java
306
// Test configuration: 1M max value, 3 significant digits
307
int maxValue = 1_000_000;
308
int precision = 3;
309

310
// Create different histogram types
311
Histogram standard = new Histogram(maxValue, precision);
312
IntCountsHistogram intCounts = new IntCountsHistogram(maxValue, precision);
313
ShortCountsHistogram shortCounts = new ShortCountsHistogram(maxValue, precision);
314
PackedHistogram packed = new PackedHistogram(maxValue, precision);
315

316
// Record same sparse data pattern
317
Random random = new Random(12345);  // Fixed seed for reproducible results
318
for (int i = 0; i < 100000; i++) {
319
    long value = random.nextDouble() < 0.8 
320
        ? random.nextInt(1000)           // 80% in range 0-1000
321
        : random.nextInt(maxValue);      // 20% spread across full range
322
        
323
    standard.recordValue(value);
324
    intCounts.recordValue(value);
325
    shortCounts.recordValue(value);
326
    packed.recordValue(value);
327
}
328

329
// Compare memory footprints
330
System.out.printf("Standard Histogram:      %6d bytes%n", 
331
    standard.getEstimatedFootprintInBytes());
332
System.out.printf("IntCountsHistogram:      %6d bytes (%.1f%% of standard)%n", 
333
    intCounts.getEstimatedFootprintInBytes(),
334
    100.0 * intCounts.getEstimatedFootprintInBytes() / standard.getEstimatedFootprintInBytes());
335
System.out.printf("ShortCountsHistogram:    %6d bytes (%.1f%% of standard)%n", 
336
    shortCounts.getEstimatedFootprintInBytes(),
337
    100.0 * shortCounts.getEstimatedFootprintInBytes() / standard.getEstimatedFootprintInBytes());
338
System.out.printf("PackedHistogram:         %6d bytes (%.1f%% of standard)%n", 
339
    packed.getEstimatedFootprintInBytes(),
340
    100.0 * packed.getEstimatedFootprintInBytes() / standard.getEstimatedFootprintInBytes());
341
```
342

343
## Choosing the Right Specialized Variant
344

345
### Decision Matrix
346

347
| Use Case | Recommended Variant | Reason |
348
|----------|-------------------|---------|
349
| Memory-constrained, moderate volume | IntCountsHistogram | 50% memory savings, reasonable count limits |
350
| Sampling/testing scenarios | ShortCountsHistogram | Maximum memory savings |
351
| Sparse distributions | PackedHistogram | Adaptive memory based on actual data |
352
| Concurrent sparse data | PackedConcurrentHistogram | Thread safety + memory efficiency |
353
| Dense uniform distributions | Standard Histogram | No packing overhead |
354
355
### Migration Considerations
356

357
All specialized variants maintain API compatibility:
358

359
```java
360
// Easy migration between variants
361
AbstractHistogram source = getExistingHistogram();
362

363
// Convert to memory-optimized variant
364
PackedHistogram optimized = new PackedHistogram(source);
365

366
// Or create concurrent version
367
PackedConcurrentHistogram concurrent = new PackedConcurrentHistogram(source);
368

369
// API remains identical
370
optimized.recordValue(1234);
371
long p99 = optimized.getValueAtPercentile(99.0);
372
```
373

374
### Performance Impact
375

376
**Recording Performance**:
377
- IntCountsHistogram: ~5-10% slower than standard (int vs long operations)
378
- ShortCountsHistogram: ~10-15% slower (type conversion overhead)
379
- PackedHistogram: ~20-30% slower (packing operations)
380
- PackedConcurrentHistogram: ~25-35% slower (packing + concurrency)
381

382
**Query Performance**:
383
- IntCountsHistogram: Equivalent to standard
384
- ShortCountsHistogram: Equivalent to standard  
385
- PackedHistogram: ~10-20% slower (unpacking overhead)
386
- PackedConcurrentHistogram: Same as PackedHistogram for queries
387

388
**Memory vs Performance Trade-off**:
389
Choose based on whether memory savings outweigh performance costs in your specific use case.