in Extremem/src/main/java/com/amazon/corretto/benchmark/extremem/RelativeTimeMetrics.java [916:1100]
private void compress(int desired_slots) {
boolean coalesced_triples = false;
Trace.msg(4, id, ": compress ()");
if (Trace.enabled(3))
dump();
// First, try to coalesce triples
for (int candidate_count = biu; candidate_count >= 3; ) {
int candidate_index = incrIndexBy (fbi, candidate_count - 1);
long candidate_span = spanAt (candidate_index);
// See how many buckets have the same span
int sscb = 1; // same-sized consecutive buckets
// neighbor_count is the number of buckets that precede the candidate
int neighbor_count = candidate_count - 1;
for (int neighbor_index = decrIndex (candidate_index);
(neighbor_count > 0) && (spanAt (neighbor_index) == candidate_span);
neighbor_index = decrIndex (neighbor_index)) {
sscb++;
neighbor_count--;
}
Trace.msgNoLine(4, id, ": candidate_count: ",
Integer.toString(candidate_count),
", candidate_index: ", Integer.toString(candidate_index),
", sscb: ", Integer.toString(sscb));
Trace.msg(4, ", neighbor_count: ", Integer.toString(neighbor_count));
if (sscb >= 3) {
// Must leave at least one, possibly 2 of these uncoalesced.
int coalesce_count = (sscb - 1) / 2;
int coalesce_2nd_index = candidate_index;
int coalesce_1st_index = decrIndex (coalesce_2nd_index);
Trace.msg(4, id, ": coalescing ", Integer.toString(coalesce_count));
for (int i = 0; i < coalesce_count; i++) {
// candidate end of span
long ceos = bucket_bounds[incrIndex(candidate_index)];
buckets[candidate_index] = (buckets[coalesce_1st_index] +
buckets[coalesce_2nd_index]);
bucket_bounds[candidate_index] = ceos - 2 * candidate_span;
Trace.msg(4, id, ": coalescing @",
Integer.toString(coalesce_1st_index),
" and @", Integer.toString(coalesce_2nd_index),
" onto @", Integer.toString(candidate_index));
candidate_index = decrIndex (candidate_index);
coalesce_1st_index = decrIndexBy (coalesce_1st_index, 2);
coalesce_2nd_index = decrIndexBy (coalesce_2nd_index, 2);
}
Trace.msg(4, id, ": sliding ",
Integer.toString(candidate_count - coalesce_count * 2),
" buckets forward");
// We've removed coalesce_count buckets. Slide everything forward.
int source_index = decrIndexBy (candidate_index, coalesce_count);
for (int i = candidate_count - coalesce_count * 2; i > 0; i--) {
long original_span = spanAt (source_index);
long ceos = bucket_bounds[incrIndex (candidate_index)];
buckets[candidate_index] = buckets[source_index];
bucket_bounds[candidate_index] = ceos - original_span;
Trace.msg(4, id, ": sliding @", Integer.toString(source_index),
" onto @", Integer.toString(candidate_index));
source_index = decrIndex (source_index);
candidate_index = decrIndex (candidate_index);
}
biu -= coalesce_count;
fbi = incrIndexBy (fbi, coalesce_count);
coalesced_triples = true;
break; // we've done our compression
} else
candidate_count -= sscb;
}
if (!coalesced_triples) {
// If we failed to find three consecutive buckets with the same
// span, try this alternative strategy: coalesce consecutive
// pairs of buckets that have the same span. Work from
// larger-span buckets to shorter-span buckets.
Trace.msg(4, id, ": coalescing of triples failed");
int dest_index = incrIndexBy (fbi, biu - 1);
int second_source_index = dest_index;
int first_source_index = decrIndex (second_source_index);
int coalesce_count = 0;
int i;
for (i = 0; i < biu - 1; i++) {
Trace.msgNoLine(4, id, ": trying to coalesce @",
Integer.toString(second_source_index),
"(", Long.toString(spanAt (second_source_index)),
") with @", Integer.toString(first_source_index));
Trace.msg(4, "(", Long.toString(spanAt (first_source_index)), ")");
if (spanAt (second_source_index) == spanAt(first_source_index)) {
buckets[dest_index] = (buckets[first_source_index]
+ buckets[second_source_index]);
Trace.msg(4, id, ": coalescing @",
Integer.toString(first_source_index),
" and @", Integer.toString(second_source_index),
" onto @", Integer.toString(dest_index));
if (first_source_index != fbi)
bucket_bounds[dest_index] = bucket_bounds[first_source_index];
first_source_index = decrIndexBy (first_source_index, 2);
second_source_index = decrIndexBy (second_source_index, 2);
coalesce_count++;
i++; // extra increment: coalesced two buckets
} else {
if (second_source_index != dest_index) {
buckets[dest_index] = buckets[second_source_index];
// second_source_index known to != fbi
bucket_bounds[dest_index] = bucket_bounds[second_source_index];
Trace.msg(4, id, ": sliding @",
Integer.toString(second_source_index),
" onto @", Integer.toString(dest_index));
} else
Trace.msg(4, id, ": not sliding @",
Integer.toString(second_source_index),
" onto @", Integer.toString(dest_index));
second_source_index = first_source_index;
first_source_index = decrIndex (first_source_index);
}
dest_index = decrIndex (dest_index);
}
if (second_source_index == fbi)
buckets[dest_index] = buckets[second_source_index];
if (coalesce_count > 0) {
biu -= coalesce_count;
fbi = incrIndexBy (fbi, coalesce_count);
} else {
// Failed to coalesce triples or doubles. Take more radical
// action. Pick an entry within the existing log. Turn the
// next-smaller entry into an entry that spans the same
// range as its next-larger entry. Since there are no doubles
// and no triples, this has the effect of subsuming all
// smaller entries into the newly enlarged span.
if (biu == 2) {
int last_index = incrIndex(fbi);
long last_span = spanAt(last_index);
fblb = lbhb - 2 * last_span;
buckets[last_index] += buckets[fbi];
fbi = incrIndex(fbi);
biu--;
} else {
int available_slots = BucketCount - biu;
int discard_slots = desired_slots - available_slots;
if (discard_slots >= biu)
discard_slots = biu - 1;
// The discard_neighbor is the bucket that will hold the
// consolidation of all discarded slots.
int discard_neighbor_index = incrIndexBy(fbi, discard_slots);
int discard_index = decrIndex(discard_neighbor_index);
// Since we know there are no doubles and no triples, we are
// assured that we can double the span @ discard_neighbor_index
// without making this bucket's span larger than its next
// larger neighbor's span, and when we do double the size of
// this bucket, the enlarged bucket span will subsume all
// buckets at smaller index values.
for (int k = 0; k < discard_slots; k++) {
buckets[discard_neighbor_index] += buckets[discard_index];
discard_index = decrIndex(discard_index);
}
fblb = (bucket_bounds[discard_neighbor_index]
- spanAt(discard_neighbor_index));
fbi = discard_neighbor_index;
biu -= discard_slots;
}
}
}
Trace.msg(4, id, ": after compress ()");
if (Trace.enabled(3))
dump();
}