5 ms·

Is random access that common? I usually only iterate over strings (and random access is hard to do with utf-8 and friends). I think the two biggest reasons to

Is random access that common? I usually only iterate over strings (and random access is hard to do with utf-8 and friends). I think the two biggest reasons to not use a list of characters to represent a string are memory efficiency (not storing a linked list pointer per character) and memory locality (keeping the characters of the string near each other in memory since they are frequently used as a unit).

erik_seaberg 6y ago
Unicode grapheme clusters (letters/ideograms plus accent marks) are inherently variable length, but most devs haven’t read about how that works. We shouldn’t be working with single codepoints or bytes for the same reason we don’t work with US-ASCII one bit at a time, because most slices of a bit string will be nonsense.
- bjourne 6y ago
  Treating strings as arrays of bytes is very reasonable. It is the assumption that each byte is exactly one character that causes trouble.
  - astrange 6y ago
    You should treat them as strings, the backing data store is an implementation detail. What do you want to do with individual bytes if you access them? Whatever you do is likely to be incorrect in some language, even English with emoji mixed in or Zalgo text. This also lets you implement compressed small strings (eg in tagged pointers) which is a good memory optimization.
fiddlerwoaroof 6y ago
Not exactly random access, but things like finding the last character, trimming trailing whitespace, etc. are all less efficient with linked lists because you have to copy the head of the list to change the tail. As far as UTF-8 goes, it does add a whole layer of complexity that I had overlooked: although, I suspect intelligent data structure choices could mitigate the random access cost (something like an array of bytes plus an array of grapheme cluster offsets, or similar). I personally have never found the memory locality concerns relevant to the vast majority of programs I write: when using a language like Python or Ruby or Haskell, you already have a lot of pointer chasing going on because of your non-string data structures such that the memory locality of strings is nearly irrelevant.
- jjnoakes 6y ago
  I think if your program is string heavy you would definitely notice. It is quite a difference between chasing one pointer per structure and one per character.

erik_seaberg 6y ago

Unicode grapheme clusters (letters/ideograms plus accent marks) are inherently variable length, but most devs haven’t read about how that works. We shouldn’t be working with single codepoints or bytes for the same reason we don’t work with US-ASCII one bit at a time, because most slices of a bit string will be nonsense.

bjourne 6y ago
Treating strings as arrays of bytes is very reasonable. It is the assumption that each byte is exactly one character that causes trouble.
- astrange 6y ago
  You should treat them as strings, the backing data store is an implementation detail. What do you want to do with individual bytes if you access them? Whatever you do is likely to be incorrect in some language, even English with emoji mixed in or Zalgo text. This also lets you implement compressed small strings (eg in tagged pointers) which is a good memory optimization.

fiddlerwoaroof 6y ago

Not exactly random access, but things like finding the last character, trimming trailing whitespace, etc. are all less efficient with linked lists because you have to copy the head of the list to change the tail. As far as UTF-8 goes, it does add a whole layer of complexity that I had overlooked: although, I suspect intelligent data structure choices could mitigate the random access cost (something like an array of bytes plus an array of grapheme cluster offsets, or similar). I personally have never found the memory locality concerns relevant to the vast majority of programs I write: when using a language like Python or Ruby or Haskell, you already have a lot of pointer chasing going on because of your non-string data structures such that the memory locality of strings is nearly irrelevant.

jjnoakes 6y ago
I think if your program is string heavy you would definitely notice. It is quite a difference between chasing one pointer per structure and one per character.