5 ms·

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 bytes

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

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