3 ms·

FWIW, I profile intensive applications all the time, it's my job. You're right about the existence of hot spots, but that's not particularly relevant to my poin

by dahart 6y ago

FWIW, I profile intensive applications all the time, it's my job. You're right about the existence of hot spots, but that's not particularly relevant to my point or the author's. Just because one spot is hot doesn't mean you should rationalize using lazy or bad-practices programming on the rest. Just because you don't see a bottleneck somewhere when you profile doesn't mean it'll stay that way when other processes want the same resources at the same time. Knuth's famous quote was not intended to be a license to ignore using best practices in general for non-hot-spot code. Use of linked lists in the linux kernel is also not very relevant, and somewhat of a red herring. Kernel-level (as well as games & embedded programming) linked lists are frequently allocated and used very differently from typical high level language linked lists. Scripting languages are allocating individual linked list nodes by default. Linux uses linked lists for the memory allocator itself, for example, and allocates nodes at a lower level in blocks. There are no particularly good alternatives, and no great ways for the allocator itself to be cache aware, though that is ongoing research. The main perf problem with using linked lists in high level languages is not the fact that they cause cache-incoherent access, it's worse, it's the fact that they allocate and deallocate memory constantly which is much much slower. This is one reason why linked lists don't get used as much as arrays in high level languages, when arrays are a reasonable alternative. Anyway, it's somewhat of a straw man to bring up linked lists when the author's valid point was SoAs are better than AoSs from a cache perspective, and that our languages aren't yet doing much to help us code that way, but they could in the future if we decide to want them to.

kaba0 6y ago
I apologize for my cocky reply. I just meant to point out that SoA vs AoS or an even slower data structure is not necessarily relevant for all programs. > The main perf problem with using linked lists in high level languages is not the fact that they cause cache-incoherent access, it's worse, it's the fact that they allocate and deallocate memory constantly which is much much slower. This is not true though; at least the JVM most definitely doesn’t do that, and I’m sure other state-of-the-art GCs neither, like V8. First of all, allocation is basically free, much faster than malloc and friends. It’s only a pointer bump. And the cost of deallocation is amortized/may not even happen. With plenty of memory available, GC doesn’t really happen, and for long-lived objects in case of a generational GC, they may not necessarily get checked at all after a time. So the usual linked list gets appended a few times is close to optimal, iteration has the same cost as in lower level languages with pointer chasing (usually a bit more because objects usually have headers that take quite some space, less of them potentially fitting into cache). It even has some advantage in that a modern compacting GC may move the objects close to each other.
- dahart 6y ago
  > at least the JVM most definitely doesn’t do that, and I’m sure other state-of-the-art GCs neither, like V8. Which implementation are we talking about here? Do you mean JVM internal linked lists, or user allocations of linked list nodes? I was talking about implementations such as (first Google result for "Java linked list implementation") https://www.geeksforgeeks.org/implementing-a-linked-list-in-java-using-class/ https://www.geeksforgeeks.org/implementing-a-linked-list-in-... > First of all, allocation is basically free No, definitely not true. You're claiming that memory allocation in a tight loop is not a bottleneck. I completely disagree, having written several high performance web apps with thousands to millions of users, the single most important performance "best practices" strategy in any tight-loop Javascript is to avoid memory allocation in the hot spot. Also true in Python, true in C++, true in every language I've ever used, and has been true for decades and is still true despite significant performance improvements in V8 and other engines. This is the whole reason there are high performance libraries in JavaScript like https://glmatrix.net/ https://glmatrix.net/ that specifically structure the API so that the user has complete control over allocations, precisely because batching and re-using allocations is faster than not.
  - kaba0 6y ago
    What are the specific situation that we are talking about? Of course needless creation of non-single-use objects will have a cost, but object reuse via pools may be even worse than creating non-escaping objects in a tight loop. The “problem” with high level languages is the complexity of their runtimes - you can’t easily reason about what and how will get optimized. It can change from version to version so one should profile. Not too familiar with JS vm internals, but OpenJDK has quite a good escape analysis.
    - dahart 6y ago
      > The “problem” with high level languages is the complexity of their runtimes - you can’t easily reason about what and how will get optimized. Yes, agreed. This is the point the author was making, and noting that we have room to actually improve the languages, and make some basic optimizations easier to think about and code explicitly. > object reuse via pools may be even worse than creating non-escaping objects in a tight loop. When does this happen in practice, and how likely is it? What does it imply about object lifetime if your objects don't escape, and why wouldn't you be re-using an object on the stack or local scope instead? How often would replacing a non-escaping object creating with a re-use that escapes be a realistic alternative? I'm sure a contrived case can be setup, but this seems like an unlikely explanation to me as general advice. It's bad practice to hope your objects don't escape, and difficult to ensure. In general, if you want higher performance, then avoid using new in hot spots. The difference is often an order of magnitude in an flat O(n) loop.

by dahart 6y ago

kaba0 6y ago

I apologize for my cocky reply. I just meant to point out that SoA vs AoS or an even slower data structure is not necessarily relevant for all programs. > The main perf problem with using linked lists in high level languages is not the fact that they cause cache-incoherent access, it's worse, it's the fact that they allocate and deallocate memory constantly which is much much slower. This is not true though; at least the JVM most definitely doesn’t do that, and I’m sure other state-of-the-art GCs neither, like V8. First of all, allocation is basically free, much faster than malloc and friends. It’s only a pointer bump. And the cost of deallocation is amortized/may not even happen. With plenty of memory available, GC doesn’t really happen, and for long-lived objects in case of a generational GC, they may not necessarily get checked at all after a time. So the usual linked list gets appended a few times is close to optimal, iteration has the same cost as in lower level languages with pointer chasing (usually a bit more because objects usually have headers that take quite some space, less of them potentially fitting into cache). It even has some advantage in that a modern compacting GC may move the objects close to each other.

dahart 6y ago
> at least the JVM most definitely doesn’t do that, and I’m sure other state-of-the-art GCs neither, like V8. Which implementation are we talking about here? Do you mean JVM internal linked lists, or user allocations of linked list nodes? I was talking about implementations such as (first Google result for "Java linked list implementation") https://www.geeksforgeeks.org/implementing-a-linked-list-in-java-using-class/ https://www.geeksforgeeks.org/implementing-a-linked-list-in-... > First of all, allocation is basically free No, definitely not true. You're claiming that memory allocation in a tight loop is not a bottleneck. I completely disagree, having written several high performance web apps with thousands to millions of users, the single most important performance "best practices" strategy in any tight-loop Javascript is to avoid memory allocation in the hot spot. Also true in Python, true in C++, true in every language I've ever used, and has been true for decades and is still true despite significant performance improvements in V8 and other engines. This is the whole reason there are high performance libraries in JavaScript like https://glmatrix.net/ https://glmatrix.net/ that specifically structure the API so that the user has complete control over allocations, precisely because batching and re-using allocations is faster than not.
- kaba0 6y ago
  What are the specific situation that we are talking about? Of course needless creation of non-single-use objects will have a cost, but object reuse via pools may be even worse than creating non-escaping objects in a tight loop. The “problem” with high level languages is the complexity of their runtimes - you can’t easily reason about what and how will get optimized. It can change from version to version so one should profile. Not too familiar with JS vm internals, but OpenJDK has quite a good escape analysis.
  - dahart 6y ago
    > The “problem” with high level languages is the complexity of their runtimes - you can’t easily reason about what and how will get optimized. Yes, agreed. This is the point the author was making, and noting that we have room to actually improve the languages, and make some basic optimizations easier to think about and code explicitly. > object reuse via pools may be even worse than creating non-escaping objects in a tight loop. When does this happen in practice, and how likely is it? What does it imply about object lifetime if your objects don't escape, and why wouldn't you be re-using an object on the stack or local scope instead? How often would replacing a non-escaping object creating with a re-use that escapes be a realistic alternative? I'm sure a contrived case can be setup, but this seems like an unlikely explanation to me as general advice. It's bad practice to hope your objects don't escape, and difficult to ensure. In general, if you want higher performance, then avoid using new in hot spots. The difference is often an order of magnitude in an flat O(n) loop.