On Wed, Nov 20, 2024 at 04:46:40PM -0700, Brian Johannesmeyer wrote: > Thank you for the suggestion. I hacked together a bitmap-based > approach as you proposed, and while it does improve memory efficiency > by reducing the per-block metadata overhead, it unfortunately appears > to significantly impact the runtime performance. > > My guess as to why: The current linked list implementation allows us > to find the next free block in constant time (`O(1)`) by directly > dereferencing `pool->next_block`, and then following the `next_block` > pointers for subsequent free blocks. In contrast, the bitmap approach > requires iterating over all pages in `page->page_list` and, for each > page, iterating through its bitmap to find the first zero bit. This > results in a worst-case complexity of `O(n * b)`, where `n` is the > number of pages and `b` is the number of bits in each page's bitmap. Indeed. You'd probably need to split the linkage of the pages into a list of those that have free blocks and those that don't as a minimum. Can you share your current version?
