Sign in Join

Live chat for Free Pascal, Lazarus, Delphi and every Pascal programmer.

Mailing lists / fpc-devel / 2019-06

Inlining problem and LEB128

8 messages · 4 people · –

Reply by email Subscribe to this list Your subscription

Read-only archive. Use j and k to move between messages.

J. Gareth Moreton

This one is for Jonas in particular, but also to address a minor issue in general.

Currently, you can get away with specifying the "inline" directive for a function in just the implementation section of a unit, and the function will be inlined.  However, in some situations, this can cause compiler crashes which I believe is due to a mixture of the function no longer being inlined and the internal CRCs not changing, possibly due to a collision.  While collisions are ultimately unavoidable (for 32-bit hashes like CRC32, the chance of a collision occurring is 1 in 82,137... look up "Birthday attack" for more information), its effects can be mitigated with careful design.

Internally, inlined functions store a copy of their node tree in the compiled PPU file, and the pointer to this tree is nil if the function is not inlined, or was not able to be inlined (e.g. because of a recursive call).  The pointer is not always checked though, instead relying on a flag, and hence it's possible to trigger an EAccessViolation exception.  I may not have the details quite correct though - maybe Jonas can clarify.

The most robust solution, and the one originally proposed, is to demand that "inline" appears in the interface section, but this breaks a number of packages and RTL units and also hurts some cross-platform optimisation, where functions like SwapBuffers can be efficiently inlined on some platforms but not on others (by specifying "inline" in the appropriate implementation).

My solution to this is as follows... ALWAYS attempt to create a node tree (unless "noinline" is specified).  This is effectively auto-inlining, but routines are not inlined unless the explicit directive instructs the compiler to do so (or something like -O4 is specified and the compiler determines that a function should be inlined due to its shortness, say).  This would help mitigate the problem of the null node tree by causing the compiler to check said node tree and set the "cannot inline" flag when appropriate.

This isn't ideal though, as it would have two notable side-effects:

- General compilation will be slightly slower because of extra analysis on the node trees and copying them into the "inlined nodes" pointer.
- The compiled PPU files will increase in size significantly.

Some care with the design might be able to mitigate the slower compilation, such as not duplicating objects unless absolutely necessary (such as only when actually inlining a function into a caller, which will only occur if "inline" is specified or auto-inlining enabled) - the second issue is a bit trickier, and this is where the second subject comes into play.

You may remember that a few months ago, I attempted to shrink the size of PPU files by storing particular fields in LEB128 format, but this was suspended because it increased quick compilation time, despite it reducing the size of PPU files by over 10% (without using explicit compression algorithms).  However, preliminary tests on large projects (we used Lazarus as a test case) showed that the compilation time was about 3 seconds as compared to 2 seconds, while full compilation times were not adversely affected because the processing required to encode LEB128 values is vastly overshadowed by the compilation process in general.  Given it's unlikely that a user will quick-compile a project more than once a minute while coding, I would like to revisit this encoding proposal as a possible solution to the excessive PPU sizes that will result.  While storage is not a sacred commodity on desktop computers as it once was in the 80s and 90s, it is still a premium on some embedded platforms.

Gareth aka. Kit

P.S. If I've got my ideas of the problem completely incorrect, I humbly apologise, but hopefully I will come to properly understand the issue and a solution found.

P.P.S. Personally I actually like "inline" being in the implementation section because it's adjacent to the code that will actually be inlined and hence can be added or removed at the programmer's discretion based on what the function is doing, and as mentioned above, has a use in cross-platform optimisation.

---
This email has been checked for viruses by Avast antivirus software. https://www.avast.com/antivirus

Reply by email

Sven Barth
to J. Gareth Moreton
J. Gareth Moreton wrote 27 lines
This one is for Jonas in particular, but also to address a minor issue in general. Currently, you can get away with specifying the "inline" directive for a function in just the implementation section of a unit, and the function will be inlined.  However, in some situations, this can cause compiler crashes which I believe is due to a mixture of the function no longer being inlined and the internal CRCs not changing, possibly due to a collision.  While collisions are ultimately unavoidable (for 32-bit hashes like CRC32, the chance of a collision occurring is 1 in 82,137... look up "Birthday attack" for more information), its effects can be mitigated with careful design. Internally, inlined functions store a copy of their node tree in the compiled PPU file, and the pointer to this tree is nil if the function is not inlined, or was not able to be inlined (e.g. because of a recursive call).  The pointer is not always checked though, instead relying on a flag, and hence it's possible to trigger an EAccessViolation exception.  I may not have the details quite correct though - maybe Jonas can clarify. The most robust solution, and the one originally proposed, is to demand that "inline" appears in the interface section, but this breaks a number of packages and RTL units and also hurts some cross-platform optimisation, where functions like SwapBuffers can be efficiently inlined on some platforms but not on others (by specifying "inline" in the appropriate implementation).

It's not only the most robust, but also the most logical solution: "inline" tells the *caller* that the routine can be inlined. Thus for cross unit inlining the directive *must* be part of the interface as otherwise the idea behind the "interface" and "implementation" section is led ad absurdum. If a routine only has the "inline" directive in the implementation section it's logical that it can only be inlined in the same unit. And methods can't have the "inline" directive at their definition, only at their declaration.

Yes, this will lead to a breakage of existing code, but for something that is a bug that is considered acceptable and unavoidable. Otherwise we'd not be able to fix anything as *someone* might rely on the erractic behavior.

And regarding functions like SwapEndian: they will simply have to be adjusted with a few ifdefs so that the platform implementation can decide whether inlining is available or not.

Show quoted text 16 lines
My solution to this is as follows... ALWAYS attempt to create a node tree (unless "noinline" is specified).  This is effectively auto-inlining, but routines are not inlined unless the explicit directive instructs the compiler to do so (or something like -O4 is specified and the compiler determines that a function should be inlined due to its shortness, say).  This would help mitigate the problem of the null node tree by causing the compiler to check said node tree and set the "cannot inline" flag when appropriate. This isn't ideal though, as it would have two notable side-effects: - General compilation will be slightly slower because of extra analysis on the node trees and copying them into the "inlined nodes" pointer. - The compiled PPU files will increase in size significantly.

And those two points are why I'd be against this.

Show quoted text 16 lines
You may remember that a few months ago, I attempted to shrink the size of PPU files by storing particular fields in LEB128 format, but this was suspended because it increased quick compilation time, despite it reducing the size of PPU files by over 10% (without using explicit compression algorithms).  However, preliminary tests on large projects (we used Lazarus as a test case) showed that the compilation time was about 3 seconds as compared to 2 seconds, while full compilation times were not adversely affected because the processing required to encode LEB128 values is vastly overshadowed by the compilation process in general.  Given it's unlikely that a user will quick-compile a project more than once a minute while coding, I would like to revisit this encoding proposal as a possible solution to the excessive PPU sizes that will result.  While storage is not a sacred commodity on desktop computers as it once was in the 80s and 90s, it is still a premium on some embedded platforms.

However this is only important if you *compile* projects *on* such platforms. And systems like the Pi can use large SD cards or USB drives without problems.

Regards,
Sven

Reply by email

Jonas Maebe
to J. Gareth Moreton: This one is for Jonas in particular, but also to address a minor issue in general.…
J. Gareth Moreton wrote 6 lines
Currently, you can get away with specifying the "inline" directive for a function in just the implementation section of a unit, and the function will be inlined.  However, in some situations, this can cause compiler crashes which I believe is due to a mixture of the function no longer being inlined and the internal CRCs not changing, possibly due to a collision.

While possible, I don't think the issue is CRC collisions. It's more likely to be stale pointers somewhere.

Show quoted text 14 lines
My solution to this is as follows... ALWAYS attempt to create a node tree (unless "noinline" is specified).  This is effectively auto-inlining, but routines are not inlined unless the explicit directive instructs the compiler to do so (or something like -O4 is specified and the compiler determines that a function should be inlined due to its shortness, say).  This would help mitigate the problem of the null node tree by causing the compiler to check said node tree and set the "cannot inline" flag when appropriate. This isn't ideal though, as it would have two notable side-effects: - General compilation will be slightly slower because of extra analysis on the node trees and copying them into the "inlined nodes" pointer. - The compiled PPU files will increase in size significantly.

The main issue is that loading PPUs would become a lot slower in this case: the entire node tree of all of those functions would then also be reconstructed while loading the PPUs -> tons of class instantiations. That would also significantly increase the compiler's memory usage.

Jonas

Reply by email

Florian Klämpfl
to Jonas Maebe
Jonas Maebe wrote 37 lines
On 23/06/2019 01:10, J. Gareth Moreton wrote: > Currently, you can get away with specifying the "inline" directive for a > function in just the implementation section of a unit, and the function > will be inlined. However, in some situations, this can cause compiler > crashes which I believe is due to a mixture of the function no longer > being inlined and the internal CRCs not changing, possibly due to a > collision. While possible, I don't think the issue is CRC collisions. It's more likely to be stale pointers somewhere. > My solution to this is as follows... ALWAYS attempt to create a node > tree (unless "noinline" is specified). This is effectively > auto-inlining, but routines are not inlined unless the explicit > directive instructs the compiler to do so (or something like -O4 is > specified and the compiler determines that a function should be inlined > due to its shortness, say). This would help mitigate the problem of the > null node tree by causing the compiler to check said node tree and set > the "cannot inline" flag when appropriate. > > This isn't ideal though, as it would have two notable side-effects: > > - General compilation will be slightly slower because of extra analysis > on the node trees and copying them into the "inlined nodes" pointer. > - The compiled PPU files will increase in size significantly. The main issue is that loading PPUs would become a lot slower in this case: the entire node tree of all of those functions would then also be reconstructed while loading the PPUs -> tons of class instantiations. That would also significantly increase the compiler's memory usage. Jonas _______________________________________________ fpc-devel maillist - https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel

Not to forget that it would be very easy to reconstruct the source code from PPU. Some users might not like this ...

Reply by email

J. Gareth Moreton
to Florian Klämpfl

That's a point, true.  I've been for openness a lot lately, and one doesn't normally distribute the PPU files with a closed-source project, but I guess for those programs that need compiling on Linux before they can be run, it's not very desirable if the PPU files contain information on, say, a licence key algorithm.

I did make some adjustments somewhere where I fixed the inlined methods for the compiler and the RTL units so it at least honours having "inline" in the interface section, but I'm not sure where I put them.  Either way, currently changing the system to demand inline appear in the interface section causes a heap of compilation errors.  Allowing "inline" to appear only in the implementation, but only having a local effect, I haven't researched how to do that yet, but I sense this is something that needs to be fixed eventualy.

Gareth aka. Kit

Florian Klämpfl wrote 45 lines
Am 23. Juni 2019 16:05:05 schrieb Jonas Maebe : > On 23/06/2019 01:10, J. Gareth Moreton wrote: > >> Currently, you can get away with specifying the "inline" directive for a >> function in just the implementation section of a unit, and the function >> will be inlined. However, in some situations, this can cause compiler >> crashes which I believe is due to a mixture of the function no longer >> being inlined and the internal CRCs not changing, possibly due to a >> collision. > While possible, I don't think the issue is CRC collisions. It's more > likely to be stale pointers somewhere. > >> My solution to this is as follows... ALWAYS attempt to create a node >> tree (unless "noinline" is specified). This is effectively >> auto-inlining, but routines are not inlined unless the explicit >> directive instructs the compiler to do so (or something like -O4 is >> specified and the compiler determines that a function should be inlined >> due to its shortness, say). This would help mitigate the problem of the >> null node tree by causing the compiler to check said node tree and set >> the "cannot inline" flag when appropriate. >> >> This isn't ideal though, as it would have two notable side-effects: >> >> - General compilation will be slightly slower because of extra analysis >> on the node trees and copying them into the "inlined nodes" pointer. >> - The compiled PPU files will increase in size significantly. > The main issue is that loading PPUs would become a lot slower in this > case: the entire node tree of all of those functions would then also be > reconstructed while loading the PPUs -> tons of class instantiations. > That would also significantly increase the compiler's memory usage. > > > Jonas > _______________________________________________ > fpc-devel maillist - > https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel Not to forget that it would be very easy to reconstruct the source code from PPU. Some users might not like this ... _______________________________________________ fpc-devel maillist - https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel

---
This email has been checked for viruses by Avast antivirus software. https://www.avast.com/antivirus

Reply by email

J. Gareth Moreton
to J. Gareth Moreton

Ah, found it.  It was buried in the "noise" and me having a bit of a bad time mentally at the time.

https://bugs.freepascal.org/view.php?id=35346

The patches in that issue fix the inlined methods for compiler/cstreams.pas and compiler/entfile.pas so that "inline" appears in the interface section, as well as adding "inline" for methods that are short enough to warrant it (normally because their code only involves calling another method).

Gareth aka. Kit

J. Gareth Moreton wrote 79 lines
That's a point, true.  I've been for openness a lot lately, and one doesn't normally distribute the PPU files with a closed-source project, but I guess for those programs that need compiling on Linux before they can be run, it's not very desirable if the PPU files contain information on, say, a licence key algorithm. I did make some adjustments somewhere where I fixed the inlined methods for the compiler and the RTL units so it at least honours having "inline" in the interface section, but I'm not sure where I put them.  Either way, currently changing the system to demand inline appear in the interface section causes a heap of compilation errors.  Allowing "inline" to appear only in the implementation, but only having a local effect, I haven't researched how to do that yet, but I sense this is something that needs to be fixed eventualy. Gareth aka. Kit On 23/06/2019 15:06, Florian Klämpfl wrote: > Am 23. Juni 2019 16:05:05 schrieb Jonas Maebe : > >> On 23/06/2019 01:10, J. Gareth Moreton wrote: >> >>> Currently, you can get away with specifying the "inline" directive >>> for a >>> function in just the implementation section of a unit, and the >>> function >>> will be inlined.  However, in some situations, this can cause compiler >>> crashes which I believe is due to a mixture of the function no longer >>> being inlined and the internal CRCs not changing, possibly due to a >>> collision. >> While possible, I don't think the issue is CRC collisions. It's more >> likely to be stale pointers somewhere. >> >>> My solution to this is as follows... ALWAYS attempt to create a node >>> tree (unless "noinline" is specified).  This is effectively >>> auto-inlining, but routines are not inlined unless the explicit >>> directive instructs the compiler to do so (or something like -O4 is >>> specified and the compiler determines that a function should be >>> inlined >>> due to its shortness, say).  This would help mitigate the problem >>> of the >>> null node tree by causing the compiler to check said node tree and set >>> the "cannot inline" flag when appropriate. >>> >>> This isn't ideal though, as it would have two notable side-effects: >>> >>> - General compilation will be slightly slower because of extra >>> analysis >>> on the node trees and copying them into the "inlined nodes" pointer. >>> - The compiled PPU files will increase in size significantly. >> The main issue is that loading PPUs would become a lot slower in this >> case: the entire node tree of all of those functions would then also be >> reconstructed while loading the PPUs -> tons of class instantiations. >> That would also significantly increase the compiler's memory usage. >> >> >> Jonas >> _______________________________________________ >> fpc-devel maillist  -  >> https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel > Not to forget that it would be very easy to reconstruct the source > code from PPU. Some users might not like this ... > > > _______________________________________________ > fpc-devel maillist  -  > https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel > > --- This email has been checked for viruses by Avast antivirus software. https://www.avast.com/antivirus _______________________________________________ fpc-devel maillist  -  https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel

Reply by email

Sven Barth
to J. Gareth Moreton: That's a point, true.  I've been for openness a lot lately, and one doesn't normally…
J. Gareth Moreton wrote 5 lines
That's a point, true.  I've been for openness a lot lately, and one doesn't normally distribute the PPU files with a closed-source project, but I guess for those programs that need compiling on Linux before they can be run, it's not very desirable if the PPU files contain information on, say, a licence key algorithm.

It's not only projects aka excutables, but also components that can be used with e.g. Lazarus. There *do* exist commercial, closed source component providers that only provide the PPU (and maybe an interface only unit so that Lazarus' code completion works).

Regards,
Sven

Reply by email

J. Gareth Moreton
to Sven Barth

Fair enough - thank you for the insight.

To clarify, it is easy enough to demand "inline" appear in the interface section, but it breaks a lot of pre-existing code.  I'll have a think about how to implement the alternative solution of "implementation-only inline" only affecting the routine locally.

Gareth aka. Kit

Sven Barth wrote 18 lines
Am 24.06.2019 um 01:02 schrieb J. Gareth Moreton: > That's a point, true.  I've been for openness a lot lately, and one > doesn't normally distribute the PPU files with a closed-source > project, but I guess for those programs that need compiling on Linux > before they can be run, it's not very desirable if the PPU files > contain information on, say, a licence key algorithm. It's not only projects aka excutables, but also components that can be used with e.g. Lazarus. There *do* exist commercial, closed source component providers that only provide the PPU (and maybe an interface only unit so that Lazarus' code completion works). Regards, Sven _______________________________________________ fpc-devel maillist  -  https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel

---
This email has been checked for viruses by Avast antivirus software. https://www.avast.com/antivirus

Reply by email