|
|
|
|
|
|
by tikhonj
3973 days ago
|
|
|
Modern radix trees[1] can be as fast as the hash maps you'd find in a language's standard library while providing additional capabilities (ie fast ordered traversal). Making them immutable and persistent[2] is easy and only adds a bit of performance overhead. Obviously programs that rely on communicating by mutating parts of a dictionary would have to be rewritten to use an immutable, persistent map—but they could still maintain similar performance. [1]: Namely "adaptive radix trees" as described in “The adaptive radix tree: Artful indexing for main-memory databases” by V. Leis, A. Kemper, and T. Neumann
<http://www3.informatik.tu-muenchen.de/~leis/papers/ART.pdf> [2]: A persistent adaptive radix tree in Java: https://github.com/ankurdave/part |
|
|
On the other hand, stating "they could still maintain similar performance" for immutable dictionaries is misleading at best (you are right for dictionary sizes approaching 0). Anyone can look up benchmarks on the Internet showing real-world performance of immutable data structures and make their mind up if they actually can deliver in their particular use cases.
Mutability could be always used to boost performance on Von Neumann architecture if you know what you are doing. It's just becoming impractical due to increased complexity, pervasive security paranoia and the fact that there are very few people that can get things done right. If you want to contribute to advance your case, please create a competing computer architecture as fast as Von Neumann's, physically possible, but based on immutability.