qiyao wrote: @felipepiovezan , thanks for the review, you're right that the pattern you describe is bad, so I'm going to drop the scan window rather than defend it. To be precise about the bound first: the scan isn't over the whole cache, only over chunks whose start falls in `[addr - (M-1), addr + len)`, where `M` is the largest chunk length inserted since the last stop. So one insert is `O(log n + k)` with `k <= min(n, M)`, and `n` inserts are `O(n log n + n * min(n, M))`, linear in `n` once the inserted ranges are spread further apart than `M`. But your example is exactly the clustered case: 1000 ranges 16 bytes apart span 16KB, which is M, so k grows to n and it does degenerate to quadratic. `M` also never shrinks when a chunk is erased, so one big expedited chunk keeps the window wide. The way out is your suggestion in the following comment, and it also answers the lookup question: a lookup miss is not a correctness problem, it just falls through to L2 or the inferior. Only invalidation has to be exhaustive. So: - `Flush` walks the L1 cache and erases every chunk that intersects the range: `O(n)`, one caller (`Process::WriteMemory`), which then does a packet round trip anyway. - `AddL1CacheData` goes back to a plain insert: `O(log n)`. - `FindL1CacheEntry` goes back to checking only the nearest chunk starting at or below the address: `O(log n)`, identical to what we ship today, so no new data structure is needed. - `m_L1_max_chunk_byte_size` and `GetLowestPossibleChunkStart` disappear, along with the comments you flagged above. If we later want lookups to exploit overlapping chunks, that is a separate change and wants a real interval map. What do you think?
https://github.com/llvm/llvm-project/pull/208347 _______________________________________________ lldb-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/lldb-commits
