4 ms·

What is a proper implementation of strings? I often hear this argument (and that null terminated are even worse) but I never understood what is a proper solutio

What is a proper implementation of strings? I often hear this argument (and that null terminated are even worse) but I never understood what is a proper solution then? Can you please explain? Thank you.

nerdponx 6y ago
A text string standalone data type (maybe called Text) that supports traversal/iteration, subsetting/slicing, containment checking, and has a finite known length. Internally it can be a list or array or whatever. Traversal could yield Character objects, which would correspond to Unicode code points (the easy but less-good option, like in Python) or extended grapheme clusters (the actually useful option, like in Swift [0]). It should also be easy to convert to/from a list or array of raw bytes. [0]: https://docs.swift.org/swift-book/LanguageGuide/StringsAndCharacters.html https://docs.swift.org/swift-book/LanguageGuide/StringsAndCh...
brundolf 6y ago
I think they just meant that for ergonomic purposes, strings are very fundamental to most types of programs and deserve first-class support on the same level as primitives Though possibly they just meant a string shouldn't be stored as a linked-list; I'm not familiar enough with Haskell to know whether List implies that underlying representation
- mannerheim 6y ago
  String in Haskell is a type synonym for `List Char` (or `List<Char>`). The question of 'primitives' in Haskell is tricky, as usually you don't deal with primitives at all, although this depends on what you mean by that word: > Primitive (unboxed) types cannot be defined in Haskell, and are therefore built into the language and compiler. Primitive types are always unlifted; that is, a value of a primitive type cannot be bottom. We use the convention (but it is only a convention) that primitive types, values, and operations have a # suffix (see Section 7.3.2, “The magic hash”). For some primitive types we have special syntax for literals, also described in the same section. So with respect to 'primitives', Strings are not less special in Haskell-land than, say, Integers (which are arbitrary-size and assignable as literals). Anyway, Strings as Lists of Chars perform poorly both memory-wise and speed-wise, which is why the linked-list implementation is generally considered a mistake.
ModernMech 6y ago
As with all things, it's a balance of several competing interests. If the string is stored in a contiguous array of memory, you can maintain a pointer to the start of the string and then do some pointer arithmetic to get char n. This is an O(1) operation. If you store the string as a linked list of characters, then to access the nth character you have to follow a bunch of pointers until you get to that char. This is an O(n) operation, and it's going to take up more memory (4/8bytes per pointer, plus a byte for each character). Also it can make your memory fragmented. The upside is that you can grow and shrink the string. Adding chars to the front or end will be O(1). Adding chars in the middle will be O(n). In the array case, if you want to modify the string you'd likely have to allocate a new block of memory for the larger string and copy all chars over. That will be an O(n) operation. Null terminated strings are annoying because you don't know how big the string is without reading it. So getting the length of the string is an O(n) operation. The plus side is you don't have to carry around an extra byte(s) to hold the string length. So it really depends on what you're doing with the string. Are you reading the string and accessing random characters often? Then an array is better. Are you mutating the string often? Then probably a linked list is better. Do you need to know how large your string is? Then keeping a byte around to indicate that is useful. But if you often read the entire string until the NULL character, then that extra memory dedicated to its length is wasted.
- mannerheim 6y ago
  For cases like strings as lists of chars and null-terminated strings, I think the reasons why they're generally considered mistakes is because the tradeoffs don't make sense, at least not compared to their downsides. Null-terminated strings save a constant number of bytes, at the expense of expensive length-checking, potential complications, and liability for generating footgun mistakes (I believe they've been the cause of many a CVE over the years). Most systems aren't generally memory-starved enough that you can't spare the constant number of bytes for keeping track of string lengths. As for linked lists, I believe the times where they're more performant are fairly rare, and unlikely to occur at the level of a data structure for individual characters, which is reflected in String's poor performance in practice. Pretty much the only advantage you get from using string-as-a-list-of-chars is that you get to use List's Functor and Monad instances, but that probably should be avoided in any case.
hn_throwaway_99 6y ago
I think Java Strings are pretty well accepted as being a good implementation: 1. Primarily, the Java String class stores an array of characters as instance data. The underlying format of arrays in Java is JVM dependent, but most JVMs store arrays (which are immutable) as a contiguous block of memory, with a 4-byte length field. This allows for very fast access for a number of different operations, at the cost of storing those 4 bytes for each array. 2. String instances themselves are also immutable, which has a number of very nice features. Back in the day when C was created there was essentially a trade-off between storage (storing the length as an int value for each array) and ease of use. These days I think most people would argue that the teeny amount of storage used for Java arrays is mostly a moot point. Also, since Strings are immutable Java can do some optimizations like representing the same string value as just a single underlying instance even if multiple instances of that String are created in code.
- throwaway894345 6y ago
  What is a “character” in Java? I’m guessing it’s not a unicode code point? Is it basically a byte? Go also has immutable strings which are basically just byte slices (slice being a window into an array).
  - hn_throwaway_99 6y ago
    Java basically uses UTF-16, thus, a char is 2 bytes. All characters in the Unicode Basic Multilingual Plane are encoded with just a single char, while characters in the Supplementary Plane (i.e those with code points above 64K) require 2 chars (4 bytes) in what is called "Surrogate Pairs". Interestingly, code points beyond the BMP used to be quite uncommon (Unicode was originally designed for just 64k code points), but now emoji are in there, which of course are used a lot.
    - astrange 6y ago
      Using UTF-16 is a mistake because it doesn't represent anything well. Even if you use UTF-32 you still can't fit all characters in a single codepoint because some of them (like flag emoji) are composed. So you should expect things to be variable length. But once you do, UTF-8 is more efficient than UTF-16 even if you're processing CJK text because it so often has ASCII characters mixed in. Cocoa/ObjC has the same problem - actually Java is based on Cocoa so that's probably where it came from.
mamcx 6y ago
Similar to what pascal do it. And certainly NOT how C do it. The best internals (imho) is just a array (see, on rust): https://doc.rust-lang.org/src/alloc/string.rs.html#278-280 https://doc.rust-lang.org/src/alloc/string.rs.html#278-280 This allow a lot of efficient operations and the possibility of use views (for substrings). Where thing get nasty is all the unicode stuff. So even if the internal are simply, provide a good API that allow to use unicode correctly is what is more complicated. I think here "proper implementation of strings" must take in account if is proper unicode, ascii or raw. Rust and other modern languages choose UTF-8 and I think this is the best posible option.

nerdponx 6y ago

A text string standalone data type (maybe called Text) that supports traversal/iteration, subsetting/slicing, containment checking, and has a finite known length. Internally it can be a list or array or whatever. Traversal could yield Character objects, which would correspond to Unicode code points (the easy but less-good option, like in Python) or extended grapheme clusters (the actually useful option, like in Swift [0]). It should also be easy to convert to/from a list or array of raw bytes. [0]: https://docs.swift.org/swift-book/LanguageGuide/StringsAndCharacters.html https://docs.swift.org/swift-book/LanguageGuide/StringsAndCh...

brundolf 6y ago

I think they just meant that for ergonomic purposes, strings are very fundamental to most types of programs and deserve first-class support on the same level as primitives Though possibly they just meant a string shouldn't be stored as a linked-list; I'm not familiar enough with Haskell to know whether List implies that underlying representation

mannerheim 6y ago
String in Haskell is a type synonym for `List Char` (or `List<Char>`). The question of 'primitives' in Haskell is tricky, as usually you don't deal with primitives at all, although this depends on what you mean by that word: > Primitive (unboxed) types cannot be defined in Haskell, and are therefore built into the language and compiler. Primitive types are always unlifted; that is, a value of a primitive type cannot be bottom. We use the convention (but it is only a convention) that primitive types, values, and operations have a # suffix (see Section 7.3.2, “The magic hash”). For some primitive types we have special syntax for literals, also described in the same section. So with respect to 'primitives', Strings are not less special in Haskell-land than, say, Integers (which are arbitrary-size and assignable as literals). Anyway, Strings as Lists of Chars perform poorly both memory-wise and speed-wise, which is why the linked-list implementation is generally considered a mistake.

ModernMech 6y ago

As with all things, it's a balance of several competing interests. If the string is stored in a contiguous array of memory, you can maintain a pointer to the start of the string and then do some pointer arithmetic to get char n. This is an O(1) operation. If you store the string as a linked list of characters, then to access the nth character you have to follow a bunch of pointers until you get to that char. This is an O(n) operation, and it's going to take up more memory (4/8bytes per pointer, plus a byte for each character). Also it can make your memory fragmented. The upside is that you can grow and shrink the string. Adding chars to the front or end will be O(1). Adding chars in the middle will be O(n). In the array case, if you want to modify the string you'd likely have to allocate a new block of memory for the larger string and copy all chars over. That will be an O(n) operation. Null terminated strings are annoying because you don't know how big the string is without reading it. So getting the length of the string is an O(n) operation. The plus side is you don't have to carry around an extra byte(s) to hold the string length. So it really depends on what you're doing with the string. Are you reading the string and accessing random characters often? Then an array is better. Are you mutating the string often? Then probably a linked list is better. Do you need to know how large your string is? Then keeping a byte around to indicate that is useful. But if you often read the entire string until the NULL character, then that extra memory dedicated to its length is wasted.

mannerheim 6y ago
For cases like strings as lists of chars and null-terminated strings, I think the reasons why they're generally considered mistakes is because the tradeoffs don't make sense, at least not compared to their downsides. Null-terminated strings save a constant number of bytes, at the expense of expensive length-checking, potential complications, and liability for generating footgun mistakes (I believe they've been the cause of many a CVE over the years). Most systems aren't generally memory-starved enough that you can't spare the constant number of bytes for keeping track of string lengths. As for linked lists, I believe the times where they're more performant are fairly rare, and unlikely to occur at the level of a data structure for individual characters, which is reflected in String's poor performance in practice. Pretty much the only advantage you get from using string-as-a-list-of-chars is that you get to use List's Functor and Monad instances, but that probably should be avoided in any case.

hn_throwaway_99 6y ago

I think Java Strings are pretty well accepted as being a good implementation: 1. Primarily, the Java String class stores an array of characters as instance data. The underlying format of arrays in Java is JVM dependent, but most JVMs store arrays (which are immutable) as a contiguous block of memory, with a 4-byte length field. This allows for very fast access for a number of different operations, at the cost of storing those 4 bytes for each array. 2. String instances themselves are also immutable, which has a number of very nice features. Back in the day when C was created there was essentially a trade-off between storage (storing the length as an int value for each array) and ease of use. These days I think most people would argue that the teeny amount of storage used for Java arrays is mostly a moot point. Also, since Strings are immutable Java can do some optimizations like representing the same string value as just a single underlying instance even if multiple instances of that String are created in code.

throwaway894345 6y ago
What is a “character” in Java? I’m guessing it’s not a unicode code point? Is it basically a byte? Go also has immutable strings which are basically just byte slices (slice being a window into an array).
- hn_throwaway_99 6y ago
  Java basically uses UTF-16, thus, a char is 2 bytes. All characters in the Unicode Basic Multilingual Plane are encoded with just a single char, while characters in the Supplementary Plane (i.e those with code points above 64K) require 2 chars (4 bytes) in what is called "Surrogate Pairs". Interestingly, code points beyond the BMP used to be quite uncommon (Unicode was originally designed for just 64k code points), but now emoji are in there, which of course are used a lot.
  - astrange 6y ago
    Using UTF-16 is a mistake because it doesn't represent anything well. Even if you use UTF-32 you still can't fit all characters in a single codepoint because some of them (like flag emoji) are composed. So you should expect things to be variable length. But once you do, UTF-8 is more efficient than UTF-16 even if you're processing CJK text because it so often has ASCII characters mixed in. Cocoa/ObjC has the same problem - actually Java is based on Cocoa so that's probably where it came from.

mamcx 6y ago

Similar to what pascal do it. And certainly NOT how C do it. The best internals (imho) is just a array (see, on rust): https://doc.rust-lang.org/src/alloc/string.rs.html#278-280 https://doc.rust-lang.org/src/alloc/string.rs.html#278-280 This allow a lot of efficient operations and the possibility of use views (for substrings). Where thing get nasty is all the unicode stuff. So even if the internal are simply, provide a good API that allow to use unicode correctly is what is more complicated. I think here "proper implementation of strings" must take in account if is proper unicode, ascii or raw. Rust and other modern languages choose UTF-8 and I think this is the best posible option.