DOC PREVIEW
Princeton COS 217 - Optimizing Malloc and Free

This preview shows page 1-2-14-15-30-31 out of 31 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 31 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 31 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 31 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 31 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 31 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 31 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 31 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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 implementationCircular 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 freeLimitations–Fragmentation of memory due to first-fit strategy–Linear time to scan the list during malloc and free•Optimizations related to assignment #6Placement choice, splitting, and coalescingFaster free–Size information in both header and footer–Next and previous free-list pointers in header and footerFaster 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 memoryPointer to the next chunkSize of the chunkUser datap (address returned to the user)user datasizeheader4Free List: Circular Linked List•Free chunks, linked togetherExample: circular linked list•Keep list in order of increasing addressesMakes it easier to coalesce adjacent free chunksInuseInuseInuseFree list5Malloc: First-Fit Algorithm•Start at the beginning of the list•Sequence through the listKeep a pointer to the previous element•Stop when reaching first chunk that is big enoughPatch up the listReturn a chunk to the userp pprev pprev6Malloc: First Case, A Perfect Fit•Suppose the first fit is a perfect fitRemove the chunk from the listLink the previous free chunk with the next free chunkReturn the current to the user (skipping header)pprevp+17Malloc: Second Case: Big Chunk•Suppose the chunk is bigger than requestedDivide the free chunk into two chunksKeep first (now smaller) chunk in the free listAllocate 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 listIdentify the start of entry Find the location in the free listAdd 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 memoryTo-be-freed chunk is before first entry in the free list, orTo-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 insertingPointer to to-be-freed element: bpPointer to previous element in free list: p•Coalescing into larger free chunksCheck 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•AdvantagesSimplicity of the code•OptimizationsRoving free-list pointer is left at the last place a chunk was allocatedSplitting large free chunks to avoid wasting spaceCoalescing contiguous free chunks to reduce fragmentation•LimitationsInefficient use of memory: fragmentation–Best-fit policy can leave lots of “holes” of free chunks in memoryLong 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 fragmentationDeciding which free chunk to use to satisfy a malloc() requestK&R uses “first fit” (really, “next fit”)–Example: malloc(8) would choose the 20-byte chunkAlternative : “best fit” or “good fit” to avoid wasting space–Example: malloc(8) would choose the 8-byte chunkInuseInuseInuseFree list208 5017Improvements: Splitting•Splitting: avoiding wasted memorySubdividing a large free chunk, and giving part to the userK&R malloc() does splitting whenever the free chunk is too big–Example: malloc(14) splits the 20-byte chunkAlternative : selective splitting, only when the savings is big enough–Example: malloc(14) allocates the entire 20-byte chunkInuseInuseInuseFree list8 502018Improvements: Coalescing•Coalescing: reducing fragmentationCombining contiguous free chunks into a larger free chunkK&R does coalescing in free() whenever possible–Example: combine free chunk with lower and upper neighborsAlternative : 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 insertKeeping 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 chunkFooter 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 memoryStart with the user’s data portion of the chunkGo backwards to the head of the chunk–Easy, since you know the size of the headerGo 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

Princeton COS 217 - Optimizing Malloc and Free

Documents in this Course
Summary

Summary

4 pages

Lecture

Lecture

4 pages

Generics

Generics

14 pages

Generics

Generics

16 pages

Lecture

Lecture

20 pages

Debugging

Debugging

35 pages

Types

Types

7 pages

Lecture

Lecture

21 pages

Assembler

Assembler

16 pages

Lecture

Lecture

20 pages

Lecture

Lecture

39 pages

Testing

Testing

44 pages

Pipeline

Pipeline

19 pages

Lecture

Lecture

6 pages

Signals

Signals

67 pages

Building

Building

17 pages

Lecture

Lecture

7 pages

Modules

Modules

12 pages

Generics

Generics

16 pages

Testing

Testing

22 pages

Signals

Signals

34 pages

Lecture

Lecture

19 pages

Load more
Download Optimizing Malloc and Free
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Optimizing Malloc and Free and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Optimizing Malloc and Free 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?