Open YoDaMa opened 2 years ago
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.
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?
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
@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