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 A7E427F615 for ; Mon, 19 Dec 2016 17:45:10 +0100 (CET) Authentication-Results: mail2-smtp-roc.national.inria.fr; spf=None smtp.pra=yotambarnoy@gmail.com; spf=Pass smtp.mailfrom=yotambarnoy@gmail.com; spf=None smtp.helo=postmaster@mail-yb0-f174.google.com Received-SPF: None (mail2-smtp-roc.national.inria.fr: no sender authenticity information available from domain of yotambarnoy@gmail.com) identity=pra; client-ip=209.85.213.174; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="yotambarnoy@gmail.com"; x-sender="yotambarnoy@gmail.com"; x-conformance=sidf_compatible Received-SPF: Pass (mail2-smtp-roc.national.inria.fr: domain of yotambarnoy@gmail.com designates 209.85.213.174 as permitted sender) identity=mailfrom; client-ip=209.85.213.174; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="yotambarnoy@gmail.com"; x-sender="yotambarnoy@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-yb0-f174.google.com) identity=helo; client-ip=209.85.213.174; receiver=mail2-smtp-roc.national.inria.fr; envelope-from="yotambarnoy@gmail.com"; x-sender="postmaster@mail-yb0-f174.google.com"; x-conformance=sidf_compatible IronPort-PHdr: =?us-ascii?q?9a23=3AnMWPkRIBUv/MlppilNmcpTZWNBhigK39O0sv0rFi?= =?us-ascii?q?tYgUKvvxwZ3uMQTl6Ol3ixeRBMOAuqkC1LWd4vmoGTRZp83e4DZaKN0EfiRGoP?= =?us-ascii?q?tVtjRoONSCB0z/IayiRA0BN+MGamVY+WqmO1NeAsf0ag6aiHSz6TkPBke3blIt?= =?us-ascii?q?dazdU7TfhMWv1u2054abI0AR3GL8MvtOK0CXswzX/uYRnYx8IaYw1gCB9npWdM?= =?us-ascii?q?xXyG5lY1WJkECvyN23+ctS9DhZvroL/tRGVrSyK7U/UbVdBj08NWckzMLuvBjH?= =?us-ascii?q?CwCI4y1PAS0tjhNUDl2dv1nBVZDrv36/77Il1Q=3D=3D?= X-IronPort-Anti-Spam-Filtered: true X-IronPort-Anti-Spam-Result: =?us-ascii?q?A0BdAACBDVhYhq7VVdFdGgEBAQECAQEBA?= =?us-ascii?q?QgBAQEBFgEBAQMBAQEJAQEBgwwBAQEBAT86gQYHgTaMEpZZiGaMKIIKJoV8AoF?= =?us-ascii?q?7Bz8UAQEBAQEBAQEBAQESAQEBCAsLCR0wgjMEARUBBIIXAQUjHQEUBx0BAwwGB?= =?us-ascii?q?QsDCgICJgICIgERAQUBHAYTCYhHAQMXDpscP4wCggQFAR6DDQWDUwoZJw1Ugm4?= =?us-ascii?q?BAQEBBgEBAQEBGwIGEnmFK4RZhEAMgkALLYJdBYhUDocciTCBQo1Fg2+QTYgOh?= =?us-ascii?q?guCSRQegRQfgTlOE4M7IIIGIDQBhkwqRIFPAQEB?= X-IPAS-Result: =?us-ascii?q?A0BdAACBDVhYhq7VVdFdGgEBAQECAQEBAQgBAQEBFgEBAQM?= =?us-ascii?q?BAQEJAQEBgwwBAQEBAT86gQYHgTaMEpZZiGaMKIIKJoV8AoF7Bz8UAQEBAQEBA?= =?us-ascii?q?QEBAQESAQEBCAsLCR0wgjMEARUBBIIXAQUjHQEUBx0BAwwGBQsDCgICJgICIgE?= =?us-ascii?q?RAQUBHAYTCYhHAQMXDpscP4wCggQFAR6DDQWDUwoZJw1Ugm4BAQEBBgEBAQEBG?= =?us-ascii?q?wIGEnmFK4RZhEAMgkALLYJdBYhUDocciTCBQo1Fg2+QTYgOhguCSRQegRQfgTl?= =?us-ascii?q?OE4M7IIIGIDQBhkwqRIFPAQEB?= X-IronPort-AV: E=Sophos;i="5.33,374,1477954800"; d="scan'208";a="250727591" Received: from mail-yb0-f174.google.com ([209.85.213.174]) by mail2-smtp-roc.national.inria.fr with ESMTP/TLS/AES128-GCM-SHA256; 19 Dec 2016 17:45:09 +0100 Received: by mail-yb0-f174.google.com with SMTP id v78so58751888ybe.3 for ; Mon, 19 Dec 2016 08:45:09 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc:content-transfer-encoding; bh=09akg13/UV+G2zKyvBvoeYL5cHxS25XSztASM5In4pM=; b=XwnQBMCK1j8h04cWqKyi9RiyMxEoGz2iWFPN0qRtpsOxdoQ67X20vXLBxyPxv1NRGY 4DQ0fSZ0YVIxzMrnA6LLesfFv/lPPYE9FFW2r6l8QWYIUWgtmsviScE/7zwaQlqsoVjA jbvh+KBONo+4HX6/OO/ye6J8har2ko/pFsV5uC/5z7PoQVUa/U+rdK4HpT1E0x4cFHKO pebePkntOyXW+jPQJBuPgG98/soCKH8lN7VtNCZ5DxKNV695SS1hGrE9Fxn1ZPlVhC47 STcpZgoIiEWUvNq8oRc00ux4TsW29+Fj50SKG9qTdY6KYDbHF0oMuhM8Tu1lNCDiJFgv LfaA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to:cc:content-transfer-encoding; bh=09akg13/UV+G2zKyvBvoeYL5cHxS25XSztASM5In4pM=; b=N94XmBrOpUtMiFFQIw636txQO4c3P8dZmGcyll/kOR/Sc8A7ENcZeYMAEvEjD1eLwh 4kh5rMbrCGYgpKsUqCOnWb/JFHw53gh0hA+PIupmqKqncaVqOZhPqBIXyUjYF5Jg0hS1 T0Qi8WUlA+nKDlx+kBmVQ/zHwwcN92t4s5xpu9kvpl0OMtqLHx2KlqBFdxKqu+3uinfK cMb3tY9S2fLcP5YQfw3YDl5vbnxAq2MWBgt1OBX0gX+YTzwBIcZe3Of8vVii0WIhqsa4 SqBwo6rWWUQIFB9qrJdsZxMwdnwEbgyDZBhxT9lIKmsbpp2QNFbwnHwZc4+Tw7vP7dSR L1Yg== X-Gm-Message-State: AIkVDXLLnr6qnZPqlPwUXsIEhnMyvmgzTaoZvJa5omlmAySukUUhCOHWdV/0IZIKuSW+Nxe5QUrIrG2+UdTf+Q== X-Received: by 10.37.221.135 with SMTP id u129mr510815ybg.36.1482165907621; Mon, 19 Dec 2016 08:45:07 -0800 (PST) MIME-Version: 1.0 Received: by 10.37.18.86 with HTTP; Mon, 19 Dec 2016 08:44:47 -0800 (PST) In-Reply-To: References: <7bc766a2-d460-524b-35ca-89609a34b719@tu-berlin.de> <1482148297.4629.19.camel@gerd-stolpmann.de> From: Yotam Barnoy Date: Mon, 19 Dec 2016 11:44:47 -0500 Message-ID: To: Ivan Gotovchits Cc: Gerd Stolpmann , =?UTF-8?Q?Christoph_H=C3=B6ger?= , caml-list Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable Subject: Re: [Caml-list] Closing the performance gap to C Christoph, you don't mention which version of OCaml you're compiling with, and whether FLambda is used. Flambda should be able to do the kind of optimizations Ivan mentions, at least ideally. If it's not able to do them yet, it will be when the rewritten version is deployed. -Yotam On Mon, Dec 19, 2016 at 10:48 AM, Ivan Gotovchits wrote: > Hi Christoph, > > The problem is that your function definitions, like `loop` and `rk4_step`, > have too many parameters > and OCaml is not able to eliminate them and is actually not trying. It was > always a feature of OCaml > that poorly written code will be compiled into a poorly written program. > OCaml never tries to fix > programmer's errors. It will try to minimize the abstraction overhead (of= ten > to the zero). But if the abstractions, > on the first hand, were chosen incorrectly, then it won't fix the code. > > In your particular example, the C compiler was quite aggressive and was > capable of eliminating unnecessary computations. > I wouldn't, however, assume that the C compiler will be always able to do > this for you. > > Let's go through the code: > > > let rec loop steps h n y t =3D > if n < steps then loop steps h (n+1) (rk4_step y t h) (t +. h) else > y > > Here variables `steps` and `h` are loop invariants, so you shouldn't put = it > into the loop function parameter list. > Well yes, a compiler can find out loop invariants and remove them for you. > But in our case, to remove them, > it will need to change the type of the function. The compiler will not go > that far for us. It respects a programmer, and if a > programmer decided to make his loop function to depend on `6` arguments, > then it means that the computation is actually depending > on 6 arguments. So, it will allocate 6 registers to hold loop variables, > with all the consequences. > > > Now, let's take a look at the `rk4_step` function: > > let rk4_step y t h =3D > let k1 =3D h *. y' t y in > let k2 =3D h *. y' (t +. 0.5*.h) (y +. 0.5*.k1) in > let k3 =3D h *. y' (t +. 0.5*.h) (y +. 0.5*.k2) in > let k4 =3D h *. y' (t +. h) (y +. k3) in > y +. (k1+.k4)/.6.0 +. (k2+.k3)/.3.0 > > > > This function, is, in fact, a body of the loop, and everything except t is > loop invariant here. Moreover, > function `y'` is defined as: > > let y' t y =3D cos t > > I.e., it doesn't really use it the second argument. Probably, a compiler > should inline the call, and eliminate > lots of unecessary computations, and thus free a few registers, but, > apparently, OCaml doesn't do this > (even in 4.03+flambda). > > So we should do this manually: > > let rk4_step y t =3D > let k1 =3D h *. y' t in > let k2 =3D h *. y' (t +. 0.5*.h) in > let k3 =3D h *. y' (t +. 0.5*.h) in > let k4 =3D h *. y' (t +. h) (y +. k3) in > y +. (k1+.k4)/.6.0 +. (k2+.k3)/.3.0 > > We can even see, that `k3` and `k2` are equal now, so we can eliminate th= em: > > let rk4_step y t =3D > let k1 =3D h *. y' t in > let k2 =3D h *. y' (t +. 0.5*.h) in > let k4 =3D h *. y' (t +. h) (y +. k3) in > y +. (k1+.k4)/.6.0 +. k2 *. 1.5 > > > Finally, we don't want to pass `y` into the `rk4_step` every time, as we > don't want to require an extra register for it. > After all these manual optimizations, we have the following program: > > let h =3D 0.1 > > > let exact t =3D sin t > > > let rk4_step t =3D > > let k1 =3D h *. cos t in > > let k2 =3D h *. cos (t +. 0.5*.h) in > > let k4 =3D h *. cos (t +. h) in > > (k1+.k4)/.6.0 +. k2*.1.5 > > > let compute steps =3D > > let rec loop n y t =3D > > if n < steps > > then loop (n+1) (y +. rk4_step t) (t +. h) > > else y in > > loop 1 1.0 0.0 > > > let () =3D > > let y =3D compute 102 in > > let err =3D abs_float (y -. (exact ((float_of_int 102) *. h))) in > > let large =3D 50000000 in > > let y =3D compute large in > > Printf.printf "%b\n" > > (abs_float (y -. (exact (float_of_int large) *. h)) < 2. *. err) > > > > This program has the same performance as the C one... unless I pass really > aggressive optimization options > to the C compiler, that will emit a platform specific code, e.g., > > gcc rk.c -lm -O3 -march=3Dcorei7-avx -o rksse > > > These options basically double the performance of the C version, leaving > OCaml lagging behind. That is because, > OCaml, obviously, cannot follow the latest developments of intel CPU, > especially in the field of SSE. > > The fun part is that when I've tried to compile the same file with clang, > the resulting program was even slower > than the original non-optimized OCaml. But this is all micro benchmarking= of > course, so don't jump to fast conclusions > (although I like to think that OCaml is faster than Clang :)) > > > As a final remark, my experience in HPC shows that in general you should = not > really rely on compiler optimizations and hope > that the compiler will do the magic for you. Even the GCC compiler. It wo= uld > be very easy to accidentally amend the above program > in a such way, that the optimizations will no longer fire in. Of course, > writing in assembly is also not a choice. If you really need > to optimize, then you should find out the performance bottleneck and then > optimize it manually until you get an expected performance. > Alternatively, you can use plain old Fortran to get the reliable > performance. And then call it from C or OCaml. > > > Best wishes, > Ivan > > > > On Mon, Dec 19, 2016 at 6:51 AM, Gerd Stolpmann > wrote: >> >> Hi Christoph, >> >> the extra code looks very much like an allocation on the minor heap: >> >> sub $0x10,%r15 >> lea 0x25c7b6(%rip),%rax >> cmp (%rax),%r15 >> jb 404a8a >> lea 0x8(%r15),%rax >> movq $0x4fd,-0x8(%rax) >> >> r15 points to the used area of the minor heap - by decrementing it you >> get an additional block of memory. It is compared against the beginning >> of the heap to check whether GC is needed. The constant 0x4fd is the >> header of the new block (which must be always initialized). >> >> From the source code, it remains unclear for what this is used. >> Obviously, the compiler runs out of registers, and moves some values to >> the minor heap (temporarily). When you call a C function like cos it is >> likely that this happens because the C calling conventions do not >> preserve the FP registers (xmm*). This could be improved if the OCaml >> compiler tried alternate places for temporarily storing FP values: >> >> - int registers (which is perfectly possible on 64 bit platforms). >> A number of int registers survive C calls. >> - stack >> >> To my knowledge, the OCaml compiler never tries this (but this could be >> out of date). This is a fairly specific optimization that makes mostly >> sense for purely iterating or aggregating functions like yours that do >> not store FP values away. >> >> Gerd >> >> Am Samstag, den 17.12.2016, 14:02 +0100 schrieb Christoph H=C3=B6ger: >> > Ups. Forgot the actual examples. >> > >> > Am 17.12.2016 um 14:01 schrieb Christoph H=C3=B6ger: >> > > >> > > Dear all, >> > > >> > > find attached two simple runge-kutta iteration schemes. One is >> > > written >> > > in C, the other in OCaml. I compared the runtime of both and gcc (- >> > > O2) >> > > produces an executable that is roughly 30% faster (to be more >> > > precise: >> > > 3.52s vs. 2.63s). That is in itself quite pleasing, I think. I do >> > > not >> > > understand however, what causes this difference. Admittedly, the >> > > generated assembly looks completely different, but both compilers >> > > inline >> > > all functions and generate one big loop. Ocaml generates a lot more >> > > scaffolding, but that is to be expected. >> > > >> > > There is however an interesting particularity: OCaml generates 6 >> > > calls >> > > to cos, while gcc only needs 3 (and one direct jump). Surprisingly, >> > > there are also calls to cosh, acos and pretty much any other >> > > trigonometric function (initialization of constants, maybe?) >> > > >> > > However, the true culprit seems to be an excess of instructions >> > > between >> > > the different calls to cos. This is what happens between the first >> > > two >> > > calls to cos: >> > > >> > > gcc: >> > > jmpq 400530 >> > > nop >> > > nopw %cs:0x0(%rax,%rax,1) >> > > >> > > sub $0x38,%rsp >> > > movsd %xmm0,0x10(%rsp) >> > > movapd %xmm1,%xmm0 >> > > movsd %xmm2,0x18(%rsp) >> > > movsd %xmm1,0x8(%rsp) >> > > callq 400530 >> > > >> > > ocamlopt: >> > > >> > > callq 401a60 >> > > mulsd (%r12),%xmm0 >> > > movsd %xmm0,0x10(%rsp) >> > > sub $0x10,%r15 >> > > lea 0x25c7b6(%rip),%rax >> > > cmp (%rax),%r15 >> > > jb 404a8a >> > > lea 0x8(%r15),%rax >> > > movq $0x4fd,-0x8(%rax) >> > > >> > > movsd 0x32319(%rip),%xmm1 >> > > >> > > movapd %xmm1,%xmm2 >> > > mulsd %xmm0,%xmm2 >> > > addsd 0x0(%r13),%xmm2 >> > > movsd %xmm2,(%rax) >> > > movapd %xmm1,%xmm0 >> > > mulsd (%r12),%xmm0 >> > > addsd (%rbx),%xmm0 >> > > callq 401a60 >> > > >> > > >> > > Is this caused by some underlying difference in the representation >> > > of >> > > numeric values (i.e. tagged ints) or is it reasonable to attack >> > > this >> > > issue as a hobby experiment? >> > > >> > > >> > > thanks for any advice, >> > > >> > > Christoph >> > > >> > >> -- >> ------------------------------------------------------------ >> Gerd Stolpmann, Darmstadt, Germany gerd@gerd-stolpmann.de >> My OCaml site: http://www.camlcity.org >> Contact details: http://www.camlcity.org/contact.html >> Company homepage: http://www.gerd-stolpmann.de >> ------------------------------------------------------------ >> >> >