Quantcast

Even faster string equality (see #16863)

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
14 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Even faster string equality (see #16863)

Scott Jones
I have made a branch with an even faster version of == for the String type (it took 28%-40% less time in my testing).
Instead of calling lexcmp, which has to deal with strings of different length, it calls memcmp directly if the string lengths are equal, and checks if the result is 0.


If somebody could make a PR out of this branch, it would be appreciated.

Thanks in advance,
Scott

Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Even faster string equality (see #16863)

Jeffrey Sarnoff
looks sane

On Wednesday, June 8, 2016 at 11:55:11 PM UTC-4, Scott Jones wrote:
I have made a branch with an even faster version of == for the String type (it took 28%-40% less time in my testing).
Instead of calling lexcmp, which has to deal with strings of different length, it calls memcmp directly if the string lengths are equal, and checks if the result is 0.

<a href="https://github.com/ScottPJones/julia/tree/spj/fasteqstr" target="_blank" rel="nofollow" onmousedown="this.href=&#39;https://www.google.com/url?q\x3dhttps%3A%2F%2Fgithub.com%2FScottPJones%2Fjulia%2Ftree%2Fspj%2Ffasteqstr\x26sa\x3dD\x26sntz\x3d1\x26usg\x3dAFQjCNH-OchpH5f_ukg0-v3VhYUNrdd2rQ&#39;;return true;" onclick="this.href=&#39;https://www.google.com/url?q\x3dhttps%3A%2F%2Fgithub.com%2FScottPJones%2Fjulia%2Ftree%2Fspj%2Ffasteqstr\x26sa\x3dD\x26sntz\x3d1\x26usg\x3dAFQjCNH-OchpH5f_ukg0-v3VhYUNrdd2rQ&#39;;return true;">https://github.com/ScottPJones/julia/tree/spj/fasteqstr

If somebody could make a PR out of this branch, it would be appreciated.

Thanks in advance,
Scott

Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Even faster string equality (see #16863)

Scott Jones
In reply to this post by Scott Jones
Just wanted to thank Stefan (again!) for getting this pulled in as https://github.com/JuliaLang/julia/pull/16855 !

On Wednesday, June 8, 2016 at 11:55:11 PM UTC-4, Scott Jones wrote:
I have made a branch with an even faster version of == for the String type (it took 28%-40% less time in my testing).
Instead of calling lexcmp, which has to deal with strings of different length, it calls memcmp directly if the string lengths are equal, and checks if the result is 0.

<a href="https://github.com/ScottPJones/julia/tree/spj/fasteqstr" target="_blank" rel="nofollow" onmousedown="this.href=&#39;https://www.google.com/url?q\x3dhttps%3A%2F%2Fgithub.com%2FScottPJones%2Fjulia%2Ftree%2Fspj%2Ffasteqstr\x26sa\x3dD\x26sntz\x3d1\x26usg\x3dAFQjCNH-OchpH5f_ukg0-v3VhYUNrdd2rQ&#39;;return true;" onclick="this.href=&#39;https://www.google.com/url?q\x3dhttps%3A%2F%2Fgithub.com%2FScottPJones%2Fjulia%2Ftree%2Fspj%2Ffasteqstr\x26sa\x3dD\x26sntz\x3d1\x26usg\x3dAFQjCNH-OchpH5f_ukg0-v3VhYUNrdd2rQ&#39;;return true;">https://github.com/ScottPJones/julia/tree/spj/fasteqstr

If somebody could make a PR out of this branch, it would be appreciated.

Thanks in advance,
Scott

Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Even faster string equality (see #16863)

Páll Haraldsson
In reply to this post by Jeffrey Sarnoff
On Thursday, June 9, 2016 at 4:46:46 AM UTC, Jeffrey Sarnoff wrote:
looks sane

Are you sure? I'm not sure what lexcmp does (or should do..), but if say one string has precomposed Unicode letters, and the other doesn't, should it be possible for them to compare the same? Maybe it's not preferable by default? Or is it..?

These things can all be tricky; E.g. minor recent upgrades of PostgreSQL are generally considered safe (and recommended over not upgrading), with a rare "exception" (just just need to be careful and REINDEX afterwards, as broken in a former minor update..):

https://www.postgresql.org/docs/9.5/static/release-9-5-2.html

"PostgreSQL 9.5 introduced logic for speeding up comparisons of string data types by using the standard C library function strxfrm() as a substitute for strcoll(). It now emerges that most versions of glibc (Linux's implementation of the C library) have buggy implementations of strxfrm() that, in some locales, can produce string comparison results that do not match strcoll(). Until this problem can be better characterized, disable the optimization in all non-C locales. (C locale is safe since it uses neither strcoll() nor strxfrm().)

Unfortunately, this problem affects not only sorting but also entry ordering in B-tree indexes, which means that B-tree indexes on text, varchar, or char columns may now be corrupt if they sort according to an affected locale and were built or modified under PostgreSQL 9.5.0 or 9.5.1. Users should REINDEX indexes that might be affected.


It is not possible at this time to give an exhaustive list of known-affected locales. C locale is known safe, and there is no evidence of trouble in English-based locales such as en_US, but some other popular locales such as de_DE are affected in most glibc versions."



On Wednesday, June 8, 2016 at 11:55:11 PM UTC-4, Scott Jones wrote:
I have made a branch with an even faster version of == for the String type (it took 28%-40% less time in my testing).
Instead of calling lexcmp, which has to deal with strings of different length, it calls memcmp directly if the string lengths are equal, and checks if the result is 0.

<a href="https://github.com/ScottPJones/julia/tree/spj/fasteqstr" rel="nofollow" target="_blank" onmousedown="this.href=&#39;https://www.google.com/url?q\x3dhttps%3A%2F%2Fgithub.com%2FScottPJones%2Fjulia%2Ftree%2Fspj%2Ffasteqstr\x26sa\x3dD\x26sntz\x3d1\x26usg\x3dAFQjCNH-OchpH5f_ukg0-v3VhYUNrdd2rQ&#39;;return true;" onclick="this.href=&#39;https://www.google.com/url?q\x3dhttps%3A%2F%2Fgithub.com%2FScottPJones%2Fjulia%2Ftree%2Fspj%2Ffasteqstr\x26sa\x3dD\x26sntz\x3d1\x26usg\x3dAFQjCNH-OchpH5f_ukg0-v3VhYUNrdd2rQ&#39;;return true;">https://github.com/ScottPJones/julia/tree/spj/fasteqstr

If somebody could make a PR out of this branch, it would be appreciated.

Thanks in advance,
Scott

Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Even faster string equality (see #16863)

Jeffrey Sarnoff
Páll Haraldsson -- 
        Absolutely.  Definitely.  <hat tip>.  Good catch.


On Wednesday, July 13, 2016 at 9:48:01 AM UTC-4, Páll Haraldsson wrote:
On Thursday, June 9, 2016 at 4:46:46 AM UTC, Jeffrey Sarnoff wrote:
looks sane

Are you sure? I'm not sure what lexcmp does (or should do..), but if say one string has precomposed Unicode letters, and the other doesn't, should it be possible for them to compare the same? Maybe it's not preferable by default? Or is it..?

These things can all be tricky; E.g. minor recent upgrades of PostgreSQL are generally considered safe (and recommended over not upgrading), with a rare "exception" (just just need to be careful and REINDEX afterwards, as broken in a former minor update..):

<a href="https://www.postgresql.org/docs/9.5/static/release-9-5-2.html" target="_blank" rel="nofollow" onmousedown="this.href=&#39;https://www.google.com/url?q\x3dhttps%3A%2F%2Fwww.postgresql.org%2Fdocs%2F9.5%2Fstatic%2Frelease-9-5-2.html\x26sa\x3dD\x26sntz\x3d1\x26usg\x3dAFQjCNF_9bhSOSV67Kl2qUYHWBSjrvS_rA&#39;;return true;" onclick="this.href=&#39;https://www.google.com/url?q\x3dhttps%3A%2F%2Fwww.postgresql.org%2Fdocs%2F9.5%2Fstatic%2Frelease-9-5-2.html\x26sa\x3dD\x26sntz\x3d1\x26usg\x3dAFQjCNF_9bhSOSV67Kl2qUYHWBSjrvS_rA&#39;;return true;">https://www.postgresql.org/docs/9.5/static/release-9-5-2.html

"PostgreSQL 9.5 introduced logic for speeding up comparisons of string data types by using the standard C library function strxfrm() as a substitute for strcoll(). It now emerges that most versions of glibc (Linux's implementation of the C library) have buggy implementations of strxfrm() that, in some locales, can produce string comparison results that do not match strcoll(). Until this problem can be better characterized, disable the optimization in all non-C locales. (C locale is safe since it uses neither strcoll() nor strxfrm().)

Unfortunately, this problem affects not only sorting but also entry ordering in B-tree indexes, which means that B-tree indexes on text, varchar, or char columns may now be corrupt if they sort according to an affected locale and were built or modified under PostgreSQL 9.5.0 or 9.5.1. Users should REINDEX indexes that might be affected.


It is not possible at this time to give an exhaustive list of known-affected locales. C locale is known safe, and there is no evidence of trouble in English-based locales such as en_US, but some other popular locales such as de_DE are affected in most glibc versions."



On Wednesday, June 8, 2016 at 11:55:11 PM UTC-4, Scott Jones wrote:
I have made a branch with an even faster version of == for the String type (it took 28%-40% less time in my testing).
Instead of calling lexcmp, which has to deal with strings of different length, it calls memcmp directly if the string lengths are equal, and checks if the result is 0.

<a href="https://github.com/ScottPJones/julia/tree/spj/fasteqstr" rel="nofollow" target="_blank" onmousedown="this.href=&#39;https://www.google.com/url?q\x3dhttps%3A%2F%2Fgithub.com%2FScottPJones%2Fjulia%2Ftree%2Fspj%2Ffasteqstr\x26sa\x3dD\x26sntz\x3d1\x26usg\x3dAFQjCNH-OchpH5f_ukg0-v3VhYUNrdd2rQ&#39;;return true;" onclick="this.href=&#39;https://www.google.com/url?q\x3dhttps%3A%2F%2Fgithub.com%2FScottPJones%2Fjulia%2Ftree%2Fspj%2Ffasteqstr\x26sa\x3dD\x26sntz\x3d1\x26usg\x3dAFQjCNH-OchpH5f_ukg0-v3VhYUNrdd2rQ&#39;;return true;">https://github.com/ScottPJones/julia/tree/spj/fasteqstr

If somebody could make a PR out of this branch, it would be appreciated.

Thanks in advance,
Scott

Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Even faster string equality (see #16863)

Páll Haraldsson
On mið 13.júl 2016 13:56, Jeffrey Sarnoff wrote:
> Páll Haraldsson --
>          Absolutely.  Definitely.  <hat tip>.  Good catch.

This is already merged.. so needs to be reverted in case I'm right on
the default behavior..

Another thing, but might be to late to change the default bahavior of
sorts (comparisons):

https://blog.codinghorror.com/sorting-for-humans-natural-sort-order/

I'm partial to "natural sort" being the default.. Then we could have
non-default ASCIIbetical or Unicode disregarding precomposed etc.
whatever is fastest.

--
Palli.


> *
> *
> On Wednesday, July 13, 2016 at 9:48:01 AM UTC-4, Páll Haraldsson wrote:
>
>     On Thursday, June 9, 2016 at 4:46:46 AM UTC, Jeffrey Sarnoff wrote:
>
>         looks sane
>
>
>     Are you sure? I'm not sure what lexcmp does (or should do..), but if
>     say one string has precomposed Unicode letters, and the other
>     doesn't, should it be possible for them to compare the same? Maybe
>     it's not preferable by default? Or is it..?
>
>     These things can all be tricky; E.g. minor recent upgrades of
>     PostgreSQL are generally considered safe (and recommended over not
>     upgrading), with a rare "exception" (just just need to be careful
>     and REINDEX afterwards, as broken in a former minor update..):
>
>     https://www.postgresql.org/docs/9.5/static/release-9-5-2.html
>     <https://www.postgresql.org/docs/9.5/static/release-9-5-2.html>
>
>     "PostgreSQL 9.5 introduced logic for speeding up comparisons of
>     string data types by using the standard C library function
>     |strxfrm()| as a substitute for |strcoll()|. It now emerges that
>     most versions of glibc (Linux's implementation of the C library)
>     have buggy implementations of |strxfrm()| that, in some locales, can
>     produce string comparison results that do not match |strcoll()|.
>     Until this problem can be better characterized, disable the
>     optimization in all non-C locales. (C locale is safe since it uses
>     neither |strcoll()| nor |strxfrm()|.)
>
>     Unfortunately, this problem affects not only sorting but also entry
>     ordering in B-tree indexes, which means that B-tree indexes on text,
>     varchar, or char columns may now be corrupt if they sort according
>     to an affected locale and were built or modified under PostgreSQL
>     9.5.0 or 9.5.1. Users should REINDEX indexes that might be affected.
>
>
>     It is not possible at this time to give an exhaustive list of
>     known-affected locales. C locale is known safe, and there is no
>     evidence of trouble in English-based locales such as en_US, but some
>     other popular locales such as de_DE are affected in most glibc
>     versions."
>
>
>
>         On Wednesday, June 8, 2016 at 11:55:11 PM UTC-4, Scott Jones wrote:
>
>             I have made a branch with an even faster version of == for
>             the String type (it took 28%-40% less time in my testing).
>             Instead of calling lexcmp, which has to deal with strings of
>             different length, it calls memcmp directly if the string
>             lengths are equal, and checks if the result is 0.
>
>             https://github.com/ScottPJones/julia/tree/spj/fasteqstr
>             <https://github.com/ScottPJones/julia/tree/spj/fasteqstr>
>
>             If somebody could make a PR out of this branch, it would be
>             appreciated.
>
>             Thanks in advance,
>             Scott
>
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Even faster string equality (see #16863)

Stefan Karpinski
We're moving towards the built-in String type being essentially just a container for bytes with a UTF-8-like interpretation. Thus if two String objects don't have the same underlying data, they are not equal. If you want fancier Unicode-aware behavior like UTF-8 validation or normalized comparison, then you'll need to use a package that provides a type like EncodedString{UTF8} (or something). Care needs to be taken to make sure that == is transitive, but that's a problem for the to-be-created external Unicode strings package.

On Wed, Jul 13, 2016 at 10:36 AM, Páll Haraldsson <[hidden email]> wrote:
On mið 13.júl 2016 13:56, Jeffrey Sarnoff wrote:
Páll Haraldsson --
         Absolutely.  Definitely.  <hat tip>.  Good catch.

This is already merged.. so needs to be reverted in case I'm right on the default behavior..

Another thing, but might be to late to change the default bahavior of sorts (comparisons):

https://blog.codinghorror.com/sorting-for-humans-natural-sort-order/

I'm partial to "natural sort" being the default.. Then we could have non-default ASCIIbetical or Unicode disregarding precomposed etc. whatever is fastest.

--
Palli.


*
*
On Wednesday, July 13, 2016 at 9:48:01 AM UTC-4, Páll Haraldsson wrote:

    On Thursday, June 9, 2016 at 4:46:46 AM UTC, Jeffrey Sarnoff wrote:

        looks sane


    Are you sure? I'm not sure what lexcmp does (or should do..), but if
    say one string has precomposed Unicode letters, and the other
    doesn't, should it be possible for them to compare the same? Maybe
    it's not preferable by default? Or is it..?

    These things can all be tricky; E.g. minor recent upgrades of
    PostgreSQL are generally considered safe (and recommended over not
    upgrading), with a rare "exception" (just just need to be careful
    and REINDEX afterwards, as broken in a former minor update..):

    https://www.postgresql.org/docs/9.5/static/release-9-5-2.html
    <https://www.postgresql.org/docs/9.5/static/release-9-5-2.html>

    "PostgreSQL 9.5 introduced logic for speeding up comparisons of
    string data types by using the standard C library function
    |strxfrm()| as a substitute for |strcoll()|. It now emerges that

    most versions of glibc (Linux's implementation of the C library)
    have buggy implementations of |strxfrm()| that, in some locales, can
    produce string comparison results that do not match |strcoll()|.
    Until this problem can be better characterized, disable the
    optimization in all non-C locales. (C locale is safe since it uses
    neither |strcoll()| nor |strxfrm()|.)

    Unfortunately, this problem affects not only sorting but also entry
    ordering in B-tree indexes, which means that B-tree indexes on text,
    varchar, or char columns may now be corrupt if they sort according
    to an affected locale and were built or modified under PostgreSQL
    9.5.0 or 9.5.1. Users should REINDEX indexes that might be affected.


    It is not possible at this time to give an exhaustive list of
    known-affected locales. C locale is known safe, and there is no
    evidence of trouble in English-based locales such as en_US, but some
    other popular locales such as de_DE are affected in most glibc
    versions."



        On Wednesday, June 8, 2016 at 11:55:11 PM UTC-4, Scott Jones wrote:

            I have made a branch with an even faster version of == for
            the String type (it took 28%-40% less time in my testing).
            Instead of calling lexcmp, which has to deal with strings of
            different length, it calls memcmp directly if the string
            lengths are equal, and checks if the result is 0.

            https://github.com/ScottPJones/julia/tree/spj/fasteqstr
            <https://github.com/ScottPJones/julia/tree/spj/fasteqstr>

            If somebody could make a PR out of this branch, it would be
            appreciated.

            Thanks in advance,
            Scott


Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Even faster string equality (see #16863)

Páll Haraldsson
On Wednesday, July 13, 2016 at 2:56:43 PM UTC, Stefan Karpinski wrote:
We're moving towards the built-in String type being essentially just a container for bytes with a UTF-8-like interpretation. Thus if two String objects don't have the same underlying data, they are not equal. If you want fancier Unicode-aware behavior

Ok, we can define it that way, then the optimization that is already merged is ok.

This still does not imply anything for ordering. That must be defined. ASCIIbetical is sometimes used (but is bad), similar for Unicode would also be a disaster. Since I want my alphabet, e.g. a á b c.., then it's not a leap to correclty order á weather it's precomposed or not.
 
like UTF-8 validation or normalized comparison, then you'll need to use a package that provides a type like EncodedString{UTF8} (or something). Care needs to be taken to make sure that == is transitive, but that's a problem for the to-be-created external Unicode strings package.

Is it at least easy to include a package with new behavior that substitutes the default string type? If not with the same name, at least all literal will get the new type?

If you must define some order, maybe it's better that equal is not dumb..

--
Palli.

Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Even faster string equality (see #16863)

Steven G. Johnson
Rather than defining a whole new string type, you can also just normalize your strings (with the normalize_string function) before comparing them, in the rare cases where you want equality that ignores e.g. differences in encoding combining characters.

You could even overload a new infix operator (e.g. ≃) that performs normalized equality tests of whatever flavor you like.

There's no single correct answer here, because it depends on what differences you want to ignore.  Do you want to ignore differences in codepoint composition that lead to logically identical strings?  Use NFC normalization.  Do you also want to ignore differences in "confusable" characters like µ (micro) vs μ (greek mu)?  Use NFKC normalization.   Do you want to ignore all diacritical marks, e.g. treat a and á the same?  Use the stripmark=true option.   Do you want to ignore case?  Use the casefold=true option.

Julia's default of == meaning "same codepoints" is reasonable and fast (whereas anything requiring normalization will be much slower).
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Even faster string equality (see #16863)

Steven G. Johnson
Similarly, you can use the "by" keyword option of the sort function if you want to sort strings according to one of their normalized forms.
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Even faster string equality (see #16863)

Scott Jones
In reply to this post by Páll Haraldsson

On Jul 13, 2016, at 1:11 PM, Páll Haraldsson <[hidden email]> wrote:

On Wednesday, July 13, 2016 at 2:56:43 PM UTC, Stefan Karpinski wrote:
We're moving towards the built-in String type being essentially just a container for bytes with a UTF-8-like interpretation. Thus if two String objects don't have the same underlying data, they are not equal. If you want fancier Unicode-aware behavior

Ok, we can define it that way, then the optimization that is already merged is ok.

Julia, AFAIK, has never compared UTF8String (or now String) in any way except for just checking if the encoded bytes are the same.
Before my fixes to handle different technically invalid (but common) UTF-8 encodings, you could easily get two strings like “\xc0\x80” and “\0” which contained the same Unicode code point, but with a different byte encoding (as well as have many completely invalid sequences that were simply not detected).

I think there is a problem now, in that the String constructor does not seem to be making sure that all strings produced are actually valid UTF-8, and methods that deal with String assume that a String is valid UTF-8.
In v0.4.x, utf8 (and convert) ensured that each character in the resulting UTF8String was encoded correctly, but now utf8 has been deprecated, and convert(String doesn’t create a canonically encoded UTF-8 string.

This still does not imply anything for ordering. That must be defined. ASCIIbetical is sometimes used (but is bad), similar for Unicode would also be a disaster. Since I want my alphabet, e.g. a á b c.., then it's not a leap to correclty order á weather it's precomposed or not

Ordering like that is language dependent, and really needs something very complex like the ICU library to attempt to do it right (I wrote code to handle those issues before ICU was available - it’s not at all a trivial task).

like UTF-8 validation or normalized comparison, then you'll need to use a package that provides a type like EncodedString{UTF8} (or something). Care needs to be taken to make sure that == is transitive, but that's a problem for the to-be-created external Unicode strings package.

Is it at least easy to include a package with new behavior that substitutes the default string type? If not with the same name, at least all literal will get the new type?

That is not currently possible.


If you must define some order, maybe it's better that equal is not dumb..

--
Palli.


Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Even faster string equality (see #16863)

Scott Jones
In reply to this post by Steven G. Johnson


On Wednesday, July 13, 2016 at 2:46:43 PM UTC-4, Steven G. Johnson wrote:
Rather than defining a whole new string type, you can also just normalize your strings (with the normalize_string function) before comparing them, in the rare cases where you want equality that ignores e.g. differences in encoding combining characters.

You could even overload a new infix operator (e.g. ≃) that performs normalized equality tests of whatever flavor you like.

There's no single correct answer here, because it depends on what differences you want to ignore.  Do you want to ignore differences in codepoint composition that lead to logically identical strings?  Use NFC normalization.  Do you also want to ignore differences in "confusable" characters like µ (micro) vs μ (greek mu)?  Use NFKC normalization.   Do you want to ignore all diacritical marks, e.g. treat a and á the same?  Use the stripmark=true option.   Do you want to ignore case?  Use the casefold=true option.

Julia's default of == meaning "same codepoints" is reasonable and fast (whereas anything requiring normalization will be much slower).

Unfortunately, that is simply not true (and as far as I've seen has never been) for UTF8String (and now String).

Since Julia never requires that strings be valid, there are many different ways of encoding a single code point using either overly long encodings (such as 0xc0 0x80, which is an invalid (overly long) encoding of 0x00), or encoding non-BMP characters with 6 bytes, i.e. as two 3 byte surrogate characters, which also cause strings to not sort correctly), and those will give bad results.   Fixing those issues would make the performance be far worse than it already is.
At least, with convert and utf8 in v0.4.x (because of my PRs), you could eliminate those problems and ensure that you had valid UTF-8 encoded strings before comparisons, but now, in v0.5.x, you'd need to add the LegacyStrings package to gain back that functionality.
It would be possible, although rather inefficient, to do something like ==(x::String,y::String) = convert(Vector{Char},x) == convert(Vector{Char},y), and then you also have to deal with all sorts of hashing problems as well.
Just to be very clear here - I am *not* talking about composed Unicode characters - which is another matter entirely, I'm talking about simply trying to compare two Unicode strings accepted by String.

This is one of the reasons I felt that the string changes that have gone into v0.5 were a mistake. (I'm not saying either that the way strings are in v0.3 were good either, with 4 different inconsistent basic string types, and my fixes in v0.4 didn't change that mess).
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Even faster string equality (see #16863)

Steven G. Johnson


On Wednesday, July 13, 2016 at 11:23:38 PM UTC+1, Scott Jones wrote:
Julia's default of == meaning "same codepoints" is reasonable and fast (whereas anything requiring normalization will be much slower).

Unfortunately, that is simply not true (and as far as I've seen has never been) for UTF8String (and now String).

It's true for valid strings, which is what most applications are concerned with. For invalid encodings, it's true that we compare encodings.  I don't see a problem with that.  If the user just stuffed arbitrary binary data into a string, comparing encodings (valid or not) seems to be the most reasonable choice of == without knowing application-specific information.

(For example, if your application knows that you are importing "modified UTF-8" from Java code that has (invalid) surrogate pairs, you can do an application-specific preprocessing step to convert these into proper UTF-8 if you want to use the String type.   But it would be inappropriate for Base.String to do this preprocessing for you, because Base.String doesn't know the origin of your invalid encoding.)
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Even faster string equality (see #16863)

Scott Jones
Then what you are saying is that == for String type means simply "same code units", which is not at all the same thing as "same codepoints".

This isn't the case of just arbitrary binary data, these are UTF-8 encodings that are going to be frequently found, whether coming from Java (or languages using the JVM) or many databases.

I don't think it is inappropriate for `convert(String, x::Vector{UInt8})` to make sure that the string is canonically encoded, it can save a lot of grief when people UTF-8 data from a variety of sources.



On Sunday, July 17, 2016 at 9:07:59 PM UTC+2, Steven G. Johnson wrote:


On Wednesday, July 13, 2016 at 11:23:38 PM UTC+1, Scott Jones wrote:
Julia's default of == meaning "same codepoints" is reasonable and fast (whereas anything requiring normalization will be much slower).

Unfortunately, that is simply not true (and as far as I've seen has never been) for UTF8String (and now String).

It's true for valid strings, which is what most applications are concerned with. For invalid encodings, it's true that we compare encodings.  I don't see a problem with that.  If the user just stuffed arbitrary binary data into a string, comparing encodings (valid or not) seems to be the most reasonable choice of == without knowing application-specific information.

(For example, if your application knows that you are importing "modified UTF-8" from Java code that has (invalid) surrogate pairs, you can do an application-specific preprocessing step to convert these into proper UTF-8 if you want to use the String type.   But it would be inappropriate for Base.String to do this preprocessing for you, because Base.String doesn't know the origin of your invalid encoding.)
Loading...