Performance was improved by using computeIfAbsent for CLDRLocale.getInstance, in https://unicode-org.atlassian.net/browse/CLDR-13334 . However it turns out occasionally to hang, when called recursively for parent = CLDRLocale.getInstance(parentId).
computeIfAbsent is known to hang when used recursively, see https://stackoverflow.com/questions/28840047/recursive-concurrenthashmap-computeifabsent-call-never-terminates-bug-or-fea .
This should be easy to solve using lazy initialization for parent. When constructing a CLDRLocale, record its parentId (a String), but postpone construction of the parent CLDRLocale until needed (if ever), as for one of the three methods getParent, childOf, getHighestNonrootParent.