From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!.POSTED!not-for-mail From: Mikael Djurfeldt Newsgroups: gmane.lisp.guile.devel Subject: Re: Native code generation and gcc Date: Sun, 11 Dec 2016 19:09:07 +0100 Message-ID: References: <878truxsbg.fsf@fimbulvetr.bsc.es> Reply-To: mikael@djurfeldt.com NNTP-Posting-Host: blaine.gmane.org Mime-Version: 1.0 Content-Type: multipart/alternative; boundary=001a114cd348269501054365e2dd X-Trace: blaine.gmane.org 1481479864 6858 195.159.176.226 (11 Dec 2016 18:11:04 GMT) X-Complaints-To: usenet@blaine.gmane.org NNTP-Posting-Date: Sun, 11 Dec 2016 18:11:04 +0000 (UTC) Cc: Andy Wingo To: guile-devel Original-X-From: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Sun Dec 11 19:10:58 2016 Return-path: Envelope-to: guile-devel@m.gmane.org Original-Received: from lists.gnu.org ([208.118.235.17]) by blaine.gmane.org with esmtp (Exim 4.84_2) (envelope-from ) id 1cG8aN-0008Ho-1z for guile-devel@m.gmane.org; Sun, 11 Dec 2016 19:10:55 +0100 Original-Received: from localhost ([::1]:56625 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1cG8aP-0002Uv-2e for guile-devel@m.gmane.org; Sun, 11 Dec 2016 13:10:57 -0500 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:56971) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1cG8a2-0002Ud-QM for guile-devel@gnu.org; Sun, 11 Dec 2016 13:10:36 -0500 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1cG8Zz-0005XJ-HI for guile-devel@gnu.org; Sun, 11 Dec 2016 13:10:34 -0500 Original-Received: from mail-wm0-f67.google.com ([74.125.82.67]:34217) by eggs.gnu.org with esmtps (TLS1.0:RSA_AES_128_CBC_SHA1:16) (Exim 4.71) (envelope-from ) id 1cG8Zz-0005N1-6M for guile-devel@gnu.org; Sun, 11 Dec 2016 13:10:31 -0500 Original-Received: by mail-wm0-f67.google.com with SMTP id g23so6310419wme.1 for ; Sun, 11 Dec 2016 10:10:09 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:reply-to:sender:in-reply-to:references:from:date :message-id:subject:to:cc; bh=Wu/166fMLLBP7DAolcEasw6JiiikWWcebW/I4BVbJn4=; b=n8HfRdILmbUY6tgB458I5ajuiiQCiNOLRqTzMTW2NigwwLpe93zs+lS1hy+UTRAboD Mde05SLMP45zlWmUSxvP45YHFim55K24SpH9cNj5WA9SONIr5/DNEuiXLAUlJMEQYot2 jDt+PIXWL9iMjH1y0U8zpSUNX+UQ+hiNhe+RJrJg8d8cEXFAWOBp7gjG5O8ngAfY4eiX K86vxw07Q6qD8Y3dV0CMw0NEZpB/hfchL7hg77zd6mpnX8maRVSCIXauwtabNxK5Fwb2 KeBiaUO0QBf2QOSl8wSlVuvD7b7hFYyQ7l4UMoQQxUN0PSQZOQsF+Ap/FEYhNiOf0mR6 tkZA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:reply-to:sender:in-reply-to :references:from:date:message-id:subject:to:cc; bh=Wu/166fMLLBP7DAolcEasw6JiiikWWcebW/I4BVbJn4=; b=MwAzif/Zwa7EIdIHaCO6X/pGeMWpFAHJFe1ozRWjP8DD/EbbH7QwEYUDiiUKe61zNK YDJNjXgKEDtXjTPQ/G7ubl9G5Sh205Cu/BOUNtBxO+Ks2Ri8geJoHJyyfjZfns40Ebtu CmONJ4QiOrDpYMnNCIx3AL8uOWVBBC7g3/LhhriCP0KXO7TV5oFHl6K6Dn7UUxdTBXzU HzlcF9qp5nr/2L4YmsskR9AMC4m8mSm31pFgRM0jRdfxvj6hvYbMRvrj7M/X53+2/UaO zKilx8BbHBj552XpmUQIZE4iG/rln/mKebr2owVBmp+L6VWO+U9rHruVau4lTytljNI1 8hPA== X-Gm-Message-State: AKaTC03aVazzmD/cxbQlUnDItoc2OS9duIoydSqcTALA2LtHemppuBhzxU7/EH6xf0fSmyrP34CDP2U6dvyJkQ== X-Received: by 10.28.161.67 with SMTP id k64mr6656334wme.69.1481479748488; Sun, 11 Dec 2016 10:09:08 -0800 (PST) Original-Received: by 10.80.131.199 with HTTP; Sun, 11 Dec 2016 10:09:07 -0800 (PST) In-Reply-To: <878truxsbg.fsf@fimbulvetr.bsc.es> X-Google-Sender-Auth: -yV5OxB9adxLnIxbqKwZ5Xr6gVo X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.2.x-3.x [generic] [fuzzy] X-Received-From: 74.125.82.67 X-BeenThere: guile-devel@gnu.org X-Mailman-Version: 2.1.21 Precedence: list List-Id: "Developers list for Guile, the GNU extensibility library" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: guile-devel-bounces+guile-devel=m.gmane.org@gnu.org Original-Sender: "guile-devel" Xref: news.gmane.org gmane.lisp.guile.devel:18786 Archived-At: --001a114cd348269501054365e2dd Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable Many thanks for these links! It seems like the GCC JIT interface is the kind of "adaptation" of gcc which I asked for. :-) Then there's the calling convention problem which Helmut brough up earlier in this thread. But I guess there could be workarounds. In any case one would have to look closer regarding this. Regarding "hotness": The original GOOPS implementation had a somewhat crazy feature that an application of a generic function to a specific argument list first resulted in the standard MOP procedure for finding a set of applicable methods and, second, from this/these generated something called a "cmethod" (compiled method) which, in turn, was stored in a cache as well as applied to the list of arguments. Next time this generic function was applied to an argument list with the same type signature, the *same* cmethod as had been used the first time could be very quickly looked up in the cache. (This lookup is described in doc/goops.mail in the repository.) The thought behind this was that when a cmethod is compiled, there is knowledge about the specific types of the arguments. This means that a compiler which compiles the applicable method into a cmethod can do some of the type dispatch during compile time, for example that of slot access. This is partially equivalent to unboxing, but more general, since some of the *generic function applications* can have their type dispatch resolved at compile time too. In the most ambitious approach one would include return values in the cmethod type signature---something which is natural to do when compiling to cps. (This type dispatch elimination was never implemented in GOOPS.) I was curious how much impact this caching scheme of things would have in real-world programs. It turned out to work very well. I'm only aware of one complaint on memory use. Obviously, though, if a generic function with a longer argument list is repeatedly called with different type signatures of the argument list, this could lead to a combinatorial explosion and fill up memory (as well as being rather inefficient). When Andy re-wrote GOOPS for the new compiler, the cmethod caching was removed---a sensible thing to do in my mind. *But*, some of the downsides of this scheme could be removed if hotness counting was added to the cache. One could do it in various ways. One could be to initially just associate the argument list type signature with a counter. If this counter reaches a certain threshold, the applicable method(s) is/are compiled into a cmethod stored in the cache. The storage of type signatures and counters still has the combinatorial explosion problem. This could now be avoided by limiting the size of the cache such that the counters compete for available space. (There are further issues to consider such as adaptability through forgetting, but I won't make this discussion even more complicated.) Best regards, Mikael On Mon, Dec 5, 2016 at 5:18 PM, Llu=C3=ADs Vilanova w= rote: > Mikael Djurfeldt writes: > > > [I apologize beforehand for being completely out of context.] > > Are there fundamental reasons for not re-using the gcc backends for > native code generation? I'm thinking of the (im?)possibility to convert t= he > cps to some of the intermediate languages of gcc. > > > If it wouldn't cause bad constraints the obvious gain is the many > targets (for free), the gcc optimizations, not having to maintain backend= s > and free future development. > > > Of course, there's the practical problem that gcc needs to be adapted > for this kind of use---but shouldn't it be adapted that way anyway? :) > > > Just an (old) idea... > > > Mikael > > Guile 2.1 has a register-base bytecode VM that makes using a code > generation > library like GNU lightning [1] a convenient alternative. In fact, that's > the > library used by nash [2] (an experimental Guile VM that generates native > code > for hot routines). You also have the experimental GCC JIT interface [3] t= o > achieve similar goals (available upstream since GCC 5, I think). > > IMO, if guile wants to go the tracing JIT way (like nash), it should stor= e > the > CPS representation of routines to be able to iteratively apply more > heavy-weight > optimizations as the routine becomes hotter (called more frequently). > > For example, you could start with the current state. If the routine is > called > many times with the same argument types, you can create a version > specialized > for these types, opening more unboxing possibilities (the routine entry > point > would then have to be a version dispatcher). If a routine version later > becomes > hotter, re-compile that version into native code. > > One open question is whether the VM needs to be changed to count routine > "hotness" efficiently (as in nash), or if a simple routine prelude > inserted by > guile's compiler tower could do that almost as efficiently (the bytecode > ISA > might need new atomic integer operations to cope with routine tracing in = a > multi-threaded app). > > Also, these all are no small tasks. > > [1] https://www.gnu.org/software/lightning/ > [2] https://github.com/8c6794b6/guile-tjit > [3] https://gcc.gnu.org/wiki/JIT > > Cheers, > Lluis > --001a114cd348269501054365e2dd Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable
Many thanks for these links!

I= t seems like the GCC JIT interface is the kind of "adaptation" of= gcc which I asked for. :-)

Then there's the calling conve= ntion problem which Helmut brough up earlier in this thread. But I guess th= ere could be workarounds. In any case one would have to look closer regardi= ng this.

Regarding "hotness":

The original GOOPS implementation had a somewhat crazy feature that an app= lication of a generic function to a specific argument list first resulted i= n the standard MOP procedure for finding a set of applicable methods and, s= econd, from this/these generated something called a "cmethod" (co= mpiled method) which, in turn, was stored in a cache as well as applied to = the list of arguments.

Next time this generic function wa= s applied to an argument list with the same type signature, the *same* cmet= hod as had been used the first time could be very quickly looked up in the = cache. (This lookup is described in doc/goops.mail in the repository.)
<= /div>

The thought behind this was that when a cmethod is= compiled, there is knowledge about the specific types of the arguments. Th= is means that a compiler which compiles the applicable method into a cmetho= d can do some of the type dispatch during compile time, for example that of= slot access. This is partially equivalent to unboxing, but more general, s= ince some of the *generic function applications* can have their type dispat= ch resolved at compile time too. In the most ambitious approach one would i= nclude return values in the cmethod type signature---something which is nat= ural to do when compiling to cps. (This type dispatch elimination was never= implemented in GOOPS.)

I was curious how much impact this caching s= cheme of things would have in real-world programs. It turned out to work ve= ry well. I'm only aware of one complaint on memory use. Obviously, thou= gh, if a generic function with a longer argument list is repeatedly called = with different type signatures of the argument list, this could lead to a c= ombinatorial explosion and fill up memory (as well as being rather ineffici= ent).

When Andy re-wrote GOOPS for the new com= piler, the cmethod caching was removed---a sensible thing to do in my mind.= *But*, some of the downsides of this scheme could be removed if hotness co= unting was added to the cache. One could do it in various ways. One could b= e to initially just associate the argument list type signature with a count= er. If this counter reaches a certain threshold, the applicable method(s) i= s/are compiled into a cmethod stored in the cache. The storage of type sign= atures and counters still has the combinatorial explosion problem. This cou= ld now be avoided by limiting the size of the cache such that the counters = compete for available space. (There are further issues to consider such as = adaptability through forgetting, but I won't make this discussion even = more complicated.)

Best regards,
Mikael

On Mon, Dec 5, 2016 at 5:18 PM, Llu=C3=ADs Vilanova <vilanova@ac.u= pc.edu> wrote:
Mikael Djurfeldt writes:

> [I apologize beforehand for being completely out of context.]
> Are there fundamental reasons for not re-using the gcc backends for na= tive code generation? I'm thinking of the (im?)possibility to convert t= he cps to some of the intermediate languages of gcc.

> If it wouldn't cause bad constraints the obvious gain is the many = targets (for free), the gcc optimizations, not having to maintain backends = and free future development.

> Of course, there's the practical problem that gcc needs to be adap= ted for this kind of use---but shouldn't it be adapted that way anyway?= :)

> Just an (old) idea...

> Mikael

Guile 2.1 has a register-base bytecode VM that makes using a co= de generation
library like GNU lightning [1] a convenient alternative. In fact, that'= s the
library used by nash [2] (an experimental Guile VM that generates native co= de
for hot routines). You also have the experimental GCC JIT interface [3] to<= br> achieve similar goals (available upstream since GCC 5, I think).

IMO, if guile wants to go the tracing JIT way (like nash), it should store = the
CPS representation of routines to be able to iteratively apply more heavy-w= eight
optimizations as the routine becomes hotter (called more frequently).

For example, you could start with the current state. If the routine is call= ed
many times with the same argument types, you can create a version specializ= ed
for these types, opening more unboxing possibilities (the routine entry poi= nt
would then have to be a version dispatcher). If a routine version later bec= omes
hotter, re-compile that version into native code.

One open question is whether the VM needs to be changed to count routine "hotness" efficiently (as in nash), or if a simple routine prelud= e inserted by
guile's compiler tower could do that almost as efficiently (the bytecod= e ISA
might need new atomic integer operations to cope with routine tracing in a<= br> multi-threaded app).

Also, these all are no small tasks.

[1] https://www.gnu.org/software/lightning/
[2] https://github.com/8c6794b6/guile-tjit
[3] https://gcc.gnu.org/wiki/JIT

Cheers,
=C2=A0 Lluis

--001a114cd348269501054365e2dd--