4 ms·

Mostly agree with your comment but linear search through arrays of size less than a few hundred will typically beat more sophisticated structures such as red-bl

Mostly agree with your comment but linear search through arrays of size less than a few hundred will typically beat more sophisticated structures such as red-black trees or hashtables. This is due to prefetching and avoidance of unpredictable pointer traversals. Asymptotic complexity is only that: asymptotic. In many programs in many domains the sizes of these data structures will rarely exceed this limit.

vbezhenar 6y ago
It might be fast, but it'll load CPU caches with that data and it'll evict another useful data. Which means that while this particular code will be fast or at least not very slow, some other code will be slow because its data have to be fetched again. I have no idea whether that matters or even easy to measure...
- forrestthewoods 6y ago
  You’re stretching there imho. L1 and L2 are per core. A cacheline is 64 bytes and per-core cache size is on the order of 32kb and 256kb for L1/L2. Reading data from L1 is on the order of 1 nanosecond (or less) and RAM on the order of 50 nanoseconds. If you’re scanning an array and load a dozen cachelines that’s almost certainly preferable to several cache-misses (and lines). Memory access is very often an application’s bottleneck. The answer is almost always more arrays and fewer pointers.
  - deleted 6y ago
    [deleted]
  - naikrovek 6y ago
    > The answer is almost always more arrays and fewer pointers. The number of people who dismiss the lowly array is way too high. Arrays are fast. Keep your data in the cache and they're 10x or more faster than normal, and plain flat arrays are almost always faster than literally any OOP nonsense. By "almost always" I mean that I've never once encountered a situation where flat arrays weren't the fastest solution attempted, and I haven't seen everything, so I can't claim they're always fastest. People really don't understand how fast their computers really are, thanks to developers not caring how fast their code is.
- josephg 6y ago
  > I have no idea whether that matters or even easy to measure... It is reasonably easy to measure, and the GP is about right. I've measured a crossover point of around a few hundred items too. (Though I'm sure it'll vary depending on use case and whatnot.) I made a rope data structure a few years ago in C. Its a fancy string data structure which supports inserts and deletes of characters at arbitrary offsets. (Designed for text editors). The implementation uses a skip list (which performs similarly to a b-tree). At every node we store an array of characters. To insert or delete, we traverse the structure to find the node at the requested offset, then (usually) memmove a bunch of characters at that node. Q: How large should that per-node array be? A small number would put more burden on the skip list structure and the allocator, and incur more cache misses. A large number will be linearly slower because of all the time spent in memmove. Benchmarking shows the ideal number is in the ballpark of 100-200, depending on CPU and some specifics of the benchmark itself. Cache misses are extremely expensive. Storing only a single character at each node (like the SGI C++ rope structure does) makes it run several times slower. (!!) Code: https://github.com/josephg/librope https://github.com/josephg/librope This is the constant to change if you want to experiment yourself: https://github.com/josephg/librope/blob/81e1938e45561b0856d40b2946c0e8aaa7eadbe6/rope.h#L37 https://github.com/josephg/librope/blob/81e1938e45561b0856d4... In my opinion, hash tables, btrees and the like in the standard library should probably swap to flat lists internally when the number of items in the collection is small. I'm surprised more libraries don't do that.
  - loup-vaillant 6y ago
    > In my opinion, hash tables, btrees and the like in the standard library should probably swap to flat lists internally when the number of items in the collection is small. I'm surprised more libraries don't do that. If I recall correctly, the STL provides guarantees that prevents it from taking advantage of flat lists. I think some containers (not arrays) guarantee that they don't move the address of whatever they're containing, even if you insert or remove elements. Even if they switched to flat lists, it would be a flat list of pointers, with all the incurred overhead. Likewise, I believe I have heard of small string optimisation being impossible with std::string for similar reasons.
    - 6y ago
- scottlamb 6y ago
  Conversely, more sophisticated algorithms, and particularly monomorphization, may bloat the code size, causing icache, L2/L3 cache, and TLB misses. (Also slows compilation.) I think this is under-appreciated because it doesn't show in microbenchmarks. (I wish I knew of an easy way to measure how much cache pressure you're causing from a microbenchmark.) I suspect for this reason it'd be better in Rust to use a Go-like hash map implementation [1] that keeps all the key/value information (size, Hash and Eq implementations) in a vtable-like form rather than be monomorphized, except in really hot inner loops where the specialization is worth it. There was an interesting article and discussion on reddit relating to this [2] where someone made a toy type-erased map (though not as nice as Go's) to measure the difference in compilation times. Maybe some day I'll make a more production-ready attempt... [1] https://dave.cheney.net/2018/05/29/how-the-go-runtime-implements-maps-efficiently-without-generics https://dave.cheney.net/2018/05/29/how-the-go-runtime-implem... [2] https://www.reddit.com/r/rust/comments/g1skz4/an_experiment_with_typeerased_datastructures/ https://www.reddit.com/r/rust/comments/g1skz4/an_experiment_...
  - pbadenski 6y ago
    Thank you for mentioning monomorphization - I wasn't aware of this concept. Would you maybe if there's any source discussing how this is solved in different languages and performance consequences of it?
    - bicolao 6y ago
      Not really answering your questions, but regarding monomorphization, you can see a comparison of code size and compilation speed between printf, std::format and C++ iostream. The last one is monomophization, I believe. https://github.com/fmtlib/fmt#compile-time-and-code-bloat https://github.com/fmtlib/fmt#compile-time-and-code-bloat
    - scottlamb 6y ago
      I'm not aware of a high-quality source discussing this. I'd be interested in seeing one. Off the top of my head: * In many languages, monomorphization is impractical. Eg, in C it requires macros or external code generators. Java and Go don't even have macros. So it's rarely done. Instead, stuff uses type erasure, dynamic dispatch, more heap allocations, and tables like the ones described in that dave.cheney.net link. Maybe some JITs or even some ahead-of-time compilers do monomorphization internally in some cases, but I'm speculating rather than speaking from knowledge. * In C++ and Rust, monomorphization is easy. You don't have to do it, but it's easy, so many people do. The containers in the standard library are monomorphized. This code can perform very well in any particular case, but in aggregate it's large enough that I have doubts about whether it's always worth it for the whole program.
- deleted 6y ago
  [deleted]
- snicker7 6y ago
  The CPU will load less cache data with linear searches. This is because you will have less cache misses. Less cache misses == less loading from memory. With pointer-heavy data structures, you load more from memory, and most of the stuff you do load is useless.
  - jstimpfle 6y ago
    A binary tree might require you to visit only O(log2(N)) of your data, while a linear array on average requires you to visit one half. How does that correspond to less loading from memory? Linear arrays are often faster, not because they require fewer memory loads, but because the cache has intelligence built in (the prefetcher) that loads some memory in advance even before the code requests it. That intelligence works way better with linear array scans than with pointer chasing. (I'm not sure if these loads will count as cache misses or not).
    - snicker7 6y ago
      You need to look at the coefficients. Memory queries pull in 64 bytes of contiguous memory at a time (actually more with speculative prefetching). That extra data is used in a linear scan, but is mostly wasted when doing random access. You also have other bottlenecks with binary search, e.g. branch misprediction. Yes, for large enough N, a BST easily beats linear search.
      - jstimpfle 6y ago
        > That extra data is used in a linear scan, but is mostly wasted when doing random access You are shifting goalposts. What the parent poster said is that a linear scan will read more memory than a binary search, therefore it will cause more churn in the cache (assuming same cache policies, which I don't know is a safe assumption), therefore linear scan may actually be less cache friendly - given that you're not interested in the data in any other way besides for the scan - by way of putting other parts of the program whose data was pushed out of the cache at a disadvantage. Implied was also that linear scan might actually result in a slower program, even if the scan itself might be faster than a binary search. What you replied is "The CPU will load less cache data with linear searches", which I assume to be false, although I will be happy to learn that it's actually the case (for example because the CPU has a clever cache eviction policy, executing linear scans by streaming in memory into a small part of the cache instead of thrashing the whole cache). Let's say we have an array of 200 4-byte ints. Let's do a linear array scan and on average will touch 100 of them (or about 7 cache lines). Now let's say we have each integer in its own linked node in a BST in a totally random memory location. We can expect to need about 7 steps as well (2^8 = 256 > 200), which is 7 cache lines. So about 200 is already a lower bound where BST is more efficient in terms of visited cache lines, even for a pessimistic inefficient data structure like this 4-byte integer example.
ummonk 6y ago
This is why Rust uses B-trees, which combine linear search and trees at optimal ratios.

vbezhenar 6y ago

It might be fast, but it'll load CPU caches with that data and it'll evict another useful data. Which means that while this particular code will be fast or at least not very slow, some other code will be slow because its data have to be fetched again. I have no idea whether that matters or even easy to measure...

forrestthewoods 6y ago
You’re stretching there imho. L1 and L2 are per core. A cacheline is 64 bytes and per-core cache size is on the order of 32kb and 256kb for L1/L2. Reading data from L1 is on the order of 1 nanosecond (or less) and RAM on the order of 50 nanoseconds. If you’re scanning an array and load a dozen cachelines that’s almost certainly preferable to several cache-misses (and lines). Memory access is very often an application’s bottleneck. The answer is almost always more arrays and fewer pointers.
- deleted 6y ago
  [deleted]
- naikrovek 6y ago
  > The answer is almost always more arrays and fewer pointers. The number of people who dismiss the lowly array is way too high. Arrays are fast. Keep your data in the cache and they're 10x or more faster than normal, and plain flat arrays are almost always faster than literally any OOP nonsense. By "almost always" I mean that I've never once encountered a situation where flat arrays weren't the fastest solution attempted, and I haven't seen everything, so I can't claim they're always fastest. People really don't understand how fast their computers really are, thanks to developers not caring how fast their code is.
josephg 6y ago
> I have no idea whether that matters or even easy to measure... It is reasonably easy to measure, and the GP is about right. I've measured a crossover point of around a few hundred items too. (Though I'm sure it'll vary depending on use case and whatnot.) I made a rope data structure a few years ago in C. Its a fancy string data structure which supports inserts and deletes of characters at arbitrary offsets. (Designed for text editors). The implementation uses a skip list (which performs similarly to a b-tree). At every node we store an array of characters. To insert or delete, we traverse the structure to find the node at the requested offset, then (usually) memmove a bunch of characters at that node. Q: How large should that per-node array be? A small number would put more burden on the skip list structure and the allocator, and incur more cache misses. A large number will be linearly slower because of all the time spent in memmove. Benchmarking shows the ideal number is in the ballpark of 100-200, depending on CPU and some specifics of the benchmark itself. Cache misses are extremely expensive. Storing only a single character at each node (like the SGI C++ rope structure does) makes it run several times slower. (!!) Code: https://github.com/josephg/librope https://github.com/josephg/librope This is the constant to change if you want to experiment yourself: https://github.com/josephg/librope/blob/81e1938e45561b0856d40b2946c0e8aaa7eadbe6/rope.h#L37 https://github.com/josephg/librope/blob/81e1938e45561b0856d4... In my opinion, hash tables, btrees and the like in the standard library should probably swap to flat lists internally when the number of items in the collection is small. I'm surprised more libraries don't do that.
- loup-vaillant 6y ago
  > In my opinion, hash tables, btrees and the like in the standard library should probably swap to flat lists internally when the number of items in the collection is small. I'm surprised more libraries don't do that. If I recall correctly, the STL provides guarantees that prevents it from taking advantage of flat lists. I think some containers (not arrays) guarantee that they don't move the address of whatever they're containing, even if you insert or remove elements. Even if they switched to flat lists, it would be a flat list of pointers, with all the incurred overhead. Likewise, I believe I have heard of small string optimisation being impossible with std::string for similar reasons.
  - 6y ago
scottlamb 6y ago
Conversely, more sophisticated algorithms, and particularly monomorphization, may bloat the code size, causing icache, L2/L3 cache, and TLB misses. (Also slows compilation.) I think this is under-appreciated because it doesn't show in microbenchmarks. (I wish I knew of an easy way to measure how much cache pressure you're causing from a microbenchmark.) I suspect for this reason it'd be better in Rust to use a Go-like hash map implementation [1] that keeps all the key/value information (size, Hash and Eq implementations) in a vtable-like form rather than be monomorphized, except in really hot inner loops where the specialization is worth it. There was an interesting article and discussion on reddit relating to this [2] where someone made a toy type-erased map (though not as nice as Go's) to measure the difference in compilation times. Maybe some day I'll make a more production-ready attempt... [1] https://dave.cheney.net/2018/05/29/how-the-go-runtime-implements-maps-efficiently-without-generics https://dave.cheney.net/2018/05/29/how-the-go-runtime-implem... [2] https://www.reddit.com/r/rust/comments/g1skz4/an_experiment_with_typeerased_datastructures/ https://www.reddit.com/r/rust/comments/g1skz4/an_experiment_...
- pbadenski 6y ago
  Thank you for mentioning monomorphization - I wasn't aware of this concept. Would you maybe if there's any source discussing how this is solved in different languages and performance consequences of it?
  - bicolao 6y ago
    Not really answering your questions, but regarding monomorphization, you can see a comparison of code size and compilation speed between printf, std::format and C++ iostream. The last one is monomophization, I believe. https://github.com/fmtlib/fmt#compile-time-and-code-bloat https://github.com/fmtlib/fmt#compile-time-and-code-bloat
  - scottlamb 6y ago
    I'm not aware of a high-quality source discussing this. I'd be interested in seeing one. Off the top of my head: * In many languages, monomorphization is impractical. Eg, in C it requires macros or external code generators. Java and Go don't even have macros. So it's rarely done. Instead, stuff uses type erasure, dynamic dispatch, more heap allocations, and tables like the ones described in that dave.cheney.net link. Maybe some JITs or even some ahead-of-time compilers do monomorphization internally in some cases, but I'm speculating rather than speaking from knowledge. * In C++ and Rust, monomorphization is easy. You don't have to do it, but it's easy, so many people do. The containers in the standard library are monomorphized. This code can perform very well in any particular case, but in aggregate it's large enough that I have doubts about whether it's always worth it for the whole program.
deleted 6y ago
[deleted]
snicker7 6y ago
The CPU will load less cache data with linear searches. This is because you will have less cache misses. Less cache misses == less loading from memory. With pointer-heavy data structures, you load more from memory, and most of the stuff you do load is useless.
- jstimpfle 6y ago
  A binary tree might require you to visit only O(log2(N)) of your data, while a linear array on average requires you to visit one half. How does that correspond to less loading from memory? Linear arrays are often faster, not because they require fewer memory loads, but because the cache has intelligence built in (the prefetcher) that loads some memory in advance even before the code requests it. That intelligence works way better with linear array scans than with pointer chasing. (I'm not sure if these loads will count as cache misses or not).
  - snicker7 6y ago
    You need to look at the coefficients. Memory queries pull in 64 bytes of contiguous memory at a time (actually more with speculative prefetching). That extra data is used in a linear scan, but is mostly wasted when doing random access. You also have other bottlenecks with binary search, e.g. branch misprediction. Yes, for large enough N, a BST easily beats linear search.
    - jstimpfle 6y ago
      > That extra data is used in a linear scan, but is mostly wasted when doing random access You are shifting goalposts. What the parent poster said is that a linear scan will read more memory than a binary search, therefore it will cause more churn in the cache (assuming same cache policies, which I don't know is a safe assumption), therefore linear scan may actually be less cache friendly - given that you're not interested in the data in any other way besides for the scan - by way of putting other parts of the program whose data was pushed out of the cache at a disadvantage. Implied was also that linear scan might actually result in a slower program, even if the scan itself might be faster than a binary search. What you replied is "The CPU will load less cache data with linear searches", which I assume to be false, although I will be happy to learn that it's actually the case (for example because the CPU has a clever cache eviction policy, executing linear scans by streaming in memory into a small part of the cache instead of thrashing the whole cache). Let's say we have an array of 200 4-byte ints. Let's do a linear array scan and on average will touch 100 of them (or about 7 cache lines). Now let's say we have each integer in its own linked node in a BST in a totally random memory location. We can expect to need about 7 steps as well (2^8 = 256 > 200), which is 7 cache lines. So about 200 is already a lower bound where BST is more efficient in terms of visited cache lines, even for a pessimistic inefficient data structure like this 4-byte integer example.

ummonk 6y ago

This is why Rust uses B-trees, which combine linear search and trees at optimal ratios.