[ADT] [WIP] Add MutableRange class

[abrachet]

Summary

MutableRange provides an interface to effectively make a const container mutable without copying every element or modifying the const container in any way.

This will eventually be used in D64281.

[jhenderson]

Nice work so far. I think it would be more natural to me if the "main" template argument was that of the underlying container, rather than the iterator. This shouldn't affect the functionality, if I've followed it correctly.

I've got a number of other comments, but don't want to overload things too much in the first instance.

llvm/include/llvm/Support/UpdatableRange.h

1

Don't forget to include LLVM copyright headers, even in WIP code.

35

Is the KeyType type useful in this version?

49

In the current version, you don't need this, since you don't have any way of removing anything.

65

Isn't this simply not generated if another constructor was defined?

71

Use size_t.

72

Rather than this, have you considered using std::transform?

75

Make sure to include comments for each public member function describing what it does.

95

You'll probably want to make this return an Expected or similar, I suspect, rather than assert.

[abrachet]

Moved files from Support to ADT. Removed base class because it wasn't adding anything. Changed enable_if to specialize on the container type, between AssociativeContainer and SequenceContainer's. Added doxygen comments for all public methods. Added collect() method to return the UpdatableRange as the same type of the original container. Updated unit test to be more comprehensive and use test fixtures. Addressed review comments.

[abrachet]

llvm/include/llvm/ADT/UpdatableRange.h

122 ↗

(On Diff #209123)

Should this return Error?

[jhenderson]

If you haven't already, it's worth looking at the other ADT classes like SmallVector to make sure your code matches the same style etc used there.

I think the name "MutableRange" might be more consistent with naming schemes within LLVM.

Overall, I quite like this. I think it's at the point where it's worth getting a wider audience by adding some more people as reviewers.

llvm/include/llvm/ADT/UpdatableRange.h

1 ↗

(On Diff #209123)

Minor point this but I believe this needs to mention c++ somewhere so that editors can detect the language properly. I'm also not sure the rest of the text makes much sense... ;)

55 ↗

(On Diff #209123)

Nit: replacment -> replacement

87–88 ↗

(On Diff #209123)

Nit: clang-format?

122 ↗

(On Diff #209123)

Actually, looking at SmallVector, it looks like I was wrong to encourage you to use Expected below (it uses asserts too), so this should remain an assert.

[abrachet]

Addressed review comments. Renamed to MutableRange

[abrachet]

llvm/include/llvm/ADT/UpdatableRange.h

1 ↗

(On Diff #209123)

I got caught copy and pasting on that one! :)

[abrachet]

clang-format

[jhenderson]

llvm/include/llvm/ADT/MutableRange.h

52 ↗

(On Diff #209357)

Why is the alignas needed?

67–68 ↗

(On Diff #209357)

Begin and End? Probably even UnderlyingBegin and UnderlyingEnd to disambiguate

90 ↗

(On Diff #209357)

Begin and End. Don't use "Last", as it could be thought to be the last valid member (i.e. one before the end iterator).

101 ↗

(On Diff #209357)

"to the object"

107 ↗

(On Diff #209357)

I would say that it's more common for insert to take a value_type to insert, rather than a variadic template list to construct it. I don't mind this method existing as is, but I think you should provide the "standard" signature too.

115 ↗

(On Diff #209357)

"a new element"

[abrachet]

Added specialization for associative containers. Addressed review comments.

[MaskRay]

This will eventually be used in D64281.

You probably need a data structure to process symbol table/section header table/program header table. To that end, this patch adds an overlay data structure (MutableRange as the name made me puzzled) to make operations more efficient. Have you benchmarked whether the librarified llvm-objcopy will benefit from a fancy data structure like this? I'm thinking plain vectors (as is) may just meet the needs.

If you just want to make interleaved insertion/deletion efficient:

1. add section .a: O(n)
2. remove section .b: O(n)
3. add section .c: O(n)
4. remove section .d: O(n)
5. add section .e: O(n)

Note you pay the O(n) cost for each operation. If you group them (online algorithm->offline) by insertion/deletion:

a) batched insertion: 1,3,5: O(n)
b) batched deletion: 2,4: O(n)

You pay the O(n) cost just twice.

If this is going to be promoted to ADT, I think it should be justified by a second use case.

[abrachet]

Created iterator for sequence container specialization. Created Clone template parameter from non trivially copy constructable types.

[abrachet]

Thanks, @MaskRay!

You probably need a data structure to process symbol table/section header table/program header table. To that end, this patch adds an overlay data structure (MutableRange as the name made me puzzled) to make operations more efficient.

The idea here was the llvm-objcopy needs to reference the original sections/symbols etc and that such a data structure could be used to keep both the original and update or add new entries.

Have you benchmarked whether the librarified llvm-objcopy will benefit from a fancy data structure like this? I'm thinking plain vectors (as is) may just meet the needs.

Not yet. But this can keep the original entries without needing to make a copy of every single one, only the ones that get modified.

If you just want to make interleaved insertion/deletion efficient

So like cache insertion/deletion and then execute them whenever the data structure is read? Can this be done with std::transform efficiently?

(MutableRange as the name made me puzzled)

Not married to the name by any means :) Just called such because it creates a mutable layer over an immutable data structure.

[MaskRay]

In D64462#1587661, @abrachet wrote:

Thanks, @MaskRay!

You probably need a data structure to process symbol table/section header table/program header table. To that end, this patch adds an overlay data structure (MutableRange as the name made me puzzled) to make operations more efficient.

The idea here was the llvm-objcopy needs to reference the original sections/symbols etc and that such a data structure could be used to keep both the original and update or add new entries.

Have you benchmarked whether the librarified llvm-objcopy will benefit from a fancy data structure like this? I'm thinking plain vectors (as is) may just meet the needs.

Not yet. But this can keep the original entries without needing to make a copy of every single one, only the ones that get modified.

If you just want to make interleaved insertion/deletion efficient

So like cache insertion/deletion and then execute them whenever the data structure is read? Can this be done with std::transform efficiently?

(MutableRange as the name made me puzzled)

Not married to the name by any means :) Just called such because it creates a mutable layer over an immutable data structure.

Using a overlay data structure for section header table is not necessary. There are not many sections. ~50 is a cap for most applications, so O(N) isn't slow at all. In lld, orphan placement algorithm is quadratic in terms of the number of output sections. This isn't an performance issue at all. I believe ld.bfd has a similar complexity.

Speaking of the dynamic symbol table and the static symbol table. Some shared objects have an awful number of .dynsym entries, e.g. my libclangAST.so has 5000+ .dynsym entries and 7000+ .symtab entries. We do should keep an eye on its performance. IMHO as long as we don't make it O(|syms|^2) it should be fine. It is currently O(|syms| * constant).

After making llvm-objcopy a library, we may do a bunch of operations on it. As I think about it, the operations may look like:

Objcopy o;
o.addSymbol();
o.removeSymbol(); // x100
o.addSymbol(); // x100
o.addSection(); // x100
o.removeSection(); // x100
o.commit(); // actually perform the operations. Make sure at this point, aggregate the previous operations and do addSymbol() in batch, removeSymbol() in batch, addSection() in batch, and removeSection() in batch.

The time complexity will be just O(|syms|*|types of operations|) instead of O(|syms|*|operations|).

[jhenderson]

Using a overlay data structure for section header table is not necessary. There are not many sections.

Not true: llvm-objcopy can be easily used on object files, which can have tens of thousands of sections, possibly more, in real-world cases that I work with, due to -ffunction-sections/-fdata-sections, COMDATs etc. Symbols are also sometimes in the order of hundreds of thousands at least, especially in linked applications. In other words, we need to be careful about the performance trade-offs we make (though linear is probably fine if anything simpler is more complex).

I'll come back to this tomorrow. Ran out of time to look more today.

[abrachet]

Fixed bug with iterator not using Cloner.

[jhenderson]

I think you're trying to do too much in this patch. Having an idea of how it could be extended is very different from going ahead and implementing it, and I really don't see a need to add support for all the types you are currently supporting. Certainly, I think this is too big to review as is.

I know I suggested bringing it across here, but @MaskRay is probably right in that we probably need another concrete use case for this code to put it into ADT. I think it would be wise to scale it back to what is needed for the MutableObject patch series, sorry.

Rather than completely throwing this all away, maybe you should create a new patch that just keeps it tightly focused to what is needed (perhaps similar to what you had before), referencing this patch, and then abandoning this patch. Then, if someone in the future feels there's a need for a more general solution, this patch can be resurrected.

llvm/include/llvm/ADT/MutableRange.h

29 ↗

(On Diff #210731)

Things like this probably belong in a separate TypeTraits header or similar.

32 ↗

(On Diff #210731)

It might be worth adding an implementation of C++ 17's void_t to make this, is_map and is_unordered much cleaner:

template <typename T>
class is_associative<T, void_t<T::key_type>> : public std::true_type {};

llvm/include/llvm/Support/UpdatableRange.h

+#include "llvm/ADT/SmallVector.h"
+#include <iterator>
+#include <type_traits>
+#include <vector>
+
+namespace llvm {
+
+template <typename T> class UpdatableRangeBase {
+protected:
+  using Iter = T;
+  using ValueType = typename T::value_type;
+
+  const Iter Start;
+  const Iter End;
+
+public:
+  UpdatableRangeBase() = delete;
+  UpdatableRangeBase(const UpdatableRangeBase &) = default;
+  UpdatableRangeBase(UpdatableRangeBase &&) = default;
+  UpdatableRangeBase(Iter Start, Iter End) : Start(Start), End(End) {}
+};
+
+template <typename IterTag> class is_random_access : public std::false_type {};
+template <>
+class is_random_access<std::random_access_iterator_tag>
+    : public std::true_type {};
+
+/// Creates a wrapper over a const container effectively making it mutable
+/// without modifying the underlying container.
+/// Specialization for random access iterators. Such iterators have an
+/// operator+(size_t) with constant complexity.
+/// @tparam T iterator.
+/// @tparam KeyType type of index to use.
+template <
+    typename T, typename KeyType = uint64_t,
+    typename std::enable_if<
+        is_random_access<typename T::iterator_category>::value, int>::type = 0>
+class UpdatableRange : UpdatableRangeBase<T> {
+  static_assert(std::is_integral<KeyType>::value, "expected integral KeyType");
+
+  using Iter = typename UpdatableRangeBase<T>::Iter;
+  using ValueType = typename UpdatableRangeBase<T>::ValueType;
+
+  /// Describes where to find the underlying object that is pointed to
+  /// by Index.
+  struct MappingType {
+    enum Operation {
+      Original = 0, // Index represents offset from Start.
+      Removed,      // Index not meaningful.
+      New           // Index represents index into Modified.
+                    // Is either an addition or replacment.
+    };
+    Operation Type : 2;
+    KeyType Index : sizeof(void *) * 8 - 2;
+
+    MappingType(Operation Type, KeyType Index) : Type(Type), Index(Index) {}
+
+    operator KeyType() { return Index; }
+  };
+
+  std::vector<MappingType> Mappings;
+  std::vector<ValueType> Modified;
+
+public:
+  UpdatableRange() = delete;
+  UpdatableRange(const UpdatableRange &) = default;
+  UpdatableRange(UpdatableRange &&) = default;
+  UpdatableRange(Iter Start, Iter End) : UpdatableRangeBase<T>(Start, End) {
+    auto Length = std::distance(Start, End);
+    Mappings.reserve(Length);
+    for (int I = 0; I < Length; ++I)
+      Mappings.push_back(MappingType(MappingType::Original, I));
+  }
+
+  const ValueType &operator[](KeyType Index) {
+    if (Mappings[Index].Type == MappingType::Original)
+      return *(this->Start + Mappings[Index]);
+    return Modified[Mappings[Index]];
+  }
+
+  /// Emplaces a T::value_type at a specified index
+  template <class... Ts> ValueType &insert(KeyType Index, Ts &&... Args) {
+    Modified.emplace_back(ValueType(std::forward<Ts>(Args)...));
+    Mappings.insert(Mappings.begin() + Index,
+                    MappingType(MappingType::New, Modified.size() - 1));
+    return Modified.back();
+  }
+
+  template <class... Ts> ValueType &emplace_back(Ts &&... Args) {
+    return insert(Mappings.size(), std::forward<Ts>(Args)...);
+  }
+
+  /// Returns a mutable reference to the index at Index.
+  ValueType &makeMutable(KeyType Index) {
+    assert(Mappings[Index].Type != MappingType::Removed &&
+           "Element was removed");
+    if (Mappings[Index].Type == MappingType::New)
+      return Modified[Mappings[Index]];
+
+    Modified.emplace_back(ValueType(this->Start[Mappings[Index]]));
+    Mappings[Index] = MappingType(MappingType::New, Modified.size() - 1);
+    return Modified.back();
+  }
+};
+
+} // namespace llvm

llvm/unittests/Support/CMakeLists.txt

add_llvm_unittest(SupportTests
   ThreadPool.cpp
   Threading.cpp
   TimerTest.cpp
   TypeNameTest.cpp
   TypeTraitsTest.cpp
   TrailingObjectsTest.cpp
   TrigramIndexTest.cpp
   UnicodeTest.cpp
+  UpdatableRangeTest.cpp
   VersionTupleTest.cpp
   VirtualFileSystemTest.cpp
   YAMLIOTest.cpp
   YAMLParserTest.cpp
   formatted_raw_ostream_test.cpp
   raw_ostream_test.cpp
   raw_pwrite_stream_test.cpp
   raw_sha1_ostream_test.cpp

llvm/unittests/Support/UpdatableRangeTest.cpp

+
+#include "llvm/Support/UpdatableRange.h"
+#include "gtest/gtest.h"
+#include <vector>
+
+TEST(Basic, Test) {
+  const std::vector<int> Vec {1, 2, 3};
+
+  llvm::UpdatableRange<decltype(Vec.begin())> Range(Vec.begin(), Vec.end());
+
+  EXPECT_EQ(Range[0], 1) << "doesn't correctly represent underlying container";
+  EXPECT_EQ(Range[1], 2);
+  EXPECT_EQ(Range[2], 3);
+
+  EXPECT_EQ(Range.insert(1, 9), 9);
+
+  EXPECT_EQ(Range[0], 1);
+  EXPECT_EQ(Range[1], 9) << "inserted in wrong area";
+  EXPECT_EQ(Range[2], 2);
+  EXPECT_EQ(Range[3], 3);
+
+  EXPECT_EQ(Range.emplace_back(4), 4);
+
+  EXPECT_EQ(Range[0], 1);
+  EXPECT_EQ(Range[1], 9);
+  EXPECT_EQ(Range[2], 2);
+  EXPECT_EQ(Range[3], 3);
+  EXPECT_EQ(Range[4], 4) << "emplace_back didn't push to back";
+
+  Range.makeMutable(0) = 2;
+
+  EXPECT_EQ(Range[0], 2) << "makeMutable didn't correctly update";
+  EXPECT_EQ(Range[1], 9);
+  EXPECT_EQ(Range[2], 2);
+  EXPECT_EQ(Range[3], 3);
+  EXPECT_EQ(Range[4], 4);
+
+  EXPECT_EQ(Vec[0], 1) << "const not respected on underlying container";
+  EXPECT_EQ(Vec[1], 2);
+  EXPECT_EQ(Vec[2], 3);
+}