4 ms·

You raise a valid point, and one that a lot of algorithm and data structure textbooks neglect to mention at all; seen purely from a practical perspective, thing

You raise a valid point, and one that a lot of algorithm and data structure textbooks neglect to mention at all; seen purely from a practical perspective, things like locality of data with respect to CPU caches are probably more important than picking a slightly cleverer algorithm/data structure on any modern-day CPU. It may not make it into the basics, but locality of data is absolutely considered in a lot of real work on algorithms and data structures. For example, the theoretical advantages of hopscotch hashing rest on data locality concerns. On a hypothetical machine for which memory access always takes the same amount of time, I believe - but have not bothered to prove - that hopscotch hashing and other open addressing techniques should actually be slower than other forms of collision resolution. As for how it affects the question of imperative vs. functional data structure performance, it should tend to favor the imperative ones. The issue is that purely functional data structures aren't allowed to just grab a block of memory all at once and insert data into it at leisure. (That would be a form of mutation.) Instead space has to be allocated as it is needed, in a piecemeal fashion. As a result, longer-lived and more active purely functional data structures will tend to scatter across the heap over time.

eru 15y ago
> As for how it affects the question of imperative vs. functional data structure performance, it should tend to favor the imperative ones. The issue is that purely functional data structures aren't allowed to just grab a block of memory all at once and insert data into it at leisure. (That would be a form of mutation.) Instead space has to be allocated as it is needed, in a piecemeal fashion. As a result, longer-lived and more active purely functional data structures will tend to scatter across the heap over time. It's a bit more complicated than that. To talk about runtime (and memory) of an algorithm or a data structure, you need to have a machine model. If you look at what happens in, say, Haskell: We write our algorithms in a purely functional way, but we are interested in their runtime after compilation into native code. The compiler is free to do any transformation that preserves correctness, so if it's smart enough, it might grab a block of memory all at once. Or if it can prove that data won't be used again, it can safely change variables in place. (The language Clean even has type system support for that kind of mutation. (See https://en.wikipedia.org/wiki/Linear_type_system) https://en.wikipedia.org/wiki/Linear_type_system)) You might be able to analyse functional algorithms with a machine model that doesn't involve compilation to some form of imperative code. Perhaps by counting reductions in lambda calculus. But then it's hard to compare that to asymptotic performance of imperative algorithms.
- bunderbunder 15y ago
  Absolutely. But many of those hypothetical compiler transformations would only work if the code isn't really taking advantage some of the most important advantages of purely functional data structures. Persistence, for example. That, and in a sense it's side-stepping the theoretical issue more than anything else. A compiler that's smart enough to find spots where a performance improvement can safely be gained by replacing a pure structure with a mutable one in the background doesn't really counter the idea that impure structures can be faster so much as acknowledge it.
  - eru 15y ago
    Yes. And instead of comparing purely functional vs imperative languages, we could sidestep those issues by comparing persistent vs ephemeral data structures, regardless of language. (For an example of the distinction--straight out of Okasaki's book: the standard purely-functional queue implementation as two linked lists has O(1) amortized runtime in adding and removing only if used `single-threaded' / ephemeral. As a persistent data structure you get a worst case of O(n).)
    - bunderbunder 15y ago
      Sure. Honestly, that's how I had been interpreting it from the beginning. The SO question seems to be specifically talking about algorithms and not programming languages.
carterschonwald 15y ago
Actually, the question then becomes one of trading off sharing vs cache locality. To whit, for many functional languages, memory allocation is essentially just a pointer increment, so there is no a prior reason to not assume that a freshly allocated tree occupies a contiguous region of memory, or at least contiguoudly on each page where it's been allocated. Claims about data structures in the context of how they're allocated in a modern machine architecture / memory model are not the same thing as claims regarding the semantics that are exposed to the user of a programming language. I think you do raise an interesting question, namely what's the layout in memory of a tree like data structure in eg scheme or Haskell, when the tree is built from scratch, but also when updated and a garbage collection run has compacted the data. Oooo, I totally want to investigate this now! (I don't have the time to, but I totally want to.) Point being, depending on the memory management semantics for heap data in a programming language, any claims about locslity happening for tree data may or may not happen. This actually raises a really beautiful question: what is the complextity of any garbage collection algorithm that exactly or approximately maximizes the locality of tree or directed graph like data structures in memory? I want to speculate that perhaps the data structures which people find fast in practice are actually in some sense enabling the gc to preserve locality. I wonder how optimally the layout can be when only linear or nearly linear time algorithms are considered!
- bunderbunder 15y ago
  there is no a prior reason to not assume that a freshly allocated tree occupies a contiguous region of memory But I'm sure you'll also agree that a freshly allocated tree probably hasn't been alive for long and hasn't seen much activity. :)
  - carterschonwald 15y ago
    Very true! Hence the part where I'm thinking out loud regarding how the gc ordering of data after a copy/compact (in the one generation gc) impacts locality. And I suppose this also applies to more modern gc setups like multiple generations or parallel collection. Is there some notion of data locality that we can formalize and analyze for at least simplified versions of modern memory hierarchy? How well do standard gc algorithms perform when analyzed thusly? How efficient can each style of gc algorithm be if it's designed to optimize locality? It clearly has some relation to optimal caching optimization problems, but with more explicit interdependencies. It's also seemingly both an online and offline problem in terms of how to analyze it, but I need to think on it more

eru 15y ago

> As for how it affects the question of imperative vs. functional data structure performance, it should tend to favor the imperative ones. The issue is that purely functional data structures aren't allowed to just grab a block of memory all at once and insert data into it at leisure. (That would be a form of mutation.) Instead space has to be allocated as it is needed, in a piecemeal fashion. As a result, longer-lived and more active purely functional data structures will tend to scatter across the heap over time. It's a bit more complicated than that. To talk about runtime (and memory) of an algorithm or a data structure, you need to have a machine model. If you look at what happens in, say, Haskell: We write our algorithms in a purely functional way, but we are interested in their runtime after compilation into native code. The compiler is free to do any transformation that preserves correctness, so if it's smart enough, it might grab a block of memory all at once. Or if it can prove that data won't be used again, it can safely change variables in place. (The language Clean even has type system support for that kind of mutation. (See https://en.wikipedia.org/wiki/Linear_type_system) https://en.wikipedia.org/wiki/Linear_type_system)) You might be able to analyse functional algorithms with a machine model that doesn't involve compilation to some form of imperative code. Perhaps by counting reductions in lambda calculus. But then it's hard to compare that to asymptotic performance of imperative algorithms.

bunderbunder 15y ago
Absolutely. But many of those hypothetical compiler transformations would only work if the code isn't really taking advantage some of the most important advantages of purely functional data structures. Persistence, for example. That, and in a sense it's side-stepping the theoretical issue more than anything else. A compiler that's smart enough to find spots where a performance improvement can safely be gained by replacing a pure structure with a mutable one in the background doesn't really counter the idea that impure structures can be faster so much as acknowledge it.
- eru 15y ago
  Yes. And instead of comparing purely functional vs imperative languages, we could sidestep those issues by comparing persistent vs ephemeral data structures, regardless of language. (For an example of the distinction--straight out of Okasaki's book: the standard purely-functional queue implementation as two linked lists has O(1) amortized runtime in adding and removing only if used `single-threaded' / ephemeral. As a persistent data structure you get a worst case of O(n).)
  - bunderbunder 15y ago
    Sure. Honestly, that's how I had been interpreting it from the beginning. The SO question seems to be specifically talking about algorithms and not programming languages.

carterschonwald 15y ago

Actually, the question then becomes one of trading off sharing vs cache locality. To whit, for many functional languages, memory allocation is essentially just a pointer increment, so there is no a prior reason to not assume that a freshly allocated tree occupies a contiguous region of memory, or at least contiguoudly on each page where it's been allocated. Claims about data structures in the context of how they're allocated in a modern machine architecture / memory model are not the same thing as claims regarding the semantics that are exposed to the user of a programming language. I think you do raise an interesting question, namely what's the layout in memory of a tree like data structure in eg scheme or Haskell, when the tree is built from scratch, but also when updated and a garbage collection run has compacted the data. Oooo, I totally want to investigate this now! (I don't have the time to, but I totally want to.) Point being, depending on the memory management semantics for heap data in a programming language, any claims about locslity happening for tree data may or may not happen. This actually raises a really beautiful question: what is the complextity of any garbage collection algorithm that exactly or approximately maximizes the locality of tree or directed graph like data structures in memory? I want to speculate that perhaps the data structures which people find fast in practice are actually in some sense enabling the gc to preserve locality. I wonder how optimally the layout can be when only linear or nearly linear time algorithms are considered!

bunderbunder 15y ago
there is no a prior reason to not assume that a freshly allocated tree occupies a contiguous region of memory But I'm sure you'll also agree that a freshly allocated tree probably hasn't been alive for long and hasn't seen much activity. :)
- carterschonwald 15y ago
  Very true! Hence the part where I'm thinking out loud regarding how the gc ordering of data after a copy/compact (in the one generation gc) impacts locality. And I suppose this also applies to more modern gc setups like multiple generations or parallel collection. Is there some notion of data locality that we can formalize and analyze for at least simplified versions of modern memory hierarchy? How well do standard gc algorithms perform when analyzed thusly? How efficient can each style of gc algorithm be if it's designed to optimize locality? It clearly has some relation to optimal caching optimization problems, but with more explicit interdependencies. It's also seemingly both an online and offline problem in terms of how to analyze it, but I need to think on it more