MQTT.js vNext Unique Packet ID Allocator Discussion

compare.js

import { IntervalListAllocator } from "./invervalListAllocator.js";
import { SetAllocator } from "./setAllocator.js";
import { NumberAllocator } from "number-allocator"

const maxPacketId = 65535

function testAllocators() {
  const setAllocator = new SetAllocator();
  const packetIdAllocator = new PacketIdAllocator();
  const numberAllocator = new NumberAllocator(1, maxPacketId);

  /* [1, 2, 3, ..., 65535] */
  const idsToRelease = Array.from({ length: maxPacketId }, (_, i) => i + 1);
  /* Shuffle array using Fisher-Yates */
  for (let i = 0; i < maxPacketId - 2; ++i) {
    /* j is a random index such that i <= j < maxPacketId */
    const j = Math.floor(i + Math.random() * (maxPacketId - i))
    const temp = idsToRelease[i]
    idsToRelease[i] = idsToRelease[j]
    idsToRelease[j] = temp
  }

  let times = []

  for (let allocator of [setAllocator, packetIdAllocator, numberAllocator]) {
    for (let i = 0; i < maxPacketId; ++i) {
      allocator.alloc();
    }
    const startTime = Date.now();
    for (const id of idsToRelease) {
      allocator.free(id);
    }
    times.push(Date.now() - startTime);
  }

  return times
}

let numTests = 100
let testValues = Array.from({ length: numTests }, () => testAllocators());
let [setRunningSum, packetIdAllocatorRunningSum, numberAllocatorRunningSum] = [0, 0, 0]

for (const testValue of testValues) {
  setRunningSum += testValue[0];
  packetIdAllocatorRunningSum += testValue[1];
  numberAllocatorRunningSum += testValue[2];
}

console.log([setRunningSum / numTests, packetIdAllocatorRunningSum / numTests, numberAllocatorRunningSum / numTests]);

intervalListAllocator.js

/* Keeps track of free and used packet ids by storing available IDs as intervals */
export class IntervalListAllocator {
  constructor() {
      /**
       * Intervals are stored in reverse order since push/pop from end of a list is
       * faster than shift/unshift from beginning.
       */
      this._intervals = [[65535, 1]];
  }
  alloc() {
      if (this._intervals.length === 0) {
          throw new Error('No more packet IDs available');
      }
      const lastInterval = this._intervals[this._intervals.length - 1];
      const [lastIntervalMax, lastIntervalMin] = lastInterval;
      if (lastIntervalMax === lastIntervalMin) {
          /* We just used the last packet ID in the interval, so remove it. */
          this._intervals.pop();
      }
      else {
          /* We are using the lowest value in the interval, so increment the min */
          ++lastInterval[1];
      }
      return lastIntervalMin;
  }
  free(id) {
      if (id < 1 || id > 65535) {
          throw new RangeError('Packet ID must be between 1 and 65535');
      }
      if (this._intervals.length === 0) {
          this._intervals.push([id, id]);
          return;
      }
      let lastInterval = this._intervals[this._intervals.length - 1];
      let lastIntervalMin = lastInterval[1];
      if (id < lastIntervalMin - 1) {
          this._intervals.push([id, id]);
          return;
      }
      if (id === lastIntervalMin - 1) {
          --lastInterval[1];
          return;
      }
      const insertionPoint = this._intervals.findIndex(([max]) => id > max);
      if (insertionPoint === -1) {
          throw new Error('Packet ID already available');
      }
      const insertionPointInterval = this._intervals[insertionPoint];
      const beforeInsertionPointInterval = this._intervals[insertionPoint - 1];
      const [insertionPointMax, insertionPointMin] = insertionPointInterval;
      if (id - 1 === insertionPointMax && id + 1 === beforeInsertionPointInterval?.[1]) {
          /* The ID is adjacent to two intervals, so we can merge them. */
          beforeInsertionPointInterval[1] = insertionPointMin; // Merge the two intervals
          this._intervals.splice(insertionPoint, 1); // Remove the extraneous interval
      }
      else if (id === insertionPointMax + 1) {
          /**
           * The ID is at the high end of insertionPointInterval, so we can
           * increment the max
           */
          ++insertionPointInterval[0];
      }
      else if (id + 1 === beforeInsertionPointInterval?.[1]) {
          /**
           * The ID is at the low end of beforeInsertionPointInterval, so we can
           * decrement the min
           */
          --beforeInsertionPointInterval[1];
      }
      else {
          /**
           * The ID is in the middle of two intervals, so we must insert a new
           * interval
           */
          this._intervals.splice(insertionPoint, 0, [id, id]);
      }
  }
}

setAllocator.js

export class SetAllocator {
  constructor() {
    this._ids = new Set(Array.from({ length: 65535 }, (_, i) => i + 1));
  }

  alloc() {
    if (this._ids.size === 0) {
      throw new Error('No more packet IDs available');
    }
    const item = this._ids.values().next().value;
    this._ids.delete(item);
    return item;
  }

  free(id) {
    if (id < 1 || id > 65535) {
      throw new RangeError('Packet ID must be between 1 and 65535');
    }
    if (this._ids.has(id)) {
      throw new Error('Packet ID already available');
    }
    this._ids.add(id);
  }
}