From: brangdonj@googlemail.com   
      
   In article ,   
   DavidL@example.invalid (David Lowndes) wrote:   
   > >Allocations and deallocations are way cheaper than they were old   
   > >times.   
   >   
   > Why, what's magically changed?   
      
   Better algorithms. In the olden days, there would be a single heap   
   used for blocks of all sizes. Allocation code would have to search   
   for a free block of a suitable size, and potentially split it in   
   two, and deallocation code would potentially have to coalesce   
   adjacent free blocks.   
      
   I believe modern allocators keep, in effect, a free list for each   
   size of block. Allocation code is like:   
      
        void *alloc( size_t sz ) {   
            size_t index = sz / 8;   
            if (index < 256)   
                if (Block *pBlock = freeList[index]) {   
                    freeList[index]->next = pBlock->next;   
                    pBlock->next = (Block *)index;   
                    return pBlock->memory;   
                }   
            // ...   
        }   
      
        void free( void *memory ) {   
            if (!memory)   
                return;   
            Block *pBlock = (Block *)((char *)memory - sizeof(Block *));   
            size_t index = (size_t) pBlock->next;   
            if (index < 256) {   
                pBlock->next = freeList[index];   
                freeList[index] = pBlock;   
                return;   
            }   
            // ...   
        }   
      
   So in the common case, there is no looping at all, and not many   
   if-statements.   
      
   -- Dave Harris, Nottingham, UK.   
      
      
   --   
         [ See http://www.gotw.ca/resources/clcm.htm for info about ]   
         [ comp.lang.c++.moderated.    First time posters: Do this! ]   
      
   --- SoupGate-Win32 v1.05   
    * Origin: you cannot sedate... all the things you hate (1:229/2)