3 ms·

That code makes zero sense in Unicode. First question how are representing your umlauts, followed by Zero Join Width Characters. You never work on characters,

by Ygg2 3y ago

That code makes zero sense in Unicode. First question how are representing your umlauts, followed by Zero Join Width Characters. You never work on characters, you work on grapheme clusters or whatnot but never characters.

alexvitkov 3y ago
I'm not advocating you write this, I'm saying people have written it, probably hundreds of thousands of times, and if charAt() becomes O(n) instead of O(1), this code suddenly hangs your CPU for 10 seconds on a long string, thus you can't really swap out UTF-16 for UTF-8 transparently.
- Ygg2 3y ago
  Your point doesn't stand for UTF-16 either. It's not a fixed length encoding either. It's broken in UTF-16 as well. It was always O(n). Of course assuming you aren't using UTF-32, which has its own set of problems (BE or LE), and sees little usage outside of China.
  - taway1237 3y ago
    ...it's not O(n). Many languages, JS, Java and C# included, have O(1) access to a character at a given position. You correctly note that it won't work well with international strings, but GP is right that A LOT of code like this was written by western ASCII-brained developers.
  - alexvitkov 3y ago
    Haven't used Java in a while but I believe charAt() returns a UTF-16 codepoint and is constant time access. So something like the above works not only for ASCII, as well as for the majority of Western languages and special characters you may encounter on a day to day basis.
    - Ygg2 3y ago
      It's constant time iff you ignore surrogate pairs and Unicode. By that logic UTF8 is constant time if you ignore anything not ASCII because most text is in English. Saying it works fine if you ignore errors and avoid edge cases is just a clever rephrashing of it worked on my machine. Plus Emojis are Unicode U+1F600 and above, so even in Western language you are bound to find such "exceptions" .
hyperpape 3y ago
You’re correct about algorithms that do “human” things with text, but you need to think of more examples. That’s how you write hashing algorithms, checksums, and certain trivial parsers.[0] But most importantly, right or wrong, this code is out there, running today, god knows where, and you do not slow it down from O(n) to O(n^2).
- SAI_Peregrinus 3y ago
  Hashing algorithms and checksums work on bytes, not characters.
  - hyperpape 3y ago
    Here is the JDK 7 String#hashCode(), which operates on characters: https://github.com/openjdk-mirror/jdk7u-jdk/blob/f4d80957e89a19a29bb9f9807d2a28351ed7f7df/src/share/classes/java/lang/String.java#L1494 https://github.com/openjdk-mirror/jdk7u-jdk/blob/f4d80957e89.... That's changed in the newer versions, because String has a `byte[]` not a `char[]`, but it was just fine. A hash algorithm can take in bytes, characters, ints, it doesn't matter. In Java, you don't get access to the bytes that make up a string, to preserve the string's immutability. So for many operations where you might operate on bytes in a lower level language, you end up using characters (unless you're the standard library, and you can finagle access to the bytes), or alternately doing a byte copy of the entire string. I admit, checksums using characters are a bit weird sounding, but they should also be perfectly well-defined.
    - samus 3y ago
      A possible optimization would be to change internal representation on-the-fly for long-ish strings as soon as random accesses are observed. Guidance from experiments would be required to tell where the right tresholds are. Also JavaScript implementations already do internal conversions between string implementations.
- samus 3y ago
  Is such code really going to be ported to WASM though? And does it really matter for the string lengths that a typical web application has to process? WASM really doesn't have to worry about legacy that much.
nvm0n2 3y ago
In practice you often do because it's common to parse text that has "special" characters which are always ASCII. Think CSV, XML, JSON, source code, that sort of thing. These formats may have non-ASCII characters in them in places, but it's still a very common task to work with indexes into the string and the "character" at that index, which works fine because in practice that character is known to always be a single code unit.
- Ygg2 3y ago
  I've found in that case it's much easier to just operate on raw bytes, then transform those into UTF characters. It works trivially for UTF8 and needs some massaging for UTF16 and UTF32 because BE/LE.

by Ygg2 3y ago

alexvitkov 3y ago

I'm not advocating you write this, I'm saying people have written it, probably hundreds of thousands of times, and if charAt() becomes O(n) instead of O(1), this code suddenly hangs your CPU for 10 seconds on a long string, thus you can't really swap out UTF-16 for UTF-8 transparently.

Ygg2 3y ago
Your point doesn't stand for UTF-16 either. It's not a fixed length encoding either. It's broken in UTF-16 as well. It was always O(n). Of course assuming you aren't using UTF-32, which has its own set of problems (BE or LE), and sees little usage outside of China.
- taway1237 3y ago
  ...it's not O(n). Many languages, JS, Java and C# included, have O(1) access to a character at a given position. You correctly note that it won't work well with international strings, but GP is right that A LOT of code like this was written by western ASCII-brained developers.
- alexvitkov 3y ago
  Haven't used Java in a while but I believe charAt() returns a UTF-16 codepoint and is constant time access. So something like the above works not only for ASCII, as well as for the majority of Western languages and special characters you may encounter on a day to day basis.
  - Ygg2 3y ago
    It's constant time iff you ignore surrogate pairs and Unicode. By that logic UTF8 is constant time if you ignore anything not ASCII because most text is in English. Saying it works fine if you ignore errors and avoid edge cases is just a clever rephrashing of it worked on my machine. Plus Emojis are Unicode U+1F600 and above, so even in Western language you are bound to find such "exceptions" .

hyperpape 3y ago

You’re correct about algorithms that do “human” things with text, but you need to think of more examples. That’s how you write hashing algorithms, checksums, and certain trivial parsers.[0] But most importantly, right or wrong, this code is out there, running today, god knows where, and you do not slow it down from O(n) to O(n^2).

SAI_Peregrinus 3y ago
Hashing algorithms and checksums work on bytes, not characters.
- hyperpape 3y ago
  Here is the JDK 7 String#hashCode(), which operates on characters: https://github.com/openjdk-mirror/jdk7u-jdk/blob/f4d80957e89a19a29bb9f9807d2a28351ed7f7df/src/share/classes/java/lang/String.java#L1494 https://github.com/openjdk-mirror/jdk7u-jdk/blob/f4d80957e89.... That's changed in the newer versions, because String has a `byte[]` not a `char[]`, but it was just fine. A hash algorithm can take in bytes, characters, ints, it doesn't matter. In Java, you don't get access to the bytes that make up a string, to preserve the string's immutability. So for many operations where you might operate on bytes in a lower level language, you end up using characters (unless you're the standard library, and you can finagle access to the bytes), or alternately doing a byte copy of the entire string. I admit, checksums using characters are a bit weird sounding, but they should also be perfectly well-defined.
  - samus 3y ago
    A possible optimization would be to change internal representation on-the-fly for long-ish strings as soon as random accesses are observed. Guidance from experiments would be required to tell where the right tresholds are. Also JavaScript implementations already do internal conversions between string implementations.
samus 3y ago
Is such code really going to be ported to WASM though? And does it really matter for the string lengths that a typical web application has to process? WASM really doesn't have to worry about legacy that much.

nvm0n2 3y ago

In practice you often do because it's common to parse text that has "special" characters which are always ASCII. Think CSV, XML, JSON, source code, that sort of thing. These formats may have non-ASCII characters in them in places, but it's still a very common task to work with indexes into the string and the "character" at that index, which works fine because in practice that character is known to always be a single code unit.

Ygg2 3y ago
I've found in that case it's much easier to just operate on raw bytes, then transform those into UTF characters. It works trivially for UTF8 and needs some massaging for UTF16 and UTF32 because BE/LE.