Algorithm Help
David Mott
I have a bitmap representing available pages in a file. A
GetPage(PageCount) function should return the offset into the file where
PageCount of contiguous pages resides. Within the function I have a pointer
to the bitmap and want to scan the bitmap until PageCount of free bits is
found. For example assume the following bitmap is present in memory:
10101100110001101010000111111011001011001
If I wanted to retrieve the offset where 4 bits are free, the
FindFreeBitsInBitmap(4) function should return 18 (the location of 0000)
My FindFreeBitsInBitmap(BitCount) function should scan the block of memory
until it encounters BitCount of free bits. Then should return the offset
into the block where the free bits occur. There's several approaches to
this problem, can someone provide me with a very efficient algorithm to
locate the starting offset? This function resides in a DBMS and should be
very efficient as it's called very frequently. All input is greatly
appreciated.
Cheers,
David
Randall Hyde
"The Art of Assembly Language" at http://webster.cs.ucr.edu.
It deals with this sort of stuff.
Cheers,
Randy Hyde
"David Mott" <dm...@austin.rr.not.home.com> wrote in message
news:gN%Pb.7292$6o4...@fe2.texas.rr.com...
Matt Taylor
news:gN%Pb.7292$6o4...@fe2.texas.rr.com...
This system would probably be better managed with a bucket allocator. Bit
manipulations are slow.
For searching a bit string for a run of 0s, I would make use of the fact
that a run of N 0s has the property that (x >> 0) | (x >> 1) | (x >> 2) |
.... | (x >> N - 1) != -1. The following code exploits that to search 32 bits
in parallel. This code is nowhere near optimal, but it's written for
clarity, not speed.
; uint SearchBitString(byte *bits, uint len, uint pages)
SearchBitString:
push ebp
push edi
push esi
push ebx
; ASSUMPTIONS:
; (bits & 3 == 0) && (len & 3 == 0)
; 0 < pages < 32
; eax = current dword
; ebx = scratch
; ecx = scratch
; edx = previous dword
; esi = end pointer
; edi = current pointer
; ebp = scratch
mov edi, [esp+20]
mov esi, [esp+24]
add esi, edi
; If this isn't -1, we'll spurriously detect that the first N pages are
free.
mov edx, -1
..Search:
; Load next value
mov eax, [edi]
; Save current
mov ebx, eax
; This is a particularly bad loop, but I'm striving for simplicity to
; demonstrate the algorithm. You probably want to bsf on the length and
; do this in approximately logarithmic time. Too bad imul can't be used
here.
mov ecx, [esp+28]
..Check32:
; Shift 1 bit from edx -> eax
add edx, edx ; CF = last >> 31
mov ebp, eax ; ebp = eax
adc eax, eax ; eax = (eax << 1) | (last >> 31)
or eax, ebp ; eax = eax | (eax << 1) | (last >> 31)
dec ecx
jnz .Check32
; Prev = current
mov edx, ebx
; Check to see if we found a run of 0s
cmp eax, -1
jne .Found
; Keep going...
add edi, 4
cmp edi, esi
jb .Search
; Found nothing
mov eax, -1
..Done:
pop ebx
pop esi
pop edi
pop ebp
ret
..Found:
; Find first 0
not eax
bsf eax, eax
; Compute offset in bit string
sub edi, [esp+20]
lea eax, [edi*8+eax]
; Final adjustment to get base
sub eax, [esp+28]
; Return our answer
jmp .Done
-Matt
Terje Mathisen
> "David Mott" <dm...@austin.rr.not.home.com> wrote in message
> news:gN%Pb.7292$6o4...@fe2.texas.rr.com...
>
>>Hi all, hope someone can help me with an algorithm.
>>
>>I have a bitmap representing available pages in a file. A
>>GetPage(PageCount) function should return the offset into the file where
>>PageCount of contiguous pages resides. Within the function I have a
>
> pointer
>
>>to the bitmap and want to scan the bitmap until PageCount of free bits is
>>found. For example assume the following bitmap is present in memory:
>>
>>10101100110001101010000111111011001011001
>>
>>If I wanted to retrieve the offset where 4 bits are free, the
>>FindFreeBitsInBitmap(4) function should return 18 (the location of 0000)
> This system would probably be better managed with a bucket allocator. Bit
> manipulations are slow.
>
> For searching a bit string for a run of 0s, I would make use of the fact
> that a run of N 0s has the property that (x >> 0) | (x >> 1) | (x >> 2) |
> ..... | (x >> N - 1) != -1. The following code exploits that to search 32 bits
> in parallel. This code is nowhere near optimal, but it's written for
> clarity, not speed.
It seems to me that this is really two different problems, depending
upon the expected length of the requested blocks.
I.e. if the block length is >> 32, then you should first scan for a
number of consecutive zero dwords.
If, otoh, len = 4 is typical, then we need another method, particularly
if the expected scan length is substantial. I.e. how large is the entire
table?
The fast way is (as Matt mentions) to maintain some kind of parallel
data structure which remembers where the free blocks, sorted by size.
I.e. one table for single free blocks, another for blocks of length 2
(or 3), one for 4+, one for 8+ etc.
Allocation then becomes simply picking the first entry from the relevant
list, optionally going through it for the best fit.
With the naked bitstream you can use combinations of REPE SCASD for
locating the first word with at least one free block (bit), BSF to find
that bit and SHRD + BSF to determine how long it was.
Terje
--
- <Terje.M...@hda.hydro.com>
"almost all programming can be viewed as an exercise in caching"
C
Finding a free page is relatively easy, however finding
contigious groupings of pages is a little more difficult.
I implemented something similar for the page mananger in
an old version of my operating system kernel. (However,
for this implementation groupings of greater than 32 bits
the algorithm provided will not work, this was not a problem
in my application -- but maybe in yours.)
The algorithm (using pseudo code) would go something like
this ...
find_in_bitmap:
set POS:Cardinal32 := offset BITMAP
set MASK:Cardinal32 := ( 1 shift left GROUP_SIZE ) - 1
while not at end of bitmap [
TEMP:Cardinal32 := inverted value at POS.
while TEMP >= MASK [
COUNT:Cardinal32 := 0
TEMP2:Cardinal32 := TEMP & MASK
if TEMP2 == MASK [
goto return_found
]
TEMP2 := TEMP2 shift right 1
COUNT := COUNT + 1
]
POS := POS + 4
]
return := error contigious group not found
return_found:
return ( found at POS - offset BITMAP ) * 32 + COUNT
(converting to assembly should be easy .. please
post your solution)
I advise you provide a different function to search for
single pages -- this is both a trivial case of the above
algorithm and normally the most common case.
Also caching the point where the search should be started
instead of always starting from offset BITMAP (to avoid
having to look though many set bits) will save some time.
MMX or XMM may help if groups tend to be small (< 8 bits).
In the innerloop, instead of shifting right one bit at a
time, shift right multiple bits depending on the value of
TEMP2. Eg. if TEMP2 & ( 1 << GROUP_SIZE ) == 0 then shift
right by GROUP_SIZE. (Mathematically, this is somewhat
similar to a simplified case of the Boyer Moore search
algorithm.)
Finally there are better ways to store page lists -- eg.
RLE compressing the bitmap or linked lists. If you can
use a different way to represent that data (ie. something
other than a single bitmap) more efficient algorithms may
be utilised. There where a number of good posts on this
subject in alt.os.development a few months ago -- I suggest
you look them up in the archives.
C
2004-01-23
Terje Mathisen
> In the innerloop, instead of shifting right one bit at a
> time, shift right multiple bits depending on the value of
> TEMP2. Eg. if TEMP2 & ( 1 << GROUP_SIZE ) == 0 then shift
> right by GROUP_SIZE. (Mathematically, this is somewhat
> similar to a simplified case of the Boyer Moore search
> algorithm.)
Indeed, this is a very important observation, and one that should
definitely be employed for any largish block request.
I.e. as I wrote in my previous msg, if the block count is large, use
faster method to locate it, starting with dwords if possible.
One possible method which is quite fast is to subtract 7 and truncate
the count to the nearest multiple of 8, and then start by scanning for
the corresponding number of free bytes, using a BM byte-based algorithm:
(Always keeping a guarding free block at the end of the freemap, larger
than the largest allowable request can speed it up!)
int findfree(int blocks)
{
if (blocks > LIMIT) {
bytes = (blocks-7) >> 3;
b_minus_1 = bytes - 1;
last_full_byte = b_minus_1;
do {
while (last_full_byte < freemap_size &&
freelist[last_full_byte] != '\0')
last_full_byte += b_minus_1;
if (last_full_byte >= freemap) return ERROR_NOT_FOUND;
found_bits = b_minus_1 << 3;
if (/* check for additional free bits before and after */) return
found_bit_position;
} while (1);
}
else if (blocks > BITLIMIT) { // Do bitbased BM search
bitpos = b_minus_1 = blocks-1;
do {
while ((bitpos < max_bitpos) &&
(freemap[bitpos >> 3] & (1 << (bitpos & 7)])
) bitpos += b_minus_1;
if (i >= max_bitpos) return ERROR_NOT_FOUND;
// Possible location, check previous bits:
for (i = bitpos - b_minus_1; i < bitpos; i++) {
if (freemap[i >> 3] & (1 << (i & 7))]) break;
} while (i < bitpos);
return bitpos - b_minus_1;
}
else { // Do a simple search!
}
>
> Finally there are better ways to store page lists -- eg.
> RLE compressing the bitmap or linked lists. If you can
> use a different way to represent that data (ie. something
> other than a single bitmap) more efficient algorithms may
> be utilised. There where a number of good posts on this
> subject in alt.os.development a few months ago -- I suggest
> you look them up in the archives.
You can probably find quite a bit of good code in any of the open source
OS repositories, they all have some form of freelist maintenance in
their file systems.
David Mott
future I'll come across a better implementation. Maybe someone can benifit
or improve the following functions. This VB/ASM code is broken into two
functions. GetByteBitFields returns an array of possible entires within a
byte boundry. The GetByteBitFields is used by FindFreeBitsInArray to scan
the entire buffer using the returned possibilities from GetByteBitFields to
locate the first occurance of the free bits. Comments or improvements
please?
Public Function GetByteBitFields(ByVal BitCount As Byte) As Byte()
'returns an array of all possible combinations of set bits in a byte
Dim I As Long, X As Long
Dim bMask() As Byte
ReDim bMask(8 - BitCount) 'allocate possible entries in array
For I = 0 To BitCount - 1 'set bits according to count
X = (X * 2) + 1
Next I
X = (X Xor &HFF) 'chop off leading bits if present
For I = UBound(bMask) To 0 Step -1 'loop through possible entries,
sort ascending
bMask(I) = X
ROL _X$[EBP], 1
Next I
GetByteBitFields = bMask
End Function
Public Function FindFreeBitsInArray(ByVal ArrPtr As Long, ByVal BitCount As
Byte) As Long
Dim bMask() As Byte
Dim I As Long, X As Long, CurrByte As Long
'Calls GetByteBitFields to retrieves an array of all possible bits
of BitCount in a byte..
'scans the array pointed at by ArrPtr for the first location of free
bits in the array then sets the bits in the array
bMask = GetByteBitFields(BitCount) 'get all possible entries
For I = 0 To PAGE_SIZE - 1 'scan the entire page for entires one
byte at a time
MOV EAX, DWORD PTR _ArrPtr$[EBP]
ADD EAX, _I$[EBP]
MOVZX EBX, BYTE PTR [EAX]
MOV _CurrByte$[EBP], BX
For X = 0 To UBound(bMask) 'scan the byte using the
possible entires
If (CurrByte Or bMask(X)) = bMask(X) Then 'if the
entry has enough free bits
CurrByte = CurrByte Or bMask(X) 'mark the
bits
MemCpy VarPtr(ArrPtr) + I, CurrByte, 1
'replace the entry with the marked bits
FindFreeBitsInArray = (I * 8) + X + 1
'return the offset
Exit Function
End If
Next X
Next I
End Function
"David Mott" <dm...@austin.rr.not.home.com> wrote in message
news:gN%Pb.7292$6o4...@fe2.texas.rr.com...