Page MenuHomePhabricator

[InterleavedAccessAnalysis] Use unordered_map to avoid tombstone insertion.
Changes PlannedPublic

Authored by fhahn on Mar 6 2019, 2:03 PM.

Details

Summary

Nothing prevents a key to the Members map being a tombstone/empty
special value. By using unordered_map, we avoid limiting the keys to
exclude tombstone/empty key values. Alternatively we could avoid adding
tombstone/empty key values to interleave groups, but there should be no
performance impact by not using DenseMap.

Fixes https://bugs.chromium.org/p/oss-fuzz/issues/detail?id=11638

Event Timeline

fhahn created this revision.Mar 6 2019, 2:03 PM
Herald added a project: Restricted Project. · View Herald TranscriptMar 6 2019, 2:03 PM

unordered_map is going to be pretty inefficient given the key/value types... it might be worthwhile to add some sort of DenseMap relative to LLVM that handles tombstones differently. (This also just came up in https://reviews.llvm.org/D59016.)

fhahn added a comment.Mar 6 2019, 3:15 PM

unordered_map is going to be pretty inefficient given the key/value types... it might be worthwhile to add some sort of DenseMap relative to LLVM that handles tombstones differently. (This also just came up in https://reviews.llvm.org/D59016.)

Ok, I'll look into that.

fhahn planned changes to this revision.Thu, Apr 4, 1:06 PM

I'm currently prototyping a version of DenseMap, that uses bit vectors to mark empty/tombstone slots to circumvent the issue. There are some scenarios where this could potentially also improve runtime performance, at the cost of 2 bits per slot. What do you think?

That layout generally makes sense, sure. Maybe you could get away with one bit per slot by sticking a bit to distinguish between either empty/tombstone into the main table, but I guess it's not really a big deal either way if you're talking about one or two bits per entry. I guess two bits makes failed lookups faster.

A higher-quality MapVector, which doesn't store two copies of the key, would also be generally nice to have... although the overhead is higher for small keys/values.