(Note: each test uses 1000 iterations of abbreviate-file-name.)

Vanilla Emacs 29.0.50:
----------------------

Empty ‘directory-abbrev-alist’
Local | Elapsed time: 0.051336s (0.016125s in 1 GCs)
TRAMP | Elapsed time: 2.173621s (0.501653s in 38 GCs)

100 items in ‘directory-abbrev-alist’ (no matches)
Local | Elapsed time: 0.316021s (0.133531s in 10 GCs)
TRAMP | Elapsed time: 2.459212s (0.633373s in 48 GCs)

100 items in ‘directory-abbrev-alist’ (all matches)
Local | Elapsed time: 0.539636s (0.327637s in 25 GCs)
TRAMP | Elapsed time: 2.484629s (0.642597s in 49 GCs)

500 items in ‘directory-abbrev-alist’ (no matches)
Local | Elapsed time: 1.075650s (0.500043s in 38 GCs)
TRAMP | Elapsed time: 3.241414s (1.006143s in 76 GCs)

500 items in ‘directory-abbrev-alist’ (all matches)
Local | Elapsed time: 1.302201s (0.696249s in 53 GCs)
TRAMP | Elapsed time: 3.261984s (1.018098s in 77 GCs)


Updated Patches:
----------------

Empty ‘directory-abbrev-alist’
Local | Elapsed time: 0.050861s (0.013198s in 1 GCs)
TRAMP | Elapsed time: 0.505943s (0.128814s in 9 GCs)

100 items in ‘directory-abbrev-alist’ (no matches)
Local | Elapsed time: 0.303332s (0.121235s in 9 GCs)
TRAMP | Elapsed time: 0.827096s (0.260078s in 19 GCs)

100 items in ‘directory-abbrev-alist’ (all matches)
Local | Elapsed time: 0.543074s (0.331712s in 25 GCs)
TRAMP | Elapsed time: 0.823411s (0.253757s in 19 GCs)

500 items in ‘directory-abbrev-alist’ (no matches)
Local | Elapsed time: 1.088234s (0.511505s in 38 GCs)
TRAMP | Elapsed time: 1.722948s (0.629359s in 47 GCs)

500 items in ‘directory-abbrev-alist’ (all matches)
Local | Elapsed time: 1.306427s (0.701965s in 53 GCs)
TRAMP | Elapsed time: 1.759451s (0.653703s in 47 GCs)


Original Patches:
-----------------

Local | Elapsed time: 0.076620s (0.013434s in 1 GCs)
TRAMP | Elapsed time: 3.543266s (0.864729s in 64 GCs)

100 items in ‘directory-abbrev-alist’ (no matches)
Local | Elapsed time: 0.365402s (0.131290s in 10 GCs)
TRAMP | Elapsed time: 3.736696s (0.955474s in 73 GCs)

100 items in ‘directory-abbrev-alist’ (all matches)
Local | Elapsed time: 0.608122s (0.340677s in 26 GCs)
TRAMP | Elapsed time: 3.818867s (0.956361s in 73 GCs)

500 items in ‘directory-abbrev-alist’ (no matches)
Local | Elapsed time: 1.232221s (0.499099s in 38 GCs)
TRAMP | Elapsed time: 4.599799s (1.313629s in 100 GCs)

500 items in ‘directory-abbrev-alist’ (all matches)
Local | Elapsed time: 1.479609s (0.708903s in 54 GCs)
TRAMP | Elapsed time: 4.656963s (1.345125s in 101 GCs)