Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

best unique packet id allocator #1

Open
YoDaMa opened this issue Mar 2, 2022 · 3 comments
Open

best unique packet id allocator #1

YoDaMa opened this issue Mar 2, 2022 · 3 comments
Assignees

Comments

@YoDaMa
Copy link
Contributor

YoDaMa commented Mar 2, 2022

@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
Copy link
Member

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.

@vishnureddy17 vishnureddy17 changed the title best unique number allocator best unique packet id allocator Mar 2, 2022
@redboltz
Copy link

redboltz commented Mar 3, 2022

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
Copy link
Member

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 vishnureddy17 transferred this issue from mqttjs/MQTT.js Jun 20, 2022
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

3 participants