Optimizing Malloc and FreeGoals of This LectureFree Block: Pointer, Size, DataFree List: Circular Linked ListMalloc: First-Fit AlgorithmMalloc: First Case, A Perfect FitMalloc: Second Case: Big BlockFreeFree: Finding Location to InsertFree: Handling Corner CasesFree: Inserting Into Free ListCoalescing With NeighborsCoalesce With Upper NeighborCoalesce With Lower NeighborStrengths of K&R Malloc and FreeWeaknesses of K&R Malloc and FreeImprovements: PlacementImprovements: SplittingImprovements: CoalescingImprovements: Faster FreeSize: Finding Next BlockSize: Finding Previous BlockPointers: Next Free BlockPointers: Previous Free BlockEfficient FreeBut Malloc is Still Slow…Binning Strategies: Exact FitBinning Strategies: RangeSuggestions for Assignment #6ConclusionsBackup SlidesStupid Programmer TricksSlide 331Optimizing Malloc and FreeProfessor Jennifer Rexfordhttp://www.cs.princeton.edu/~jrex2Goals of This Lecture•Brief review of K&R implementationCircular linked list of free blocks, with pointer and size in header–Malloc: first-fit algorithm, with splitting–Free: coalescing with adjacent blocks, if they are freeLimitations–Fragmentation of memory due to first-fit strategy–Linear time to scan the list during malloc and free•Optimizations related to assignment #6Placement choice, splitting, and coalescingFaster free–Size information in both header and footer–Next and previous free-list pointers in header and footerFaster malloc–Separate free list for free blocks of different sizes–One bin per block size, or one bin for a range of sizes3Free Block: Pointer, Size, Data•Free block in memoryPointer to the next blockSize of the blockUser datap (address returned to the user)user datasizeheader4Free List: Circular Linked List•Free blocks, linked togetherExample: circular linked list•Keep list in order of increasing addressesMakes it easier to coalesce adjacent free blocksInuseInuseInuseFree list5Malloc: First-Fit Algorithm•Start at the beginning of the list•Sequence through the listKeep a pointer to the previous element•Stop when reaching first block that is big enoughPatch up the listReturn a pointer to the userp pprev pprev6Malloc: First Case, A Perfect Fit•Suppose the first fit is a perfect fitRemove the block from the listLink the previous free block with the next free blockReturn the current to the user (skipping header)pprevp+17Malloc: Second Case: Big Block•Suppose the block is bigger than requestedDivide the free block into two blocksKeep first (now smaller) block in the free listAllocate the second block to the userp p8Free•User passes a pointer to the memory block void free(void *ap);•Free function inserts block into the listIdentify the start of entry Find the location in the free listAdd to the list, coalescing entries, if neededapbp9Free: Finding Location to Insert•Start at the beginning•Sequence through the list•Stop at last entry before the to-be-freed elementInuseFREEMEInuseFree listbpp10Free: Handling Corner Cases•Check for wrap-around in memoryTo-be-freed block is before first entry in the free list, orTo-be-freed block is after the last entry in the free listInuseFREEMEInuseFree listbp p11Free: Inserting Into Free List•New element to add to free list•Insert in between previous and next entries•But, there may be opportunities to coalescebpp p->s.ptr12Coalescing With Neighbors•Scanning the list finds the location for insertingPointer to to-be-freed element: bpPointer to previous element in free list: p•Coalescing into larger free blocksCheck if contiguous to upper and lower neighborsInuseFREEMEInuseFree listbpplower upper13Coalesce With Upper Neighbor•Check if next part of memory is in the free list•If so, make into one bigger block•Else, simply point to the next free elementbpupperp p->s.ptrp p->s.ptr14Coalesce With Lower Neighbor•Check if previous part of memory is in the free list•If so, make into one bigger blockbpplowerp->s.ptrp p->s.ptr15Strengths of K&R Malloc and Free•AdvantagesSimplicity of the code•Optimizations to malloc()Splitting large free block to avoid wasting space•Optimization to free()Roving free-list pointer is left at the last place a block was allocatedCoalescing contiguous free blocks to reduce fragmentationpbpupperp p->s.ptr16Weaknesses of K&R Malloc and Free•Inefficient use of memory: fragmentationBest-fit policy can leave lots of “holes” of free blocks in memory•Long execution times: linear-time overheadMalloc scans the free list to find a big-enough blockFree scans the free list to find where to insert a block•Accessing a wide range of memory addresses in free listCan lead to large amount of paging to/from the diskInuseInuseInuseFree list208 5017Improvements: Placement•Placement: reducing fragmentationDeciding which free block to use to satisfy a malloc() requestK&R uses “first fit” (really, “next fit”)–Example: malloc(8) would choose the 20-byte blockAlternative: “best fit” or “good fit” to avoid wasting space–Example: malloc(8) would choose the 8-byte blockInuseInuseInuseFree list208 5018Improvements: Splitting•Splitting: avoiding wasted memorySubdividing a large free block, and giving part to the userK&R malloc() does splitting whenever the free block is too big–Example: malloc(14) splits the 20-byte blockAlternative: selective splitting, only when the savings is big enough–Example: malloc(14) allocates the entire 20-byte blockInuseInuseInuseFree list8 502019Improvements: Coalescing•Coalescing: reducing fragmentationCombining contiguous free blocks into a larger free blocksK&R does coalescing in free() whenever possible–Example: combine free block with lower and upper neighborsAlternative: deferred coalescing, done only intermittently–Example: wait, and coalesce many blocks at a time laterInuseFREEMEInuseFree listbpplower upper20Improvements: Faster Free•Performance problems with K&R free()Scanning the free list to know where to insertKeeping track of the “previous” node to do the insertion•Doubly-linked, non-circular list Header–Size of the block (in # of units)–Flag indicating whether the block is free or in use–If free, a pointer to the next free blockFooter–Size of the block (in # of units)–If free, a pointer to the previous free blockheadfoot21Size:
View Full Document
Unlocking...