Vous pouvez vous abonner à nos annonces de séminaires http://gallium.inria.fr/seminaires/ S E M I N A I R E __ / _` _ / / o /| /| __ __ __ __ _ _ / ) __) / / / / / /\/| ----- / |/ | / )(_ / / ) ) ) __) (___/ (_/ (_ (_ / (__/ / | / | (__/ __)(_ (__/ (_/ (_/ I N R I A - Rocquencourt Amphi Turing du bâtiment 1 Lundi 9 décembre, 10h30 ----------- Mike Rainey ----------- INRIA ========================================= Theory of chunked sequences and applications to parallel graph algorithms ========================================= For designing parallel algorithms, we needed a container data structure (e.g., sequence, stack, bag, etc.) with log-time split and concatenation operations, in addition to fast access to the ends of the sequence. Tree data structures supporting these operations match the required asymptotics, yet impose prohibitive constant factors. By instantiating the leaves of these trees with chunks (i.e., arrays or lists of items), previous work shows that the constant factors can be significantly improved. However, these results hold only in the typical case and degenerate in worst-case patterns. We propose a general-purpose chunked-sequence data structure that we are able to prove to deliver good constant factors in the worst case. We implemented our data structure in C++ and show that it competes well with the push and pop operations of STL vectors and deques. We also implemented ephemeral sequences in OCaml and measured them to be no more than twice slower than fixed-size circular arrays; we implemented a persistent version that, on a LIFO microbenchmark, was no more than twice slower than native lists. We discuss only one particular application, namely parallel DFS. However, we believe that this data structure has many more application in the context of fork-join parallel computations, purely functional programming, and representations of persistent strings.