Интересно было бы сравнить с реализацией векторов в Clojure, которая опирается на работу того же Phil Bagwell. Статьи нормальной я не нашёл, но есть подробный блог-пост: https://hypirion.com/musings/understanding-persistent-vector-pt-1 (и исходники).
Антон On Thu, Feb 21, 2019 at 4:18 PM Sergei Romanenko sergei.romanenko_AT_supercompilers.ru <refal@botik.ru> wrote: > Nicolas Stucki, Tiark Rompf, Vlad Ureche, and Phil Bagwell. 2015. RRB > vector: a practical general purpose immutable sequence. In *Proceedings > of the 20th ACM SIGPLAN International Conference on Functional Programming* > (ICFP 2015). ACM, New York, NY, USA, 342-354. DOI= > http://dx.doi.org/10.1145/2784731.2784739 > > State-of-the-art immutable collections have wildly differing performance > characteristics across their operations, often forcing programmers to > choose different collection implementations for each task. Thus, changes to > the program can invalidate the choice of collections, making code evolution > costly. It would be desirable to have a collection that performs well for a > broad range of operations. To this end, we present the RRB-Vector, an > immutable sequence collection that offers good performance across a large > number of sequential and parallel operations. The underlying innovations > are: (1) the Relaxed-Radix-Balanced (RRB) tree structure, which allows > efficient structural reorganization, and (2) an optimization that exploits > spatio-temporal locality on the RRB data structure in order to offset the > cost of traversing the tree. In our benchmarks, the RRB-Vector speedup for > parallel operations is lower bounded by 7x when executing on 4 CPUs of 8 > cores each. The performance for discrete operations, such as appending on > either end, or updating and removing elements, is consistently good and > compares favorably to the most important immutable sequence collections in > the literature and in use today. The memory footprint of RRB-Vector is on > par with arrays and an order of magnitude less than competing collections. > ---- > > В порядке информации. > > СР > >
