On May 28, 2015, at 5:42 PM, Sean Silva <chisophugis at gmail.com> wrote:> I guess, looking back at Nick's comment: > > "The atom model is a good fit for the llvm compiler model for all architectures. There is a one-to-one mapping between llvm::GlobalObject (e.g. function or global variable) and lld:DefinedAtom." > > it seems that the primary issue on the ELF/COFF side is that currently the LLVM backends are taking a finer-grained atomicity that is present inside LLVM, and losing information by converting that to a coarser-grained atomicity that is the typical "section" in ELF/COFF. > But doesn't -ffunction-sections -fdata-sections already fix this, basically? > > On the Mach-O side, the issue seems to be that Mach-O's notion of section carries more hard-coded meaning than e.g. ELF, so at the very least another layer of subdivision below what Mach-O calls "section" would be needed to preserve this information; currently symbols are used as a bit of a hack as this "sub-section" layer.I’m not sure what you mean here.> > So the problem seems to be that the transport format between the compiler and linker varies by platform, and each one has a different way to represent things, some can't represent everything we want to do, apparently.Yes!> BUT it sounds like at least relocatable ELF semantics can, in principle, represent everything that we can imagine an "atom-based file format"/"native format" to want to represent. Just to play devil's advocate here, let's start out with the "native format" being relocatable ELF - on *all platforms*. Relocatable object files are just a transport format between compiler and linker, after all; who cares what we use? If the alternative is a completely new format, then bootstrapping from relocatable ELF is strictly less churn/tooling cost. > > People on the "atom side of the fence", what do you think? Is there anything that we cannot achieve by saying "native"="relocatable ELF"?1) Turns out .o files are written once but read many times by the linker. Therefore, the design goal of .o files should be that they are as fast to read/parse in the linker as possible. Slowing down the compiler to make a .o file that is faster for the linker to read is a good trade off. This is the motivation for the native format - not that it is a universal format. 2) I think the ELF camp still thinks that linkers are “dumb”. That they just collate .o files into executable files. The darwin linker does a lot of processing/optimizing the content (e.g. Objective-C optimizing, dead stripping, function/data re-ordering). This is why atom level granularity is needed. For darwin, ELF based .o files is not interesting. It won’t be faster, and it will take a bunch of effort to figure out how to encode all the mach-o info into ELF. We’d rather wait for a new native format. -Nick -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150528/fb195718/attachment.html>
On Thu, May 28, 2015 at 6:25 PM, Nick Kledzik <kledzik at apple.com> wrote:> > On May 28, 2015, at 5:42 PM, Sean Silva <chisophugis at gmail.com> wrote: > > I guess, looking back at Nick's comment: > > "The atom model is a good fit for the llvm compiler model for all > architectures. There is a one-to-one mapping between llvm::GlobalObject > (e.g. function or global variable) and lld:DefinedAtom." > > it seems that the primary issue on the ELF/COFF side is that currently the > LLVM backends are taking a finer-grained atomicity that is present inside > LLVM, and losing information by converting that to a coarser-grained > atomicity that is the typical "section" in ELF/COFF. > But doesn't -ffunction-sections -fdata-sections already fix this, > basically? > > On the Mach-O side, the issue seems to be that Mach-O's notion of section > carries more hard-coded meaning than e.g. ELF, so at the very least another > layer of subdivision below what Mach-O calls "section" would be needed to > preserve this information; currently symbols are used as a bit of a hack as > this "sub-section" layer. > > I’m not sure what you mean here. > > > So the problem seems to be that the transport format between the compiler > and linker varies by platform, and each one has a different way to > represent things, some can't represent everything we want to do, apparently. > > Yes! > > > BUT it sounds like at least relocatable ELF semantics can, in principle, > represent everything that we can imagine an "atom-based file > format"/"native format" to want to represent. Just to play devil's > advocate here, let's start out with the "native format" being relocatable > ELF - on *all platforms*. Relocatable object files are just a transport > format between compiler and linker, after all; who cares what we use? If > the alternative is a completely new format, then bootstrapping from > relocatable ELF is strictly less churn/tooling cost. > > People on the "atom side of the fence", what do you think? Is there > anything that we cannot achieve by saying "native"="relocatable ELF"? > > 1) Turns out .o files are written once but read many times by the linker. > Therefore, the design goal of .o files should be that they are as fast to > read/parse in the linker as possible. Slowing down the compiler to make a > .o file that is faster for the linker to read is a good trade off. This is > the motivation for the native format - not that it is a universal format. >Whenever this has come up, Rafael has always told me that (at least in the context of ELF) that the current file format isn't a problem in this regard. Maybe you guys should talk?> > 2) I think the ELF camp still thinks that linkers are “dumb”. That they > just collate .o files into executable files. The darwin linker does a lot > of processing/optimizing the content (e.g. Objective-C optimizing, dead > stripping, function/data re-ordering). This is why atom level granularity > is needed. >As has been mentioned elsewhere in the thread, ELF is able to represent atoms (in fact, something more general). So I guess this just leaves us with that you think that current object file formats are too slow to read? That begs for some numbers.> > For darwin, ELF based .o files is not interesting. It won’t be faster, > and it will take a bunch of effort to figure out how to encode all the > mach-o info into ELF. >I was playing devil's advocate with the concrete ELF suggestion, but I think that it wouldn't be really any different amount of effort vs encoding it in a "native" format. I mean, in the worst case you can just make a custom section in the ELF file and put whatever you want in there, while keeping the rest of the file structure for the bulk of the object. ELF has very much a "bag of bytes" approach, so layering any semantics on top should be pretty easy. -- Sean Silva> We’d rather wait for a new native format. > > -Nick > >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150528/44869a6a/attachment.html>
On Thu, May 28, 2015 at 6:25 PM, Nick Kledzik <kledzik at apple.com> wrote:> > On May 28, 2015, at 5:42 PM, Sean Silva <chisophugis at gmail.com> wrote: > > I guess, looking back at Nick's comment: > > "The atom model is a good fit for the llvm compiler model for all > architectures. There is a one-to-one mapping between llvm::GlobalObject > (e.g. function or global variable) and lld:DefinedAtom." > > it seems that the primary issue on the ELF/COFF side is that currently the > LLVM backends are taking a finer-grained atomicity that is present inside > LLVM, and losing information by converting that to a coarser-grained > atomicity that is the typical "section" in ELF/COFF. > But doesn't -ffunction-sections -fdata-sections already fix this, > basically? > > On the Mach-O side, the issue seems to be that Mach-O's notion of section > carries more hard-coded meaning than e.g. ELF, so at the very least another > layer of subdivision below what Mach-O calls "section" would be needed to > preserve this information; currently symbols are used as a bit of a hack as > this "sub-section" layer. > > I’m not sure what you mean here. > > > So the problem seems to be that the transport format between the compiler > and linker varies by platform, and each one has a different way to > represent things, some can't represent everything we want to do, apparently. > > Yes! > > > BUT it sounds like at least relocatable ELF semantics can, in principle, > represent everything that we can imagine an "atom-based file > format"/"native format" to want to represent. Just to play devil's > advocate here, let's start out with the "native format" being relocatable > ELF - on *all platforms*. Relocatable object files are just a transport > format between compiler and linker, after all; who cares what we use? If > the alternative is a completely new format, then bootstrapping from > relocatable ELF is strictly less churn/tooling cost. > > People on the "atom side of the fence", what do you think? Is there > anything that we cannot achieve by saying "native"="relocatable ELF"? > > 1) Turns out .o files are written once but read many times by the linker. > Therefore, the design goal of .o files should be that they are as fast to > read/parse in the linker as possible. Slowing down the compiler to make a > .o file that is faster for the linker to read is a good trade off. This is > the motivation for the native format - not that it is a universal format. >I don't think that switching from ELF to something new can make linkers significantly faster. We need to handle ELF files carefully not to waste time on initial load, but if you do, reading data required for symbol resolution from ELF file should be satisfactory fast (I did that for COFF -- the current "atom-based ELF" linker is doing too much things in an initial load, like read all relocation tables, splitting indivisble chunk of data and connect them with "indivisible" edges, etc.) Looks like we read symbol table pretty quickly in the new implementation, and the bottleneck of it is now the time to insert symbols into the symbol hash table -- which you cannot make faster by changing object file format. Speaking of the performance, if I want to make a significant difference, I'd focus on introducing new symbol resolution semantics. Especially, the Unix linker semantics is pretty bad for performance because we have to visit files one by one serially and possibly repeatedly. It's not only bad for parallelism but also for a single-thread case because it increase size of data to be processed. This is I believe the true bottleneck of Unix linkers. Tackling that problem seems to be most important to me, and "ELF as a file format is slow" is still an unproved thing to me.> > 2) I think the ELF camp still thinks that linkers are “dumb”. That they > just collate .o files into executable files. The darwin linker does a lot > of processing/optimizing the content (e.g. Objective-C optimizing, dead > stripping, function/data re-ordering). This is why atom level granularity > is needed. >I think that all these things are doable (and are being done) using -ffunction-sections.> > For darwin, ELF based .o files is not interesting. It won’t be faster, > and it will take a bunch of effort to figure out how to encode all the > mach-o info into ELF. We’d rather wait for a new native format. >> -Nick > > > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev > >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150528/d29ccbe8/attachment.html>
I want to make it clear that I didn't (at least intend to) compromise flexibility or beauty of design with short-term performance gain. I was trying to do simple things in a simple way for both humans and computers, and I believe I did that fairly well. I'd even argue that the new design is cleaner and more expressive than before, because the "atom" model is in some part too detailed and restrictive on how to represent data and relations between symbols, particularly how to represent relocations. It also lacked capability of representing indivisible memory areas having multiple names. After I wrote up the first patch, I realized that the goal of the code is somewhat similar to what the atom model aims to achieve, with some differences. I assume that you have read the readme file for the new port. The differences are - An atom has only one name, but the new "chunk" can have one or more symbols referring that. But the actual difference is that chunks are agnostic of symbols referring them in the new design. I have separated actual data from symbols to get more flexibility. And that flexibility enabled me to achieve better performance by writing more abstract code which reads less data. - In the atom model, we have detailed information about relocations, including relocation target, offset, etc, for each atom. In the new design, we don't have them. Instead, we have just a set of symbols for each chunk that needs to be resolved to include that input chunk properly. This is more abstract and flexible than the existing design. - The atom model reads too much data from files prematurely to construct a complete graph, while the new design avoided that. This is partly an implementation's issue, but partly unavoidable, because we actually needed to build more complex data structure. - And this might be stemmed from the implementation and not from the model itself, but the thing is that it's hard to write code for the atom model because their data types have too much detailed relations with other types. For example, any atom in the model has to have a "file" that an atom was created from. This makes it hard to append linker-generated data to output which don't have a source file (we ended up having a notion of "virtual input file" that doesn't do anything meaningful itself.). Another example is that, if you want to create a symbol on-demand, you've got to create a "virtual archive" file that returns a "virtual file" containing one "virtual atom" when the archive file is asked for that symbol. In the new design, it can be expressed in one line of code instead of multiple class definitions and object juggling. Also, because relocations are explicitly represented as "references" in the atom model, we've got to create platform-specific relocation objects even for linker-generated data if it refers some other symbols, and let a platform-specific relocation function to consume that data to apply relocations. That's less abstracted than the new design, in which all classes but the actual data type needs to know about relocations are agnostic about how relocations are represented and how to actually apply them. Besides them, I'd say from my experiences of working on the atom model, the new model's ability is not that different from the atom model. They are different, there are pros and cons, and I don't agree that the atom model is more flexible or conceptually better. On Thu, May 28, 2015 at 8:22 PM, Rui Ueyama <ruiu at google.com> wrote:> On Thu, May 28, 2015 at 6:25 PM, Nick Kledzik <kledzik at apple.com> wrote: > >> >> On May 28, 2015, at 5:42 PM, Sean Silva <chisophugis at gmail.com> wrote: >> >> I guess, looking back at Nick's comment: >> >> "The atom model is a good fit for the llvm compiler model for all >> architectures. There is a one-to-one mapping between llvm::GlobalObject >> (e.g. function or global variable) and lld:DefinedAtom." >> >> it seems that the primary issue on the ELF/COFF side is that currently >> the LLVM backends are taking a finer-grained atomicity that is present >> inside LLVM, and losing information by converting that to a coarser-grained >> atomicity that is the typical "section" in ELF/COFF. >> But doesn't -ffunction-sections -fdata-sections already fix this, >> basically? >> >> On the Mach-O side, the issue seems to be that Mach-O's notion of section >> carries more hard-coded meaning than e.g. ELF, so at the very least another >> layer of subdivision below what Mach-O calls "section" would be needed to >> preserve this information; currently symbols are used as a bit of a hack as >> this "sub-section" layer. >> >> I’m not sure what you mean here. >> >> >> So the problem seems to be that the transport format between the compiler >> and linker varies by platform, and each one has a different way to >> represent things, some can't represent everything we want to do, apparently. >> >> Yes! >> >> >> BUT it sounds like at least relocatable ELF semantics can, in principle, >> represent everything that we can imagine an "atom-based file >> format"/"native format" to want to represent. Just to play devil's >> advocate here, let's start out with the "native format" being relocatable >> ELF - on *all platforms*. Relocatable object files are just a transport >> format between compiler and linker, after all; who cares what we use? If >> the alternative is a completely new format, then bootstrapping from >> relocatable ELF is strictly less churn/tooling cost. >> >> People on the "atom side of the fence", what do you think? Is there >> anything that we cannot achieve by saying "native"="relocatable ELF"? >> >> 1) Turns out .o files are written once but read many times by the >> linker. Therefore, the design goal of .o files should be that they are as >> fast to read/parse in the linker as possible. Slowing down the compiler to >> make a .o file that is faster for the linker to read is a good trade off. >> This is the motivation for the native format - not that it is a universal >> format. >> > > I don't think that switching from ELF to something new can make linkers > significantly faster. We need to handle ELF files carefully not to waste > time on initial load, but if you do, reading data required for symbol > resolution from ELF file should be satisfactory fast (I did that for COFF > -- the current "atom-based ELF" linker is doing too much things in an > initial load, like read all relocation tables, splitting indivisble chunk > of data and connect them with "indivisible" edges, etc.) Looks like we read > symbol table pretty quickly in the new implementation, and the bottleneck > of it is now the time to insert symbols into the symbol hash table -- which > you cannot make faster by changing object file format. > > Speaking of the performance, if I want to make a significant difference, > I'd focus on introducing new symbol resolution semantics. Especially, the > Unix linker semantics is pretty bad for performance because we have to > visit files one by one serially and possibly repeatedly. It's not only bad > for parallelism but also for a single-thread case because it increase size > of data to be processed. This is I believe the true bottleneck of Unix > linkers. Tackling that problem seems to be most important to me, and "ELF > as a file format is slow" is still an unproved thing to me. > > >> >> 2) I think the ELF camp still thinks that linkers are “dumb”. That they >> just collate .o files into executable files. The darwin linker does a lot >> of processing/optimizing the content (e.g. Objective-C optimizing, dead >> stripping, function/data re-ordering). This is why atom level granularity >> is needed. >> > > I think that all these things are doable (and are being done) using > -ffunction-sections. > > >> >> For darwin, ELF based .o files is not interesting. It won’t be faster, >> and it will take a bunch of effort to figure out how to encode all the >> mach-o info into ELF. We’d rather wait for a new native format. >> > > >> -Nick >> >> >> _______________________________________________ >> LLVM Developers mailing list >> LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu >> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev >> >> >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150529/2236a3ec/attachment.html>
> Speaking of the performance, if I want to make a significant difference, I'd > focus on introducing new symbol resolution semantics. Especially, the Unix > linker semantics is pretty bad for performance because we have to visit > files one by one serially and possibly repeatedly. It's not only bad for > parallelism but also for a single-thread case because it increase size of > data to be processed. This is I believe the true bottleneck of Unix linkers. > Tackling that problem seems to be most important to me, and "ELF as a file > format is slow" is still an unproved thing to me.It is more than unproven. It is proven wrong. Short of your new COFF linker, gold is ELF only and the fastest linker around. We have a badly designed ELF linker. That is hardly ELF's fault. Cheers, Rafael
> 2) I think the ELF camp still thinks that linkers are “dumb”. That they > just collate .o files into executable files. The darwin linker does a lot > of processing/optimizing the content (e.g. Objective-C optimizing, dead > stripping, function/data re-ordering). This is why atom level granularity > is needed.If there is any linker in here that is dumb that is the old lld. It reads parts of the file it doesn't need, it can't optimize exception frames, --gc-section is not working, strings are not tail merged and it takes about 2x the cpu time of gold even with gold doing all those things. Rui's new design finally given us the opportunity of making an useful linker out of lld. Cheers, Rafael
On Fri, May 29, 2015 at 6:46 AM Rafael Espíndola <rafael.espindola at gmail.com> wrote:> > 2) I think the ELF camp still thinks that linkers are “dumb”. That they > > just collate .o files into executable files. The darwin linker does a > lot > > of processing/optimizing the content (e.g. Objective-C optimizing, dead > > stripping, function/data re-ordering). This is why atom level > granularity > > is needed. > > If there is any linker in here that is dumb that is the old lld.Rafael, I know you're trying to make a point here, but I think this really pushes into name calling and putting down of work. Every project starts off slow and without features. I'm not trying to push one way or the other on the topic of this thread, I just think you should take a more charitable tone when describing the existing work that your colleagues in the open source community have done. Lots of lots of folks worked really hard on LLD up until now, and I think it is important to be more respectful of the hard work they put in. Even when things don't work out, or the code ends up not being as good as we need it to be, I want to make sure we show appropriate respect for the work that went into it. We should provide a technical critique, and try to make sure it isn't too easily misinterpreted as a critique of intentions, etc. -Chandler -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150529/2ac81df6/attachment.html>
On 28 May 2015 at 18:25, Nick Kledzik <kledzik at apple.com> wrote:> For darwin, ELF based .o files is not interesting. It won’t be faster, and > it will take a bunch of effort to figure out how to encode all the mach-o > info into ELF. We’d rather wait for a new native format.Practically, you're almost certainly right (in terms of development costs to a temporary solution). But from a personal level I would much prefer an ELF-based Darwin to the status quo. I think Darwin suffers greatly from being based on MachO, which isn't something I could say about Linux/ELF. There are far too many implicit contracts between tools.> We’d rather wait for a new native format.Assuming a good one comes along. Tim.
On 29 May 2015 at 18:48, Tim Northover <t.p.northover at gmail.com> wrote:>I think Darwin suffers > greatly from being based on MachO, which isn't something I could say > about Linux/ELF.P.S. This is by no means intended to belittle the work of the people who've created MachO in its current form. Given what you started with (an object format with *16*(!!!!!) possible relocations, for example) you've done miracles. But the end result is not optimal, and probably a guide for the rest of us on what to avoid. Tim.