From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 20740 invoked by alias); 25 Nov 2004 21:54:17 -0000 Mailing-List: contact gcc-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Archive: List-Post: List-Help: Sender: gcc-owner@gcc.gnu.org Received: (qmail 20722 invoked from network); 25 Nov 2004 21:54:12 -0000 Received: from unknown (HELO mx1.redhat.com) (66.187.233.31) by sourceware.org with SMTP; 25 Nov 2004 21:54:12 -0000 Received: from int-mx1.corp.redhat.com (int-mx1.corp.redhat.com [172.16.52.254]) by mx1.redhat.com (8.12.11/8.12.11) with ESMTP id iAPLsCCS011357; Thu, 25 Nov 2004 16:54:12 -0500 Received: from vpn50-42.rdu.redhat.com (vpn50-42.rdu.redhat.com [172.16.50.42]) by int-mx1.corp.redhat.com (8.11.6/8.11.6) with ESMTP id iAPLs6r20141; Thu, 25 Nov 2004 16:54:06 -0500 Subject: Re: profile-driven optimization and the linker? From: Jeffrey A Law Reply-To: law@redhat.com To: Dan Kegel Cc: GCC Mailing List , bastian@kde.org In-Reply-To: <41A63996.1020407@kegel.com> References: <41A620F5.5040209@kegel.com> <1101412168.13475.19.camel@localhost.localdomain> <41A63996.1020407@kegel.com> Content-Type: text/plain Organization: Red Hat, Inc Date: Thu, 25 Nov 2004 23:13:00 -0000 Message-Id: <1101419643.13475.69.camel@localhost.localdomain> Mime-Version: 1.0 Content-Transfer-Encoding: 7bit X-SW-Source: 2004-11/txt/msg01001.txt.bz2 On Thu, 2004-11-25 at 11:59 -0800, Dan Kegel wrote: > Jeffrey A Law wrote: > >>http://gcc.gnu.org/news/profiledriven.html doesn't mention > >>having ld reorder sections to improve locality of reference > >>of frequently called functions. Has that technique > >>been tried with gcc and binutils? > > > > Yes. I had some success with it a while back. > > Was that on static executables, or dynamically linked ones? I've done both at different times with different linker technologies. > > > With ELF it's not terribly hard since we can arrange for > > each function to be put in its own section. Thus you get > > to do function-level reordering by just twiddling a linker > > map. In fact, that's where -ffunction-sections name from. > > > > We had some hacks to gprof which would take profile data > > and build a linker map. That's the code that really needs > > to be improved. I never understood the gprof code well > > enough to do it right. > > I may take a whack at this in my copious free time. > Are any such hacks online, or shall I just start from scratch? I believe we put all the code into gprof, though I haven't followed it over time and it may have been removed. Basically there was two pieces to gprof. The first within gprof itself to produce an ordering of functions. That code will probably need to be rewritten (I never liked the way I did it and I never got the coalescing of information step done). The second piece was a simple shell script which took the ordering produced by gprof and created a linker script. Nothing too radical here. > I guess further discussion should be on the binutils mailing list. Probably. From a compiler standpoint I think all the pieces are in place. > I first heard of this technique about 1993 or so, when > Lee Hasiuk implemented it on MS-DOS. I did a lot of this kind of stuff in the early 90s -- back when a.out was still popular. With some assembler help we were able to do function level reordering even on a.out files. There's some awful memories... I have no idea if OMOS lives on or not. The gcc/gas/gprof stuff was done in the mid 90s. > http://mail.kde.org/pipermail/kde-optimize/2003-January/000108.html > describes something similar, but which only aimed at > increasing *disk* cache locality when paging in functions from > disk for the first call. We were primarily measuring TLB effects with ours -- page locality for disk access falls out from the obvious algorithms. Though IIRC we actually did better by first removing all the single call nodes from the graph and putting them into one contigious region, then applying the greedy algorithm on the rest of the call graph. > FWIW, Alan Cox mentioned the technique a couple weeks ago, > http://marc.theaimsgroup.com/?l=linux-kernel&m=109935741612533&w=2 > but didn't mention any code. I've heard of GNU Rope, but I've never seen any code... jeff