I’ve been working on a function in the code that I believed could be optimized. The original simplefs_ext_search function was using a linear search, which can be quite slow for large values of SIMPLEFS_MAX_EXTENTS.
In my commit, I’ve implemented a binary search in place of the linear search. This has reduced the time complexity from O(n) to O(log n), making the function much faster for large values of SIMPLEFS_MAX_EXTENTS.
Additionally, I’ve added a preliminary sorting of extents based on ee_block to ensure the binary search works correctly. This sorting has a time cost, but should be acceptable if index->extents doesn’t change frequently.
I hope these changes are helpful and improve the performance of our project. I’m open to feedback and suggestions on how we might further improve this code. 😊
jserv
commented
4 months ago
👋 Hello everyone,
I’ve been working on a function in the code that I believed could be optimized. The original simplefs_ext_search function was using a linear search, which can be quite slow for large values of SIMPLEFS_MAX_EXTENTS.
In my commit, I’ve implemented a binary search in place of the linear search. This has reduced the time complexity from O(n) to O(log n), making the function much faster for large values of SIMPLEFS_MAX_EXTENTS.
Additionally, I’ve added a preliminary sorting of extents based on ee_block to ensure the binary search works correctly. This sorting has a time cost, but should be acceptable if index->extents doesn’t change frequently.
I hope these changes are helpful and improve the performance of our project. I’m open to feedback and suggestions on how we might further improve this code. 😊
Thank you for considering my pull request!
I hope this helps! 😊