On Sun, Dec 23, 2012 at 11:41 PM, Mathias Gaunard < mathias.gaunard@ens-lyon.org> wrote:
SIMD algorithms and segmented iterator algorithms were done for different purposes. Lifting them to the same general algorithm is just a bad idea.
Despite this conclusion I am still interested in segmented data structures and I think that the question how to use SIMD algorithms with or in segmented data structures will arise again and again. The reason is that there is a class of advanced data structures that offers much more efficient algorithms compared to basic data structures. In particular, an augmented array based B+ tree supports summation and accumulation algorithms with logarithmic running time. The mean value can be also calculated in logarithmic time. Adding SIMD algorithms to such data structures in theory should deliver even better performance. You've explained that segmented iterators do not work with SIMD algorithms. However, there are should be some other options, since at implementation level a segmented data structure uses arrays. This is why I am wondering if it is possible: 1. provide variants of SIMD algorithms that can be applied by the implementation of a segmented data structure directly to arrays? 2. improve generalization level of these algorithms through local iterators, such as a pointer based iterator for an array? Regards, Vadim Stadnik