# Announcing Sek, an efficient implementation of sequences **URL:** \ **Category:** Ecosystem\ **Created:** [April 4, 2020, 10:14am UTC](https://discuss.ocaml.org/t/announcing-sek-an-efficient-implementation-of-sequences/5442 "2020-04-04T10:14:09Z")\ **Posts on this page:** 5\ **Page:** 1
**Author:** ![fpottier](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/fpottier/32/677_2.png) [@fpottier](https://discuss.ocaml.org/u/fpottier)\ **Post date:** [April 4, 2020, 10:14am UTC](https://discuss.ocaml.org/t/announcing-sek-an-efficient-implementation-of-sequences/5442/1 "2020-04-04T10:14:09Z")
Fellow OCaml users, We are pleased to announce the first release of Sek, an OCaml library that offers an efficient implementation of sequences. The library offers both ephemeral (mutable) sequences and persistent (immutable) sequences, and offers constant-time conversions between these flavors. It supports all of the standard operations on stacks, queues, deques (e.g. push, pop at either end), catenable sequences (concat, split), and random access sequences (get, set). Data is stored internally in chunks (fixed-capacity arrays), which is why this data structure is known as a chunK SEquence. It is intended to achieve excellent time complexity and memory usage. This is an initial release. The library has not been tested in production, but has received extensive unit testing, via afl-fuzz and ocaml+afl – which are remarkably effective tools, by the way! This is work in progress; more features, such as iterators, will be added in the future. To install Sek, just type ```auto opam update && opam install sek ``` Documentation is [online](http://cambium.inria.fr/~fpottier/sek/doc/sek/Sek/index.html). Feedback is welcome! Arthur Charguéraud François Pottier with contributions by Émilie Guermeur ---
**Author:** ![Yaron\_Minsky](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/yaron_minsky/32/11_2.png) [@Yaron\_Minsky](https://discuss.ocaml.org/u/Yaron_Minsky)\ **Post date:** [April 4, 2020, 12:14pm UTC](https://discuss.ocaml.org/t/announcing-sek-an-efficient-implementation-of-sequences/5442/2 "2020-04-04T12:14:04Z")
Exciting stuff! Do you have any benchmarking to compare it to the other sequence libraries out there? I’m particularly interested in how it compares to Base.Sequence and Seq in the OCaml distribution, but surely there are others as well. y ---
**Author:** ![charguer](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/charguer/32/2199_2.png) [@charguer](https://discuss.ocaml.org/u/charguer)\ **Post date:** [April 4, 2020, 1:31pm UTC](https://discuss.ocaml.org/t/announcing-sek-an-efficient-implementation-of-sequences/5442/3 "2020-04-04T13:31:26Z")
Thanks! Regarding benchmarks: we have preliminary results; they look good; we still need to complete the benchmarks and write text explaining what we are measuring exactly. + Arthur ---
**Author:** ![copy](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/copy/32/480_2.png) [@copy](https://discuss.ocaml.org/u/copy)\ **Post date:** [April 4, 2020, 4:48pm UTC](https://discuss.ocaml.org/t/announcing-sek-an-efficient-implementation-of-sequences/5442/4 "2020-04-04T16:48:46Z")
> [@Yaron\_Minsky](#): > > I’m particularly interested in how it compares to Base.Sequence and Seq in the OCaml distribution, but surely there are others as well. This actually looks like an array/vector structure (supporting, among other things, fast access to the nth element), so a comparison with `CCVector`, `CCFun_vec`, `BatVect`, `Clarity.Vector` etc. would be more appropriate. The name is a bit unfortunate considering the naming used in the general ecosystem. Some time ago, I added some crude benchmarks to [containers’ benchsuite](https://github.com/c-cube/ocaml-containers/blob/d34b7588b028f3618cc44d3f4c6417295db586c8/benchs/run_benchs.ml#L112). I’ll see if I can add Sek when I find time. ---
**Author:** ![gasche](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/gasche/32/4_2.png) [@gasche](https://discuss.ocaml.org/u/gasche)\ **Post date:** [April 5, 2020, 9:34am UTC](https://discuss.ocaml.org/t/announcing-sek-an-efficient-implementation-of-sequences/5442/5 "2020-04-05T09:34:14Z")
I think it really is a sequence library in the sense that in maintains an in-order sequence of items, and sequences can be joined/split efficiently. It also provides logarithmic random access, but this is probably not competitive with fixed-size arrays. It would be comparable to “persistent vector” libraries, ropes, finger trees, etc. The fact that the authors expose a Stack/Queue interface suggests that it has also been tuned to perform reasonably well in this case. It does not provide any delayed computation of items, so in that regard it is not comparable to Sequence/Seq. @charguer has designed similar datastructures in the past to represent the work-queues of concurrent workers (you want at least a fast “push” to add a new task and, when doing work-stealing, having a fast “split” is convenient). See [Theory and Practice of Chunked Sequences](https://www.chargueraud.org/research/2014/chunkedseq/chunkedseq.pdf), Umut Acar, Arthur Charguéraud, Mike Rainey, 2014, and [A Work-Efficient Algorithm for Parallel Unordered Depth-First Search](https://www.chargueraud.org/research/2015/pdfs/pdfs_sc15.pdf). As far as I know, the OCaml implementation just released has not been tested/benchmarked for parallel algorithms. I would be curious to see an experiment of parallel graph traversal with this structure and Multicore-OCaml.