Searching for a string of set (or unset) bits in a bitmap

[AndrewAPrice]

Perhaps you could use a linked list instead (or something similar). This would waste a lot of space unless you were using 4MB pages.

4MB of pages could be would be an array of 1024 of these: (which should be simplified to an array of ushorts)

Code: Select all

struct freePage
{
   unsigned short nextFreePage;
};

All you'd have to do is keep the ID of the first free page, and each page keeps to ID of the next free page. When a page is freed, add it to the beginning of the list, when a page is allocated take it off the beginning of the list. It'll be really fast but the table requires 128x more storage space. You could probably tightly pack the table into an array of 10 bit IDs, but that is still 10x more storage space. It's really a matter of size versus speed. And would you really be allocating/freeing pages that often?

@hckr83: If it helps, you don't have to have to allocate a contiguous space in your physical memory, only virtual memory. This will help in avoiding fragmentation in your kernel's bitmap.

[Korona]

Perhaps you could use a linked list instead (or something similar). This would waste a lot of space unless you were using 4MB pages.

A B-Tree with node size = page size is much more efficient
I think I'll use that approach for my virtual memory manager. (And a number of stacks (memory < 1 MB, memory < 16 MB, memory < 4 GB) for my physical memory manager)

[bewing]

@ Solar: that was very interesting. Clearly gcc is willing to create a 47 qword entry sparse lookup table for the jump, for a 7 entry switch. I would be really curious to see, however, what it did if you were to have a few random values from 0 to a million. I doubt it would create the table, then.

(I admit to being somewhat confused about some of those opcodes, but reading gcc's mind is beyond me.)

[AndrewAPrice]

I tried searching the GCC internals doc, and either I've missed the section on how it handles switch statements or it's up to the specific backend implementation.

[AJ]

Clearly gcc is willing to create a 47 qword entry sparse lookup table for the jump, for a 7 entry switch. I would be really curious to see, however, what it did if you were to have a few random values from 0 to a million. I doubt it would create the table, then.

I guess that this optimisation is fair enough with -O2. If it did the same with -Os, you would be a bit disappointed, though (unfortunately I'm on a computer without GCC at the moment and am not going to install it to find out!).

I also suspect there must be some kind of limit to the logic. For example, if you had values 1000000, 1000002, 1000007 etc..., perhaps it would still do the same but just add an initial offset. If, however, you had 0, 1001, 100002, 1000007 etc, I would hope that it wouldn't create a sparse lookup...

Cheers,
Adam

[bewing]

I guess that this optimisation is fair enough with -O2. If it did the same with -Os, you would be a bit disappointed, though (unfortunately I'm on a computer without GCC at the moment and am not going to install it to find out!).

Me neither.

For example, if you had values 1000000, 1000002, 1000007 etc..., perhaps it would still do the same but just add an initial offset.

If you look at that second example of solar's, you can see that is precisely what it did. The switch values went from 5 to 51. On the very first line, it subtracted the 5, and ran the sparse table from 0 to 46.

If, however, you had 0, 1001, 100002, 1000007 etc, I would hope that it wouldn't create a sparse lookup...

Obviously, it won't. -- that was half the point of my post.
But the other half was the question: what is gcc's fallback algorithm when it is too expensive to just make a sparse lookup table? Under this case, will it just code the switch as a nested if? That is my guess -- that there *is* no fallback algorthm. That "switch" is only efficient if you have a "tight" set of switch values. If the values are not sufficiently dense, then switch isn't any more efficient than a nested if.

Or, will it try to somehow convert the switch values to indices, and use the indices in a tight lookup table?

[Solar]

Code: Select all

int main( int argc, char * argv[] )
{
    switch ( argc )
    {
        case 5:
            return 254;
        case 284:
            return 125;
        case 5261:
            return 42;
        case 6178:
            return 23;
        case 16732:
            return 7;
        case 183676:
            return 1;
        default:
            return 0;
    }
}

yields (with -O2):

Code: Select all

00000000 <main>:
   0:   8d 4c 24 04             lea    0x4(%esp),%ecx
   4:   83 e4 f0                and    $0xfffffff0,%esp
   7:   ff 71 fc                pushl  -0x4(%ecx)
   a:   b8 2a 00 00 00          mov    $0x2a,%eax
   f:   55                      push   %ebp
  10:   89 e5                   mov    %esp,%ebp
  12:   51                      push   %ecx
  13:   8b 11                   mov    (%ecx),%edx
  15:   81 fa 8d 14 00 00       cmp    $0x148d,%edx
  1b:   74 33                   je     50 <main+0x50>
  1d:   7e 37                   jle    56 <main+0x56>
  1f:   81 fa 5c 41 00 00       cmp    $0x415c,%edx
  25:   b8 07 00 00 00          mov    $0x7,%eax
  2a:   74 24                   je     50 <main+0x50>
  2c:   81 fa 7c cd 02 00       cmp    $0x2cd7c,%edx
  32:   b8 01 00 00 00          mov    $0x1,%eax
  37:   74 17                   je     50 <main+0x50>
  39:   81 fa 22 18 00 00       cmp    $0x1822,%edx
  3f:   b8 17 00 00 00          mov    $0x17,%eax
  44:   74 0a                   je     50 <main+0x50>
  46:   31 c0                   xor    %eax,%eax
  48:   90                      nop
  49:   8d b4 26 00 00 00 00    lea    0x0(%esi),%esi
  50:   59                      pop    %ecx
  51:   5d                      pop    %ebp
  52:   8d 61 fc                lea    -0x4(%ecx),%esp
  55:   c3                      ret
  56:   83 fa 05                cmp    $0x5,%edx
  59:   b8 fe 00 00 00          mov    $0xfe,%eax
  5e:   74 f0                   je     50 <main+0x50>
  60:   81 fa 1c 01 00 00       cmp    $0x11c,%edx
  66:   75 de                   jne    46 <main+0x46>
  68:   b8 7d 00 00 00          mov    $0x7d,%eax
  6d:   8d 76 00                lea    0x0(%esi),%esi
  70:   eb de                   jmp    50 <main+0x50>

[bewing]

Thanks, Solar.

Yup, basically a plain ol' nested if. So much for the "efficiency" of a switch statement in the general case.

[Korona]

Thanks, Solar.

Yup, basically a plain ol' nested if. So much for the "efficiency" of a switch statement in the general case.

The switch statement is not made for random numbers that come from a huge interval. There is no better solution than to produce nested ifs. Even if gcc could generate a perfect [minimal] hash function for every switch statement, computing the hash function would take more time than doing a few comparisons and jumps. (for small input sets)

EDIT: Actually there is a gnu utility that generates perfect hash function (gpref). You could use it to produce efficient lookup tables for large input sets. I wonder whether gcc uses a perfect hash function if a switch statement has a large amount of cases. (say ~512 cases; computing 512 cases with nested ifs will take at least 9 comparisons in the worst-case)