3 ms·

Out of curiosity, how to purely functional data structures compare with classic mutable data structures in terms of real hardware performance? From what I hear,

Out of curiosity, how to purely functional data structures compare with classic mutable data structures in terms of real hardware performance? From what I hear, they are useful if you are into functional purity, and sometimes if you are doing certain parallel programming tasks, but suffer significant overhead outside that domain, but I would like to hear of any specific evidence people have in either direction.

chipsy 13y ago
The biggest benefit of a purely functional data structure for performance is the same as functional programming in general - they capture the problem in a way that is easier for a compiler to reason about and rewrite to hardware-optimized forms; a computation problem addressed in functional style is going to have fewer ordering dependencies, and (depending on the language) a potentially richer, more expressive type system enabling more aggressive optimizations. Functional code happens to be particularly amenable to parallel optimization, so it's one of the go-to examples of what can be done. In a practical benchmarking scenario like gcc vs. GHC on the benchmarks game[0], gcc is still going to win most of the time. This is mainly a reflection of where the bulk of effort in compiler technology has gone, though, not a definitive "a purely functional data structure is going to be slower" statement. You're leaning a lot more on your compiler when trying to make functional languages run fast, and the biggest benefits of compiler optimizers are going to appear in the overall performance of applications, not benchmarks of an individual data structure. That said, there are also plenty of examples where a mutable structure just wins and nothing with equivalent performance is likely to appear in the functional world anytime soon. If you want to get into the details of that you have to look at each category of data structure case-by-case. [0] http://benchmarksgame.alioth.debian.org/u64q/benchmark.php?test=all&lang=gcc&lang2=ghc&data=u64q http://benchmarksgame.alioth.debian.org/u64q/benchmark.php?t...
evincarofautumn 13y ago
If I may make a sweeping overgeneralisation and phrase it poorly, immutable data structures tend to be logarithmically worse (esp. in terms of allocations) than mutable structures. But if your language or runtime can prove that a reference is unique, then that overhead can be eliminated because the runtime can simply mutate with no one the wiser. And these languages tend to use GCs in which allocations are cheap, besides the fact that sharing saves you on copying. There are many factors at play. Source: professional Haskell and C++ programmer extraordinaire.
- deleted 13y ago
  [deleted]
jules 13y ago
Since the other comments are platitudes, I'll try to give some concrete information. Well implemented purely functional data structures are usually anywhere from just as fast to about 20x slower. If the imperative version is tree like, the cost for lookups in the functional version is the same, but the cost for updating is a bit higher because a path needs to be copied rather than just 1 node modified in place. For a data structure like an unordered map, you can use a hash table backed by an array for the imperative version, but you'll have to use a tree for the purely functional one. This can cause about a 10x-20x slowdown. For example in this post http://donsbot.wordpress.com/2009/09/26/very-fast-scalable-mutable-maps-and-hashes-for-haskell/ http://donsbot.wordpress.com/2009/09/26/very-fast-scalable-m... Haskell's Data.Map is compared with Judy arrays, and found to be 11x slower. Judy arrays themselves are about 2x slower than a basic hash table http://preshing.com/20130107/this-hash-table-is-faster-than-a-judy-array/ http://preshing.com/20130107/this-hash-table-is-faster-than-... Is this slow? Perhaps, but in most cases the difference is smaller. Compare this to the speed of Ruby vs C, that can easily be a 100x difference yet people use Ruby a lot because of productivity reasons.
- dons 13y ago
  Importantly, comparing "ephemeral" structures - those that destroy previous states through direct hardware mutation - with persistent structures (such as all pure data structures) - is a fraught topic. You can surely gain speed ups on real hardware directly mutating memory you know to be reusable (linear) - but proving that precondition is very hard, and we often screw it up. Persistent data is a safe default. Mutation/destruction is an optimisation.
dllthomas 13y ago
The tremendous win in avoiding mutable data structures is in implementing persistent data structures, where appropriate. This isn't something you get automatically (usually), but the leap from "efficient purely-functional data structure" is usually much smaller than the leap from "efficient mutable data structure". Persistent data structures retain the same amortized performance even if you replay them from arbitrary old versions. There is also sharing of unchanged portions of the data, which can shrink your memory footprint if you're saving some old versions, and which you'll usually get some of in any moderately efficient functional data structure, even if it's not truly persistent. This, of course, doesn't apply to all situations - if all you care about is the latest version and you're working in a single thread, a mutable data structure with destructive updates will quite frequently be fastest.

chipsy 13y ago

The biggest benefit of a purely functional data structure for performance is the same as functional programming in general - they capture the problem in a way that is easier for a compiler to reason about and rewrite to hardware-optimized forms; a computation problem addressed in functional style is going to have fewer ordering dependencies, and (depending on the language) a potentially richer, more expressive type system enabling more aggressive optimizations. Functional code happens to be particularly amenable to parallel optimization, so it's one of the go-to examples of what can be done. In a practical benchmarking scenario like gcc vs. GHC on the benchmarks game[0], gcc is still going to win most of the time. This is mainly a reflection of where the bulk of effort in compiler technology has gone, though, not a definitive "a purely functional data structure is going to be slower" statement. You're leaning a lot more on your compiler when trying to make functional languages run fast, and the biggest benefits of compiler optimizers are going to appear in the overall performance of applications, not benchmarks of an individual data structure. That said, there are also plenty of examples where a mutable structure just wins and nothing with equivalent performance is likely to appear in the functional world anytime soon. If you want to get into the details of that you have to look at each category of data structure case-by-case. [0] http://benchmarksgame.alioth.debian.org/u64q/benchmark.php?test=all&lang=gcc&lang2=ghc&data=u64q http://benchmarksgame.alioth.debian.org/u64q/benchmark.php?t...

evincarofautumn 13y ago

If I may make a sweeping overgeneralisation and phrase it poorly, immutable data structures tend to be logarithmically worse (esp. in terms of allocations) than mutable structures. But if your language or runtime can prove that a reference is unique, then that overhead can be eliminated because the runtime can simply mutate with no one the wiser. And these languages tend to use GCs in which allocations are cheap, besides the fact that sharing saves you on copying. There are many factors at play. Source: professional Haskell and C++ programmer extraordinaire.

deleted 13y ago
[deleted]

jules 13y ago

Since the other comments are platitudes, I'll try to give some concrete information. Well implemented purely functional data structures are usually anywhere from just as fast to about 20x slower. If the imperative version is tree like, the cost for lookups in the functional version is the same, but the cost for updating is a bit higher because a path needs to be copied rather than just 1 node modified in place. For a data structure like an unordered map, you can use a hash table backed by an array for the imperative version, but you'll have to use a tree for the purely functional one. This can cause about a 10x-20x slowdown. For example in this post http://donsbot.wordpress.com/2009/09/26/very-fast-scalable-mutable-maps-and-hashes-for-haskell/ http://donsbot.wordpress.com/2009/09/26/very-fast-scalable-m... Haskell's Data.Map is compared with Judy arrays, and found to be 11x slower. Judy arrays themselves are about 2x slower than a basic hash table http://preshing.com/20130107/this-hash-table-is-faster-than-a-judy-array/ http://preshing.com/20130107/this-hash-table-is-faster-than-... Is this slow? Perhaps, but in most cases the difference is smaller. Compare this to the speed of Ruby vs C, that can easily be a 100x difference yet people use Ruby a lot because of productivity reasons.

dons 13y ago
Importantly, comparing "ephemeral" structures - those that destroy previous states through direct hardware mutation - with persistent structures (such as all pure data structures) - is a fraught topic. You can surely gain speed ups on real hardware directly mutating memory you know to be reusable (linear) - but proving that precondition is very hard, and we often screw it up. Persistent data is a safe default. Mutation/destruction is an optimisation.

dllthomas 13y ago

The tremendous win in avoiding mutable data structures is in implementing persistent data structures, where appropriate. This isn't something you get automatically (usually), but the leap from "efficient purely-functional data structure" is usually much smaller than the leap from "efficient mutable data structure". Persistent data structures retain the same amortized performance even if you replay them from arbitrary old versions. There is also sharing of unchanged portions of the data, which can shrink your memory footprint if you're saving some old versions, and which you'll usually get some of in any moderately efficient functional data structure, even if it's not truly persistent. This, of course, doesn't apply to all situations - if all you care about is the latest version and you're working in a single thread, a mutable data structure with destructive updates will quite frequently be fastest.