Skip to content

Instantly share code, notes, and snippets.

@cheremin
Created January 18, 2023 10:03
Show Gist options
  • Save cheremin/37023f259020ce0d640a5bf8113451d3 to your computer and use it in GitHub Desktop.
Save cheremin/37023f259020ce0d640a5bf8113451d3 to your computer and use it in GitHub Desktop.
Simulation: space wasted due to records being page-aligned
import java.util.ArrayList;
import java.util.OptionalDouble;
import java.util.concurrent.ThreadLocalRandom;
class PaginationWastedSizeSimulation {
public static void main(final String[] args) {
//Records of random size, with avg=averageRecordSize
//Page of pageSize
//If record doesn't fit page -- it is moved to the next page, remaining space on the first page
// is 'wasted' (padding).
//Q: How much space is 'wasted', on average?
//
//A: with record size random enough (poisson) avg(wasted) == avg(recordSize).
// With less random (less entropy) distributions avg(wasted) > 1/2 avg(recordSize)
final double pageSize = 1;
final double averageRecordSize = 0.01;
final int pagesToSimulate = 10_000;
final ArrayList<Double> wastedSizes = new ArrayList<>();
double occupiedOnPage = 0;
while (wastedSizes.size() < pagesToSimulate) {
final double recordSize = generateRecordSizeCutoffGauss(averageRecordSize);
if (occupiedOnPage + recordSize > pageSize) {
final double wastedSpace = pageSize - occupiedOnPage;
wastedSizes.add(wastedSpace);
occupiedOnPage = recordSize;//move whole record to next page
}
else {
occupiedOnPage += recordSize;
}
}
final OptionalDouble averageReminder = wastedSizes.stream().mapToDouble(Double::doubleValue).average();
System.out.printf("Average wasted space = %.3f of average record size per page\n",
averageReminder.orElse(0) / averageRecordSize);
}
private static double generateRecordSizeUniform(final double averageRecordSize) {
final ThreadLocalRandom rnd = ThreadLocalRandom.current();
return averageRecordSize + rnd.nextDouble(0, 0.5 * averageRecordSize);
}
private static double generateRecordSizeCutoffGauss(final double averageRecordSize) {
final ThreadLocalRandom rnd = ThreadLocalRandom.current();
while (true) {
final double candidate = rnd.nextGaussian(averageRecordSize, averageRecordSize);
if (candidate > 0) {
return candidate;
}
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment