Solve redraw performance issue in huge asset libraries

In a big asset library (>3000 assets in the one I'm testing with), the asset
browser would get a notable redraw lag due to the O(n^2) complexity of the tree
item matching (to recognize items over multiple redraws and keep state like
selection, highlights, renaming, ...).

source/blender/editors/include/UI_grid_view.hh

@@ -24,7 +24,9 @@
 #pragma once
 
 #include "BLI_function_ref.hh"
+#include "BLI_map.hh"
 #include "BLI_vector.hh"
+
 #include "UI_resources.h"
 
 struct bContext;
@@ -52,8 +54,8 @@ class AbstractGridViewItem {
   bool is_active_ = false;
 
  protected:
-  /** This label is used as the default way to identifying an item in the view. */
-  std::string label_{};
+  /** Reference to a string that uniquely identifies this item in the view. */
+  StringRef identifier_{};
   /** Every visible item gets a button of type #UI_BTYPE_GRID_TILE during the layout building. */
   uiButGridTile *grid_tile_but_ = nullptr;
 
@@ -63,12 +65,11 @@ class AbstractGridViewItem {
   virtual void build_grid_tile(uiLayout &layout) const = 0;
 
   /**
-   * Compare this item to \a other to check if they represent the same data.
+   * Compare this item's identifier to \a other to check if they represent the same data.
    * Used to recognize an item from a previous redraw, to be able to keep its state (e.g. active,
-   * renaming, etc.). By default this just matches the item's label. If that isn't good enough for
-   * a sub-class, that can override it.
+   * renaming, etc.).
    */
-  virtual bool matches(const AbstractGridViewItem &other) const;
+  bool matches(const AbstractGridViewItem &other) const;
 
   const AbstractGridView &get_view() const;
 
@@ -79,7 +80,7 @@ class AbstractGridViewItem {
   bool is_active() const;
 
  protected:
-  AbstractGridViewItem() = default;
+  AbstractGridViewItem(StringRef identifier);
 
   /** Called when the item's state changes from inactive to active. */
   virtual void on_activate();
@@ -131,6 +132,9 @@ class AbstractGridView {
 
  protected:
   Vector<std::unique_ptr<AbstractGridViewItem>> items_;
+  /** <identifier, item> map to lookup items by identifier, used for efficient lookups in
+   * #update_from_old(). */
+  Map<StringRef, AbstractGridViewItem *> item_map_;
   GridViewStyle style_;
   bool is_reconstructed_ = false;
 
@@ -177,8 +181,8 @@ class AbstractGridView {
    * #AbstractGridViewItem.update_from_old().
    */
   void update_from_old(uiBlock &new_block);
-  AbstractGridViewItem *find_matching_item(const AbstractGridViewItem &lookup_item,
-                                           const AbstractGridView &view) const;
+  AbstractGridViewItem *find_matching_item(const AbstractGridViewItem &item_to_match,
+                                           const AbstractGridView &view_to_search_in) const;
   /**
    * Items may want to do additional work when state changes. But these state changes can only be
    * reliably detected after the view has completed reconstruction (see #is_reconstructed()). So
@@ -236,9 +240,10 @@ class PreviewGridItem : public AbstractGridViewItem {
   IsActiveFn is_active_fn_;
 
  public:
+  std::string label{};
   int preview_icon_id = ICON_NONE;
 
-  PreviewGridItem(StringRef label, int preview_icon_id);
+  PreviewGridItem(StringRef identifier, StringRef label, int preview_icon_id);
 
   void build_grid_tile(uiLayout &layout) const override;
 

source/blender/editors/interface/grid_view.cc

@@ -44,6 +44,9 @@ AbstractGridViewItem &AbstractGridView::add_item(std::unique_ptr<AbstractGridVie
 
   AbstractGridViewItem &added_item = *items_.last();
   added_item.view_ = this;
+
+  item_map_.add(added_item.identifier_, &added_item);
+
   return added_item;
 }
 
@@ -60,17 +63,14 @@ bool AbstractGridView::listen(const wmNotifier &) const
   return false;
 }
 
-AbstractGridViewItem *AbstractGridView::find_matching_item(const AbstractGridViewItem &lookup_item,
-                                                           const AbstractGridView &view) const
+AbstractGridViewItem *AbstractGridView::find_matching_item(
+    const AbstractGridViewItem &item_to_match, const AbstractGridView &view_to_search_in) const
 {
-  for (const auto &iter_item_ptr : view.items_) {
-    if (lookup_item.matches(*iter_item_ptr)) {
-      /* We have a matching item! */
-      return iter_item_ptr.get();
-    }
-  }
+  AbstractGridViewItem *const *match = view_to_search_in.item_map_.lookup_ptr(
+      item_to_match.identifier_);
+  BLI_assert(!match || item_to_match.matches(**match));
 
-  return nullptr;
+  return match ? *match : nullptr;
 }
 
 void AbstractGridView::change_state_delayed()
@@ -127,9 +127,13 @@ GridViewStyle::GridViewStyle(int width, int height) : tile_width(width), tile_he
 
 /* ---------------------------------------------------------------------- */
 
+AbstractGridViewItem::AbstractGridViewItem(StringRef identifier) : identifier_(identifier)
+{
+}
+
 bool AbstractGridViewItem::matches(const AbstractGridViewItem &other) const
 {
-  return label_ == other.label_;
+  return identifier_ == other.identifier_;
 }
 
 void AbstractGridViewItem::grid_tile_click_fn(struct bContext * /*C*/,
@@ -449,10 +453,9 @@ void GridViewBuilder::build_grid_view(AbstractGridView &grid_view, const View2D
 
 /* ---------------------------------------------------------------------- */
 
-PreviewGridItem::PreviewGridItem(StringRef label, int preview_icon_id)
-    : preview_icon_id(preview_icon_id)
+PreviewGridItem::PreviewGridItem(StringRef identifier, StringRef label, int preview_icon_id)
+    : AbstractGridViewItem(identifier), label(label), preview_icon_id(preview_icon_id)
 {
-  label_ = label;
 }
 
 void PreviewGridItem::build_grid_tile(uiLayout &layout) const
@@ -463,7 +466,7 @@ void PreviewGridItem::build_grid_tile(uiLayout &layout) const
   uiBut *but = uiDefBut(block,
                         UI_BTYPE_PREVIEW_TILE,
                         0,
-                        label_.c_str(),
+                        label.c_str(),
                         0,
                         0,
                         style.tile_width,

source/blender/editors/space_assets/asset_view.cc

@@ -74,16 +74,15 @@ bool AssetGridView::listen(const wmNotifier &notifier) const
 
 AssetGridViewItem::AssetGridViewItem(const AssetLibraryReference &asset_library_ref,
                                      AssetHandle &asset)
-    : ui::PreviewGridItem(ED_asset_handle_get_name(&asset),
+    : ui::PreviewGridItem(ED_asset_handle_get_identifier(&asset),
+                          ED_asset_handle_get_name(&asset),
                           ED_assetlist_asset_preview_icon_id_request(&asset_library_ref, &asset)),
-      asset_identifier_(ED_asset_handle_get_identifier(&asset))
+      /* Get a copy so the identifier is always available (the file data wrapped by the handle may
+       * be freed). */
+      asset_identifier_(identifier_)
 {
-}
-
-bool AssetGridViewItem::matches(const ui::AbstractGridViewItem &other) const
-{
-  const AssetGridViewItem &other_item = dynamic_cast<const AssetGridViewItem &>(other);
-  return asset_identifier_ == other_item.asset_identifier_;
+  /* Update reference so we don't point into the possibly freed file data. */
+  identifier_ = asset_identifier_;
 }
 
 /* ---------------------------------------------------------------------- */

source/blender/editors/space_assets/asset_view.hh

@@ -60,8 +60,6 @@ class AssetGridViewItem : public ui::PreviewGridItem {
 
  public:
   AssetGridViewItem(const AssetLibraryReference &asset_library_ref, AssetHandle &);
-
-  bool matches(const AbstractGridViewItem &other) const override;
 };
 
 void asset_view_create_in_layout(const bContext &C,