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 2A3341E6 for ; Thu, 29 Mar 2018 20:52:58 +0000 (UTC) X-IronPort-AV: E=Sophos;i="5.48,378,1517871600"; d="scan'208";a="320621777" Received: from sympa.inria.fr ([193.51.193.213]) by mail2-relais-roc.national.inria.fr with ESMTP; 29 Mar 2018 22:52:56 +0200 Received: by sympa.inria.fr (Postfix, from userid 20132) id B13A68243F; Thu, 29 Mar 2018 22:52:55 +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 A63D68239C for ; Thu, 29 Mar 2018 22:52:45 +0200 (CEST) Authentication-Results: mail3-smtp-sop.national.inria.fr; spf=None smtp.pra=armael.gueneau@ens-lyon.fr; spf=Neutral smtp.mailfrom=armael.gueneau@ens-lyon.fr; spf=None smtp.helo=postmaster@labbe.ens-lyon.fr IronPort-PHdr: =?us-ascii?q?9a23=3AEzM4zBdAa/ac1RfowFl4pux8lGMj4u6mDksu8pMi?= =?us-ascii?q?zoh2WeGdxcuzYR7h7PlgxGXEQZ/co6odzbaO6Oa4ASQp2tWoiDg6aptCVhsI24?= =?us-ascii?q?09vjcLJ4q7M3D9N+PgdCcgHc5PBxdP9nC/NlVJSo6lPwWB6nK94iQPFRrhKAF7?= =?us-ascii?q?Ovr6GpLIj8Swyuu+54Dfbx9HiTahb75+Ngm6oRnMvcQKnIVuLbo8xAHUqXVSYe?= =?us-ascii?q?RWwm1oJVOXnxni48q74YBu/SdNtf8/7sBMSar1cbg2QrxeFzQmLns65Nb3uhnZ?= =?us-ascii?q?TAuA/WUTX2MLmRdVGQfF7RX6XpDssivms+d2xSeXMdHqQb0yRD+v9LlgRgP2hy?= =?us-ascii?q?gbNj456GDXhdJ2jKJHuxKquhhzz5fJbI2JKPZye6XQds4YS2VcRMZcTzJPDIOh?= =?us-ascii?q?YYUMAeQOM+lXoJXyqVYVsRuzBhOhCP/zxjJGhHL727Ax3eQ7EQHB2QwtB84DsG?= =?us-ascii?q?7RrNrvKKASVfi6wqjVzTLZafNZxy3y6JXVeR0mu/6MR7dwftDPxkkrDQ/FgUiQ?= =?us-ascii?q?ppLjPzyLzOsNrnOW4PRmVeK0kmInrwFwoj+pxss2hInJnJsYx1bZ/it62IY4Pc?= =?us-ascii?q?C0RUFnbdK+EpZdtTuWO5Z3T84gWW1kpjg2xqMetZO4fyUG0okryhrCZ/CdboSF?= =?us-ascii?q?4wzvWPyMLTp7hn9ofq+0iQyo/ki60OL8U9G50FZUoSpBldnBrnQN2AbI5cecVP?= =?us-ascii?q?Rx5Fmu2TCU1wzK7uFFIUc0lazBJ54v2L48jpsTsULdES/qgEj6kaCbelk+9uWq?= =?us-ascii?q?6enreKjqq56eOoNulA3yLLoiltS6AesiMwgOW2ab+f671L3m5UD2Wq9Kjvgsna?= =?us-ascii?q?bHtJDWP8sbprOnDA9TzIks8Qu/Aiy439QehnkLNVZFeRKAj4jvIV3OLur4Ae+l?= =?us-ascii?q?g1uwiDdr2+zGPrr5D5rRNHfDlbPhca95605d0woz0ctS54lUC7EEOPL8QFX9tN?= =?us-ascii?q?3eDh8jMgy72fzrCNtn1tBWZWXaCaacNObWsESUzuMpOeiFIoEP6xjnLP1wzuTr?= =?us-ascii?q?hPw9rnAA/K+k1IZfPHmiG/1rJwOWfHfqj94cOWoMpU86XevszlOYB20AL02uVr?= =?us-ascii?q?4xs2loQLmtCp3OE8X02OTYjXWLW6ZOb2UDMWiiVHLhdoGKQfAJMXnAL8l61zgV?= =?us-ascii?q?Ur7nRZVzj0jy5j+/8KJuK6/vwgNdrYjqjYMn6uvI0BUj8joyAd7PizjQHVExpX?= =?us-ascii?q?sBQnoN5I46oUF5zQ7Sg6xxifZVU9FV/LZNQwA8c5DGnbR3?= X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: =?us-ascii?q?A0AVAQC8Ub1ah96nTYxdGgEBAQEBAgEBA?= =?us-ascii?q?QEIAQEBAYQmbIQElQKCA4EAjWWFAIFmC4UEhBwZBQczFQECAQEBAQEBAQEBEgE?= =?us-ascii?q?BAQoLCQgoL4I4JAGCQTEPAUY1AiYCbAgBATKEVwStY4IchFWDRiWCKoEIhDyCG?= =?us-ascii?q?oITgS6CNQGEY4EEgjSCVAKGOpB5CG9FjHKHQoR2j3qBIwIygXR0S4JEgi2OIZA?= =?us-ascii?q?0AQE?= X-IPAS-Result: =?us-ascii?q?A0AVAQC8Ub1ah96nTYxdGgEBAQEBAgEBAQEIAQEBAYQmbIQ?= =?us-ascii?q?ElQKCA4EAjWWFAIFmC4UEhBwZBQczFQECAQEBAQEBAQEBEgEBAQoLCQgoL4I4J?= =?us-ascii?q?AGCQTEPAUY1AiYCbAgBATKEVwStY4IchFWDRiWCKoEIhDyCGoITgS6CNQGEY4E?= =?us-ascii?q?EgjSCVAKGOpB5CG9FjHKHQoR2j3qBIwIygXR0S4JEgi2OIZA0AQE?= X-IronPort-AV: E=Sophos;i="5.48,378,1517871600"; d="scan'208";a="260332246" Received: from labbe.ens-lyon.fr ([140.77.167.222]) by mail3-smtp-sop.national.inria.fr with ESMTP; 29 Mar 2018 22:52:29 +0200 Received: from localhost (localhost [127.0.0.1]) by labbe.ens-lyon.fr (Postfix) with ESMTP id 6CD61320C35; Thu, 29 Mar 2018 22:52:29 +0200 (CEST) X-Virus-Scanned: by amavisd-new-2.10.1 (20141025) (Debian) at ens-lyon.fr Received: from labbe.ens-lyon.fr ([127.0.0.1]) by localhost (labbe.ens-lyon.fr [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id UfehgLhoEqfG; Thu, 29 Mar 2018 22:52:28 +0200 (CEST) Received: from [192.168.0.91] (unknown [88.191.162.187]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (Client did not present a certificate) by labbe.ens-lyon.fr (Postfix) with ESMTPSA id D3C50320B05; Thu, 29 Mar 2018 22:52:28 +0200 (CEST) To: caml-list@inria.fr Cc: =?UTF-8?Q?Arthur_Chargu=c3=a9raud?= From: =?UTF-8?Q?Arma=c3=abl_Gu=c3=a9neau?= Message-ID: Date: Thu, 29 Mar 2018 22:49:20 +0200 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101 Thunderbird/52.5.2 MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Language: en-US Content-Transfer-Encoding: 8bit Subject: [Caml-list] Hashtbl and shrinking Reply-To: =?UTF-8?Q?Arma=c3=abl_Gu=c3=a9neau?= X-Loop: caml-list@inria.fr X-Sequence: 16759 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: Dear caml-list, It happens Arthur Charguéraud and myself were looking this afternoon at the implementation of the Hashtbl module, provided in our beloved OCaml standard library. We noticed there is no shrinking implemented, that would typically happen when the number of elements goes under a certain threshold compared to the size of the underlying array. This yields a space complexity that we think may not be what people might expect: an almost empty hashtable will consume as much memory as when it was full. The time complexity might also be worse than expected, because the GC will still spend time scanning the whole array even when there are only a few elements. What do people here think about this? If we submitted a patch implementing shrinking for Hashtbl, could it be detrimental for some specific workloads? — Armaël -- Caml-list mailing list. Subscription management and archives: https://sympa.inria.fr/sympa/arc/caml-list Beginner's list: http://groups.yahoo.com/group/ocaml_beginners Bug reports: http://caml.inria.fr/bin/caml-bugs