From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail2-relais-roc.national.inria.fr (mail2-relais-roc.national.inria.fr [192.134.164.83]) by c5ff346549e7 (Postfix) with ESMTPS id 6C2FC5D5 for ; Sat, 4 Apr 2020 13:18:51 +0000 (UTC) X-IronPort-AV: E=Sophos;i="5.72,343,1580770800"; d="scan'208,217";a="443810107" Received: from sympa.inria.fr ([193.51.193.213]) by mail2-relais-roc.national.inria.fr with ESMTP; 04 Apr 2020 15:18:50 +0200 Received: by sympa.inria.fr (Postfix, from userid 20132) id 424077F486; Sat, 4 Apr 2020 15:18:50 +0200 (CEST) Received: from mail3-relais-sop.national.inria.fr (mail3-relais-sop.national.inria.fr [192.134.164.104]) by sympa.inria.fr (Postfix) with ESMTPS id 377487F42C for ; Sat, 4 Apr 2020 15:18:47 +0200 (CEST) Authentication-Results: mail3-smtp-sop.national.inria.fr; spf=None smtp.pra=gabriel.scherer@gmail.com; spf=Pass smtp.mailfrom=gabriel.scherer@gmail.com; spf=None smtp.helo=postmaster@mail-qk1-f181.google.com IronPort-PHdr: =?us-ascii?q?9a23=3AApTfFxfy1dvtoNbz86q9XzqHlGMj4u6mDksu8pMi?= =?us-ascii?q?zoh2WeGdxc6/bB7h7PlgxGXEQZ/co6odzbGJ4+a9ASQp2tWojjMrSNR0TRgLiM?= =?us-ascii?q?EbzUQLIfWuLgnFFsPsdDEwB89YVVVorDmROElRH9viNRWJ+iXhpRZbIBj0NBJ0?= =?us-ascii?q?K+LpAcaSyp3vj6Hhs6HUNitSjTwyZrJpGy2xsRnQu9Ne1YV4I6A6zRrS5GNPZ/?= =?us-ascii?q?hXyHlAJFSJnh+66N3muNZK6ThQpugW3M5JS6rn/r4xULAQWD08L2Ao/uXgtRDZ?= =?us-ascii?q?QhaC/HIBXiMRiBUeUCbf6xSvcZ77qCr3sqJG0ymXJ8DsBeQ7UD647qpvDgTjiC?= =?us-ascii?q?odOiQR/2Tei8g2h6Ve9kHy7ydjypLZNdnGfMF1ebnQKJZDHTIYD5RhEhdZC4b5?= =?us-ascii?q?VLMhSu8IPOJWtY74/gJcoh63BA3qD+TqmGYR2i3GmJYi2uFkKjnomRQ6FotX4n?= =?us-ascii?q?vRpdTxcqwVVLLtlfSa/XD4d/pTnAzFxs3IfxQm+6/eWLtxdY/IyhBqGVqV1xOf?= =?us-ascii?q?rovqOz7T3eMI4TCW?= X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: =?us-ascii?q?A0AyBgDQiIheh7XeVdFmFgcBAQEJAREFB?= =?us-ascii?q?QGBe4JRRIEHKoQbgRyCXYsEghGKdJBTCgEDAQwjDAQBAYFQgnQCgkYcBwEENBM?= =?us-ascii?q?CEAEBBQEBAQIBAgMEARMBAQEIDQkIKYVdDII7BQEjAQaDBgEBAQIBEhEdARsdA?= =?us-ascii?q?QMBCwYFCzcCAiIBEQEFARwGAQkJCBqDBAGCSgEDDiAPoimBBD2LKIEVBQEXgwA?= =?us-ascii?q?FgURBgn0KGScNYgOBMwIHEoEmjDEPgUw/gUeCLC4+gX5eCwMBAoRzgl4EoTaOa?= =?us-ascii?q?HoHgkB8BIZwjzkdgkyBBJgwizyDd4FSh1KTGA8jgRwqgXkzGiNQMYI4CUcYDY4?= =?us-ascii?q?dGoNZgT6JGUIwAo4KgVIBAQ?= X-IPAS-Result: =?us-ascii?q?A0AyBgDQiIheh7XeVdFmFgcBAQEJAREFBQGBe4JRRIEHKoQ?= =?us-ascii?q?bgRyCXYsEghGKdJBTCgEDAQwjDAQBAYFQgnQCgkYcBwEENBMCEAEBBQEBAQIBA?= =?us-ascii?q?gMEARMBAQEIDQkIKYVdDII7BQEjAQaDBgEBAQIBEhEdARsdAQMBCwYFCzcCAiI?= =?us-ascii?q?BEQEFARwGAQkJCBqDBAGCSgEDDiAPoimBBD2LKIEVBQEXgwAFgURBgn0KGScNY?= =?us-ascii?q?gOBMwIHEoEmjDEPgUw/gUeCLC4+gX5eCwMBAoRzgl4EoTaOaHoHgkB8BIZwjzk?= =?us-ascii?q?dgkyBBJgwizyDd4FSh1KTGA8jgRwqgXkzGiNQMYI4CUcYDY4dGoNZgT6JGUIwA?= =?us-ascii?q?o4KgVIBAQ?= X-IronPort-AV: E=Sophos;i="5.72,343,1580770800"; d="scan'208,217";a="344917111" X-MGA-submission: =?us-ascii?q?MDGBTg+z81fwYerLjIQznxz+RLAuOIIcnoIDFQ?= =?us-ascii?q?98kc7RaxxXsJWDuNMTd8vC8kZcGLD51ZELUo8BLfsi/VroF4DrISOT5l?= =?us-ascii?q?aFjQcpCs2t9fujK5B7M3r3Df8kFy6/lywcRjTI/4ScVGrISPBFx0vN6U?= =?us-ascii?q?rKBbsWLvAASHghmJUEj4CbOw=3D=3D?= Received: from mail-qk1-f181.google.com ([209.85.222.181]) by mail3-smtp-sop.national.inria.fr with ESMTP/TLS/AES256-GCM-SHA384; 04 Apr 2020 15:18:14 +0200 Received: by mail-qk1-f181.google.com with SMTP id u4so11108281qkj.13; Sat, 04 Apr 2020 06:18:14 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=GJY8MlLyu4iAAgLWT/F7CYC6Urik6uETpbxVhN6k0lI=; b=biaTVEH79e56io1ETtjYgu8vmgia7l09gkAm4QL0xrDywBIZhQr6WoRUorLeGETdr6 8Y3hl9Vs4Sh2mGYnRFuv49dar6OUqRKABoCLcHN3wMNqLeJK1vAQtdps9jzhXC+ceXZx G19cgKEhAiQuILuTZMbP2OYwjuSh2FNTTwGHXzpRFCPULdoDrlJexyNpbtNbQH7jmOuR s2QZXICClstU75RBRJRGzRk9wbdrt4F+UQP8p5pJtRgcZe6oH4tDU6kpeXUa0qiHACuM sV0uYw7TwCnyivXCphsb1wNYRcaZu9p8pFDKdfyoYOiYwQC/1PhE0ozXy8RY27WLrVs2 h5Pg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=GJY8MlLyu4iAAgLWT/F7CYC6Urik6uETpbxVhN6k0lI=; b=XKcxO6gfnPv6kex1UYLWyEWtWpPv2Mrb05hNdXLPBTmrt5JEyzxgPsShn4BE9U4e2b MrhRoWwMH/FQoVCviXGzYqDLWHIjqL3Bn7QtVPysud+Q0H/miJL0MQ3tjUNxfDbA9zhQ ogXT+6H2WvJG/G6J/BBQh3KKqdU9uztv555uy03QEz9XKFXz3J5jJS1VifnekgM1eZHW 8vs0uAYuobscPIBy7T7y/6TKwYlXV/h1Tr3R0/2V3B0r8jCavbAok5GSyhwP2ZcZ7lJ0 gtUvMA99NM2SqikLjNpB4vToP4lMnxiD9YLn9OYEqDxmiYtbNvP5I5lwatMxZbA9we2F HzEQ== X-Gm-Message-State: AGi0Pubul3btx0cjzatIqKcQd/OMw3QzeWAKD5FYcxUUHhbbm+nCZVdC nNbCPSEb+N1sIaz+hJhmwbOBBxoopPbjzS1HMYl/2NNrjL1L1Q== X-Google-Smtp-Source: APiQypIbG4hddmpCdRV+OwY9bJR6LuGiVe9U7SpsuP9cfXKgRGFLlrgWbamIvQkpawbDB4ooBm3q2xA2KUze9BgtKjg= X-Received: by 2002:ae9:dfc2:: with SMTP id t185mr13743943qkf.20.1586006292689; Sat, 04 Apr 2020 06:18:12 -0700 (PDT) MIME-Version: 1.0 References: In-Reply-To: From: Gabriel Scherer Date: Sat, 4 Apr 2020 15:17:36 +0200 Message-ID: To: =?UTF-8?Q?Fran=C3=A7ois_Pottier?= , =?UTF-8?Q?Arthur_Chargu=C3=A9raud?= Cc: caml users Content-Type: multipart/alternative; boundary="000000000000aff7a305a276dda8" Subject: Re: [Caml-list] Announcing Sek, an efficient implementation of sequences Reply-To: Gabriel Scherer X-Loop: caml-list@inria.fr X-Sequence: 18080 Errors-to: caml-list-owner@inria.fr Precedence: list Precedence: bulk Sender: caml-list-request@inria.fr X-no-archive: yes List-Id: List-Archive: List-Help: List-Owner: List-Post: List-Subscribe: List-Unsubscribe: --000000000000aff7a305a276dda8 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Looks very nice, thanks! Some feedback from reading the documentation. 1. gitlab.inria.fr makes it difficult for non-INRIA people to contribute (they cannot open a pull/merge request). It is a mistake to use it for publicly-distributed software. (In theory it would be fine if you never needed outside help, if you were the perfect maintainer whose opam, dune and whatever stuff is always up-to-date. In practice no one is.) 2. > Instead, one should first build an ephemeral sequence through a series of ephemeral push operations, > then convert it to a persistent sequence. This way, the construction cost is only *O(n+K)*. I would guess that it is O(T + K), or n has to be defined first. 3. The list of function complexities is hard to digest. Would it be possible to have, in addition or replacement, the complexity of each operation mentioned in the documentation of the operation? (This makes it easy to lookup the complexity of a given function) 4. I had never seen the trick of single-value functor parameters used as labelled arguments. It is interesting. Another approach would be to have a single Parameters module with one value for each runtime parameter. This would be syntactically lighter, and I cannot think of any downside right now. (One minor upside in general is that one can add new runtime parameters without changing the functor abstraction code / formal parameter list.) 5. > Furthermore, in a series of push operations, starting from an empty sequence, the amortized cost of one push operation is only *O(1)*. If I undestand, this sentence is in tension with the sentence mentioning a quadratic behavior up to T. Both are true, but they give contradictory advise on how to write your code. Maybe you could recall here that one should only take advantage of this property for sequences that are expected to be much larger than T? (In general there is little guidance in the documentation on how to set T, whereas there is a number given for K. For example, if I don't know the data size in advance, is it reasonable to use T=3D2? Maybe you could benchmark a good choice of T for some workload depending on the average size of your sequences (N=3D10^2, 10^4, 10^6), and let us know. 6. The natural mental model for snapshot_and_clear is a transfer of unique ownership (into shareable ownership). If this is the model I am using in my program, then performing any operation after the snapshot would be a programming mistake. Your _and_clear specification avoids any undefined or surprising/undocumented behavior in the case that happens, but it may still hide my programming mistake. Could there be a control-transfer version that "poisons" the ephemeral structure, so that any later operation on it raises an exception? On Sat, Apr 4, 2020 at 12:12 PM Fran=C3=A7ois Pottier wrote: > > Fellow OCaml users, > > We are pleased to announce the first release of Sek, an OCaml library tha= t > 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 > > opam update && opam install sek > > Documentation is at > > http://cambium.inria.fr/~fpottier/sek/doc/sek/Sek/index.html > > Feedback is welcome! > > -- > Arthur Chargu=C3=A9raud > Fran=C3=A7ois Pottier > with contributions by =C3=89milie Guermeur > On Sat, Apr 4, 2020 at 12:12 PM Fran=C3=A7ois Pottier wrote: > > Fellow OCaml users, > > We are pleased to announce the first release of Sek, an OCaml library tha= t > 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 > > opam update && opam install sek > > Documentation is at > > http://cambium.inria.fr/~fpottier/sek/doc/sek/Sek/index.html > > Feedback is welcome! > > -- > Arthur Chargu=C3=A9raud > Fran=C3=A7ois Pottier > with contributions by =C3=89milie Guermeur > --000000000000aff7a305a276dda8 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
Looks very nice, thanks! Some feedback from reading t= he documentation.

1. gitlab.inria.fr makes it difficult for non-INRIA people to = contribute (they cannot open a pull/merge request). It is a mistake to use = it for publicly-distributed software. (In theory it would be fine if you ne= ver needed outside help, if you were the perfect maintainer whose opam, dun= e and whatever stuff is always up-to-date. In practice no one is.)

2.
> Instead, one should = first build an ephemeral sequence through a series of ephemeral push<= /code> operations,
> then convert it to a persistent sequence.= This way, the construction cost is only O(n+K).
I would g= uess that it is O(T + K), or n has to be defined first.

<= /div>
3. The list of function complexities is hard to digest. Would it = be possible to have, in addition or replacement, the complexity of each ope= ration mentioned in the documentation of the operation? (This makes it easy= to lookup the complexity of a given function)

4. = I had never seen the trick of single-value functor parameters used as label= led arguments. It is interesting. Another approach would be to have a singl= e Parameters module with one value for each runtime parameter. This would b= e syntactically lighter, and I cannot think of any downside right now. (One= minor upside in general is that one can add new runtime parameters without= changing the functor abstraction code / formal parameter list.)
=
5.
> Furthermore, in a series of push operation= s, starting from an empty sequence, the amortized cost of one push operatio= n is only O(1).
If I undestand, this sentence is in tensio= n with the sentence mentioning a quadratic behavior up to T. Both are true,= but they give
contradictory advise on how to write your code. Ma= ybe you could recall here that one should only take advantage of this prope= rty for sequences that are expected to be much larger than T?
(In general there is little guidance in the documentation on ho= w to set T, whereas there is a number given for K. For example, if I don= 9;t know the data size in advance, is it reasonable to use T=3D2? Maybe you= could benchmark a good choice of T for some workload depending on the aver= age size of your sequences (N=3D10^2, 10^4, 10^6), and let us know.

6. The natural mental model for snapshot_and_clear is= a transfer of unique ownership (into shareable ownership). If this is the = model I am using in my program, then performing any operation after the sna= pshot would be a programming mistake. Your _and_clear specification avoids = any undefined or surprising/undocumented behavior in the case that happens,= but it may still hide my programming mistake. Could there be a control-tra= nsfer version that "poisons" the ephemeral structure, so that any= later operation on it raises an exception?

On Sat, Apr 4, 2020 = at 12:12 PM Fran=C3=A7ois Pottier <francois.pottier@inria.fr> wrote:

Fellow OCaml users,

We are pleased to announce the first release of Sek, an OCaml library that<= br> 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.<= br> 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,<= br> 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

=C2=A0 =C2=A0opam update && opam install sek

Documentation is at

=C2=A0 =C2=A0http://cambium.inria.fr/~fp= ottier/sek/doc/sek/Sek/index.html

Feedback is welcome!

--
Arthur Chargu=C3=A9raud
Fran=C3=A7ois Pottier
with contributions by =C3=89milie Guermeur

On Sat, Apr 4, 2020 at 12:12 PM Fran=C3=A7ois Pott= ier <francois.pottier@inria= .fr> wrote:

Fellow OCaml users,

We are pleased to announce the first release of Sek, an OCaml library that<= br> 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.<= br> 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,<= br> 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

=C2=A0 =C2=A0opam update && opam install sek

Documentation is at

=C2=A0 =C2=A0http://cambium.inria.fr/~fp= ottier/sek/doc/sek/Sek/index.html

Feedback is welcome!

--
Arthur Chargu=C3=A9raud
Fran=C3=A7ois Pottier
with contributions by =C3=89milie Guermeur
--000000000000aff7a305a276dda8--