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 AD9165D4 for ; Thu, 20 Dec 2018 18:45:01 +0000 (UTC) X-IronPort-AV: E=Sophos;i="5.56,378,1539640800"; d="scan'208,217";a="361303777" Received: from sympa.inria.fr ([193.51.193.213]) by mail2-relais-roc.national.inria.fr with ESMTP; 20 Dec 2018 19:45:00 +0100 Received: by sympa.inria.fr (Postfix, from userid 20132) id A772F82566; Thu, 20 Dec 2018 19:45:00 +0100 (CET) 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 C4F0C824CF for ; Thu, 20 Dec 2018 19:44:53 +0100 (CET) Authentication-Results: mail3-smtp-sop.national.inria.fr; spf=None smtp.pra=lindsay.errington@gmail.com; spf=Pass smtp.mailfrom=lindsay.errington@gmail.com; spf=None smtp.helo=postmaster@mail-yw1-f49.google.com IronPort-PHdr: =?us-ascii?q?9a23=3AeWIj4RI/Q70VGUPbCtmcpTZWNBhigK39O0sv0rFi?= =?us-ascii?q?tYgRLPnxwZ3uMQTl6Ol3ixeRBMOHs6IC07KempujcFRI2YyGvnEGfc4EfD4+ou?= =?us-ascii?q?JSoTYdBtWYA1bwNv/gYn9yNs1DUFh44yPzahANS47xaFLIv3K98yMZFAnhOgpp?= =?us-ascii?q?POT1HZPZg9iq2+yo9JDffwZFiCChbb9uMR67sRjfus4KjIV4N60/0AHJonxGe+?= =?us-ascii?q?RXwWNnO1eelAvi68mz4ZBu7T1et+ou+MBcX6r6eb84TaFDAzQ9L281/szrugLd?= =?us-ascii?q?QgaJ+3ART38ZkhtMAwjC8RH6QpL8uTb0u+ZhxCWXO9D9QLYpUjqg8qhrUgflhy?= =?us-ascii?q?gHOTA382/Zl9J+g75ArR27uxBy2ZTZbJ2JOPd8eK7WYNMURXBGXsZUTyFPBIK8?= =?us-ascii?q?b40SAOoaJ+lZr5T2qVQUrRukBAmsAuzvyiNPhn/wwKY31OAhEQDA3AM9BNIBqn?= =?us-ascii?q?TVoM/rO6cIS+C1za/IzTrfb/NR3zfw84fIchU7rvGNWbJ8a9beyU4qFw7ciFib?= =?us-ascii?q?tI/rPyuN2+gTr2SW6/BsWOGvhmI9tg18oyWjyt0jh4TNgI8e10rK+j9jwIkvIN?= =?us-ascii?q?21UE57bsCgEJtXryyaMpF5QsImQ21xuCc7xKAKtYe1fCUFzJkr3RHfa/uAc4iH?= =?us-ascii?q?5hLsSvydLit/hHJgYL6/hhCy/la8yuDkSMW4zFJHojBGn9TMrHwByh3e5tWdRv?= =?us-ascii?q?Zy+kqtwTOP2BrS6uFAL0A0j63bK5s5z740l5oTt1nMHjTsl0T2lqOZaF8k+vKp?= =?us-ascii?q?6+ThbbXmupicN4lvhwHxN6QhgM2/AeAiPgcSWGib/Pyw1Kf/8k3hXLVKkvo2n7?= =?us-ascii?q?HFv5/AIMQbore1AwtU0oY49xayFCym0dQdnXkfNl1JYhOHj47zO1HPOv/0F/m/?= =?us-ascii?q?g07/2AtskrrNN7jlR5HMNWTrkbH7fL875VQWgF44xNVbopZVEa0pIfTpW0a3us?= =?us-ascii?q?aOXTEjNAnh5+fhBM50x8szQ3iOBKCFN6Wa5VuJ4O40KvjKaZUPuTDyN/8jz/Hr?= =?us-ascii?q?hH4931QaeP/6jtMsdHmkE6E+cA2ian32j4JZSDZYjk8FVOXvzWa6f3tWbne2Ub?= =?us-ascii?q?g742hiWo2jBIbHAIuqhe7YhXvpLthtfmlDT2u0PzLwbYzdAqUDbSuTJolqlTlW?= =?us-ascii?q?DeH8Gb9k7gmnsUrB85QiLufQ/XdF55fq1dww9vKK0B9upHp7CMOS12zLRGZxzD?= =?us-ascii?q?sF?= X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: =?us-ascii?q?A0AsEQDe4RtchzGhVdFlHAEBAR8EAQEFA?= =?us-ascii?q?QGBToIngUMng31iO4JekBmLM2+HbYdWDQWHVRoHAQQ0EgEDAQECAQEBAQETAQE?= =?us-ascii?q?BCA0JCCkjAQuCNiKDDh0BGx4DEgkBBjcCJAERAQUBFgyDNYFpAQMVmGODHzyLG?= =?us-ascii?q?YESBQEXgncFhDYKGScNXoE3AgYSjC2BVz+MLIJXApBbkGIHAoIlBI88GJFdiU2?= =?us-ascii?q?QMQ8hgTyBd00jgQGCO4I1g1OKdCEwjmcBAQ?= X-IPAS-Result: =?us-ascii?q?A0AsEQDe4RtchzGhVdFlHAEBAR8EAQEFAQGBToIngUMng31?= =?us-ascii?q?iO4JekBmLM2+HbYdWDQWHVRoHAQQ0EgEDAQECAQEBAQETAQEBCA0JCCkjAQuCN?= =?us-ascii?q?iKDDh0BGx4DEgkBBjcCJAERAQUBFgyDNYFpAQMVmGODHzyLGYESBQEXgncFhDY?= =?us-ascii?q?KGScNXoE3AgYSjC2BVz+MLIJXApBbkGIHAoIlBI88GJFdiU2QMQ8hgTyBd00jg?= =?us-ascii?q?QGCO4I1g1OKdCEwjmcBAQ?= X-IronPort-AV: E=Sophos;i="5.56,378,1539640800"; d="scan'208,217";a="289775386" Received: from mail-yw1-f49.google.com ([209.85.161.49]) by mail3-smtp-sop.national.inria.fr with ESMTP/TLS/AES128-GCM-SHA256; 20 Dec 2018 19:44:52 +0100 Received: by mail-yw1-f49.google.com with SMTP id j6so1078614ywj.6 for ; Thu, 20 Dec 2018 10:44:52 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:from:date:message-id:subject:to; bh=lFy4psM5AHF2xH+GLVZu3YRo2g2QVDXi+nGh6Jat4XQ=; b=QfbfGV77az0MfRdAk+4ZBoo7MTcug7/KHLrLT1Q0bU+d464oECaZZ4IxPvFEOQ1otJ vcrH0qZs91qlih1s9pzFiTxyJet36P7aO+OiayNicxKhX6tDGwxlTdEZlvogeLXbzrMQ ft7/sZpcCkLr2o4JOYUvalPMhLIle50FoGyvWNDLpjrYbpS0Z7Y5aJ9gMdLV6lY5qoBm Kz5NIAFeOPYk27i88lhV4dR0X3970DeBnovDL05p9ENjfyhBmriLIyAW2hwNwrsnCtxA 2yuBq+U2hVsvbTXHES7nfa8C+ATL0d3Wlgp+zoeVVUxM0Aa9+7AKeqvz7y1bKCVz6P5T M16g== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:from:date:message-id:subject:to; bh=lFy4psM5AHF2xH+GLVZu3YRo2g2QVDXi+nGh6Jat4XQ=; b=YzEO+qQPg+aoLirpOQ+K+Y138qauHKMrev+HCZb6faYkBXOTaX1Fca49Ani/tjeigX m6jAbLt3j7RXyDJh5CcdlMoqMNaWOeCGEBiOkNJe9QeaM/Qhw8J+Yl7kuy3m4Tv8sscE Y5jgl74tDQaoxi1QbZVhnPJGSKW3KEBExswsnE+irj1utRp4jKxvJ6aEkkZF3PNKSxIX H041HHp/GN5r0no6+RfgW1XysybPx55Z2NvvfMsylYV4QdX5wUeXdAazn0xQonNTmF4O HWhqxQUQ2u9c2AfN0DoonrKNAOwFPz8Su3l9mSFZfRLsOzhYaRWMtQ5fHxGtn/KvYN13 q4xw== X-Gm-Message-State: AA+aEWbxy3xVStffkuelqmsFcNV65Orcg5at70GNZtLkP+n++put6VNL i+Ch95P0/uGja6hCWGFt4qitAP9laurW4Sgks7+ELtMb X-Google-Smtp-Source: AFSGD/UjI4i12SE70n1YhEdU1oDGq+ENABu8/DBaPQn50NG9JYu2HiLHfoVTv0nhhRDc3ibF+ts7sLgE3h2lz+jo1ME= X-Received: by 2002:a81:34d3:: with SMTP id b202mr27484907ywa.241.1545331490828; Thu, 20 Dec 2018 10:44:50 -0800 (PST) MIME-Version: 1.0 From: Lindsay Errington Date: Thu, 20 Dec 2018 10:44:41 -0800 Message-ID: To: "caml-list@inria.fr" Content-Type: multipart/alternative; boundary="00000000000092373e057d788636" Subject: [Caml-list] weak functional maps and ephemerons Reply-To: Lindsay Errington X-Loop: caml-list@inria.fr X-Sequence: 17257 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: --00000000000092373e057d788636 Content-Type: text/plain; charset="UTF-8" As mentioned in my previous post, I'd like to have weak functional maps. Keeping it simple, suppose the maps are implemented as binary search trees of key/value pairs where pairs are wrapped in an ephemeron: module Eph = Ephemeron.K1 type key = ... (* something boxed and ordered *) type 'a bst = | Empty | Node of {left : 'a bst; pair : (key,'a) Eph.t; right : 'a bst} Cheating a little with pattern matching, if {left; pair=(Some k, Some v); right} is an entry in a tree and I subsequently drop all references to k, then my understanding is that following gc, both options will become None. If I then encounter that node when looking for some k', I'm forced to merge the left and right subtrees before continuing. The question is, why does gc clobber the key in the ephemeron? Why not provide the key when the ephemeron is created and collect the key when the ephemeron is collected? For the above use-case, it would mean that one could still search the tree and defer cleaning up the bst until later. Lindsay -- Caml-list mailing list. Subscription management and archives: https://sympa.inria.fr/sympa/arc/caml-list https://inbox.ocaml.org/caml-list Forum: https://discuss.ocaml.org/ Bug reports: http://caml.inria.fr/bin/caml-bugs --00000000000092373e057d788636 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
As mentioned in my previous post, I'd like to hav= e weak functional maps. Keeping it simple, suppose the maps are implemented= as binary search trees of key/value pairs where pairs are wrapped in an ep= hemeron:

module Eph =3D Ephemeron.K1
typ= e key =3D ... (* something boxed and ordered *)
type 'a bst = =3D
=C2=A0 | Empty
=C2=A0 | Node of {left : 'a bst;= pair : (key,'a) Eph.t; right : 'a bst}

Ch= eating a little with pattern matching, if {left; pair=3D(Some k, Some v); r= ight} is an entry in a tree and I subsequently drop all references to k, th= en my understanding is that following gc, both options will become None. If= I then encounter that node when looking for some k', I'm forced to= merge the left and right subtrees before continuing.=C2=A0

<= /div>
The question is, why does gc clobber the key in the ephemeron? Wh= y not provide the key when the ephemeron is created and collect the key whe= n the ephemeron is collected? For the above use-case, it would mean that on= e could still search the tree and defer cleaning up the bst until later.

Lindsay
--00000000000092373e057d788636--