Page 2 of 2
Re: Searching for a string of set (or unset) bits in a bitmap
Posted: Fri Aug 01, 2008 2:34 am
by 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.
Re: Searching for a string of set (or unset) bits in a bitmap
Posted: Fri Aug 01, 2008 4:26 am
by Korona
MessiahAndrw wrote: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)
Re: Searching for a string of set (or unset) bits in a bitmap
Posted: Fri Aug 01, 2008 6:54 am
by 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.)
Re: Searching for a string of set (or unset) bits in a bitmap
Posted: Fri Aug 01, 2008 7:42 pm
by 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.
Re: Searching for a string of set (or unset) bits in a bitmap
Posted: Sat Aug 02, 2008 2:26 am
by AJ
bewing wrote: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
Re: Searching for a string of set (or unset) bits in a bitmap
Posted: Sat Aug 02, 2008 8:39 am
by bewing
AJ wrote:
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.
AJ wrote:
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.
AJ wrote:
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?
Re: Searching for a string of set (or unset) bits in a bitmap
Posted: Sat Aug 02, 2008 3:24 pm
by 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>
Re: Searching for a string of set (or unset) bits in a bitmap
Posted: Sat Aug 02, 2008 7:01 pm
by bewing
Thanks, Solar.
Yup, basically a plain ol' nested if. So much for the "efficiency" of a switch statement in the general case.
Re: Searching for a string of set (or unset) bits in a bitmap
Posted: Sun Aug 03, 2008 3:28 am
by Korona
bewing wrote: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)