3 ms·

>> Random access of a character in a text buffer could take constant time (for ASCII) or linear time (for UTF-8) depending on the character encoding This is tr

>> Random access of a character in a text buffer could take constant time (for ASCII) or linear time (for UTF-8) depending on the character encoding This is true, but incomplete. All unicode encodings take linear time, not just utf-8. That's because a character can contain multiple code points. Utf-32 allows for random access of code points in constant time, but not characters. Utf-16 has variable length code points so it is the same as utf-8 in that regard.

myworkinisgood 2y ago
Yeah, but the author was talking about ASCII. ASCII takes constant time.
- bruce511 2y ago
  The author differentiated I the statement between ASCII and utf-8. The reference to the specific encoding (utf-8) was misleading because the reference should have been to Unicode (the mapping) as the issue applies to all Unicode encodings, and is not limited to utf-8. ASCII does indeed take constant time - which I agreed with.
mjevans 2y ago
IMO within a small range iterating isn't too painful. It's probably safe, maybe even close enough to optimal for typical use, to have an array or list of bytestrings for each line. Or maybe more complex Line (of text) objects that record the byte-length, 'codepoint'-length, and '(display)character'-length. There might even be special cases built in for typical and massive documents (number of lines) and overly long lines.
- bluGill 2y ago
  In most real world cases N is small and so a linear search for data beats a binary search - the binary search is going to stall the pipeline with cache misses all the time, while the linear search will prefetch everything into the cache before you need it thus resulting in not pipeline stalls. Of course different computers (CPU, memory configuration... they all matter) have different characteristics so where N is large enough is different for each. However in general linear search is fast enough these days. Where it isn't you can look at a profile to verify you hotspot.
  - throwaway2037 2y ago
    I have heard this a few times now. Honestly, I could not believe it the first time I read it. It is a little bit like 10 years ago, when I finally gave up on using linked lists and just replaced them with dynamic arrays (whatever language is fine) after realising that the memory locality gains (less cache misses) far outweighed the relatively rare instances that I needed to insert/delete from the collection. And, if the collection was small enough, the insert or delete from a dynamic array can be faster than a linked list ... thanks again to memory locality! (Again, my mind was blown by these discoveries.) To be clear to readers: I'm talking about bog-standard CRUD apps written at mega-corps. No special operating environments. I tried to Google for some blog posts, but I could find anything. Does anyone know of any (amateur) research on this topic? Example: Running on Linux, written in C, what is the threshold for N to switch from binary search to linear search? EDIT: Fix typos
Zamicol 2y ago
Pedantically, UTF-16 has some code points out of order. The way I've always seen it implemented results in more operations spent on some points than others. See this example C code: https://icu-project.org/docs/papers/utf16_code_point_order.html https://icu-project.org/docs/papers/utf16_code_point_order.h... UTF-8 doesn't suffer from this design flaw.
LegionMammal978 2y ago
Really, it's not even random access per se that takes linear time, but random access indexed by code points. You can access the middle of a UTF-8 string just fine if you index by byte position. (Or more generally, by code units for UTF-16.)
darby_nine 2y ago
I've come to the conclusion that "character" is worth abandoning as a coherent concept. Words and bytes are much more useful and easier to define and aren't dependent on which runtime you're using, and the number of times it's worth slicing a word into characters is actually pretty low. One exception to this might be chinese (and I'm sure others) where differentiating words is not a straightforward task of splitting by whitespace, but they also have much more straightforward glyph rendering bypassing most of unicode's nastiness. Random access strings in chinese are actually super straightforward once you abandon run length encoding to heavy users of ascii and emoji.

myworkinisgood 2y ago

Yeah, but the author was talking about ASCII. ASCII takes constant time.

bruce511 2y ago
The author differentiated I the statement between ASCII and utf-8. The reference to the specific encoding (utf-8) was misleading because the reference should have been to Unicode (the mapping) as the issue applies to all Unicode encodings, and is not limited to utf-8. ASCII does indeed take constant time - which I agreed with.

mjevans 2y ago

IMO within a small range iterating isn't too painful. It's probably safe, maybe even close enough to optimal for typical use, to have an array or list of bytestrings for each line. Or maybe more complex Line (of text) objects that record the byte-length, 'codepoint'-length, and '(display)character'-length. There might even be special cases built in for typical and massive documents (number of lines) and overly long lines.

bluGill 2y ago
In most real world cases N is small and so a linear search for data beats a binary search - the binary search is going to stall the pipeline with cache misses all the time, while the linear search will prefetch everything into the cache before you need it thus resulting in not pipeline stalls. Of course different computers (CPU, memory configuration... they all matter) have different characteristics so where N is large enough is different for each. However in general linear search is fast enough these days. Where it isn't you can look at a profile to verify you hotspot.
- throwaway2037 2y ago
  I have heard this a few times now. Honestly, I could not believe it the first time I read it. It is a little bit like 10 years ago, when I finally gave up on using linked lists and just replaced them with dynamic arrays (whatever language is fine) after realising that the memory locality gains (less cache misses) far outweighed the relatively rare instances that I needed to insert/delete from the collection. And, if the collection was small enough, the insert or delete from a dynamic array can be faster than a linked list ... thanks again to memory locality! (Again, my mind was blown by these discoveries.) To be clear to readers: I'm talking about bog-standard CRUD apps written at mega-corps. No special operating environments. I tried to Google for some blog posts, but I could find anything. Does anyone know of any (amateur) research on this topic? Example: Running on Linux, written in C, what is the threshold for N to switch from binary search to linear search? EDIT: Fix typos

Zamicol 2y ago

Pedantically, UTF-16 has some code points out of order. The way I've always seen it implemented results in more operations spent on some points than others. See this example C code: https://icu-project.org/docs/papers/utf16_code_point_order.html https://icu-project.org/docs/papers/utf16_code_point_order.h... UTF-8 doesn't suffer from this design flaw.

LegionMammal978 2y ago

Really, it's not even random access per se that takes linear time, but random access indexed by code points. You can access the middle of a UTF-8 string just fine if you index by byte position. (Or more generally, by code units for UTF-16.)

darby_nine 2y ago

I've come to the conclusion that "character" is worth abandoning as a coherent concept. Words and bytes are much more useful and easier to define and aren't dependent on which runtime you're using, and the number of times it's worth slicing a word into characters is actually pretty low. One exception to this might be chinese (and I'm sure others) where differentiating words is not a straightforward task of splitting by whitespace, but they also have much more straightforward glyph rendering bypassing most of unicode's nastiness. Random access strings in chinese are actually super straightforward once you abandon run length encoding to heavy users of ascii and emoji.