On a system with almost a thousand devices (don't ask) I noticed that installing grub
takes over an hour. It was sorting device ids the whole time.
In the post install script there is a "cached_available_ids" variable set to prevent this.
But the available_ids() function gets called in a subshell like this
for id in $(available_ids) ...
so the cache variable is never set in the main script.

If I change the script to call it once in the mainscript it gets fast
--- /var/lib/dpkg/info/grub-pc.postinst 2017-02-11 16:09:19.000000000 +0100
+++ grub-pc.postinst    2018-11-13 16:12:51.884531798 +0100
@@ -44,7 +44,6 @@
 # This only works on a Linux system with udev running.  This is probably the
 # vast majority of systems where we need any of this, though, and we fall
 # back reasonably gracefully if we don't have it.
-cached_available_ids=
 available_ids()
 {
   local id path
@@ -55,14 +54,12 @@
   fi

   [ -d /dev/disk/by-id ] || return
-  cached_available_ids="$(
-    for path in /dev/disk/by-id/*; do
-      [ -e "$path" ] || continue
-      printf '%s %s\n' "$path" "$(readlink -f "$path")"
-    done | sort -k2 -s -u | cut -d' ' -f1
-  )"
-  echo "$cached_available_ids"
+  for path in /dev/disk/by-id/*; do
+    [ -e "$path" ] || continue
+    printf '%s %s\n' "$path" "$(readlink -f "$path")"
+  done | sort -k2 -s -u | cut -d' ' -f1
 }
+cached_available_ids=$(available_ids)

but that probably not a universal solution.

The device_to_id() for each device looping over all ids is O(n^2) too so it is still slow ofcourse..

Hello,

  Please find below an update from previous patch suggested

--- postinst    2021-10-06 17:16:32.966812000 -0400
+++ postinst.913655.patched       2021-10-27 09:03:25.324340000 -0400
@@ -73,7 +73,6 @@
 # This only works on a Linux system with udev running.  This is probably the
 # vast majority of systems where we need any of this, though, and we fall
 # back reasonably gracefully if we don't have it.
-cached_available_ids=
 available_ids()
 {
   local id path
@@ -84,19 +83,25 @@
   fi   [ -d /dev/disk/by-id ] || return
-  cached_available_ids="$(
-    for path in /dev/disk/by-id/*; do
-      [ -e "$path" ] || continue
-      printf '%s %s\n' "$path" "$(readlink -f "$path")"
-    done | sort -k2 -s -u | cut -d' ' -f1
-  )"
-  echo "$cached_available_ids"
+  for path in /dev/disk/by-id/*; do
+    [ -e "$path" ] || continue
+    printf '%s %s\n' "$path" "$(readlink -f "$path")"
+  done | sort -k2 -s -u | cut -d' ' -f1
 }
+cached_available_ids=$(available_ids) # Returns non-zero and no
output if no mapping can be found.
 device_to_id()
 {
   local id
+  # If it's already in /dev/disk/by-id, skip the expensive loop
+  # Using case to support glob matching with /bin/sh compatibility
+  case "$1" in
+    /dev/disk/by-id/*)
+      echo "$1"
+      return 0
+      ;;
+  esac
   for id in $(available_ids); do
     if [ "$(readlink -f "$id")" = "$(readlink -f "$1")" ]; then
       echo "$id"

Regards
-- 
 Héctor Orón  -.. . -... .. .- -.   -.. . ...- . .-.. --- .--. . .-.