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 mail2-relais-roc.national.inria.fr (mail2-relais-roc.national.inria.fr [192.134.164.83]) by sympa.inria.fr (Postfix) with ESMTPS id 1A1177F787 for ; Tue, 8 Nov 2016 11:49:23 +0100 (CET) Authentication-Results: mail2-smtp-roc.national.inria.fr; spf=None smtp.pra=pierre.chambart@ocamlpro.com; spf=None smtp.mailfrom=pierre.chambart@ocamlpro.com; spf=Pass smtp.helo=postmaster@redisdead.crans.org Received-SPF: None (mail2-smtp-roc.national.inria.fr: no sender authenticity information available from domain of pierre.chambart@ocamlpro.com) identity=pra; client-ip=138.231.136.39; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="pierre.chambart@ocamlpro.com"; x-sender="pierre.chambart@ocamlpro.com"; x-conformance=sidf_compatible Received-SPF: None (mail2-smtp-roc.national.inria.fr: no sender authenticity information available from domain of pierre.chambart@ocamlpro.com) identity=mailfrom; client-ip=138.231.136.39; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="pierre.chambart@ocamlpro.com"; x-sender="pierre.chambart@ocamlpro.com"; x-conformance=sidf_compatible Received-SPF: Pass (mail2-smtp-roc.national.inria.fr: domain of postmaster@redisdead.crans.org designates 138.231.136.39 as permitted sender) identity=helo; client-ip=138.231.136.39; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="pierre.chambart@ocamlpro.com"; x-sender="postmaster@redisdead.crans.org"; x-conformance=sidf_compatible; x-record-type="v=spf1" IronPort-PHdr: =?us-ascii?q?9a23=3AI0D4FRW02mkrlK/ovYaLwsqZ6Y7V8LGtZVwlr6E/?= =?us-ascii?q?grcLSJyIuqrYZxWDt8tkgFKBZ4jH8fUM07OQ6PG6Hz1eqs/Q+Fk5M7V0Hycfjs?= =?us-ascii?q?sXmwFySOWkMmbcaMDQUiohAc5ZX0Vk9XzoeWJcGcL5ekGA6ibqtW1aJBzzOEJP?= =?us-ascii?q?K/jvHcaK1oLshrr0qsOYOlQArQH+SIs6FA+xowTVu5teqqpZAYF19CH0pGBVcf?= =?us-ascii?q?9d32JiKAHbtR/94sCt4MwrqHwI6Lpyv/JHBIr9ZLs5S/RGCzJuGXo46MDxsR7c?= =?us-ascii?q?BV+A4WADU2NTjF9CKxfI5lf2U8G1+gD6rOtmxC6CPYXWGuc7VC7qu6xrUh7zlC?= =?us-ascii?q?AfN3g592zYh9ZYkL8eqh+7ox15hYLZNtK7Lv17K5vccMkASCJqXs9UXSVbHsvo?= =?us-ascii?q?d4oCFfAMe+1Ypoz3rkEShRy1DAyoHPnojDRPgymljuUBz+09HFSej0QbFNUUvS?= =?us-ascii?q?GMoQ=3D=3D?= X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: =?us-ascii?q?A0AQAADZrCFYlyeI54pdGgEBAQECAQEBA?= =?us-ascii?q?QgBAQEBFQEBAQECAQEBAQgBAQEBgwQBAQEBAXcsU6Q7kkSCD4IIKYV7AoITQRI?= =?us-ascii?q?BAQEBAQEBAQEBARIBAQEBAQgWB02CMxiCFwEBBCdSEAsYLlcGAQwIAQGIWAQBC?= =?us-ascii?q?bNxUotIAQEBAQEBAQECAQEBAQEBARsFhj6BfQiCUIQjJIVgAQSaLoFrhEuLf4R?= =?us-ascii?q?ygxiGHI0thAYlA4FCgyeBaXGEfoI8AQEB?= X-IPAS-Result: =?us-ascii?q?A0AQAADZrCFYlyeI54pdGgEBAQECAQEBAQgBAQEBFQEBAQE?= =?us-ascii?q?CAQEBAQgBAQEBgwQBAQEBAXcsU6Q7kkSCD4IIKYV7AoITQRIBAQEBAQEBAQEBA?= =?us-ascii?q?RIBAQEBAQgWB02CMxiCFwEBBCdSEAsYLlcGAQwIAQGIWAQBCbNxUotIAQEBAQE?= =?us-ascii?q?BAQECAQEBAQEBARsFhj6BfQiCUIQjJIVgAQSaLoFrhEuLf4RygxiGHI0thAYlA?= =?us-ascii?q?4FCgyeBaXGEfoI8AQEB?= X-IronPort-AV: E=Sophos;i="5.31,609,1473112800"; d="scan'208";a="244063077" Received: from redisdead.crans.org ([138.231.136.39]) by mail2-smtp-roc.national.inria.fr with ESMTP/TLS/DHE-RSA-AES256-GCM-SHA384; 08 Nov 2016 11:49:22 +0100 Received: from [192.168.1.164] (178-214-190-109.dsl.ovh.fr [109.190.214.178]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by redisdead.crans.org (Postfix) with ESMTPSA id E4B4F2CF; Tue, 8 Nov 2016 11:49:19 +0100 (CET) From: Pierre Chambart To: Goswin von Brederlow , Christoph H??ger References: <390aa113-a9eb-fce0-fe03-6a904ad053dd@tu-berlin.de> <20161108101015.GC18517@frosties> Cc: caml-list@inria.fr Organization: OcamlPro Message-ID: <207e46ad-86f5-4171-b1bc-7525f9e6338b@ocamlpro.com> Date: Tue, 8 Nov 2016 11:49:19 +0100 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:45.0) Gecko/20100101 Thunderbird/45.4.0 MIME-Version: 1.0 In-Reply-To: <20161108101015.GC18517@frosties> Content-Type: text/plain; charset=windows-1252 Content-Transfer-Encoding: quoted-printable X-Validation-by: pierre.chambart@ocamlpro.com Subject: Re: [Caml-list] Re: Compile-time performance problem Le 08/11/2016 =E0 11:10, Goswin von Brederlow a =E9crit : > On Tue, Nov 08, 2016 at 09:56:33AM +0100, Christoph H??ger wrote: >> let (<+) a v =3D Array.append a [|v|]=20 >> let foo k s =3D >> ((fun k -> fun s -> (k#_continue_ (object (self) end)) 1) >> (object (self) >> val _continue_ =3D >> fun x -> >> (fun k -> >> fun s -> >> ((fun k -> fun s -> (k#_continue_ (object (self) end= )) 2) > ... > > Do you have to use objects there? Does the problem go away if you use > a simple type for the continuation? > > The thing with CPS is that your code can be converted into simple > jumps instead of function calls. Everything is a tail call. And all > your objects are dummies that can be optimized away if you try hard > enough. Really complex dummies. I can imagine the bytecode simply > creates the objects and calls the methods while the native code > optimizes it all away. Hard to say if that is linear (and really > slow), quadratic or exponential with just one example though. > > MfG > Goswin > It is linear with a very large constant factor. It is linked to a known exponential case in closure conversion that was limited: In case of deeply nested functions when the initial closeness estimation is systematically wrong, this can fall into that case. To prevent problems the search depth is limited to 5. See https://github.com/ocaml/ocaml/blob/trunk/asmcomp/closure.ml#L765 and https://github.com/ocaml/ocaml/blob/trunk/asmcomp/closure.ml#L1195 Please fill a bug on mantis for this. Side not: Flambda does not have this kind of problem, this estimation is done by a linear time fixpoint. (this might be the only known example where flambda compilation is faster...) --=20 Pierre