On 7/13/2022 2:28 PM, MitchAlsup wrote:
> On Wednesday, July 13, 2022 at 3:17:16 PM UTC-5, Ivan Godard wrote:
>> On 7/13/2022 12:42 PM, John Levine wrote:
>>> According to EricP <ThatWould...@thevillage.com>:
>>>> I assume all compilers emit 64-bit global offsets and a
>>>> compacting linker eliminates the excess when it determines
>>>> which calls and mem refs are intra-dll and which are inter.
>>>> The ISA supported offset sizes just determines the frequency
>>>> of each compaction.
>>>
>>> Perhaps on some systems. On systems that use ELF libraries, including
>>> linux and the BSDs, each executable or library has a table called the
>>> Procedure Linkage Table (PLT), which contains an entry for each
>>> external routine called from the library. Initially each PLT entry
>>> contains a call to the dynamic linker which is patched on the first
>>> call to be a jump to the actual routine. So all the calls in the code
>>> are actually calls to the PLT which can use a short address.
>>>
>>> I have written assemblers that do address shortening, and the way it
>>> would work in a linker would be similar. Doing it well is NP-complete
>>> and can require a lot of code patching, since it can change the
>>> offsets of data references, so it's not a feature I would want to use
>>> a lot.
>> Don't think it's NP.
>>
>> Walk the code, keeping two distances for each unresolved branch. One is
>> how far the target would be if all unresolved were resolved as near; the
>> other is if all unresolved were resolved as far. For each unresolved, if
>> the as-far is less than the near range then resolve as near, and if the
>> as-near is greater than the near range then resolve as far; if neither
>> then leave it unresolved and go to the next unresolved. Repeat until a
>> pass resolves nothing additional. At that point, resolve all unresolved
>> as near. Done. The algorithm generalizes in the obvious way to ISAs with
>> more than two range categories.
>>
>> It helps if the code is in internal form that doesn't represent the
>> branches as instructions, i.e. short sequences of fixed length
>> containing non-branch instructions, together with the max and min
>> distances of the terminating branch; that way you walk the sequence
>> descriptors and not the actual instructions. Resolution of a descriptor
>> generates the binary of the resolved branch and glues it to the sequence
>> on either side to make a longer sequence; gluing may be actual copy or
>> just an adjustment of links.
>>
>> I have never seen actual code take more than three iterations to get to
>> the fix point, but in any case the number of iterations cannot be
>> greater than the number of branches, so not NP.
> <
> Mc 88110 just did one fix up pass and left the rest using large addresses.
> <
> I think, technically, getting it perfect requires a pass for every resolved address*
> and this smells a bit like NP-complete to me. In practice, Mc 88100 used one
> pass and saw virtually no excess code path dynamically.
> <
> (*) every time the linker shortens up an access, it creates the potential that
> some already passed over access that was left long might now fit in shorter
> form. This would require a very carefully laid out access order and corresponding
> inverted placement lay out order.

Yes, as I described, a maximal contrived example will need one pass over
the remaining unresolved branches per branch. That is O<branches>, which
is linear. If the code is represented as a sequence of descriptors, each
containing length and max/min distances, each pass over the remaining
descriptors will consolidate at least one pair, so the maximal number of
descriptors examined is (n^2)/2 where n is again the number of branches,
which is quadratic. Neither is anything like NP, which requires
exponentiality or worse.

In practice, the number of passes over real code is ~3, and the number
of descriptor examinations is ~1, both roughly constant and growing with
n at a very low rate, ~0.

On Wednesday, July 13, 2022 at 8:43:56 PM UTC-5, Ivan Godard wrote:
> On 7/13/2022 2:28 PM, MitchAlsup wrote:
> > On Wednesday, July 13, 2022 at 3:17:16 PM UTC-5, Ivan Godard wrote:
> >> On 7/13/2022 12:42 PM, John Levine wrote:
> >>> According to EricP <ThatWould...@thevillage.com>:
> >>>> I assume all compilers emit 64-bit global offsets and a
> >>>> compacting linker eliminates the excess when it determines
> >>>> which calls and mem refs are intra-dll and which are inter.
> >>>> The ISA supported offset sizes just determines the frequency
> >>>> of each compaction.
> >>>
> >>> Perhaps on some systems. On systems that use ELF libraries, including
> >>> linux and the BSDs, each executable or library has a table called the
> >>> Procedure Linkage Table (PLT), which contains an entry for each
> >>> external routine called from the library. Initially each PLT entry
> >>> contains a call to the dynamic linker which is patched on the first
> >>> call to be a jump to the actual routine. So all the calls in the code
> >>> are actually calls to the PLT which can use a short address.
> >>>
> >>> I have written assemblers that do address shortening, and the way it
> >>> would work in a linker would be similar. Doing it well is NP-complete
> >>> and can require a lot of code patching, since it can change the
> >>> offsets of data references, so it's not a feature I would want to use
> >>> a lot.
> >> Don't think it's NP.
> >>
> >> Walk the code, keeping two distances for each unresolved branch. One is
> >> how far the target would be if all unresolved were resolved as near; the
> >> other is if all unresolved were resolved as far. For each unresolved, if
> >> the as-far is less than the near range then resolve as near, and if the
> >> as-near is greater than the near range then resolve as far; if neither
> >> then leave it unresolved and go to the next unresolved. Repeat until a
> >> pass resolves nothing additional. At that point, resolve all unresolved
> >> as near. Done. The algorithm generalizes in the obvious way to ISAs with
> >> more than two range categories.
> >>
> >> It helps if the code is in internal form that doesn't represent the
> >> branches as instructions, i.e. short sequences of fixed length
> >> containing non-branch instructions, together with the max and min
> >> distances of the terminating branch; that way you walk the sequence
> >> descriptors and not the actual instructions. Resolution of a descriptor
> >> generates the binary of the resolved branch and glues it to the sequence
> >> on either side to make a longer sequence; gluing may be actual copy or
> >> just an adjustment of links.
> >>
> >> I have never seen actual code take more than three iterations to get to
> >> the fix point, but in any case the number of iterations cannot be
> >> greater than the number of branches, so not NP.
> > <
> > Mc 88110 just did one fix up pass and left the rest using large addresses.
> > <
> > I think, technically, getting it perfect requires a pass for every resolved address*
> > and this smells a bit like NP-complete to me. In practice, Mc 88100 used one
> > pass and saw virtually no excess code path dynamically.
> > <
> > (*) every time the linker shortens up an access, it creates the potential that
> > some already passed over access that was left long might now fit in shorter
> > form. This would require a very carefully laid out access order and corresponding
> > inverted placement lay out order.
<
> Yes, as I described, a maximal contrived example will need one pass over
> the remaining unresolved branches per branch. That is O<branches>, which
<
You also need to consider LDs and STs as these have several lengths depending...
<
> is linear. If the code is represented as a sequence of descriptors, each
> containing length and max/min distances, each pass over the remaining
> descriptors will consolidate at least one pair, so the maximal number of
> descriptors examined is (n^2)/2 where n is again the number of branches,
> which is quadratic. Neither is anything like NP, which requires
> exponentiality or worse.
>
> In practice, the number of passes over real code is ~3, and the number
> of descriptor examinations is ~1, both roughly constant and growing with
> n at a very low rate, ~0.

On Wednesday, July 13, 2022 at 8:43:56 PM UTC-5, Ivan Godard wrote:
> On 7/13/2022 2:28 PM, MitchAlsup wrote:
> > On Wednesday, July 13, 2022 at 3:17:16 PM UTC-5, Ivan Godard wrote:
> >> On 7/13/2022 12:42 PM, John Levine wrote:
> >>> According to EricP <ThatWould...@thevillage.com>:
> >>>> I assume all compilers emit 64-bit global offsets and a
> >>>> compacting linker eliminates the excess when it determines
> >>>> which calls and mem refs are intra-dll and which are inter.
> >>>> The ISA supported offset sizes just determines the frequency
> >>>> of each compaction.
> >>>
> >>> Perhaps on some systems. On systems that use ELF libraries, including
> >>> linux and the BSDs, each executable or library has a table called the
> >>> Procedure Linkage Table (PLT), which contains an entry for each
> >>> external routine called from the library. Initially each PLT entry
> >>> contains a call to the dynamic linker which is patched on the first
> >>> call to be a jump to the actual routine. So all the calls in the code
> >>> are actually calls to the PLT which can use a short address.
> >>>
> >>> I have written assemblers that do address shortening, and the way it
> >>> would work in a linker would be similar. Doing it well is NP-complete
> >>> and can require a lot of code patching, since it can change the
> >>> offsets of data references, so it's not a feature I would want to use
> >>> a lot.
> >> Don't think it's NP.
> >>
> >> Walk the code, keeping two distances for each unresolved branch. One is
> >> how far the target would be if all unresolved were resolved as near; the
> >> other is if all unresolved were resolved as far. For each unresolved, if
> >> the as-far is less than the near range then resolve as near, and if the
> >> as-near is greater than the near range then resolve as far; if neither
> >> then leave it unresolved and go to the next unresolved. Repeat until a
> >> pass resolves nothing additional. At that point, resolve all unresolved
> >> as near. Done. The algorithm generalizes in the obvious way to ISAs with
> >> more than two range categories.
> >>
> >> It helps if the code is in internal form that doesn't represent the
> >> branches as instructions, i.e. short sequences of fixed length
> >> containing non-branch instructions, together with the max and min
> >> distances of the terminating branch; that way you walk the sequence
> >> descriptors and not the actual instructions. Resolution of a descriptor
> >> generates the binary of the resolved branch and glues it to the sequence
> >> on either side to make a longer sequence; gluing may be actual copy or
> >> just an adjustment of links.
> >>
> >> I have never seen actual code take more than three iterations to get to
> >> the fix point, but in any case the number of iterations cannot be
> >> greater than the number of branches, so not NP.
> > <
> > Mc 88110 just did one fix up pass and left the rest using large addresses.
> > <
> > I think, technically, getting it perfect requires a pass for every resolved address*
> > and this smells a bit like NP-complete to me. In practice, Mc 88100 used one
> > pass and saw virtually no excess code path dynamically.
> > <
> > (*) every time the linker shortens up an access, it creates the potential that
> > some already passed over access that was left long might now fit in shorter
> > form. This would require a very carefully laid out access order and corresponding
> > inverted placement lay out order.
> Yes, as I described, a maximal contrived example will need one pass over
> the remaining unresolved branches per branch. That is O<branches>, which
> is linear. If the code is represented as a sequence of descriptors, each
> containing length and max/min distances, each pass over the remaining
> descriptors will consolidate at least one pair, so the maximal number of
> descriptors examined is (n^2)/2 where n is again the number of branches,
> which is quadratic. Neither is anything like NP, which requires
> exponentiality or worse.
>
> In practice, the number of passes over real code is ~3, and the number
> of descriptor examinations is ~1, both roughly constant and growing with
> n at a very low rate, ~0.
<
But, yes, far less than NP.

According to MitchAlsup <MitchAlsup@aol.com>:
>> In practice, the number of passes over real code is ~3, and the number
>> of descriptor examinations is ~1, both roughly constant and growing with
>> n at a very low rate, ~0.
><
>But, yes, far less than NP.

Like many NP complete problems, this one has approximate solutions
that are pretty close and are adequate except perhaps in the occasional
embedded application where you're trying to squeeze everything into a
small fixed amount of ROM.

--
Regards,
John Levine, johnl@taugh.com, Primary Perpetrator of "The Internet for Dummies",
Please consider the environment before reading this e-mail. https://jl.ly

On 7/14/2022 8:24 AM, John Levine wrote:
> According to MitchAlsup <MitchAlsup@aol.com>:
>>> In practice, the number of passes over real code is ~3, and the number
>>> of descriptor examinations is ~1, both roughly constant and growing with
>>> n at a very low rate, ~0.
>> <
>> But, yes, far less than NP.
>
> Like many NP complete problems, this one has approximate solutions
> that are pretty close and are adequate except perhaps in the occasional
> embedded application where you're trying to squeeze everything into a
> small fixed amount of ROM.
>
>
>
>

Worse case is linear in number of passes, quadratic in number of
instructions read. That's not an approximation, that's Deterministic
Polynomial. https://en.wikipedia.org/wiki/NP_(complexity)

John Levine wrote:
> According to MitchAlsup <MitchAlsup@aol.com>:
>>> In practice, the number of passes over real code is ~3, and the number
>>> of descriptor examinations is ~1, both roughly constant and growing with
>>> n at a very low rate, ~0.
>> <
>> But, yes, far less than NP.
>
> Like many NP complete problems, this one has approximate solutions
> that are pretty close and are adequate except perhaps in the occasional
> embedded application where you're trying to squeeze everything into a
> small fixed amount of ROM.

On those systems you were much more likely to manually optimize for
size, to the point where _all_ branches were short, all stack-relative
offsets were in the -128 to 127 range, and calls would use extremely
non-standard ABIs.

Take a look at the 256-byte asm challenges, I am very impressed by what
has been shown to be possible.

Personally I was _very_ happy with my PC-DOS TSR which replaced
IBM/Microsoft's kbd & screen (font) drivers: The originals needed 20-60
KB depending upon version and capabilities, my replacement which
provided a true superset (it included a replacement font for 43 and
50-line EGA/VGA text modes) made do with just under 700 bytes. Far
branches were never an issue. :-)

Terje
PS. HP/Compaq Norway liked it as well, to the point where they stole it
twice...

--
- <Terje.Mathisen at tmsw.no>
"almost all programming can be viewed as an exercise in caching"