>
> BTW, personally when I suggested to limit the search I was thinking of 
> `narrow-to-region` (which bounds both N factors in the N² complexity).
>

Indeed, that's another way to cope with that problem, and a better one:

diff --git a/lisp/nxml/xmltok.el b/lisp/nxml/xmltok.el
index c36d225c7c9..9badd7e4c53 100644
--- a/lisp/nxml/xmltok.el
+++ b/lisp/nxml/xmltok.el
@@ -734,8 +734,10 @@ xmltok-scan-attributes
         (atts-needing-normalization nil))
      (while (cond ((or (looking-at (xmltok-attribute regexp))
                       ;; use non-greedy group
-                     (when (looking-at (concat "[^<>\n]+?"
-                                               (xmltok-attribute regexp)))
+                     (when (with-restriction
+                             (point) (+ (point) 10000)
+                             (looking-at (concat "[^<>\n]+?"
+                                                (xmltok-attribute regexp))))
                         (unless recovering
                           (xmltok-add-error "Malformed attribute"
                                             (point)

With this opening the 4 MB file takes 1.6 seconds.  With 5000 instead of 
10000 it takes 0.8 seconds.

>
> AFAIK this part of the code is intended mostly when editing XML by hand, 
> where attributes aren't expected to be ridiculously long, so limiting to 
> a few kB would be perfectly acceptable (and if the search fails it's not 
> big deal: when the search succeeds we don't *really* know what it means 
> either, it may be a false positive anyway).
>

Indeed.