| 822 | } |
| 823 | |
| 824 | GlobalDecreasingSizeBestFitHeap::ChunkCandidate |
| 825 | GlobalDecreasingSizeBestFitHeap::FindChunkCandidate( |
| 826 | const GlobalDecreasingSizeBestFitHeap::BufferInterval& buffer_interval, |
| 827 | int64 preferred_offset) const { |
| 828 | VLOG(1) << "Finding chunks for buffer: " |
| 829 | << buffer_interval.buffer->ToString(); |
| 830 | VLOG(1) << "Size " << buffer_interval.size << ", start " |
| 831 | << buffer_interval.start << ", end " << buffer_interval.end; |
| 832 | auto chunks_overlapping_in_time = interval_tree_.ChunksOverlappingInTime( |
| 833 | buffer_interval.start, buffer_interval.end); |
| 834 | // Get all colocated buffers and gather all interferenced chunks. |
| 835 | // |
| 836 | // Imagine that we've already allocated three chunks : a, b and c. And now |
| 837 | // we want to allocate d. Since e is colocated with d, we have to allocate |
| 838 | // chunks for them together at the same address. To do this, we first gather |
| 839 | // all chunks that overlap with d and e on the time dimension, in this case |
| 840 | // the overlapped chunks are a and b (c doesn't overlap with either of d and |
| 841 | // e), then find create a new chunk that doesn't overlap with a and b on the |
| 842 | // space dimension. |
| 843 | // |
| 844 | // space |
| 845 | // ^ |
| 846 | // |+--d---+ +---e---+ |
| 847 | // | |
| 848 | // |+---+ +---------------+ +-------+ |
| 849 | // || | | | | | |
| 850 | // || | | | | | |
| 851 | // |+-a-+ +-------b-------+ +---c---+ |
| 852 | // ----------------------------------------> time |
| 853 | for (auto colocation : GetTransitiveColocations(buffer_interval)) { |
| 854 | auto colocation_interval = buffer_intervals_.at(colocation); |
| 855 | auto colocation_overlapping = interval_tree_.ChunksOverlappingInTime( |
| 856 | colocation_interval.start, colocation_interval.end); |
| 857 | VLOG(1) << " Alias size " << colocation_interval.size << ", start " |
| 858 | << colocation_interval.start << ", end " << colocation_interval.end |
| 859 | << " " << colocation_interval.buffer->ToString(); |
| 860 | chunks_overlapping_in_time.insert(chunks_overlapping_in_time.end(), |
| 861 | colocation_overlapping.begin(), |
| 862 | colocation_overlapping.end()); |
| 863 | } |
| 864 | absl::c_sort(chunks_overlapping_in_time, [](const Chunk& x, const Chunk& y) { |
| 865 | return x.offset < y.offset; |
| 866 | }); |
| 867 | |
| 868 | // Find the minimum free chunk that can hold this buffer. |
| 869 | ChunkCandidate chunk_candidate{Chunk{-1, INT64_MAX}, result_.heap_size}; |
| 870 | Chunk& min_fit_chunk = chunk_candidate.chunk; |
| 871 | int64 preferred_chunk_end = preferred_offset + buffer_interval.size; |
| 872 | auto use_free_chunk_if_smaller = [&](int64 free_offset, int64 free_size) { |
| 873 | if (free_size < buffer_interval.size) { |
| 874 | return; |
| 875 | } |
| 876 | |
| 877 | // If a preferred offset is provided, pick that offset. |
| 878 | if (free_offset <= preferred_offset && |
| 879 | free_offset + free_size >= preferred_chunk_end) { |
| 880 | min_fit_chunk = {preferred_offset, buffer_interval.size}; |
| 881 | } else if (free_offset + free_size == result_.heap_size && |
nothing calls this directly
no test coverage detected