# OSDev.org

The Place to Start for Operating System Developers
 It is currently Wed Sep 30, 2020 7:08 pm

 All times are UTC - 6 hours

 Page 1 of 1 [ 2 posts ]
 Print view Previous topic | Next topic
Author Message
 Post subject: Search-optimized bitmapPosted: Thu Aug 13, 2009 3:52 pm
 Member

Joined: Fri Oct 03, 2008 4:13 am
Posts: 142
Location: Ogre, Latvia, EU
I've come up with idea about optimized bitmap, which should be able to look up ones (or with slight modifications - zeros) pretty fast.

Begin with bitmap as usual. But then I add another bitmap on top of it and fill it by OR-ing groups of bits of lower level together. If that layer is still too large, I add another level on top of it. Repeat until top-level bitmap is small enough for sequential scan.

Here's an illustration for 64 bits, using 4-bit groups:
Attachment:

bitmap.png [ 1.7 KiB | Viewed 1787 times ]

If I set or clear bit, I update bits in upper levels, of course.

Then, if I need to look up a bit, I start from the top, find first bit, move down a level to corresponding group, search there and continue until hit the bottom level.

By my calculations lookup and bit toggling should be O(log_{bits_per_group}(N)).

Ideally I'd use 2-bit groups, thus O(log2(n)), however 8-bit groups (bytes ) seems to be more practical for coding. And O(log8(n)) doesn't seem bad either.

Now, haven't I overlooked something? It almost seems too good to be true

_________________
If something looks overcomplicated, most likely it is.

Top

 Post subject: Re: Search-optimized bitmapPosted: Thu Aug 13, 2009 4:07 pm
 Member

Joined: Tue Mar 24, 2009 8:11 pm
Posts: 1249
Location: Sunnyvale, California
It would be faster to search within each qword linearly, because that only requires one register, but have a tertiary search tree of single bit values to find the proper qword. Essentially, replace the bottom layer with 64 bit values instead of 1 bit ones. Asymptotically, it's still lg4(n).

It's really just a tertiary search tree with only one bit per node, so it does make sense that it's asymptotically lg4(n). Your only problem is that it's hard to store it efficiently without a lot of extra access code if it's not a power of 4 sized bitmap.

Top

 Display posts from previous: All posts1 day7 days2 weeks1 month3 months6 months1 year Sort by AuthorPost timeSubject AscendingDescending
 Page 1 of 1 [ 2 posts ]

 All times are UTC - 6 hours

#### Who is online

Users browsing this forum: No registered users and 3 guests

 You cannot post new topics in this forumYou cannot reply to topics in this forumYou cannot edit your posts in this forumYou cannot delete your posts in this forumYou cannot post attachments in this forum

Search for:
 Jump to:  Select a forum ------------------ Operating System Development    OS Development    OS Design & Theory    Announcements, Test Requests, & Job openings Everything Else    General Programming    General Ramblings    Auto-Delete Forum OSDev.org    OSDev Wiki    About this site