Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Z-Rays: Divide Arrays and Conquer Speed and Flexibility Jennifer B. Sartor et al.Presented by Yuhao ZhuCS 395TMotivationsContiguous implementation of arrays incurs fragmentation (wastes space), and is GC-unfriendly, especially latencyDiscontiguous implementation overcomes above problems, but brings about the throughput issue due to the high overhead of indirectionDiscountiguous ArraysOrganizationHeaderIndirection pointersRemainders Why does it work?Why does it not work?Z-rays implementation5 optimizations in a momentSeparate arraylet spacesub-space of the heapCollected under the control of its parent spineEach arraylet has its own liveness bitSpines are in the nursury space and collected as normalFirst-NNearly 90% of all array accesses occur at access positions less than 4KB. So inline them in the spine and access without indirectionMost effective optimizationAddressed the performance issue of basic discontiguous designLazy AllocationSpace optimizationEmploys an immutable zero arraylet, to which all indirection pointers are pointing upon creationNeed to be performed atomically due to possible race condition of multiple threadsZero CompressionSpace optimization, utilizes the zero arrayletReinstall the indirection pointer to the zero arraylet when all elements in an arraylet are zerosPerformed during GC timeIncurs additional indirection and scanning operatins, but compensated by the reduction in the memory costFast Array CopyDiscontiguous arrays make array copy complicatedOne optimization is to hoist the indirection operation outside of the loop when performing sequential copyOne indirection instead of nCopy-on-WriteSpace optimizationA generalization of lazy allocationOnly create the private instance of an arraylet after first writeRealized by tainting the least significant bit of the indirection pointers pointing to the shared arrayletImplementation NotesRead/Write BarriersThe arraylet space is non-moving, and the age of an object is indicated by its parent spinePromote survived spines into mature space, which effectively promotes corresponding arrayletsWhat's the arraylet space allocator? Any comment?Do we mark the liveness bits of arraylets whose source spine is in nursery space?If no, what's the implication?EvaluationsBenchmark characteristicsEvaluations (cont.)COW degrades the performanceDue to the maintenance of barriersZ-rays could even IMPROVE the performanceThe indirection overhead is compensated by the reduction of collection timeEvaluations (cont.)How does Z-ray affect the performance?Mutator: indirection beyond First NCollector: varies significantly- indirection + improvements through space efficiencyEvaluations (cont.)First-N is the most significant optimizationFast array copy benefits benchmarks with frequent array copying very muchCOW degrades performanceDiscussionWhy is it called Z-rays???Any concurrency to explore?How to configure Z-rays for different design goals?Any further
View Full Document