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.

Sign up for GitHub

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

Jump to bottom

Add message id to message key hash option #929

Closed
skliper opened this issue Sep 30, 2020 · 0 comments · Fixed by #947 or #975
Closed

Add message id to message key hash option #929

skliper opened this issue Sep 30, 2020 · 0 comments · Fixed by #947 or #975
Assignees
@skliper
Labels
enhancement Priority: Mission Feature or bug related to stakeholder needs
Milestone
Caelum

Comments

@skliper
Copy link
Contributor

skliper commented Sep 30, 2020

Is your feature request related to a problem? Please describe.
Core implementation is message id == message key, leading to a large, sparse message table to get the route index.

Describe the solution you'd like
Hash message and deconflict on lookup (confirm route matches MsgId). Could decrease message table size to a small multiple (2 or 4 maybe) of the routing table size depending on how many conflicts are acceptable.

Describe alternatives you've considered
Ordering the routing table and implement binary search and completely eliminate message table.

Additional context
See #928

Requester Info
Jacob Hageman - NASA/GSFC
@skliper skliper added enhancement Priority: Mission Feature or bug related to stakeholder needs labels Sep 30, 2020
@skliper skliper added this to the 7.0.0 milestone Sep 30, 2020
@skliper skliper mentioned this issue Sep 30, 2020
Open
@skliper skliper self-assigned this Oct 5, 2020
skliper added a commit to skliper/cFE that referenced this issue Oct 21, 2020
@skliper
Fix nasa#929, Add message map has implementation
b67b11f 
- Message map size based on used routes
- Oversized (4x) to limit collisions while retaining
  resonable size related to routing table (still smaller)
- ~10% single collisions seen for full routing table
  with realistic message ID use
- Oversizing means map can never fill, simplifies logic
- Observed approximately 10%-20% performance hit, trade
  against memory use (can now use full 32 bit MsgId space)
- Hash intended for 32 bit, if CFE_SB_MsgId_Atom_t size
  changes may require modification to hash
- Also added full coverage unit tests
@skliper skliper mentioned this issue Oct 21, 2020
Merged
skliper added a commit to skliper/cFE that referenced this issue Oct 21, 2020
@skliper
Fix nasa#929, Add message map has implementation
5a795ad 
- Message map size based on used routes
- Oversized (4x) to limit collisions while retaining
  resonable size related to routing table (still smaller)
- ~10% single collisions seen for full routing table
  with realistic message ID use
- Oversizing means map can never fill, simplifies logic
- Observed approximately 10%-20% performance hit, trade
  against memory use (can now use full 32 bit MsgId space)
- Hash intended for 32 bit, if CFE_SB_MsgId_Atom_t size
  changes may require modification to hash
- Also added full coverage unit tests
astrogeco added a commit that referenced this issue Oct 21, 2020
@astrogeco
Merge pull request #947 from skliper/fix928-route-direct-module
12f2ff1 
Fix #928 and #929 - Modularize software bus routing, add msg map hash
@astrogeco astrogeco mentioned this issue Oct 28, 2020
Merged
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@skliper skliper

Labels
enhancement Priority: Mission Feature or bug related to stakeholder needs
Projects
None yet
Milestone
Caelum
1 participant
@skliper