best unique packet id allocator

[YoDaMa]

@vishnureddy17 going to create this issue to track our discussions and work on optimizing the number allocator. Can you share the benchmarking code and your results comparing the number-allocator package, your interval list-based implementation, and the set-based implementation?

EDIT (@vishnureddy17): More context available in this PR discussion: mqttjs/MQTT.js#1429

[vishnureddy17]

Here is a gist with my implementations and code comparing the time between the different approaches: https://gist.github.com/vishnureddy17/65f3d0b587a8ca0853ee9f17b77757e8

Methodology: Use up all packet ids. Then time the insertion of all the packet ids in random order.

Results on my machine (average over 100 iterations): Using a Set: 4.47ms Using the implementation in this PR: 1709.79ms Using NumberAllocator written by @redboltz : 60.01ms

Seems like Set is the fastest, but it uses more memory as there are 65535 numbers stored in the set if all the IDs are free. Might not be a big deal in the grand scheme of things.

[redboltz]

It seems that only free() time is measured.

I think that the following code

https://gist.github.com/vishnureddy17/65f3d0b587a8ca0853ee9f17b77757e8#file-compare-js-L25-L34

  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);
  }

should be

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

.

What do you think?

[vishnureddy17]

Hmm, I intentionally only measured the free time since that tends to be slower. Your suggestion is good though, @redboltz . I went ahead and tried out your suggestion, here are the results: Using a Set: 1000.83ms Using the implementation in this PR: 1898.27ms Using NumberAllocator written by @redboltz : 71.68ms