Optimizing Malloc and FreeGoals of This LectureFree Chunk: Pointer, Size, DataFree List: Circular Linked ListMalloc: First-Fit AlgorithmMalloc: First Case, A Perfect FitMalloc: Second Case: Big ChunkFreeFree: Finding Location to InsertFree: Handling Corner CasesFree: Inserting Into Free ListCoalescing With NeighborsCoalesce With Upper NeighborCoalesce With Lower NeighborK&R Malloc and FreeImprovements: PlacementImprovements: SplittingImprovements: CoalescingImprovements: Faster FreeSize: Finding Next ChunkSize: Finding Previous ChunkPointers: Next Free ChunkPointers: Previous Free ChunkEfficient FreeBut Malloc is Still Slow…Binning Strategies: Exact FitBinning Strategies: RangeStupid Programmer TricksSlide 29Suggestions for Assignment #6Conclusions1Optimizing Malloc and Free2Goals of This Lecture•Brief review of K&R implementationCircular linked list of free chunks, with pointer and size in header–Malloc: first-fit algorithm, with splitting–Free: coalescing with adjacent chunks, 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 chunks of different sizes–One bin per chunk size, or one bin for a range of sizes3Free Chunk: Pointer, Size, Data•Free chunk in memoryPointer to the next chunkSize of the chunkUser datap (address returned to the user)user datasizeheader4Free List: Circular Linked List•Free chunks, linked togetherExample: circular linked list•Keep list in order of increasing addressesMakes it easier to coalesce adjacent free chunksInuseInuseInuseFree 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 chunk that is big enoughPatch up the listReturn a chunk to the userp pprev pprev6Malloc: First Case, A Perfect Fit•Suppose the first fit is a perfect fitRemove the chunk from the listLink the previous free chunk with the next free chunkReturn the current to the user (skipping header)pprevp+17Malloc: Second Case: Big Chunk•Suppose the chunk is bigger than requestedDivide the free chunk into two chunksKeep first (now smaller) chunk in the free listAllocate the second chunk to the userp p8Free•User passes a pointer to the memory chunk void free(void *ap);•Free function inserts chunk 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 chunk is before first entry in the free list, orTo-be-freed chunk 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 chunksCheck 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 chunk•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 chunkbpplowerp->s.ptrp p->s.ptr15K&R Malloc and Free•AdvantagesSimplicity of the code•OptimizationsRoving free-list pointer is left at the last place a chunk was allocatedSplitting large free chunks to avoid wasting spaceCoalescing contiguous free chunks to reduce fragmentation•LimitationsInefficient use of memory: fragmentation–Best-fit policy can leave lots of “holes” of free chunks in memoryLong execution times: linear-time overhead–Malloc scans the free list to find a big-enough chunk–Free scans the free list to find where to insert a chunk16Improvements: Placement•Placement: reducing fragmentationDeciding which free chunk to use to satisfy a malloc() requestK&R uses “first fit” (really, “next fit”)–Example: malloc(8) would choose the 20-byte chunkAlternative : “best fit” or “good fit” to avoid wasting space–Example: malloc(8) would choose the 8-byte chunkInuseInuseInuseFree list208 5017Improvements: Splitting•Splitting: avoiding wasted memorySubdividing a large free chunk, and giving part to the userK&R malloc() does splitting whenever the free chunk is too big–Example: malloc(14) splits the 20-byte chunkAlternative : selective splitting, only when the savings is big enough–Example: malloc(14) allocates the entire 20-byte chunkInuseInuseInuseFree list8 502018Improvements: Coalescing•Coalescing: reducing fragmentationCombining contiguous free chunks into a larger free chunkK&R does coalescing in free() whenever possible–Example: combine free chunk with lower and upper neighborsAlternative : deferred coalescing, done only intermittently–Example: wait, and coalesce many entries at a time laterInuseFREEMEInuseFree listbpplower upper19Improvements: 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 chunk (in # of units)–Flag indicating whether the chunk is free or in use–If free, a pointer to the next free chunkFooter in all chunks–Size of the chunk (in # of units)–If free, a pointer to the previous free chunkheadfoot20Size: Finding Next Chunk•Go quickly to next chunk in memoryStart with the user’s data portion of the chunkGo backwards to the head of the chunk–Easy, since you know the size of the headerGo forward to the head of the next chunk–Easy, since you know the size of the current chunk21Size: Finding Previous Chunk•Go quickly to
View Full Document