Serious autocomplete performance degradation

[SafwatHalaby]

Intro

I deal with a huge dataset (about 30k bus stops nodes) almost daily.
This was never a problem before, but since recently, JOSM often hangs when I edit the bus stop tags.
Waiting for a few seconds (can be up to ~30) always resolves this.

It happens seems to happen when editing massively used keys. For instance, all stops have a
"ref" key, and when I click "edit" on a single stop's "ref", JOSM
stalls. A similar issue occurs when adding "description" to changeset
uploads. Description is also used by all stops. So it appears this is triggered whenever auto-complete is in use.

Profiling

"I can reproduce this locally on JOSM 13106. According to jvisualvm cpu
profiling (on Oracle JDK), most time is spent in method
org.openstreetmap.josm.data.tagging.ac.AutoCompletionSet.add"
-- mmd

It's a CPU starvation issue and not a memory overuse issue.
(Core at 100% for 10-30 seconds).

Test case

Run the Overpass query below to obtain a huge bus stop dataset, then try editing the ref or name of a stop.
12712 works flawlessly.
13053 hangs for 10-30 seconds.

Query

[out:xml][timeout:90][bbox:29.4013195,33.8818359,33.4131022,36.0791016]
;
(
area(3601473946); // Israel
area(3601803010); // Judea and Samaria district
)->.a;
(
  node["highway"="bus_stop"](area.a);
  way["highway"="bus_stop"](area.a);
)->.b;
(rel(bw.b);rel(bn.b))->.routes;
(.b;way(bn.b);)->.b;
(.b;node(w.b);)->.b;
(.b;.routes;);
out meta;

Status report

URL:http://josm.openstreetmap.de/svn/trunk
Repository:UUID: 0c6e7542-c601-0410-84e7-c038aed88b3b
Last:Changed Date: 2017-09-02 14:47:18 +0200 (Sat, 02 Sep 2017)
Build-Date:2017-09-02 20:53:16
Revision:12712
Relative:URL: ^/trunk

Identification: JOSM/1.5 (12712 en) Linux Debian GNU/Linux 9.2 (stretch)
Memory Usage: 468 MB / 811 MB (227 MB allocated, but free)
Java version: 1.8.0_141-8u141-b15-1~deb9u1-b15, Oracle Corporation, OpenJDK 64-Bit Server VM
Screen: :0.0 1366x768
Maximum Screen Size: 1366x768
Java package: openjdk-8-jre:amd64-8u141-b15-1~deb9u1
Java ATK Wrapper package: libatk-wrapper-java:all-0.33.3-13
Dataset consistency test: No problems found

Nothing fancy installed, everything is default. No extra plugins, validator rules, map paint styles, presets, etc.