Subject: Re: [xmpp] [apps-discuss] i18n intro, Sunday 14:00-16:00

From: Joe Hildebrand <[email-masked]>
Date: Thu, 21 Jul 2011 10:28:59 -0600

On 7/21/11 1:03 AM, "Martin J. Dürst" <[email-masked]> wrote:

> Slide 123: Good to see that. By the way, I seem to remember both John 
and me
> begging you for an explanation of why Jabber wants to use NFD a 
few months
> ago, and I'm not sure I have seen an answer. Now might be a 
good time (if you
> already sent one, a pointer would be appreciated).

Let me try.  First some assumptions:
- Stringprep is currently one of the performance hotspots of some XMPP
servers.
- XMPP does not guarantee that the original form of the address that is
entered by the user or sent on the first hop is transmitted without
modification to other hops in the system.
- As such, many XMPP servers optimize by performing canonicalization at the
edges of their system and even store the canonical version for future
comparison.
- If the spec is written that clients SHOULD perform canonicalization, many
in our community will, particularly if they know that they will get better
performance from the server.

The property of NFK?D that we like is that if you have a string of
codepoints that is already in NFK?D, you can check that the string is in the
correct normalization form without having to allocate memory.  With NFK?C,
you'll have to decompose (allocating memory), recompose (at some finite CPU
cost), then recompose (possibly allocating *again*) just to check if you
have already done the normalization.

For the K portion, I have found John's argument compelling that codepoints
with compatibility decompositions should just be prohibited in our
localparts.  In our resourceparts, I'm of the opinion that we don't need to
compatibility map -- it's fine for all of those codepoints to stay distinct.

The idea is that clients SHOULD normalize, servers double-check inputs from
non-trusted sources (like clients and other servers), then always store and
forward the normalized version.

-- 
Joe Hildebrand

---

From: Bjoern Hoehrmann <[email-masked]>
Date: Thu, 21 Jul 2011 18:57:02 +0200

>have already done the normalization.

The set of strings that is in Normalization Form C is a regular language
see <http://lists.w3.org/Archives/Public/www-archive/2009Feb/0071.html>,
so recognizing NFC strings is just as easy as recognizing NFD strings if
ignore that automata for NFC are bigger and harder to make than for NFD.
It's easier to use the simple heuristic in the specification and then do
what you suggest above for complicated strings, but it's not necessary.
-- 
Björn Höhrmann · mailto:[email-masked] · http://bjoern.hoehrmann.de
Am Badedeich 7 · Telefon: +49(0)160/4415681 · http://www.bjoernsworld.de
25899 Dagebüll · PGP Pub. KeyID: 0xA4357E78 · http://www.websitedev.de/

---

From: "Martin J. Dürst" <[email-masked]>
Date: Fri, 22 Jul 2011 16:50:27 +0900

Hello Joe,

On 2011/07/22 1:28, Joe Hildebrand wrote:
> On 7/21/11 1:03 AM, "Martin J. Dürst"<[email-masked]>  wrote:
>
> Let me try.

Glad to start talking.

> First some assumptions:

Is that an assumption backed by facts or a wild guess?

> edges of their system and even store the canonical version for future

Makes sense.

> performance from the server.

That's the same for NFC and NFD, isn't it? The advantage of NFC is that 
it's designed to more-or-less match what's out there, so you get the 
advantage that there is more stuff that's already canonicalized even if 
if a client doesn't do anything. That gets reinforced by both the IETF 
and the W3C telling everybody to use NFC.

> have already done the normalization.

Nope. That's just how the algorithm was defined, because the 
decomposition component was already around, and NFD was what defined 
canonical equivalence.

As an example, http://www.w3.org/2003/06/xml1.1test/Overview.html has 
some code (both UTF-8 and UTF-16) for compact (memory footprint) and 
reasonably fast NFC check. Please ignore the "XML 1.1" in the title. 
Also please note that this is proof of concept code, and may need 
additional testing and of course upgrade to the newest version of 
Unicode. I don't have any open bug reports, but that may be for other 
reasons than that there are no bugs.

Also, there are various ways to trade off speed against memory (see also 
Björn's mail), but the memory here is just the footprint of the sharable 
data, there's no need for lots of memory per conversion.

> localparts.

Probably just fine for most cases. Potentially a problem for wide/narrow 
in places like Japan.

> In our resourceparts, I'm of the opinion that we don't need to

Yes indeed.

> forward the normalized version.

That's fine. But it doesn't explain the choice of NFD (vs. NFC).

Regards,   Martin.

---

From: Joe Hildebrand <[email-masked]>
Date: Fri, 22 Jul 2011 09:26:17 -0600

> Is that an assumption backed by facts or a wild guess?

I can only talk definitively about one server, but yes, I've got data to
back up that assumption for that one server.

> and the W3C telling everybody to use NFC.

Absolutely.  However, my point is that our client community, unlike the MUA
community (for example) is more likely to adopt change.

> reasons than that there are no bugs.

Am I correct that the key bit of your algorithm is:

"""Check for potential combination with starter. The list of recombinations
is calculated so that any combining character that would lead to a change
(full combination, recombination so that the combining character gets
combined in but another combining character is separated, complete
decomposition,...) is listed. 2176 such pairs have been found."""

Can you talk more about that?  Do we expect that future versions of Unicode
will change that set of pairs?

> Probably just fine for most cases. Potentially a problem for wide/narrow

Yup.  That's why the wide/narrow stuff is still on the list of questions to
be addressed with this approach.  I also fully expect that there are N other
codepoints that are marked as having compatibility decomposition but are
actually in widespread use, and someone's going to complain about them one
day.

> That's fine. But it doesn't explain the choice of NFD (vs. NFC).

One other point, the re-composition stuff in the C forms *is* objectively
more difficult to implement, and will *always* take more CPU.  If it's not
required, it should be avoided.  And I haven't seen any compelling arguments
as to why C should be preferred.  What I've seen so far:

- That's the way we've always done it.  Not compelling to me if we're going
to switch away from NFKC in any way.
- Saves a few bytes on the wire.  Not compelling in a world with
compression.  (see: http://xmpp.org/extensions/xep-0138.html)
- More likely to render correctly.  Not with today's font renderers.

Are there any others I'm missing?

-- 
Joe Hildebrand

---

From: Dave Cridland <[email-masked]>
Date: Fri, 22 Jul 2011 16:44:35 +0100

> back up that assumption for that one server.

I have no opinion on NFC versus NFD, but on this specific point it is  
true for our server as well, and I'm aware of at least one other  
server for which stringprep is a key area of CPU usage (Not Joe's).

Dave.
-- 
Dave Cridland - mailto:[email-masked] - xmpp:[email-masked]
  - acap://acap.dave.cridland.net/byowner/user/dwd/bookmarks/
  - http://dave.cridland.net/
Infotrope Polymer - ACAP, IMAP, ESMTP, and Lemonade

---

From: "Martin J. Dürst" <[email-masked]>
Date: Mon, 25 Jul 2011 14:37:40 +0900

Hello Joe,

On 2011/07/23 0:26, Joe Hildebrand wrote:
> On 7/22/11 1:50 AM, "Martin J. Dürst"<[email-masked]>  wrote:
>
>>> First some assumptions:

Okay, thanks for the confirmation.

> community (for example) is more likely to adopt change.

Yes, but there's no need to adopt change without a really good reason. 
And there should be no need for XMPP to differ from the rest of the IETF.

BTW, can you tell us what programming language the server is written in? 
Are you using any kinds of libraries for character-related business?

> Am I correct that the key bit of your algorithm is:

In some way, yes.

> Can you talk more about that?

The actual list is in
http://dev.w3.org/cvsweb/~checkout~/charlint/xml1.1test/nf16data.c?content-type=text/plain, 
in the array 'recombiners'.

The first entry is {0x003C, 0x0338}, which is a '<' and a COMBINING LONG 
SOLIDUS OVERLAY. It's here because there is U+226E, NOT LESS-THAN, which 
is canonically equivalent, and therefore the sequence U+003C, U+0338 (or 
any sequence  U+003C, [other combining characters], U+0338 ) isn't in NFC.

Let's look at another entry: {0x00FC, 0x0300}. This is LATIN SMALL 
LETTER U WITH DIAERESIS (ü) followed by COMBINING GRAVE ACCENT. This is 
not in NFC because there is U+01DC, LATIN SMALL LETTER U WITH DIAERESIS 
AND GRAVE.

Another, somewhat more involved example: {0x1EC5, 0x0323}. This is LATIN 
SMALL LETTER E WITH CIRCUMFLEX AND TILDE and COMBINING DOT BELOW. This 
is not in NFC because there is U+1EC7, LATIN SMALL LETTER E WITH 
CIRCUMFLEX AND DOT BELOW, and NFC is U+1EC7 + U+0303 (COMBINING TILDE) 
because combining characters below have a lower combining class and 
therefore are preferred when recombining.

> Do we expect that future versions of Unicode

This is at least in theory possible. The data is from 2003. With input 
from the W3C, the Unicode Consortium created a fairly strong stability 
policies regarding normalization (please see 
http://www.unicode.org/policies/stability_policy.html, under 
"Normalization Stability"). As a result, for new precomposed characters, 
they had to be included in the combining exclusions. That meant that the 
benefit of proposing them as precomposed characters was lost, and there 
were virtually no such characters that made it all the way. It's still 
possible to propose a new script with some precomposed/decomposed 
alternatives, but I wouldn't know about a case where this has been done.

Please note that such additions would also affect decomposition, so a 
software (table) update would be needed independent of whether you go 
for NFC or NFD.

> more difficult to implement,

Yes, but usually, you'd just use a library, and be done with it.

> and will *always* take more CPU.

Not if most of your data is already in NFC, and you can check that quickly.

I do not have actual statistics, but I don't know any major language or 
script where data would from the start be in NFD. On the other hand, 
there are examples such as Korean where essentially everything is in 
NFC, and NFD expands the number of characters by a factor of between 2 
and 3, affecting every single character. For other big languages such as 
Spanish, Portuguese, French, German, Italian, Polish, Japanese,... data 
is also essentially in NFC, although the characters that would be 
decomposed are less frequent than the 100% for Korean.

> If it's not required, it should be avoided.

That's similar to the argument about saving bytes on the wire. It's not 
compelling in a world with efficient libraries and faster and faster 
processors.

Also, please note that the code at 
http://www.w3.org/2003/06/xml1.1test/Overview.html isn't really the only 
way to optimize, and it's just a proof of concept, not really optimized 
based on actual benchmarks. My guess is that there are things that are 
"overoptimized" (i.e. too complicated without a corresponding speed 
gain) and some spots that could still be further optimized. In many 
cases, checking for all-ASCII first can shave off quite a bit of time. 
Also, doing a lookup of the string (which I guess has to happen sooner 
or later anyway) before checking for normalization may speed up things.

> And I haven't seen any compelling arguments

That may not be compelling on the level of XMPP, but on the level of the 
IETF or the Internet, it's a different issue.

Also, under the assumption that actual characters where NFKC makes a 
difference are few and far between, NFKC and NFC are quite close. A 
change from NFKC to NFC may be much smoother than a change from NFKC to NFD.

> compression.  (see: http://xmpp.org/extensions/xep-0138.html)

Agreed.

> - More likely to render correctly.  Not with today's font renderers.

Depends on the exact characters in question. Can go either way.

> Are there any others I'm missing?

See above (libraries, frequency of data in NFC vs. NFD,...).

Regards,   Martin.