From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Original-To: caml-list@sympa.inria.fr Delivered-To: caml-list@sympa.inria.fr 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 14EDF7EF0D for ; Mon, 22 Feb 2016 20:45:27 +0100 (CET) IronPort-PHdr: 9a23:As2NtBYOMTZ3atkDT2xl9mT/LSx+4OfEezUN459isYplN5qZpcm7bnLW6fgltlLVR4KTs6sC0LqJ9f28EjVavN6oizMrTt9lb1c9k8IYnggtUoauKHbQC7rUVRE8B9lIT1R//nu2YgB/Ecf6YEDO8DXptWZBUiv2OQc9HOnpAIma153xjLDtvcCPKFwS2XKUWvBbElaflU3prM4YgI9veO4a6yDihT92QdlQ3n5iPlmJnhzxtY+a9Z9n9DlM6bp6r5YTGfayQ6NtapdRCTBuLns4/taj4RLKSA/K4noHTk0XlABJCk7L9kepcI32t37RtuN7kA+VOoWiRrA9X3Kk4KAxEkezoCgCPj89tmrQj5oj3+pgvBu9qkknkMbva4aPOa8mcw== Authentication-Results: mail3-smtp-sop.national.inria.fr; spf=None smtp.pra=chan.ngo2203@gmail.com; spf=Pass smtp.mailfrom=chan.ngo2203@gmail.com; spf=None smtp.helo=postmaster@mail-qg0-f42.google.com Received-SPF: None (mail3-smtp-sop.national.inria.fr: no sender authenticity information available from domain of chan.ngo2203@gmail.com) identity=pra; client-ip=209.85.192.42; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="chan.ngo2203@gmail.com"; x-sender="chan.ngo2203@gmail.com"; x-conformance=sidf_compatible Received-SPF: Pass (mail3-smtp-sop.national.inria.fr: domain of chan.ngo2203@gmail.com designates 209.85.192.42 as permitted sender) identity=mailfrom; client-ip=209.85.192.42; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="chan.ngo2203@gmail.com"; x-sender="chan.ngo2203@gmail.com"; x-conformance=sidf_compatible; x-record-type="v=spf1" Received-SPF: None (mail3-smtp-sop.national.inria.fr: no sender authenticity information available from domain of postmaster@mail-qg0-f42.google.com) identity=helo; client-ip=209.85.192.42; receiver=mail3-smtp-sop.national.inria.fr; envelope-from="chan.ngo2203@gmail.com"; x-sender="postmaster@mail-qg0-f42.google.com"; x-conformance=sidf_compatible X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: A0B7AAD4ZMtWkSrAVdFehAxtr3uDP4caAQ2BZiGFbAKBRDgUAQEBAQEBAQEQAQEBAQcLCwkfMUESAYFZghQBAQEDARIVEwYBGx4DAQsGEA0uIxEBBQEcBhMih2MBAwoIDp0qgTE+MY0dgleFAQoZJw1Rg3kBAQEBAQEBAwEBAQEBAQEBAQEBDwEFCgSHcAiKJoEPBY4eiGEIhVeIB4Imhm2FYI0LL4EPHgEBgjgNEQiBZkwBg3+EOQEBAQ X-IPAS-Result: A0B7AAD4ZMtWkSrAVdFehAxtr3uDP4caAQ2BZiGFbAKBRDgUAQEBAQEBAQEQAQEBAQcLCwkfMUESAYFZghQBAQEDARIVEwYBGx4DAQsGEA0uIxEBBQEcBhMih2MBAwoIDp0qgTE+MY0dgleFAQoZJw1Rg3kBAQEBAQEBAwEBAQEBAQEBAQEBDwEFCgSHcAiKJoEPBY4eiGEIhVeIB4Imhm2FYI0LL4EPHgEBgjgNEQiBZkwBg3+EOQEBAQ X-IronPort-AV: E=Sophos;i="5.22,485,1449529200"; d="scan'208";a="165617877" Received: from mail-qg0-f42.google.com ([209.85.192.42]) by mail3-smtp-sop.national.inria.fr with ESMTP/TLS/AES128-GCM-SHA256; 22 Feb 2016 20:45:26 +0100 Received: by mail-qg0-f42.google.com with SMTP id y89so119739949qge.2 for ; Mon, 22 Feb 2016 11:45:26 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=content-type:mime-version:subject:from:in-reply-to:date :content-transfer-encoding:message-id:references:to; bh=+Ebn5hJTUdN4f3m+7dH68tY+NW7evRnIgzzXu8wvmRs=; b=i5ci1GW1n2Ef2zjsaRi3VCTwmfG9z/iNyiXxC4SjZuHXPjeStyWONSHDk/1p+iJzQB tqabv8xLq+g9lwxMPF7m5jAle78cBBs5jY030KOyX34dXvwzpTA0sG9lQ5ME9RY4oRX7 EHS+vsWndUXKBnQxNRgClHv+3rWVtFZsAwPSFa677R1Yvyh5KYZoh4VSR/+9Px/RvF2m X/KpjCrXmxaAos0lKcsAh/5SI7LZQS0ESy3G+R+upQYs2gZiegumfOrM3HwfEqmjOh62 Lh8+FZeRoSDbB5Rl7bhRj/fythyYFWCog9+mg/e7keG54D7St0ubCpr+a2MlaG88qFxW Z/Xw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:content-type:mime-version:subject:from :in-reply-to:date:content-transfer-encoding:message-id:references:to; bh=+Ebn5hJTUdN4f3m+7dH68tY+NW7evRnIgzzXu8wvmRs=; b=JJfkr5GpAldBNCH0OH7AIybbkM9uUJtrRyJ5niWMB0wLP9jsA9i5B/+UhNJnpKiIPR Zw44uhFpvAMaw9kQHdyYFMoEQSVCeCGgjkHU4Ex8qlp0aV8u7MrkM1WeUE0aVhlcprzz Fb1bwjz7A4A4OUNkYRGtQpUvwqBJf9cEK1SFH0xFcvJjAdu6DlRHISpbcV2lk9vHr1m2 S1XInTSulp0QscoPiKV3ku1XEzg3SukSA9eMRWmonsQfjelGwBd9502EB+YNiK3+ixrs aAQm23cDOfyGbC56Jt5kponHPCqQ2zPW1sDST40m1L/0Qh59KpqHdV231oOL+S6tgM5x cDCw== X-Gm-Message-State: AG10YOT4KPAYeOcT0+pZZXMJD0WlM6plgJNtGdqgN7qVrSiVdreoxAPC6NnCk26MIh1mAg== X-Received: by 10.140.181.130 with SMTP id c124mr38679701qha.75.1456170325194; Mon, 22 Feb 2016 11:45:25 -0800 (PST) Received: from chans-mbp.wv.cc.cmu.edu (Chans-MBP.wv.cc.cmu.edu. [128.237.202.31]) by smtp.gmail.com with ESMTPSA id 2sm7195223qgi.33.2016.02.22.11.45.23 for (version=TLS1 cipher=ECDHE-RSA-AES128-SHA bits=128/128); Mon, 22 Feb 2016 11:45:23 -0800 (PST) Content-Type: text/plain; charset=us-ascii Mime-Version: 1.0 (Mac OS X Mail 9.2 \(3112\)) From: Chan Ngo In-Reply-To: <20160222094853.GH1544@nunchakus.loria.fr> Date: Mon, 22 Feb 2016 14:45:22 -0500 Content-Transfer-Encoding: quoted-printable Message-Id: <46EAD496-8667-47FE-B39A-74DA94BC0C25@gmail.com> References: <20160222094853.GH1544@nunchakus.loria.fr> To: OCaml users X-Mailer: Apple Mail (2.3112) Subject: [Caml-list] Constant-time function Dear all, I have write a simple function to compare two lists as below: let rec lcomp l1 l2 =3D=20 if (List.length l1 !=3D List.length l2)=20 then false else match l1, l2 with=20 | h1::t1, h2::t2 -> h1 =3D h2 && lcomp t1 t2 | _, _ -> true;; In theory, we can see that the execution is a function of length of l1 and = l2 (in case they are same length, otherwise it return immediately) and it i= s constant time (i.e., we fixed the length of l1 and l2). However, in fact,= when I run this function with two lists of around 100 elements,=20 + with only 10th element is different: it takes 0.000027s + with only 90th element is different: it takes 0.000116s You see the execution times are really different. Thus, I wonder that the c= ompiler did some optimization? Does anyone have some pointers? Thanks, Chan > On Feb 22, 2016, at 4:48 AM, Simon Cruanes w= rote: >=20 > Hello, >=20 > I released bigstring.0.1 yesterday, a small module for dealing with > bigarrays of chars. It used to be part of containers, but is useful on > its own for low level IO, mirage, etc.; hence the split. The license is > BSD-2-clauses. >=20 > Code, issues, etc. can be found at https://github.com/c-cube/ocaml-bigstr= ing , > and contributions and criticism are welcome. >=20 > Cheers, >=20 > --=20 > Simon Cruanes >=20 > http://weusepgp.info/ > key 49AA62B6, fingerprint 949F EB87 8F06 59C6 D7D3 7D8D 4AC0 1D08 49AA 6= 2B6