Re: Algorithm Help

From: Terje Mathisen (terje.mathisen_at_hda.hydro.com)
Date: 01/23/04 

Date: Fri, 23 Jan 2004 16:53:16 +0000 (UTC)

C wrote:
> 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.

Terje 

-- 
- <Terje.Mathisen@hda.hydro.com>
"almost all programming can be viewed as an exercise in caching"

Relevant Pages

  • Re: Algorithm Help
    ... 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, ... > other than a single bitmap) more efficient algorithms may ...
    (alt.lang.asm)
  • Re: whats faster, initialize component, or form load?
    ... for every algorithm there is parallel version. ... Suppose you need to initialize 1 form - parallel might not do any good ... of the overhead of handling multiple threads. ... Furthermore, even when they do want to use the CPU, they are ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: Most efficient matrix multiplication algorithm
    ... In an interview recently, I was recently asked to multiply two ... If the CPU has many registers, then you could load multiple row values ... will be more efficient than the "obvious" algorithm. ... copying from external slow memories to internal fast ...
    (comp.arch.embedded)
  • Re: Transparent compression in the FS
    ... Figure that you had a 'perfect' hash algorithm, ... meaning that multiple algorithms may make the final result ... I believe that checksum/hash is a perfectly valid way of verifying the ...
    (Linux-Kernel)
Loading