diff --git a/runtime/runtime.cc b/runtime/runtime.cc
index 7a9c7fa..5a49f50 100644
--- a/runtime/runtime.cc
+++ b/runtime/runtime.cc
@@ -2416,8 +2416,8 @@
 }
 
 void Runtime::VisitTransactionRoots(RootVisitor* visitor) {
-  for (auto& transaction : preinitialization_transactions_) {
-    transaction->VisitRoots(visitor);
+  for (Transaction& transaction : preinitialization_transactions_) {
+    transaction.VisitRoots(visitor);
   }
 }
 
@@ -2668,26 +2668,33 @@
 
 void Runtime::EnterTransactionMode(bool strict, mirror::Class* root) {
   DCHECK(IsAotCompiler());
+  ArenaPool* arena_pool = nullptr;
+  ArenaStack* arena_stack = nullptr;
   if (preinitialization_transactions_.empty()) {  // Top-level transaction?
     // Make initialized classes visibly initialized now. If that happened during the transaction
     // and then the transaction was aborted, we would roll back the status update but not the
     // ClassLinker's bookkeeping structures, so these classes would never be visibly initialized.
     GetClassLinker()->MakeInitializedClassesVisiblyInitialized(Thread::Current(), /*wait=*/ true);
+    // Pass the runtime `ArenaPool` to the transaction.
+    arena_pool = GetArenaPool();
+  } else {
+    // Pass the `ArenaStack` from previous transaction to the new one.
+    arena_stack = preinitialization_transactions_.front().GetArenaStack();
   }
-  preinitialization_transactions_.push_back(std::make_unique<Transaction>(strict, root));
+  preinitialization_transactions_.emplace_front(strict, root, arena_stack, arena_pool);
 }
 
 void Runtime::ExitTransactionMode() {
   DCHECK(IsAotCompiler());
   DCHECK(IsActiveTransaction());
-  preinitialization_transactions_.pop_back();
+  preinitialization_transactions_.pop_front();
 }
 
 void Runtime::RollbackAndExitTransactionMode() {
   DCHECK(IsAotCompiler());
   DCHECK(IsActiveTransaction());
-  preinitialization_transactions_.back()->Rollback();
-  preinitialization_transactions_.pop_back();
+  preinitialization_transactions_.front().Rollback();
+  preinitialization_transactions_.pop_front();
 }
 
 bool Runtime::IsTransactionAborted() const {
@@ -2711,9 +2718,14 @@
   return IsActiveTransaction() && GetTransaction()->IsStrict();
 }
 
-const std::unique_ptr<Transaction>& Runtime::GetTransaction() const {
+const Transaction* Runtime::GetTransaction() const {
   DCHECK(!preinitialization_transactions_.empty());
-  return preinitialization_transactions_.back();
+  return &preinitialization_transactions_.front();
+}
+
+Transaction* Runtime::GetTransaction() {
+  DCHECK(!preinitialization_transactions_.empty());
+  return &preinitialization_transactions_.front();
 }
 
 void Runtime::AbortTransactionAndThrowAbortError(Thread* self, const std::string& abort_message) {
@@ -2735,43 +2747,55 @@
   GetTransaction()->ThrowAbortError(self, nullptr);
 }
 
-void Runtime::RecordWriteFieldBoolean(mirror::Object* obj, MemberOffset field_offset,
-                                      uint8_t value, bool is_volatile) const {
+void Runtime::RecordWriteFieldBoolean(mirror::Object* obj,
+                                      MemberOffset field_offset,
+                                      uint8_t value,
+                                      bool is_volatile) {
   DCHECK(IsAotCompiler());
   DCHECK(IsActiveTransaction());
   GetTransaction()->RecordWriteFieldBoolean(obj, field_offset, value, is_volatile);
 }
 
-void Runtime::RecordWriteFieldByte(mirror::Object* obj, MemberOffset field_offset,
-                                   int8_t value, bool is_volatile) const {
+void Runtime::RecordWriteFieldByte(mirror::Object* obj,
+                                   MemberOffset field_offset,
+                                   int8_t value,
+                                   bool is_volatile) {
   DCHECK(IsAotCompiler());
   DCHECK(IsActiveTransaction());
   GetTransaction()->RecordWriteFieldByte(obj, field_offset, value, is_volatile);
 }
 
-void Runtime::RecordWriteFieldChar(mirror::Object* obj, MemberOffset field_offset,
-                                   uint16_t value, bool is_volatile) const {
+void Runtime::RecordWriteFieldChar(mirror::Object* obj,
+                                   MemberOffset field_offset,
+                                   uint16_t value,
+                                   bool is_volatile) {
   DCHECK(IsAotCompiler());
   DCHECK(IsActiveTransaction());
   GetTransaction()->RecordWriteFieldChar(obj, field_offset, value, is_volatile);
 }
 
-void Runtime::RecordWriteFieldShort(mirror::Object* obj, MemberOffset field_offset,
-                                    int16_t value, bool is_volatile) const {
+void Runtime::RecordWriteFieldShort(mirror::Object* obj,
+                                    MemberOffset field_offset,
+                                    int16_t value,
+                                    bool is_volatile) {
   DCHECK(IsAotCompiler());
   DCHECK(IsActiveTransaction());
   GetTransaction()->RecordWriteFieldShort(obj, field_offset, value, is_volatile);
 }
 
-void Runtime::RecordWriteField32(mirror::Object* obj, MemberOffset field_offset,
-                                 uint32_t value, bool is_volatile) const {
+void Runtime::RecordWriteField32(mirror::Object* obj,
+                                 MemberOffset field_offset,
+                                 uint32_t value,
+                                 bool is_volatile) {
   DCHECK(IsAotCompiler());
   DCHECK(IsActiveTransaction());
   GetTransaction()->RecordWriteField32(obj, field_offset, value, is_volatile);
 }
 
-void Runtime::RecordWriteField64(mirror::Object* obj, MemberOffset field_offset,
-                                 uint64_t value, bool is_volatile) const {
+void Runtime::RecordWriteField64(mirror::Object* obj,
+                                 MemberOffset field_offset,
+                                 uint64_t value,
+                                 bool is_volatile) {
   DCHECK(IsAotCompiler());
   DCHECK(IsActiveTransaction());
   GetTransaction()->RecordWriteField64(obj, field_offset, value, is_volatile);
@@ -2780,54 +2804,51 @@
 void Runtime::RecordWriteFieldReference(mirror::Object* obj,
                                         MemberOffset field_offset,
                                         ObjPtr<mirror::Object> value,
-                                        bool is_volatile) const {
+                                        bool is_volatile) {
   DCHECK(IsAotCompiler());
   DCHECK(IsActiveTransaction());
-  GetTransaction()->RecordWriteFieldReference(obj,
-                                                            field_offset,
-                                                            value.Ptr(),
-                                                            is_volatile);
+  GetTransaction()->RecordWriteFieldReference(obj, field_offset, value.Ptr(), is_volatile);
 }
 
-void Runtime::RecordWriteArray(mirror::Array* array, size_t index, uint64_t value) const {
+void Runtime::RecordWriteArray(mirror::Array* array, size_t index, uint64_t value) {
   DCHECK(IsAotCompiler());
   DCHECK(IsActiveTransaction());
   GetTransaction()->RecordWriteArray(array, index, value);
 }
 
-void Runtime::RecordStrongStringInsertion(ObjPtr<mirror::String> s) const {
+void Runtime::RecordStrongStringInsertion(ObjPtr<mirror::String> s) {
   DCHECK(IsAotCompiler());
   DCHECK(IsActiveTransaction());
   GetTransaction()->RecordStrongStringInsertion(s);
 }
 
-void Runtime::RecordWeakStringInsertion(ObjPtr<mirror::String> s) const {
+void Runtime::RecordWeakStringInsertion(ObjPtr<mirror::String> s) {
   DCHECK(IsAotCompiler());
   DCHECK(IsActiveTransaction());
   GetTransaction()->RecordWeakStringInsertion(s);
 }
 
-void Runtime::RecordStrongStringRemoval(ObjPtr<mirror::String> s) const {
+void Runtime::RecordStrongStringRemoval(ObjPtr<mirror::String> s) {
   DCHECK(IsAotCompiler());
   DCHECK(IsActiveTransaction());
   GetTransaction()->RecordStrongStringRemoval(s);
 }
 
-void Runtime::RecordWeakStringRemoval(ObjPtr<mirror::String> s) const {
+void Runtime::RecordWeakStringRemoval(ObjPtr<mirror::String> s) {
   DCHECK(IsAotCompiler());
   DCHECK(IsActiveTransaction());
   GetTransaction()->RecordWeakStringRemoval(s);
 }
 
 void Runtime::RecordResolveString(ObjPtr<mirror::DexCache> dex_cache,
-                                  dex::StringIndex string_idx) const {
+                                  dex::StringIndex string_idx) {
   DCHECK(IsAotCompiler());
   DCHECK(IsActiveTransaction());
   GetTransaction()->RecordResolveString(dex_cache, string_idx);
 }
 
 void Runtime::RecordResolveMethodType(ObjPtr<mirror::DexCache> dex_cache,
-                                      dex::ProtoIndex proto_idx) const {
+                                      dex::ProtoIndex proto_idx) {
   DCHECK(IsAotCompiler());
   DCHECK(IsActiveTransaction());
   GetTransaction()->RecordResolveMethodType(dex_cache, proto_idx);
diff --git a/runtime/runtime.h b/runtime/runtime.h
index ff7eb9b..080ba63 100644
--- a/runtime/runtime.h
+++ b/runtime/runtime.h
@@ -20,6 +20,7 @@
 #include <jni.h>
 #include <stdio.h>
 
+#include <forward_list>
 #include <iosfwd>
 #include <memory>
 #include <set>
@@ -550,7 +551,8 @@
   // do them in one function.
   void RollbackAndExitTransactionMode() REQUIRES_SHARED(Locks::mutator_lock_);
   bool IsTransactionAborted() const;
-  const std::unique_ptr<Transaction>& GetTransaction() const;
+  const Transaction* GetTransaction() const;
+  Transaction* GetTransaction();
   bool IsActiveStrictTransactionMode() const;
 
   void AbortTransactionAndThrowAbortError(Thread* self, const std::string& abort_message)
@@ -558,36 +560,48 @@
   void ThrowTransactionAbortError(Thread* self)
       REQUIRES_SHARED(Locks::mutator_lock_);
 
-  void RecordWriteFieldBoolean(mirror::Object* obj, MemberOffset field_offset, uint8_t value,
-                               bool is_volatile) const;
-  void RecordWriteFieldByte(mirror::Object* obj, MemberOffset field_offset, int8_t value,
-                            bool is_volatile) const;
-  void RecordWriteFieldChar(mirror::Object* obj, MemberOffset field_offset, uint16_t value,
-                            bool is_volatile) const;
-  void RecordWriteFieldShort(mirror::Object* obj, MemberOffset field_offset, int16_t value,
-                          bool is_volatile) const;
-  void RecordWriteField32(mirror::Object* obj, MemberOffset field_offset, uint32_t value,
-                          bool is_volatile) const;
-  void RecordWriteField64(mirror::Object* obj, MemberOffset field_offset, uint64_t value,
-                          bool is_volatile) const;
+  void RecordWriteFieldBoolean(mirror::Object* obj,
+                               MemberOffset field_offset,
+                               uint8_t value,
+                               bool is_volatile);
+  void RecordWriteFieldByte(mirror::Object* obj,
+                            MemberOffset field_offset,
+                            int8_t value,
+                            bool is_volatile);
+  void RecordWriteFieldChar(mirror::Object* obj,
+                            MemberOffset field_offset,
+                            uint16_t value,
+                            bool is_volatile);
+  void RecordWriteFieldShort(mirror::Object* obj,
+                             MemberOffset field_offset,
+                             int16_t value,
+                             bool is_volatile);
+  void RecordWriteField32(mirror::Object* obj,
+                          MemberOffset field_offset,
+                          uint32_t value,
+                          bool is_volatile);
+  void RecordWriteField64(mirror::Object* obj,
+                          MemberOffset field_offset,
+                          uint64_t value,
+                          bool is_volatile);
   void RecordWriteFieldReference(mirror::Object* obj,
                                  MemberOffset field_offset,
                                  ObjPtr<mirror::Object> value,
-                                 bool is_volatile) const
+                                 bool is_volatile)
       REQUIRES_SHARED(Locks::mutator_lock_);
-  void RecordWriteArray(mirror::Array* array, size_t index, uint64_t value) const
+  void RecordWriteArray(mirror::Array* array, size_t index, uint64_t value)
       REQUIRES_SHARED(Locks::mutator_lock_);
-  void RecordStrongStringInsertion(ObjPtr<mirror::String> s) const
+  void RecordStrongStringInsertion(ObjPtr<mirror::String> s)
       REQUIRES(Locks::intern_table_lock_);
-  void RecordWeakStringInsertion(ObjPtr<mirror::String> s) const
+  void RecordWeakStringInsertion(ObjPtr<mirror::String> s)
       REQUIRES(Locks::intern_table_lock_);
-  void RecordStrongStringRemoval(ObjPtr<mirror::String> s) const
+  void RecordStrongStringRemoval(ObjPtr<mirror::String> s)
       REQUIRES(Locks::intern_table_lock_);
-  void RecordWeakStringRemoval(ObjPtr<mirror::String> s) const
+  void RecordWeakStringRemoval(ObjPtr<mirror::String> s)
       REQUIRES(Locks::intern_table_lock_);
-  void RecordResolveString(ObjPtr<mirror::DexCache> dex_cache, dex::StringIndex string_idx) const
+  void RecordResolveString(ObjPtr<mirror::DexCache> dex_cache, dex::StringIndex string_idx)
       REQUIRES_SHARED(Locks::mutator_lock_);
-  void RecordResolveMethodType(ObjPtr<mirror::DexCache> dex_cache, dex::ProtoIndex proto_idx) const
+  void RecordResolveMethodType(ObjPtr<mirror::DexCache> dex_cache, dex::ProtoIndex proto_idx)
       REQUIRES_SHARED(Locks::mutator_lock_);
 
   void SetFaultMessage(const std::string& message);
@@ -710,12 +724,12 @@
   ArenaPool* GetArenaPool() {
     return arena_pool_.get();
   }
-  ArenaPool* GetJitArenaPool() {
-    return jit_arena_pool_.get();
-  }
   const ArenaPool* GetArenaPool() const {
     return arena_pool_.get();
   }
+  ArenaPool* GetJitArenaPool() {
+    return jit_arena_pool_.get();
+  }
 
   void ReclaimArenaPoolMemory();
 
@@ -1237,7 +1251,7 @@
   // Support nested transactions, maintain a list containing all transactions. Transactions are
   // handled under a stack discipline. Because GC needs to go over all transactions, we choose list
   // as substantial data structure instead of stack.
-  std::list<std::unique_ptr<Transaction>> preinitialization_transactions_;
+  std::forward_list<Transaction> preinitialization_transactions_;
 
   // If kNone, verification is disabled. kEnable by default.
   verifier::VerifyMode verify_;
diff --git a/runtime/transaction.cc b/runtime/transaction.cc
index 0aec48c..193c111 100644
--- a/runtime/transaction.cc
+++ b/runtime/transaction.cc
@@ -40,14 +40,25 @@
 // TODO: remove (only used for debugging purpose).
 static constexpr bool kEnableTransactionStats = false;
 
-Transaction::Transaction(bool strict, mirror::Class* root)
-    : aborted_(false),
+Transaction::Transaction(bool strict,
+                         mirror::Class* root,
+                         ArenaStack* arena_stack,
+                         ArenaPool* arena_pool)
+    : arena_stack_(std::nullopt),
+      allocator_(arena_stack != nullptr ? arena_stack : &arena_stack_.emplace(arena_pool)),
+      object_logs_(std::less<mirror::Object*>(), allocator_.Adapter(kArenaAllocTransaction)),
+      array_logs_(std::less<mirror::Array*>(), allocator_.Adapter(kArenaAllocTransaction)),
+      intern_string_logs_(allocator_.Adapter(kArenaAllocTransaction)),
+      resolve_string_logs_(allocator_.Adapter(kArenaAllocTransaction)),
+      resolve_method_type_logs_(allocator_.Adapter(kArenaAllocTransaction)),
+      aborted_(false),
       rolling_back_(false),
       heap_(Runtime::Current()->GetHeap()),
       strict_(strict),
       root_(root),
       assert_no_new_records_reason_(nullptr) {
   DCHECK(Runtime::Current()->IsAotCompiler());
+  DCHECK_NE(arena_stack != nullptr, arena_pool != nullptr);
 }
 
 Transaction::~Transaction() {
@@ -62,15 +73,20 @@
     for (const auto& it : array_logs_) {
       array_values_count += it.second.Size();
     }
-    size_t intern_string_count = intern_string_logs_.size();
-    size_t resolve_string_count = resolve_string_logs_.size();
+    size_t intern_string_count =
+        std::distance(intern_string_logs_.begin(), intern_string_logs_.end());
+    size_t resolve_string_count =
+        std::distance(resolve_string_logs_.begin(), resolve_string_logs_.end());
+    size_t resolve_method_type_count =
+        std::distance(resolve_method_type_logs_.begin(), resolve_method_type_logs_.end());
     LOG(INFO) << "Transaction::~Transaction"
               << ": objects_count=" << objects_count
               << ", field_values_count=" << field_values_count
               << ", array_count=" << array_count
               << ", array_values_count=" << array_values_count
               << ", intern_string_count=" << intern_string_count
-              << ", resolve_string_count=" << resolve_string_count;
+              << ", resolve_string_count=" << resolve_string_count
+              << ", resolve_method_type_count=" << resolve_method_type_count;
   }
 }
 
@@ -150,13 +166,17 @@
   }
 }
 
+inline Transaction::ObjectLog& Transaction::GetOrCreateObjectLog(mirror::Object* obj) {
+  return object_logs_.GetOrCreate(obj, [&]() { return ObjectLog(&allocator_); });
+}
+
 void Transaction::RecordWriteFieldBoolean(mirror::Object* obj,
                                           MemberOffset field_offset,
                                           uint8_t value,
                                           bool is_volatile) {
   DCHECK(obj != nullptr);
   DCHECK(assert_no_new_records_reason_ == nullptr) << assert_no_new_records_reason_;
-  ObjectLog& object_log = object_logs_[obj];
+  ObjectLog& object_log = GetOrCreateObjectLog(obj);
   object_log.LogBooleanValue(field_offset, value, is_volatile);
 }
 
@@ -166,7 +186,7 @@
                                        bool is_volatile) {
   DCHECK(obj != nullptr);
   DCHECK(assert_no_new_records_reason_ == nullptr) << assert_no_new_records_reason_;
-  ObjectLog& object_log = object_logs_[obj];
+  ObjectLog& object_log = GetOrCreateObjectLog(obj);
   object_log.LogByteValue(field_offset, value, is_volatile);
 }
 
@@ -176,7 +196,7 @@
                                        bool is_volatile) {
   DCHECK(obj != nullptr);
   DCHECK(assert_no_new_records_reason_ == nullptr) << assert_no_new_records_reason_;
-  ObjectLog& object_log = object_logs_[obj];
+  ObjectLog& object_log = GetOrCreateObjectLog(obj);
   object_log.LogCharValue(field_offset, value, is_volatile);
 }
 
@@ -187,7 +207,7 @@
                                         bool is_volatile) {
   DCHECK(obj != nullptr);
   DCHECK(assert_no_new_records_reason_ == nullptr) << assert_no_new_records_reason_;
-  ObjectLog& object_log = object_logs_[obj];
+  ObjectLog& object_log = GetOrCreateObjectLog(obj);
   object_log.LogShortValue(field_offset, value, is_volatile);
 }
 
@@ -198,7 +218,7 @@
                                      bool is_volatile) {
   DCHECK(obj != nullptr);
   DCHECK(assert_no_new_records_reason_ == nullptr) << assert_no_new_records_reason_;
-  ObjectLog& object_log = object_logs_[obj];
+  ObjectLog& object_log = GetOrCreateObjectLog(obj);
   object_log.Log32BitsValue(field_offset, value, is_volatile);
 }
 
@@ -208,7 +228,7 @@
                                      bool is_volatile) {
   DCHECK(obj != nullptr);
   DCHECK(assert_no_new_records_reason_ == nullptr) << assert_no_new_records_reason_;
-  ObjectLog& object_log = object_logs_[obj];
+  ObjectLog& object_log = GetOrCreateObjectLog(obj);
   object_log.Log64BitsValue(field_offset, value, is_volatile);
 }
 
@@ -218,7 +238,7 @@
                                             bool is_volatile) {
   DCHECK(obj != nullptr);
   DCHECK(assert_no_new_records_reason_ == nullptr) << assert_no_new_records_reason_;
-  ObjectLog& object_log = object_logs_[obj];
+  ObjectLog& object_log = GetOrCreateObjectLog(obj);
   object_log.LogReferenceValue(field_offset, value, is_volatile);
 }
 
@@ -227,12 +247,8 @@
   DCHECK(array->IsArrayInstance());
   DCHECK(!array->IsObjectArray());
   DCHECK(assert_no_new_records_reason_ == nullptr) << assert_no_new_records_reason_;
-  auto it = array_logs_.find(array);
-  if (it == array_logs_.end()) {
-    ArrayLog log;
-    it = array_logs_.emplace(array, std::move(log)).first;
-  }
-  it->second.LogValue(index, value);
+  ArrayLog& array_log = array_logs_.GetOrCreate(array, [&]() { return ArrayLog(&allocator_); });
+  array_log.LogValue(index, value);
 }
 
 void Transaction::RecordResolveString(ObjPtr<mirror::DexCache> dex_cache,
@@ -240,7 +256,7 @@
   DCHECK(dex_cache != nullptr);
   DCHECK_LT(string_idx.index_, dex_cache->GetDexFile()->NumStringIds());
   DCHECK(assert_no_new_records_reason_ == nullptr) << assert_no_new_records_reason_;
-  resolve_string_logs_.emplace_back(dex_cache, string_idx);
+  resolve_string_logs_.emplace_front(dex_cache, string_idx);
 }
 
 void Transaction::RecordResolveMethodType(ObjPtr<mirror::DexCache> dex_cache,
@@ -248,7 +264,7 @@
   DCHECK(dex_cache != nullptr);
   DCHECK_LT(proto_idx.index_, dex_cache->GetDexFile()->NumProtoIds());
   DCHECK(assert_no_new_records_reason_ == nullptr) << assert_no_new_records_reason_;
-  resolve_method_type_logs_.emplace_back(dex_cache, proto_idx);
+  resolve_method_type_logs_.emplace_front(dex_cache, proto_idx);
 }
 
 void Transaction::RecordStrongStringInsertion(ObjPtr<mirror::String> s) {
@@ -334,18 +350,42 @@
 }
 
 void Transaction::VisitRoots(RootVisitor* visitor) {
+  // Transactions are used for single-threaded initialization.
+  // This is the only function that should be called from a different thread,
+  // namely the GC thread, and it is called with the mutator lock held exclusively,
+  // so the data structures in the `Transaction` are protected from concurrent use.
+  DCHECK(Locks::mutator_lock_->IsExclusiveHeld(Thread::Current()));
+
   visitor->VisitRoot(reinterpret_cast<mirror::Object**>(&root_), RootInfo(kRootUnknown));
-  VisitObjectLogs(visitor);
-  VisitArrayLogs(visitor);
+  {
+    // Create a separate `ArenaStack` for this thread.
+    ArenaStack arena_stack(Runtime::Current()->GetArenaPool());
+    VisitObjectLogs(visitor, &arena_stack);
+    VisitArrayLogs(visitor, &arena_stack);
+  }
   VisitInternStringLogs(visitor);
   VisitResolveStringLogs(visitor);
   VisitResolveMethodTypeLogs(visitor);
 }
 
-void Transaction::VisitObjectLogs(RootVisitor* visitor) {
+template <typename MovingRoots, typename Container>
+void UpdateKeys(const MovingRoots& moving_roots, Container& container) {
+  for (const auto& pair : moving_roots) {
+    auto* old_root = pair.first;
+    auto* new_root = pair.second;
+    auto node = container.extract(old_root);
+    CHECK(!node.empty());
+    node.key() = new_root;
+    bool inserted = container.insert(std::move(node)).inserted;
+    CHECK(inserted);
+  }
+}
+
+void Transaction::VisitObjectLogs(RootVisitor* visitor, ArenaStack* arena_stack) {
   // List of moving roots.
+  ScopedArenaAllocator allocator(arena_stack);
   using ObjectPair = std::pair<mirror::Object*, mirror::Object*>;
-  std::list<ObjectPair> moving_roots;
+  ScopedArenaForwardList<ObjectPair> moving_roots(allocator.Adapter(kArenaAllocTransaction));
 
   // Visit roots.
   for (auto& it : object_logs_) {
@@ -354,26 +394,19 @@
     mirror::Object* new_root = old_root;
     visitor->VisitRoot(&new_root, RootInfo(kRootUnknown));
     if (new_root != old_root) {
-      moving_roots.push_back(std::make_pair(old_root, new_root));
+      moving_roots.push_front(std::make_pair(old_root, new_root));
     }
   }
 
   // Update object logs with moving roots.
-  for (const ObjectPair& pair : moving_roots) {
-    mirror::Object* old_root = pair.first;
-    mirror::Object* new_root = pair.second;
-    auto old_root_it = object_logs_.find(old_root);
-    CHECK(old_root_it != object_logs_.end());
-    CHECK(object_logs_.find(new_root) == object_logs_.end());
-    object_logs_.emplace(new_root, std::move(old_root_it->second));
-    object_logs_.erase(old_root_it);
-  }
+  UpdateKeys(moving_roots, object_logs_);
 }
 
-void Transaction::VisitArrayLogs(RootVisitor* visitor) {
+void Transaction::VisitArrayLogs(RootVisitor* visitor, ArenaStack* arena_stack) {
   // List of moving roots.
+  ScopedArenaAllocator allocator(arena_stack);
   using ArrayPair = std::pair<mirror::Array*, mirror::Array*>;
-  std::list<ArrayPair> moving_roots;
+  ScopedArenaForwardList<ArrayPair> moving_roots(allocator.Adapter(kArenaAllocTransaction));
 
   for (auto& it : array_logs_) {
     mirror::Array* old_root = it.first;
@@ -381,20 +414,12 @@
     mirror::Array* new_root = old_root;
     visitor->VisitRoot(reinterpret_cast<mirror::Object**>(&new_root), RootInfo(kRootUnknown));
     if (new_root != old_root) {
-      moving_roots.push_back(std::make_pair(old_root, new_root));
+      moving_roots.push_front(std::make_pair(old_root, new_root));
     }
   }
 
   // Update array logs with moving roots.
-  for (const ArrayPair& pair : moving_roots) {
-    mirror::Array* old_root = pair.first;
-    mirror::Array* new_root = pair.second;
-    auto old_root_it = array_logs_.find(old_root);
-    CHECK(old_root_it != array_logs_.end());
-    CHECK(array_logs_.find(new_root) == array_logs_.end());
-    array_logs_.emplace(new_root, std::move(old_root_it->second));
-    array_logs_.erase(old_root_it);
-  }
+  UpdateKeys(moving_roots, array_logs_);
 }
 
 void Transaction::VisitInternStringLogs(RootVisitor* visitor) {
@@ -657,10 +682,8 @@
 }
 
 void Transaction::ArrayLog::LogValue(size_t index, uint64_t value) {
-  auto it = array_values_.find(index);
-  if (it == array_values_.end()) {
-    array_values_.insert(std::make_pair(index, value));
-  }
+  // Add a mapping if there is none yet.
+  array_values_.FindOrAdd(index, value);
 }
 
 void Transaction::ArrayLog::Undo(mirror::Array* array) const {
@@ -724,7 +747,7 @@
 Transaction* ScopedAssertNoNewTransactionRecords::InstallAssertion(const char* reason) {
   Transaction* transaction = nullptr;
   if (kIsDebugBuild && Runtime::Current()->IsActiveTransaction()) {
-    transaction = Runtime::Current()->GetTransaction().get();
+    transaction = Runtime::Current()->GetTransaction();
     if (transaction != nullptr) {
       CHECK(transaction->assert_no_new_records_reason_ == nullptr)
           << "old: " << transaction->assert_no_new_records_reason_ << " new: " << reason;
@@ -736,7 +759,7 @@
 
 void ScopedAssertNoNewTransactionRecords::RemoveAssertion(Transaction* transaction) {
   if (kIsDebugBuild) {
-    CHECK(Runtime::Current()->GetTransaction().get() == transaction);
+    CHECK(Runtime::Current()->GetTransaction() == transaction);
     CHECK(transaction->assert_no_new_records_reason_ != nullptr);
     transaction->assert_no_new_records_reason_ = nullptr;
   }
diff --git a/runtime/transaction.h b/runtime/transaction.h
index 8ee922f..8cd18e3 100644
--- a/runtime/transaction.h
+++ b/runtime/transaction.h
@@ -17,6 +17,7 @@
 #ifndef ART_RUNTIME_TRANSACTION_H_
 #define ART_RUNTIME_TRANSACTION_H_
 
+#include "base/scoped_arena_containers.h"
 #include "base/macros.h"
 #include "base/mutex.h"
 #include "base/safe_map.h"
@@ -47,9 +48,13 @@
  public:
   static constexpr const char* kAbortExceptionDescriptor = "Ldalvik/system/TransactionAbortError;";
 
-  Transaction(bool strict, mirror::Class* root);
+  Transaction(bool strict, mirror::Class* root, ArenaStack* arena_stack, ArenaPool* arena_pool);
   ~Transaction();
 
+  ArenaStack* GetArenaStack() {
+    return allocator_.GetArenaStack();
+  }
+
   void Abort(const std::string& abort_message)
       REQUIRES_SHARED(Locks::mutator_lock_);
   void ThrowAbortError(Thread* self, const std::string* abort_message)
@@ -157,7 +162,8 @@
       return field_values_.size();
     }
 
-    ObjectLog() = default;
+    explicit ObjectLog(ScopedArenaAllocator* allocator)
+        : field_values_(std::less<uint32_t>(), allocator->Adapter(kArenaAllocTransaction)) {}
     ObjectLog(ObjectLog&& log) = default;
 
    private:
@@ -189,7 +195,7 @@
                         const FieldValue& field_value) const REQUIRES_SHARED(Locks::mutator_lock_);
 
     // Maps field's offset to its value.
-    std::map<uint32_t, FieldValue> field_values_;
+    ScopedArenaSafeMap<uint32_t, FieldValue> field_values_;
 
     DISALLOW_COPY_AND_ASSIGN(ObjectLog);
   };
@@ -204,7 +210,9 @@
       return array_values_.size();
     }
 
-    ArrayLog() = default;
+    explicit ArrayLog(ScopedArenaAllocator* allocator)
+        : array_values_(std::less<size_t>(), allocator->Adapter(kArenaAllocTransaction)) {}
+
     ArrayLog(ArrayLog&& log) = default;
 
    private:
@@ -215,7 +223,7 @@
 
     // Maps index to value.
     // TODO use JValue instead ?
-    std::map<size_t, uint64_t> array_values_;
+    ScopedArenaSafeMap<size_t, uint64_t> array_values_;
 
     DISALLOW_COPY_AND_ASSIGN(ArrayLog);
   };
@@ -293,9 +301,9 @@
   void UndoResolveMethodTypeModifications()
       REQUIRES_SHARED(Locks::mutator_lock_);
 
-  void VisitObjectLogs(RootVisitor* visitor)
+  void VisitObjectLogs(RootVisitor* visitor, ArenaStack* arena_stack)
       REQUIRES_SHARED(Locks::mutator_lock_);
-  void VisitArrayLogs(RootVisitor* visitor)
+  void VisitArrayLogs(RootVisitor* visitor, ArenaStack* arena_stack)
       REQUIRES_SHARED(Locks::mutator_lock_);
   void VisitInternStringLogs(RootVisitor* visitor)
       REQUIRES_SHARED(Locks::mutator_lock_);
@@ -306,11 +314,19 @@
 
   const std::string& GetAbortMessage() const;
 
-  std::map<mirror::Object*, ObjectLog> object_logs_;
-  std::map<mirror::Array*, ArrayLog> array_logs_ ;
-  std::list<InternStringLog> intern_string_logs_;
-  std::list<ResolveStringLog> resolve_string_logs_;
-  std::list<ResolveMethodTypeLog> resolve_method_type_logs_;
+  ObjectLog& GetOrCreateObjectLog(mirror::Object* obj);
+
+  // The top-level transaction creates an `ArenaStack` which is then
+  // passed down to nested transactions.
+  std::optional<ArenaStack> arena_stack_;
+  // The allocator uses the `ArenaStack` from the top-level transaction.
+  ScopedArenaAllocator allocator_;
+
+  ScopedArenaSafeMap<mirror::Object*, ObjectLog> object_logs_;
+  ScopedArenaSafeMap<mirror::Array*, ArrayLog> array_logs_ ;
+  ScopedArenaForwardList<InternStringLog> intern_string_logs_;
+  ScopedArenaForwardList<ResolveStringLog> resolve_string_logs_;
+  ScopedArenaForwardList<ResolveMethodTypeLog> resolve_method_type_logs_;
   bool aborted_;
   bool rolling_back_;  // Single thread, no race.
   gc::Heap* const heap_;
diff --git a/runtime/transaction_test.cc b/runtime/transaction_test.cc
index 5c78505..88e3f4f 100644
--- a/runtime/transaction_test.cc
+++ b/runtime/transaction_test.cc
@@ -730,7 +730,9 @@
   ASSERT_TRUE(heap->ObjectIsInBootImageSpace(array_iftable.Get()));
 
   // Test non-strict transaction.
-  Transaction transaction(/*strict=*/ false, /*root=*/ nullptr);
+  ArenaPool* arena_pool = Runtime::Current()->GetArenaPool();
+  Transaction transaction(
+      /*strict=*/ false, /*root=*/ nullptr, /*arena_stack=*/ nullptr, arena_pool);
   // Static field in boot image.
   EXPECT_TRUE(transaction.WriteConstraint(boolean_class.Get()));
   EXPECT_FALSE(transaction.ReadConstraint(boolean_class.Get()));
@@ -754,7 +756,8 @@
   EXPECT_FALSE(transaction.WriteValueConstraint(long_array.Get()));
 
   // Test strict transaction.
-  Transaction strict_transaction(/*strict=*/ true, /*root=*/ static_field_class.Get());
+  Transaction strict_transaction(
+      /*strict=*/ true, /*root=*/ static_field_class.Get(), /*arena_stack=*/ nullptr, arena_pool);
   // Static field in boot image.
   EXPECT_TRUE(strict_transaction.WriteConstraint(boolean_class.Get()));
   EXPECT_TRUE(strict_transaction.ReadConstraint(boolean_class.Get()));