FazBrowse GitHub Viewer | Trending |
URL:
| Home
Tools: [Download Repo ZIP]   [Original HTTPS Page]

Add compile-time hash table for efficient function dispatch by songwenshuai · Pull Request #466 · EmbeddedRPC/erpc · GitHub

/ erpc Public

Add compile-time hash table for efficient function dispatch - #466

Open
songwenshuai wants to merge 2 commits into
EmbeddedRPC:mainfrom
CineLogic:feature/hash-table-dispatch
ConversationCommits (2)ChecksFiles changed
Open

Add compile-time hash table for efficient function dispatch#466
songwenshuai wants to merge 2 commits into
EmbeddedRPC:mainfrom
CineLogic:feature/hash-table-dispatch

Conversation

songwenshuai commented Aug 11, 2025 •
edited
Loading

Copy link
Copy Markdown

Implement O(1) function lookup using pre-computed hash tables instead of O(n) switch statements. Includes collision resolution and performance monitoring for better scalability with large interfaces.

Pull request

Choose Correct

  • bug
  • feature

Describe the pull request

Implement compile-time hash table generation for O(1) function dispatch in eRPC services. This replaces the traditional switch statement approach with pre-computed hash tables, providing better performance for interfaces with many functions. The implementation includes collision resolution using linear probing and comprehensive performance monitoring.

To Reproduce

N/A - This is a performance enhancement, not a bug fix.

Expected behavior

  • Function dispatch should use O(1) hash table lookup instead of O(n) switch statements
  • Generated code should compile without errors
  • Existing functionality should remain unchanged (backward compatibility)
  • Performance should improve for interfaces with many functions

Screenshots

N/A

Desktop (please complete the following information):

  • OS: Linux
  • eRPC Version: Latest (development version)

Steps you didn't forgot to do

  • I checked if other PR isn't solving this issue.
  • I read Contribution details and did appropriate actions.
  • PR code is tested.
  • PR code is formatted.
  • Allow edits from maintainers pull request option is set (recommended).

Additional context

This optimization is particularly beneficial for interfaces with many functions where the traditional switch statement becomes inefficient. The hash table is computed at compile time with collision resolution, maintaining both performance and reliability. Load factor monitoring helps identify when interfaces might benefit from splitting for optimal performance.

Add compile-time hash table for efficient function dispatch
193c092 
Implement O(1) function lookup using pre-computed hash tables instead
of O(n) switch statements. Includes collision resolution and performance
monitoring for better scalability with large interfaces.
songwenshuai changed the base branch from main to develop August 12, 2025 00:59
songwenshuai changed the base branch from develop to main August 12, 2025 01:06
Fix comment test failure in hash table dispatch implementation
0869e96 
The test_comments.yml was expecting the original comment pattern
"// Call the correct server shim based on method unique ID." but the
hash table implementation changed it to include additional details.
Restore the original comment to maintain test compatibility while
preserving all hash table functionality.

songwenshuai commented Aug 12, 2025

Copy link
Copy Markdown
Author

Motivation and Advantages

Problem with Original Implementation:

  • Switch-case statements provide O(n) function lookup performance, which degrades significantly with large interfaces
  • Hard limit of 256 functions due to uint8_t function IDs, restricting interface scalability
  • Linear search through cases becomes a bottleneck for interfaces with many functions

Solution - Compile-time Hash Table Dispatch:

  • O(1) Performance: Replace O(n) switch statements with O(1) hash table lookups using pre-computed compile-time hash tables
  • Scalability: Remove 256-function limit by upgrading from uint8_t to uint32_t function IDs, supporting virtually unlimited functions
  • Efficiency: Hash table is computed at compile-time and embedded as static data, eliminating runtime overhead
  • Collision Resolution: Implement linear probing for hash collisions with performance monitoring
  • Memory Optimized: Use power-of-2 table sizes for efficient modulo operations via bitwise AND

Key Benefits:

  1. Performance: Constant-time function dispatch regardless of interface size
  2. Scalability: No practical limit on number of functions per interface
  3. Compile-time Optimization: Zero runtime cost for hash table generation
  4. Backward Compatibility: Maintains existing API while improving internal implementation
  5. Performance Monitoring: Provides load factor and collision statistics for optimization insights

Technical Details:

  • Hash function: (id * 0x9E3779B9) >> (32 - log2(table_size))
  • Linear probing for collision resolution
  • Automatic table sizing with configurable load factor
  • Performance warnings for suboptimal configurations

This change enables eRPC to handle large-scale interfaces efficiently while maintaining the framework's lightweight characteristics.

This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
Show hidden characters
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

No reviews

Assignees

No one assigned

Labels

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

1 participant

Back | FazBrowse Home | New Git URL