4 ms·

Honestly, for a single threaded processing potentially the largest improvement come from: * Exploiting cache locality (related data in same cache line, operati

Honestly, for a single threaded processing potentially the largest improvement come from: * Exploiting cache locality (related data in same cache line, operations hit the data before it leaves cache, etc.) * Exploiting cache prefetching (understanding how to lay out your data and operations so that CPU prefetches data from memory into cache BEFORE it is needed) * Ensuring high density of data being accessed (make sure you only access what you need and the cache lines you access contain only data you need and not random other things that are not involved in the operation) ... at least in my own experience. These can be so powerful that may make a dumb algorithm perform like an absolute superstar. A lot of developers overthink algorithms. They try to create something that is super efficient on paper forgetting that the algorithm is not being executed on paper but by a real CPU. Sometimes it is better to sacrifice "paper efficiency" and just ensure cache locality, prefetching, data density and the result is speedup so large it more than covers for a little bit of inefficiency.

hamilyon2 4y ago
The article is about the same thing essentially? Decreasing number of memory accesses is the same thing as exploiting cache locality. Registers are the just more local more high-speed level of cache. Given on modern superscalar CPUs registers are virtual anyway.
- twawaaay 4y ago
  > The article is about the same thing essentially? Decreasing number of memory accesses is the same thing as exploiting cache locality. No, it is not. For example, you can have an application that is doing a lot of memory accesses, but the working set is controlled to fit the cache except for couple of things that need to be fetched into the cache but you make sure those things fit predictable pattern that the CPU prefetcher can recognise and supply in advance of you needing it. Now, having less memory accesses usually helps, but it is kinda newb way of looking at the problem. What if you have to make a lot of accesses because your application is memory heavy (say it is a database)? Does it mean there is nothing you can do to improve it? Of course there are things you can do to improve it -- but you need a bit more in depth knowledge.
  - mackman 4y ago
    I think this article is about cache locality, but temporal cache locality. Which is just as important albeit orthogonal to what you are describing.
    - deleted 4y ago
      [deleted]
FartyMcFarter 4y ago
> These can be so powerful that may make a dumb algorithm perform like an absolute superstar. That's an over-generalization that is only valid for small input sizes. Consider: - an O(N*log N) heap-sort implemented by a decent programmer in idiomatic high-level code. - a dumb O(N^2) bubble-sort coded by an absolute assembly optimization wizard. Your O(N^2) sort will probably be much faster for small input sizes, but it won't take a large input size for it to become dog-crap slow. You can improve constant factors all day, but that won't obviate the need for doing millions or billions of comparisons. You can only take a dumb algorithm so far before it breaks down completely in practice. This is not a theoretical thing either - in unoptimized codebases, I've often seen people finding low-hanging fruit by looking for inadvertent O(N^2) or even O(N^3) behaviour (usually it's not obvious nested loops, but looping hidden by indirection i.e. function calls) and replacing it with an O(N*log N) or O(N) alternative.
- madsbuch 4y ago
  If your problem domain never expands to more than a couple of thousand elements that needs to be ordered, but really often (which is very often the case) the the bubble sort is the way to go (Especially if you have almost-sorted data making bubble sort the ideal choice). > That's an over-generalization I think this is exactly the problem with these types of comparisons. As the original commenter also hinted: You can not generalize best choice about the algorithm.
  - twawaaay 4y ago
    I am pretty used to people defending their blind trust in big-O notation. As I mentioned, the idea is to be open to alternative ways of thinking. Performance is incredibly difficult or impossible to generalise. I have many times worked on a project where people said confidently it is not possible to speed something up and then I speeded it up by multiple orders of magnitude. I worked for one of largest banks in the world and we had a batch task on MongoDB that took 12 hours to complete. The previous team, before I joined, took it down to 4 hours but then said it is not possible to improve it anymore. The consultants from MongoDB confirmed it. This was a huge problem because there was a delay of 4 hours between end of trading day and the report being finished which was unacceptable. I took it down to ~15 seconds. Without changing data structure or the database or the application technology. The only significant thing I did is I made both the data suppliers to stream it to our app and the consumers to stream the results during the data. So the data was being processed during trading day and partial results were already being pushed to the client. The only thing that needed to be done was to sync between the sources and the clients and it took about 15 s to do it (and I could probably take it even further but it was not worth the effort). So you see, it is all about being open minded.

hamilyon2 4y ago

The article is about the same thing essentially? Decreasing number of memory accesses is the same thing as exploiting cache locality. Registers are the just more local more high-speed level of cache. Given on modern superscalar CPUs registers are virtual anyway.

twawaaay 4y ago
> The article is about the same thing essentially? Decreasing number of memory accesses is the same thing as exploiting cache locality. No, it is not. For example, you can have an application that is doing a lot of memory accesses, but the working set is controlled to fit the cache except for couple of things that need to be fetched into the cache but you make sure those things fit predictable pattern that the CPU prefetcher can recognise and supply in advance of you needing it. Now, having less memory accesses usually helps, but it is kinda newb way of looking at the problem. What if you have to make a lot of accesses because your application is memory heavy (say it is a database)? Does it mean there is nothing you can do to improve it? Of course there are things you can do to improve it -- but you need a bit more in depth knowledge.
- mackman 4y ago
  I think this article is about cache locality, but temporal cache locality. Which is just as important albeit orthogonal to what you are describing.
  - deleted 4y ago
    [deleted]

FartyMcFarter 4y ago

> These can be so powerful that may make a dumb algorithm perform like an absolute superstar. That's an over-generalization that is only valid for small input sizes. Consider: - an O(N*log N) heap-sort implemented by a decent programmer in idiomatic high-level code. - a dumb O(N^2) bubble-sort coded by an absolute assembly optimization wizard. Your O(N^2) sort will probably be much faster for small input sizes, but it won't take a large input size for it to become dog-crap slow. You can improve constant factors all day, but that won't obviate the need for doing millions or billions of comparisons. You can only take a dumb algorithm so far before it breaks down completely in practice. This is not a theoretical thing either - in unoptimized codebases, I've often seen people finding low-hanging fruit by looking for inadvertent O(N^2) or even O(N^3) behaviour (usually it's not obvious nested loops, but looping hidden by indirection i.e. function calls) and replacing it with an O(N*log N) or O(N) alternative.

madsbuch 4y ago
If your problem domain never expands to more than a couple of thousand elements that needs to be ordered, but really often (which is very often the case) the the bubble sort is the way to go (Especially if you have almost-sorted data making bubble sort the ideal choice). > That's an over-generalization I think this is exactly the problem with these types of comparisons. As the original commenter also hinted: You can not generalize best choice about the algorithm.
- twawaaay 4y ago
  I am pretty used to people defending their blind trust in big-O notation. As I mentioned, the idea is to be open to alternative ways of thinking. Performance is incredibly difficult or impossible to generalise. I have many times worked on a project where people said confidently it is not possible to speed something up and then I speeded it up by multiple orders of magnitude. I worked for one of largest banks in the world and we had a batch task on MongoDB that took 12 hours to complete. The previous team, before I joined, took it down to 4 hours but then said it is not possible to improve it anymore. The consultants from MongoDB confirmed it. This was a huge problem because there was a delay of 4 hours between end of trading day and the report being finished which was unacceptable. I took it down to ~15 seconds. Without changing data structure or the database or the application technology. The only significant thing I did is I made both the data suppliers to stream it to our app and the consumers to stream the results during the data. So the data was being processed during trading day and partial results were already being pushed to the client. The only thing that needed to be done was to sync between the sources and the clients and it took about 15 s to do it (and I could probably take it even further but it was not worth the effort). So you see, it is all about being open minded.