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 0613D5D5 for ; Mon, 2 Apr 2018 00:34:28 +0000 (UTC) X-IronPort-AV: E=Sophos;i="5.48,393,1517871600"; d="scan'208";a="320910889" Received: from sympa.inria.fr ([193.51.193.213]) by mail2-relais-roc.national.inria.fr with ESMTP; 02 Apr 2018 02:34:27 +0200 Received: by sympa.inria.fr (Postfix, from userid 20132) id 4660082438; Mon, 2 Apr 2018 02:34:27 +0200 (CEST) Received: from mail2-relais-roc.national.inria.fr (mail2-relais-roc.national.inria.fr [192.134.164.83]) by sympa.inria.fr (Postfix) with ESMTPS id 4EF278239C for ; Mon, 2 Apr 2018 02:34:17 +0200 (CEST) Authentication-Results: mail2-smtp-roc.national.inria.fr; spf=None smtp.pra=berenger@bioreg.kyushu-u.ac.jp; spf=None smtp.mailfrom=berenger@bioreg.kyushu-u.ac.jp; spf=None smtp.helo=postmaster@h4.hosting4.cc.kyushu-u.ac.jp IronPort-PHdr: =?us-ascii?q?9a23=3AD3NCRhDK8evgEEDrz0oAUyQJP3N1i/DPJgcQr6Af?= =?us-ascii?q?oPdwSPvypMbcNUDSrc9gkEXOFd2Cra4c0KyO6+jJYi8p2d65qncMcZhBBVcuqP?= =?us-ascii?q?49uEgeOvODElDxN/XwbiY3T4xoXV5h+GynYwAOQJ6tL1LdrWev4jEMBx7xKRR6?= =?us-ascii?q?JvjvGo7Vks+7y/2+94fcbglUijexe69+IAmrpgjNq8cahpdvJLwswRXTuHtIfO?= =?us-ascii?q?pWxWJsJV2Nmhv3+9m98p1+/SlOovwt78FPX7n0cKQ+VrxYES8pM3sp683xtBnM?= =?us-ascii?q?VhWA630BWWgLiBVIAgzF7BbnXpfttybxq+Rw1DWGMcDwULs5Xymp4aV2Rx/ykC?= =?us-ascii?q?oJKiA38G/XhMJzgqxUrh2uqB5jzIDbe4yVKPlzc7nBcd8GS2dMXMBcXDFBDIOm?= =?us-ascii?q?aIsPCvIMM+ZCr4bnoVsBsRy+BQi3BOjy1zJGiWP406Ii3eogHg/IwBErEtUVv3?= =?us-ascii?q?vKttX6KqESUe+rw6nS1jjMdPJW2TDn6IfWfRAtu/KMXLJtccrKyUkvChrJjkiK?= =?us-ascii?q?pYP/IzyZzOYNs3CC4udmSOmhiHYnphlsrjWhyMogkInEipgIxl3K7yl0wJ45Kc?= =?us-ascii?q?C2RUN1e9KpEIFcuz+HO4Z1WM8uXm5ltSU8x7Ybo5C0ZjIKx44ixxPHa/yIbYyI?= =?us-ascii?q?4hX7WeaRLjp0nnJleLWkhxau8EigzOL8W8au3FlWsiVJiNrMt3AQ1xzI6siHV+?= =?us-ascii?q?Jx/lq71TmVyw/f8ONEIVgsmaraLZ4u3KIwm4IOvUnNECL6gkX7gLWLekgq4OSl?= =?us-ascii?q?6/zrYrD8qZ+dM490hBv+MqMrmsGnGus3LBIOUHad+eSzyrLj51b0T65Ljv0xiK?= =?us-ascii?q?nWrp/aKd4Ypq+5Hg9VyYYj6wumAze7ytgXh2UIIEhHeBKfl4TpIU3BIOjkDfej?= =?us-ascii?q?hFShiCtkyOrDPr3lG5nNKnnDkKz9fbtm8E5dyA8zzchF6J5OC7EBJujzWk7ru9?= =?us-ascii?q?DCAB85KV/8/+GyA9x40sYaWHmTKq6fKqLb91GStcw1JOzZSpUcvj36KuNtzdPU?= =?us-ascii?q?oFkWtGVVKaOkx5YRZ32iNv5nJF+Ubjzvk8oaEXpPo0w3R6rokAvRAnZoe3+uUv?= =?us-ascii?q?dktXkAA4W8ANKbH9H/sPm6xC6+W6ZuSCVDA1GIH23vct/fCf0NbzifLYligyEf?= =?us-ascii?q?VaXkVsko3lesrF2ikuY1Hq/v4iQd8Knb+p1t/eSJzkM49DtuAsvb0HCQVGFp23?= =?us-ascii?q?5OTjRw3rgt+RUgmGfG6rBxhrljLfIW5/5NVVxjZ56Aiex9EMzzXA2dONyCDlW3?= =?us-ascii?q?X86mHHQsCNs6hd0WMR5w?= X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: =?us-ascii?q?A0CmAQBsecFaegUNBYVdHAECBAELAYQnb?= =?us-ascii?q?IQEiF6NbgghgQ+NZ4RsFIFmAQqFBAKEPgYGMhYBAgEBAQEBAQEBARIBAQsLCwQ?= =?us-ascii?q?qL4I3IoJEBwEBAQECASMPAUsLCxgCAiYCAh84EwgBATKETweuIYIchFWCZRhog?= =?us-ascii?q?iuBCYQ+hC2BLgyCVoQuCYEEgjSCVAKFVAdfhheKaQgajg4Gh0CEd499gSUjCoF?= =?us-ascii?q?5gQU6gkSCHxeOJY5iAQE?= X-IPAS-Result: =?us-ascii?q?A0CmAQBsecFaegUNBYVdHAECBAELAYQnbIQEiF6NbgghgQ+?= =?us-ascii?q?NZ4RsFIFmAQqFBAKEPgYGMhYBAgEBAQEBAQEBARIBAQsLCwQqL4I3IoJEBwEBA?= =?us-ascii?q?QECASMPAUsLCxgCAiYCAh84EwgBATKETweuIYIchFWCZRhogiuBCYQ+hC2BLgy?= =?us-ascii?q?CVoQuCYEEgjSCVAKFVAdfhheKaQgajg4Gh0CEd499gSUjCoF5gQU6gkSCHxeOJ?= =?us-ascii?q?Y5iAQE?= X-IronPort-AV: E=Sophos;i="5.48,393,1517871600"; d="scan'208";a="320910880" Received: from hosting4.cc.kyushu-u.ac.jp (HELO h4.hosting4.cc.kyushu-u.ac.jp) ([133.5.13.5]) by mail2-smtp-roc.national.inria.fr with ESMTP; 02 Apr 2018 02:34:15 +0200 Received: from [192.168.2.47] (unknown [133.5.218.148]) (using TLSv1.2 with cipher DHE-RSA-AES128-SHA (128/128 bits)) (No client certificate requested) (Authenticated sender: berenger@bioreg.kyushu-u.ac.jp) by h4.hosting4.cc.kyushu-u.ac.jp (hde-lc-postfix) with ESMTPSA id B3C252B6275 for ; Mon, 2 Apr 2018 09:34:10 +0900 (JST) (envelope-from berenger@bioreg.kyushu-u.ac.jp) To: caml-list@inria.fr References: From: Francois BERENGER Message-ID: Date: Mon, 2 Apr 2018 09:34:10 +0900 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101 Thunderbird/52.7.0 MIME-Version: 1.0 In-Reply-To: Content-Type: text/plain; charset=utf-8 Content-Language: en-US Content-Transfer-Encoding: 8bit Subject: Re: [Caml-list] Hashtbl and shrinking Reply-To: Francois BERENGER X-Loop: caml-list@inria.fr X-Sequence: 16768 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: On 03/30/2018 05:49 AM, Armaël Guéneau wrote: > 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? That your change would introduce some time complexity that may not be what people expect for some operations. That being said, if a resize operations was added to the module, appart from changing the current interface, it would not harm people much I guess. We could accept this in batteries, or even revive the old code that was doing this previously. Also, if you are so much concerned about the size of your hashtbl, why don't you use a map? Regards, Francois. > 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