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 sympa.inria.fr (Postfix) with ESMTPS id 1B6317EF0D for ; Mon, 22 Feb 2016 20:54:54 +0100 (CET) IronPort-PHdr: 9a23:JO011Ra0h2/+Od06nrXslQz/LSx+4OfEezUN459isYplN5qZpM2/bnLW6fgltlLVR4KTs6sC0LqJ9f28EjVbuN6oizMrTt9lb1c9k8IYnggtUoauKHbQC7rUVRE8B9lIT1R//nu2YgB/Ecf6YEDO8DXptWZBUiv2OQc9HOnpAIma153xjLDtvcCPKFwT3XKUWvBbElaflU3prM4YgI9veO4a6yDihT92QdlQ3n5iPlmJnhzxtY+a9Z9n9DlM6bp6r5YTGY2zRakzTKRZATI6KCh1oZSz7ViQezCS/WMRWXk6lR9BAg6NrE2rH8THm3Ci768lgWHaZJC3HvgIXmGL6btsTlfCgSwHNjhxpGjRltZ3iqhSqxKgoTRwxofVZMeeM/8oLY3HetZPbGxdWcAZfSVKAoK6J98GCfYbOuBSpoL9pl0moh63BA3qD+TqnGwbzkTq1LE3hrxyWTrN2xYtSpdV7nk= Authentication-Results: mail2-smtp-roc.national.inria.fr; spf=None smtp.pra=antronbachin@gmail.com; spf=Pass smtp.mailfrom=antronbachin@gmail.com; spf=None smtp.helo=postmaster@mail-ig0-f171.google.com Received-SPF: None (mail2-smtp-roc.national.inria.fr: no sender authenticity information available from domain of antronbachin@gmail.com) identity=pra; client-ip=209.85.213.171; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="antronbachin@gmail.com"; x-sender="antronbachin@gmail.com"; x-conformance=sidf_compatible Received-SPF: Pass (mail2-smtp-roc.national.inria.fr: domain of antronbachin@gmail.com designates 209.85.213.171 as permitted sender) identity=mailfrom; client-ip=209.85.213.171; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="antronbachin@gmail.com"; x-sender="antronbachin@gmail.com"; x-conformance=sidf_compatible; x-record-type="v=spf1" Received-SPF: None (mail2-smtp-roc.national.inria.fr: no sender authenticity information available from domain of postmaster@mail-ig0-f171.google.com) identity=helo; client-ip=209.85.213.171; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="antronbachin@gmail.com"; x-sender="postmaster@mail-ig0-f171.google.com"; x-conformance=sidf_compatible X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: A0AxAADlZstWmKvVVdFehAxtqjCQJAENgWYhhWwCgUQ4FAEBAQEBAQEBEAEBAQEBBgsLCSEvgi2CFAEBAQMBEhEEGQEbEgsBAwELBgULAwoCAgkdAgIhAhEBBQEKEgYTEhCHYwEDCggOnTWBMT4xizSBaYJXhQIKGScDClGDeQEBAQEBAQEBAQEBAQEBAQEBAQEBAQ8BBQoEbYcDgk6COoF5gwIrgQ8FhhcMh3uIaYVXhhSBc4Imhm0OhVKHBYYGL4EPHgEBgjgNEQiBZ0sBiDgBAQE X-IPAS-Result: A0AxAADlZstWmKvVVdFehAxtqjCQJAENgWYhhWwCgUQ4FAEBAQEBAQEBEAEBAQEBBgsLCSEvgi2CFAEBAQMBEhEEGQEbEgsBAwELBgULAwoCAgkdAgIhAhEBBQEKEgYTEhCHYwEDCggOnTWBMT4xizSBaYJXhQIKGScDClGDeQEBAQEBAQEBAQEBAQEBAQEBAQEBAQ8BBQoEbYcDgk6COoF5gwIrgQ8FhhcMh3uIaYVXhhSBc4Imhm0OhVKHBYYGL4EPHgEBgjgNEQiBZ0sBiDgBAQE X-IronPort-AV: E=Sophos;i="5.22,485,1449529200"; d="scan'208";a="204183404" Received: from mail-ig0-f171.google.com ([209.85.213.171]) by mail2-smtp-roc.national.inria.fr with ESMTP/TLS/AES128-GCM-SHA256; 22 Feb 2016 20:54:53 +0100 Received: by mail-ig0-f171.google.com with SMTP id y8so88107592igp.1 for ; Mon, 22 Feb 2016 11:54:53 -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:cc :content-transfer-encoding:message-id:references:to; bh=flqAYIXJ7HnrLKOEegPiBS+XFSGc3bD6i8dd0TcGN+Q=; b=mI6ERaV4TRnwBW9Hxe3vgYjYqER9WGMdFZQqOPcVLDIYFwq+ypRoA8kjMreVlXLKF5 ZU+Bxd34dJ4OD+LOL3Pj1x0B57rI18xtauYubxMhAFsWWTKSLf74pyW1TDD4tG6jtCpX 11SlyAZHUh7kHIc2C9JelZpOAG/0/bKeS5tuv/nve+io489FN6KkSlHos/EqvRnIAP7i /oNvUrTSF9Pu9maCgfZBZOIkd58I+0C4KfAKj64Xn1+BkWmTrSjogecct8dgi2NatYbB lY9TD68aceMZldTutHMYv6/ppEnTICoMD72tqlrNeuuOGQijdLykKqei+OAvPyhYeCiy G80Q== 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:cc:content-transfer-encoding:message-id:references :to; bh=flqAYIXJ7HnrLKOEegPiBS+XFSGc3bD6i8dd0TcGN+Q=; b=L0ByBMDwEu32hLkCZ1JnIPNEyYMshO+LiAK8L9yaWiwWmgNEvxdQEjL02fgfmQBdGJ HGlKd4X/GNRgX5rskdpV2pQw17KIS+NMKgnR4w0PYwQz1eKG+KDvcqU8TVIMD1umG2ou 98t7nRbMrKV7p8l4ief1rzyCd2nwoa2DYpJCT2QQ8vPSfxFZ5ZwEWNEA2cAoyyIVYnGR nKOjBNElmqXno6apMhwgwNTvgkSuM8xqbeTlvVIOE++N+p7p8Pv4U7zf91qbsHp+SA4i uYuvTg38QrGU6PTPJf9lr4P09HBr1Dvg2HrKj+WvDDRErnK8h4ItXhMYwPyqnLaYUCz3 XOow== X-Gm-Message-State: AG10YOQ1xeQbpcyz7fY0rgkVarOk8a/kz4Nbcwr7BBYwRxKcij27KU5J9JB3ByOrmxfjkg== X-Received: by 10.50.50.201 with SMTP id e9mr14029714igo.10.1456170892201; Mon, 22 Feb 2016 11:54:52 -0800 (PST) Received: from [192.168.0.10] (c-73-9-77-177.hsd1.il.comcast.net. [73.9.77.177]) by smtp.gmail.com with ESMTPSA id v29sm12019480iov.11.2016.02.22.11.54.51 (version=TLS1 cipher=ECDHE-RSA-AES128-SHA bits=128/128); Mon, 22 Feb 2016 11:54:51 -0800 (PST) Content-Type: text/plain; charset=utf-8 Mime-Version: 1.0 (Mac OS X Mail 8.2 \(2070.6\)) From: Anton Bachin In-Reply-To: Date: Mon, 22 Feb 2016 13:54:51 -0600 Cc: Chan Ngo , OCaml users X-Mao-Original-Outgoing-Id: 477863691.084889-cb7ac1771d3f281afd49405c3c6f77b2 Content-Transfer-Encoding: quoted-printable Message-Id: <10BFAE8E-7C97-458C-809C-37B9DBDD62F9@gmail.com> References: <20160222094853.GH1544@nunchakus.loria.fr> <46EAD496-8667-47FE-B39A-74DA94BC0C25@gmail.com> To: Anton Bachin X-Mailer: Apple Mail (2.2070.6) Subject: Re: [Caml-list] Constant-time function Correction: "if h1 and h2 are of nontrivial type=E2=80=9D. > On Feb 22, 2016, at 13:51, Anton Bachin wrote: >=20 > 1. You are computing the length of l1 and l2 every iteration. On the firs= t iteration, it is the lengths of the original lists. On the second iterati= on, it is the lengths of their tails. This function takes time quadratic in= the maximum of (length l1, length l2), as written. List.length itself take= s linear time. >=20 > 2. If h1 and h2 are nontrivial types, structural equality may take a nont= rivial amount of time to compute. >=20 >> On Feb 22, 2016, at 13:45, Chan Ngo wrote: >>=20 >> Dear all, >>=20 >> I have write a simple function to compare two lists as below: >>=20 >> 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;; >>=20 >> In theory, we can see that the execution is a function of length of l1 a= nd l2 (in case they are same length, otherwise it return immediately) and i= t is constant time (i.e., we fixed the length of l1 and l2). However, in fa= ct, 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 >>=20 >> You see the execution times are really different. Thus, I wonder that th= e compiler did some optimization? Does anyone have some pointers? >>=20 >> Thanks, >> Chan >>=20 >>=20 >>> On Feb 22, 2016, at 4:48 AM, Simon Cruanes = wrote: >>>=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-bigs= tring , >>> 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= 62B6 >>=20 >>=20 >> --=20 >> 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 >=20 >=20 > --=20 > 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