On Wed, Feb 24, 2021 at 11:53:34PM +0000, deadalnix via Digitalmars-d wrote:
> On Wednesday, 24 February 2021 at 22:12:46 UTC, Atila Neves wrote:
> > On Tuesday, 23 February 2021 at 14:41:59 UTC, James Lu wrote:
> > The linker can be a bottleneck, yes, especially since it doesn't do
> > work in parallel. But in my experience, if the linker takes a while,
> > compiling took a lot longer still. Of course, any improvements in
> > this area are welcome, and I hope mold is production-ready as soon
> > as possible.
> 
> This is true for a fresh build, but often not the case for incremental builds, which dev often have to go through. This is because the work you have to do for sources grows with the size of the changeset, while the work you have to do link grows with the size of the project as a whole, changed or not. On large projects, it is very common that linking dominates incremental builds.
[...]

This is very interesting.  I wonder if there's a way to incrementally update the executable, instead of starting from scratch each time?

E.g., hypothetically, if the linker emitted not only the executable but also some kind of map file describing the various parts that compose the executable, together with some extra information about offsets/addresses that depend on each other between parts, then in theory, if we change n object files (where n is significantly less than the total number N of all object files), we ought to be able to regenerate the executable by copying most of its current data, move a few sections around, and patch up some references.

If the executable format is flexible enough (I think ELF is, don't know about PE), we could also pad the executable with some extra unused space between sections to allow for growth of individual sections up to some limit. Then we might be able patch in updated object files in-place, along with updating some references as needed, as long as said object files don't grow beyond the size of the extra space.

This could significantly speed up the code-compile-run cycle during development.  For releases, of course, you'd want to compact the executable, but generally it's expected that release builds are OK to take longer.


T

-- 
Государство делает вид, что платит нам зарплату, а мы делаем вид, что работаем.

On Thursday, 25 February 2021 at 15:42:22 UTC, H. S. Teoh wrote:
> On Wed, Feb 24, 2021 at 11:53:34PM +0000, deadalnix via Digitalmars-d wrote:
>> [...]
> [...]
>
> This is very interesting.  I wonder if there's a way to incrementally update the executable, instead of starting from scratch each time?
>
> [...]

I'm more interested in a "JIT" that remembers object-file-to-in-memory-function-pointers and overwrites them with trampolines. You could use fork() to make a reloadable executable that way. Of course, you'd need a new function loading system, which could be difficult...

On Thursday, 25 February 2021 at 15:42:22 UTC, H. S. Teoh wrote:
> This is very interesting.  I wonder if there's a way to incrementally update the executable, instead of starting from scratch each time?

Zig has that: https://kristoff.it/blog/zig-new-relationship-llvm/#in-place-binary-patching

On 2/24/2021 3:53 PM, deadalnix wrote:
> This is true for a fresh build, but often not the case for incremental builds, which dev often have to go through. This is because the work you have to do for sources grows with the size of the changeset, while the work you have to do link grows with the size of the project as a whole, changed or not. On large projects, it is very common that linking dominates incremental builds.
> 
> zld is another interesting project that tries to do enable incremental linking: https://github.com/kubkon/zld
> 
> Just like mold, it is fairly new and probably not battle tested enough for production yet.

Optlink could do a full link faster than MS-Link could do an incremental link.

On Thursday, 25 February 2021 at 15:42:22 UTC, H. S. Teoh wrote:
>
> This is very interesting.  I wonder if there's a way to incrementally update the executable, instead of starting from scratch each time?

The author of mold has a section on incremental linking in the readme under "Rejected Ideas":

https://github.com/rui314/mold#rejected-ideas

On Friday, 26 February 2021 at 01:52:04 UTC, Walter Bright wrote:
> Optlink could do a full link faster than MS-Link could do an incremental link.

I wonder if you could explain to us how to port Optlink to ELF and Mach-O, if porting would be possible.

On Thursday, 25 February 2021 at 15:42:22 UTC, H. S. Teoh wrote:
> This is very interesting.  I wonder if there's a way to incrementally update the executable, instead of starting from scratch each time?
>
> E.g., hypothetically, if the linker emitted not only the executable but also some kind of map file describing the various parts that compose the executable, together with some extra information about offsets/addresses that depend on each other between parts, then in theory, if we change n object files (where n is significantly less than the total number N of all object files), we ought to be able to regenerate the executable by copying most of its current data, move a few sections around, and patch up some references.
>
> If the executable format is flexible enough (I think ELF is, don't know about PE), we could also pad the executable with some extra unused space between sections to allow for growth of individual sections up to some limit. Then we might be able patch in updated object files in-place, along with updating some references as needed, as long as said object files don't grow beyond the size of the extra space.
>
> This could significantly speed up the code-compile-run cycle during development.  For releases, of course, you'd want to compact the executable, but generally it's expected that release builds are OK to take longer.
>
>
> T

https://github.com/kubkon/zld

It is still quite experimental. Author have written about the techniques they use. There are very interesting things they do both for speed (like preloading .o as soon as they finish compiling in a daemon) and incremental link (this require to maintain extra metadata about where things are).

See https://kristoff.it/blog/zig-new-relationship-llvm/#designing-machine-code-for-incremental-compilation for more details on how this works.

On Friday, 26 February 2021 at 01:52:04 UTC, Walter Bright wrote:
> On 2/24/2021 3:53 PM, deadalnix wrote:
>> This is true for a fresh build, but often not the case for incremental builds, which dev often have to go through. This is because the work you have to do for sources grows with the size of the changeset, while the work you have to do link grows with the size of the project as a whole, changed or not. On large projects, it is very common that linking dominates incremental builds.
>> 
>> zld is another interesting project that tries to do enable incremental linking: https://github.com/kubkon/zld
>> 
>> Just like mold, it is fairly new and probably not battle tested enough for production yet.
>
> Optlink could do a full link faster than MS-Link could do an incremental link.

That is also the position of the mold guy. He think that the extra work to do incremental linking offset the gains so decided to not even try to do it.

Hard to know which is right.

On 2/25/2021 6:26 PM, deadalnix wrote:
> On Friday, 26 February 2021 at 01:52:04 UTC, Walter Bright wrote:
>> Optlink could do a full link faster than MS-Link could do an incremental link.
> 
> That is also the position of the mold guy. He think that the extra work to do incremental linking offset the gains so decided to not even try to do it.
> 
> Hard to know which is right.

Incremental linking also tends to suffer from all kinds of weird bugs. Enough so that one tends to give up and go full linking anyway.

On Wednesday, 24 February 2021 at 23:53:34 UTC, deadalnix wrote:
> On Wednesday, 24 February 2021 at 22:12:46 UTC, Atila Neves wrote:
>> On Tuesday, 23 February 2021 at 14:41:59 UTC, James Lu wrote:
>> The linker can be a bottleneck, yes, especially since it doesn't do work in parallel. But in my experience, if the linker takes a while, compiling took a lot longer still. Of course, any improvements in this area are welcome, and I hope mold is production-ready as soon as possible.
>>
>
> This is true for a fresh build, but often not the case for incremental builds, which dev often have to go through.

I only really care about incremental builds. Fresh builds should be rare, and if they're not, I don't understand that workflow.

> This is because the work you have to do for sources grows with the size of the changeset, while the work you have to do link grows with the size of the project as a whole, changed or not. On large projects, it is very common that linking dominates incremental builds.

It can, yes, and any improvements there will be very welcome.

> zld is another interesting project that tries to do enable incremental linking: https://github.com/kubkon/zld

Nice. I wrote a D program once that used the linker as a server and kept "sending" it object files that it kept on relinking, but unfortunately that didn't speed anything up.