On 6/29/2021 12:35 PM, Anton Ertl wrote:
> BGB <cr88192@gmail.com> writes:
>> If you use a link register, or return via some other special register
>> (such as treating R1 as a secondary link register), then all one needs
>> to do is check is that this register hasn't been modified within the
>> pipeline, and if so use the value held in this register as the predicted
>> branch target.
>
> McKinley and the PowerPC 970 predicted indirect jumps that way. If
> the target arrives a short time before the call, this causes a
> misprediction; IIRC it cost 6 cycles on McKinley (which did not have a
> particularly deep pipeline).
>

I am doing it this way with my BJX2 core, which has an ~ 8-stage
pipeline, eg:
PF IF ID1 ID2 EX1 EX2 EX3 WB

PF: Pass next PC to I$
IF: I$ does its thing, gives result
ID1: Decode 1, Branch Predictor does its thing.
ID2: Decode 2, Fetch register values, ...
EX1: Execute 1 (AGU)
EX2: Execute 2 (Mem 1)
EX3: Execute 3 (Mem 2)
WB: Write-Back (Store results to GPR File)

Because the branch-predictor runs in ID2 and feeds the result into PF,
correctly-predicted taken branches still have a 2 cycle latency (best
case), whereas correctly-predicted non-taken branches have a 1 cycle
latency.

> On a modern high-performance CPU, you want to be able to call a short
> routine, fetch the instructions from there, and fetch the instructions
> from after the call a cycle later. Modern AMD64 implementations
> achieve that (thanks to a very streamlined predictor including a
> return stack), but with the approach you are suggesting it would not
> be possible; keeping the return address in a register helps only so
> far.
>

Potentially, but as noted, I am not talking about a modern x86 chip (or
even necessarily OoO).

>> In this case, typically one can reload the LR or "Secondary LR" several
>> cycles before its associated RTS or JMP.
>
> On a wide processor, you often cannot, see below.
>
>> If one reloads the link
>> register before the others in a function epilog, then (typically) the
>> reloaded register will have left the pipeline before the CPU reaches the
>> return instruction.
>
> You certainly cannot if you do the load in a function epilog (rather
> than immediately after the last call). The load has 3-5 cycles of
> latency for use by some execution unit, and even in short pipelines
> several additional cycles for use in instruction fetching; let's say
> you have a short pipeline and only 6 cycles latency from executing a
> load to instruction fetch that uses its result; and you have a
> moderately wide machine at 4 instructions fetched and decoded per
> cycle; then you need to put the load 24 cycles before the return
> instructions.
>

I have a core that does a max of 3 instructions per cycle, but only 1
memory access per cycle (For the most part, lanes 2 and 3 can only do
ALU ops and similar).

There is an optional feature which does allow issuing FPU ops from Lane
2, which can sometimes help some for FPU code by allowing memory access
and the FPU to operate in parallel. This isn't really an official
feature yet though (however, this does not allow running FPU ops in
parallel, as there is still only a single FPU).

If one does something like, say:
MOV.Q (SP, 64), R1
MOV.X (SP, 0), R24
MOV.X (SP, 16), R26
MOV.X (SP, 32), R28
MOV.X (SP, 48), R30
ADD 80, SP
JMP R1

Then R1 passes through WB just before the JMP hits ID1.

Longer is safer, and shorter than this will result in a non-predicted
branch (~ 9 cycles of penalty).

Not really a good workaround (in theory, an interlock could be done in
small cases, or possibly the compiler could detect these cases and
insert a few NOPs).

Granted, a fair number of functions save more registers than this, so, eg:
MOV.Q (SP, 112), R1
MOV.X (SP, 0), R8
MOV.X (SP, 16), R10
MOV.X (SP, 32), R12
MOV.X (SP, 48), R24
MOV.X (SP, 64), R26
MOV.X (SP, 80), R28
MOV.X (SP, 96), R30
ADD 128, SP
JMP R1

In which case R1 can be predicted.

If it is a leaf function which does not save LR and uses a plain RTS,
then the body of the leaf function typically provides enough of a buffer
zone (there may still be a penalty if the function is short enough that
the original BSR does not pass through WB before the RTS hits ID1).

On 6/29/2021 3:20 PM, Stephen Fuld wrote:
> On 6/29/2021 12:27 PM, Ivan Godard wrote:
...
>>
>> What matters is the distribution of indices, not the number of
>> targets. Think a typical lexer: you want to isolate all alphas with
>> one compare, not a four way binary to a particular alpha, because all
>> the alphas go to a single label. Once you do that, normal ifconversion
>> will get rid of half the internal branches of the decision tree..
>
> I am not a compiler guy, so forgive my ignorance.  What would a compiler
> do in such a situation?  Would it first test for something like if char
> >= "a" and <= "z", etc.?
>
> Just thinking about how I might do it, I think I would have a 256 byte
> array, indexed by the character value, with each entry having an
> indicator value, say 1 for lower case letters, 2 for upper case letters,
> 3 for numbers, 4 for white space characters, etc.  Looking up the value
> shouldn't be costly as most of the table with shortly be in D-cache.
> Then use the indicator value to index a jump or call table (which I
> guess is fairly predictable as most characters are lower case letters.
>
> But what do I know?  :-(

Compilers vary a lot in their handling of switches, so I can only
comment about ours. Here's the internal comment from the internalize.cc
module, which among other things converts switches from genAsm
(approximately LLVM IR) to internal representation.

********************************************************************

/* Each of the switchInfos has a home ebb (where the switch statement
appeared) and a drop with the value that governs the switch. There
are also a dense set of cases, each with an integer range of values
and a target ebb that should get control if the governing drop has
one of these values. This function builds a CFG that routes control to
the right target.

Very large and dense case spaces are best handled by a bounding
range compare followed by indirection through a jump table. Very sparse
case spaces are best handled by a cascade of explicit equality tests
controlling branches to the targets, with the default forming the
fall-through. Dense case spaces with few distinct targets are best
handled by cascaded less-than compares with their branches. A single
switchInfo may show each of these types in different portions of the
case space.

Because the Mill can have multiple conditional branches per
instruction and needs only one prediction per ebb regardless of the
number of branches contained, it is better to put a large part of a
branch cascade in a single ebb than to use a tree of ebbs following a
binary search. However, on average half of those branches will be
executed before a winner is found, and for large cascades on small Mills
the time to run down a one-ebb cascade exceeds the time to break the
cascade in half by branching at a pivot value in the middle.

Of course, pivot branches can themselves be cascaded, thus
partitioning the case space into sub-spaces which again may be
partitioned recursively using sub-cascades. The member-dependent tuning
variable switchCascadeSize governs how big a (sub-) cascade must be
before it is broken by pivoting.

Each of the ranges can be isolated by a "less than" comparison, so
the maximal number of branches is the size of the ranges vector. A
less-than compare requires one branch per range, while an equality
compare requires one branch per non-default value. Consequently equality
takes one branch for two ranges when a non-default range of extent one
is adjacent to a default range whereas less-than would take two
branches; a non-default range of extent greater than one takes one
branch using less-than and a number of branches equal to the extent
using equality; and a non-default branch of extent one adjacent to a
non-default of any size takes one branch in both less-than and equality.

The worst case is a run of extent-one ranges. If there are N
ranges, then sequential equality needs N branches and will execute N/2
of them. With less-than you need one branch to split N to 2*(N/2), 2 to
split 2*(N/2) into 4*(N/4) and so on. That is 2N-1 total to the bottom
level, and log2(N) levels. So less-than will always need more branches
than equality, because the bottom level of a less-than is the same as an
equality and there are all the upper levels on top of that.

As for latency, the dividing point is when log2(N) is smaller than
N/2; the break-even is 8. So we less-than down until the number of cases
is eight or less, and do sequential equality after that.
*/
********************************************************************

Once this analysis is done, other code recognizes where a jump table or
comb would be better in part or all of the decision tree. The compiler
does not generate a compressing lookup table as you suggest though it
could and perhaps should. It does generate comb bitmasks for switches
where a single target is very frequent but not dense. The comb removes
all the frequent case and leaves their values as don't-care, which
simplifies the decision tree of the remaining cases.

While this function does the case partitioning, it ignores the code
located at each label, which will reside in its own ebb targeted by one
or more branches in the partitioning. Post partitioning, the control
flow is a normal CFG and has the same representation as it would have
had if the source had been written as the equivalent set of if-then.

As in any Mill CFG, subsequent processing does aggressive if-conversion
and block folding, so that nearly always the case target code gets
folded into the decision tree with appropriate predication. One of the
Mill talks (https://millcomputing.com/docs/switches/) shows how this
works in practice on a user-supplied example switch.

"The talk works through the compiled code for an example with eight
cases spanning 100 values. Spoiler: a mid-range Mill does the whole
switch, including the action bodies for each case, in three instruction
cycles and no table. Which isn’t too bad, considering that hand-crafted
Mill code can do it in two."

It would be interesting to see what code My66 has for this example.

On Tuesday, June 29, 2021 at 4:05:13 PM UTC-5, Ivan Godard wrote:
> On 6/29/2021 1:33 PM, MitchAlsup wrote:
> > On Tuesday, June 29, 2021 at 2:27:46 PM UTC-5, Ivan Godard wrote:
> >> On 6/29/2021 9:01 AM, BGB wrote:
> >>> On 6/28/2021 10:45 PM, Andy wrote:
> >>>> On 27/06/21 7:31 am, MitchAlsup wrote:
> >>>>
> >>>>> There are five cases: Switches, Returns, Method calls, Tabulated
> >>>>> Calls, and Longjump.
> >>>>> <
> >>>>> Switches tend to be unpredictable much of the time.
> >>>>> Returns are easily highly predictable
> >>>>> Method calls tend to use few methods more than others
> >>>>> Tabulated calls tend to be indexed tables of entry points
> >>>>> And longjump is a category all by itself.
> >>>>
> >>>> Ummm, so no love for Call Return Tables?, wouldn't they go some way to
> >>>> reducing the number of conditional instructions spent checking for
> >>>> error return codes and having otherwise unneeded instructions situated
> >>>> right after the original call.
> >>>>
> >>>
> >>> A dedicated call-return table probably only really makes sense for
> >>> something like x86, which loads the return address from memory at the
> >>> same time as branching to it.
> >>>
> >>> If you use a link register, or return via some other special register
> >>> (such as treating R1 as a secondary link register), then all one needs
> >>> to do is check is that this register hasn't been modified within the
> >>> pipeline, and if so use the value held in this register as the predicted
> >>> branch target.
> >>>
> >>> In this case, typically one can reload the LR or "Secondary LR" several
> >>> cycles before its associated RTS or JMP. If one reloads the link
> >>> register before the others in a function epilog, then (typically) the
> >>> reloaded register will have left the pipeline before the CPU reaches the
> >>> return instruction.
> >>>
> >>>
> >>> Meanwhile, switch faces a problem that typically one calculates the
> >>> switch target immediately before branching to it. If one could somehow
> >>> do something like:
> >>> Calculate where the "switch()" will go;
> >>> Put some prior unrelated logic here;
> >>> Do the branch to the switch target.
> >>>
> >>> Then "switch()" could potentially also be made predictable.
> >> You can do exactly that: figure index; index-load from a table in
> >> memory; do other stuff; indirect branch. Of course, that puts the table
> >> in dmem, which Mitch doesn't like, or requires a load instruction from imem.
> > <
> > Switch is common enough that it should be performed in an instruction
> > (the multiway branch) I added limit checking to this due to how it
> > "worked out" in my ISA.
> > <
> > Also note: the tables in my switches remain program relative, so you fetch
> > from ICache and then add this to the IP for the target address. This saves
> > table size as the majority of all tables fit in 16-bit offsets, retains program
> > relativity.
> > <
> >>> For small switch one might instead use linear probing or binary
> >>> subdivision or similar, in which case it is predictable if the
> >>> individual branches are predictable.
> >>>
> >>> Say (number of case labels):
> >>> 1-3: Linear Probe
> >>> 4-11: Binary Subdivide
> >>> 12-511 (and sufficiently dense): Branch Table
> >>> Else: Binary Subdivide (1)
> >>>
> >>> *1: Binary subdivide happens until either it reaches the conditions for
> >>> a branch-table, or the number of targets is small enough that it falls
> >>> back to a linear probe.
> >>>
> >>> ...
> >> What matters is the distribution of indices, not the number of targets.
> >> Think a typical lexer: you want to isolate all alphas with one compare,
> >> not a four way binary to a particular alpha, because all the alphas go
> >> to a single label. Once you do that, normal ifconversion will get rid of
> >> half the internal branches of the decision tree..
> > <
> > In any event, any HW is going to be able to sort through the situation
> > faster than any string of SW instructions.
> >
> Arguable.
>
> Label density matters for the tables too:
> switch (<32 bit>) {
> <cases: 11111, 22222, 33333, 44444, 55555, 66666, 77777, 88888, 99999>
>
> Do you really want 100k labels in your table, or a 3-deep compare tree?
<
That is considered "not dense", and get composed from ::
<
if( value==11111)
{}
else if( value ==22222 )
{}
......
>
> Out of curiosity, what happens when you throw that at Brian's compiler?
<
Don't know:: Brian ??

On Tuesday, June 29, 2021 at 5:10:08 PM UTC-5, Stefan Monnier wrote:
> > Switch is common enough that it should be performed in an instruction
> > (the multiway branch) I added limit checking to this due to how it
> > "worked out" in my ISA.
<
> BTW, what kind of prediction structure do you foresee for your "multiway
> branch" instructions? Do you foresee predicting the index (and then
> looking up the corresponding target address in the table), so similar to
> a taken/nottaken predictor but just returning more than one bit, or do
> you foresee something more like a BTB (i.e. predict the actual target
> address of the branch)?
<
For narrow machines:: do absolutely nothing
For GBOoO machines:: try to take a good guess
For things in the middle:: do a lot of simulation
<
>
>
> Stefan

On Tuesday, June 29, 2021 at 5:20:33 PM UTC-5, Stephen Fuld wrote:
> On 6/29/2021 12:27 PM, Ivan Godard wrote:
> > On 6/29/2021 9:01 AM, BGB wrote:
> >> On 6/28/2021 10:45 PM, Andy wrote:
> >>> On 27/06/21 7:31 am, MitchAlsup wrote:
> >>>
> >>>> There are five cases: Switches, Returns, Method calls, Tabulated
> >>>> Calls, and Longjump.
> >>>> <
> >>>> Switches tend to be unpredictable much of the time.
> >>>> Returns are easily highly predictable
> >>>> Method calls tend to use few methods more than others
> >>>> Tabulated calls tend to be indexed tables of entry points
> >>>> And longjump is a category all by itself.
> >>>
> >>> Ummm, so no love for Call Return Tables?, wouldn't they go some way
> >>> to reducing the number of conditional instructions spent checking for
> >>> error return codes and having otherwise unneeded instructions
> >>> situated right after the original call.
> >>>
> >>
> >> A dedicated call-return table probably only really makes sense for
> >> something like x86, which loads the return address from memory at the
> >> same time as branching to it.
> >>
> >> If you use a link register, or return via some other special register
> >> (such as treating R1 as a secondary link register), then all one needs
> >> to do is check is that this register hasn't been modified within the
> >> pipeline, and if so use the value held in this register as the
> >> predicted branch target.
> >>
> >> In this case, typically one can reload the LR or "Secondary LR"
> >> several cycles before its associated RTS or JMP. If one reloads the
> >> link register before the others in a function epilog, then (typically)
> >> the reloaded register will have left the pipeline before the CPU
> >> reaches the return instruction.
> >>
> >>
> >> Meanwhile, switch faces a problem that typically one calculates the
> >> switch target immediately before branching to it. If one could somehow
> >> do something like:
> >> Calculate where the "switch()" will go;
> >> Put some prior unrelated logic here;
> >> Do the branch to the switch target.
> >>
> >> Then "switch()" could potentially also be made predictable.
> >
> > You can do exactly that: figure index; index-load from a table in
> > memory; do other stuff; indirect branch. Of course, that puts the table
> > in dmem, which Mitch doesn't like, or requires a load instruction from
> > imem.
> >
> >> For small switch one might instead use linear probing or binary
> >> subdivision or similar, in which case it is predictable if the
> >> individual branches are predictable.
> >>
> >> Say (number of case labels):
> >> 1-3: Linear Probe
> >> 4-11: Binary Subdivide
> >> 12-511 (and sufficiently dense): Branch Table
> >> Else: Binary Subdivide (1)
> >>
> >> *1: Binary subdivide happens until either it reaches the conditions
> >> for a branch-table, or the number of targets is small enough that it
> >> falls back to a linear probe.
> >>
> >> ...
> >
> > What matters is the distribution of indices, not the number of targets.
> > Think a typical lexer: you want to isolate all alphas with one compare,
> > not a four way binary to a particular alpha, because all the alphas go
> > to a single label. Once you do that, normal ifconversion will get rid of
> > half the internal branches of the decision tree..
<
> I am not a compiler guy, so forgive my ignorance. What would a compiler
> do in such a situation? Would it first test for something like if char
> >= "a" and <= "z", etc.?
<
table[ c ] & ALPHABETIC
or
table[ c ] & (ALPHABETIC | NUMERIC)
>
> Just thinking about how I might do it, I think I would have a 256 byte
> array, indexed by the character value, with each entry having an
> indicator value, say 1 for lower case letters, 2 for upper case letters,
<
When you get more than 8 flags per character, the table grows into 16-bit
entries......
<
# define ALPHABETIC (1<<0)
# define NUMERIC (1<<1)
# define OPERATOR (1<<2)
# define SEPARATOR (1<<3)
# define WHITE (1<<4)
......
<
> 3 for numbers, 4 for white space characters, etc. Looking up the value
> shouldn't be costly as most of the table with shortly be in D-cache.
> Then use the indicator value to index a jump or call table (which I
> guess is fairly predictable as most characters are lower case letters.
>
> But what do I know? :-(
>
>
>
> --
> - Stephen Fuld
> (e-mail address disguised to prevent spam)

MitchAlsup [2021-06-29 16:52:12] wrote:
> On Tuesday, June 29, 2021 at 5:10:08 PM UTC-5, Stefan Monnier wrote:
>> > Switch is common enough that it should be performed in an instruction
>> > (the multiway branch) I added limit checking to this due to how it
>> > "worked out" in my ISA.
>> BTW, what kind of prediction structure do you foresee for your "multiway
>> branch" instructions? Do you foresee predicting the index (and then
>> looking up the corresponding target address in the table), so similar to
>> a taken/nottaken predictor but just returning more than one bit, or do
>> you foresee something more like a BTB (i.e. predict the actual target
>> address of the branch)?
> For narrow machines:: do absolutely nothing

Meaning... stall the pipeline?

Stefan

On Tuesday, June 29, 2021 at 9:23:29 PM UTC-5, Stefan Monnier wrote:
> MitchAlsup [2021-06-29 16:52:12] wrote:
> > On Tuesday, June 29, 2021 at 5:10:08 PM UTC-5, Stefan Monnier wrote:
> >> > Switch is common enough that it should be performed in an instruction
> >> > (the multiway branch) I added limit checking to this due to how it
> >> > "worked out" in my ISA.
> >> BTW, what kind of prediction structure do you foresee for your "multiway
> >> branch" instructions? Do you foresee predicting the index (and then
> >> looking up the corresponding target address in the table), so similar to
> >> a taken/nottaken predictor but just returning more than one bit, or do
> >> you foresee something more like a BTB (i.e. predict the actual target
> >> address of the branch)?
> > For narrow machines:: do absolutely nothing
> Meaning... stall the pipeline?
<
You need to remember My 66000 ISA has a Jump-through-table instruction
that performs dense switch ranges. So, it takes a few cycles (on the order of
a LD) and then control arrives at case label.
<
You can call this stalling of the pipeline, but SW did not have to perform the
range compare, and LD through the index, then JMP to the case label. All in
all it saves 3-4 instructions and takes (on average) a bit less time than the
SW equivalent, so at worst it is break even when compared to std RISC
architectures.
<
>
>
> Stefan

>> >> BTW, what kind of prediction structure do you foresee for your "multiway
>> >> branch" instructions? Do you foresee predicting the index (and then
>> >> looking up the corresponding target address in the table), so similar to
>> >> a taken/nottaken predictor but just returning more than one bit, or do
>> >> you foresee something more like a BTB (i.e. predict the actual target
>> >> address of the branch)?
>> > For narrow machines:: do absolutely nothing
>> Meaning... stall the pipeline?
> You need to remember My 66000 ISA has a Jump-through-table instruction
> that performs dense switch ranges.

Yes my question is specifically about those instructions.

> So, it takes a few cycles (on the order of a LD) and then control
> arrives at case label.
[...]
> You can call this stalling of the pipeline, but SW did not have to perform the
> range compare, and LD through the index, then JMP to the case label. All in
> all it saves 3-4 instructions and takes (on average) a bit less time than the
> SW equivalent, so at worst it is break even when compared to std RISC
> architectures.

I guess the SW equivalent has typically 2 branches (a conditional one for
out-of-bounds handling and an indirect one for the actual jump), so it
likely won't take less than 2 cycles on most systems?

You're probably right that on a narrow enough machine, stalling might be
about as good. Still, after you fetch&decode the switch instruction,
you have to:
- wait for all the data-dependencies to clear in order to get
your index. For a 10-deep pipeline, that could be what, 2 cycles?
- fetch the data from the L1$. Latency would be what? 3 cycles?
do you think you can shorten that by prefetching the cache line before
we know the index and then using the index into the cache line to
reduce this part of the latency to a single cycle?
- then finally we have the address of the next instruction and can fetch
it from L1$.
If the target is hard to predict, stalling (and working to minimize the
latency) is the better option, indeed.

Stefan

On 6/29/2021 2:27 PM, Ivan Godard wrote:
> On 6/29/2021 9:01 AM, BGB wrote:
>> On 6/28/2021 10:45 PM, Andy wrote:
>>> On 27/06/21 7:31 am, MitchAlsup wrote:
>>>
>>>> There are five cases: Switches, Returns, Method calls, Tabulated
>>>> Calls, and Longjump.
>>>> <
>>>> Switches tend to be unpredictable much of the time.
>>>> Returns are easily highly predictable
>>>> Method calls tend to use few methods more than others
>>>> Tabulated calls tend to be indexed tables of entry points
>>>> And longjump is a category all by itself.
>>>
>>> Ummm, so no love for Call Return Tables?, wouldn't they go some way
>>> to reducing the number of conditional instructions spent checking for
>>> error return codes and having otherwise unneeded instructions
>>> situated right after the original call.
>>>
>>
>> A dedicated call-return table probably only really makes sense for
>> something like x86, which loads the return address from memory at the
>> same time as branching to it.
>>
>> If you use a link register, or return via some other special register
>> (such as treating R1 as a secondary link register), then all one needs
>> to do is check is that this register hasn't been modified within the
>> pipeline, and if so use the value held in this register as the
>> predicted branch target.
>>
>> In this case, typically one can reload the LR or "Secondary LR"
>> several cycles before its associated RTS or JMP. If one reloads the
>> link register before the others in a function epilog, then (typically)
>> the reloaded register will have left the pipeline before the CPU
>> reaches the return instruction.
>>
>>
>> Meanwhile, switch faces a problem that typically one calculates the
>> switch target immediately before branching to it. If one could somehow
>> do something like:
>>    Calculate where the "switch()" will go;
>>    Put some prior unrelated logic here;
>>    Do the branch to the switch target.
>>
>> Then "switch()" could potentially also be made predictable.
>
> You can do exactly that: figure index; index-load from a table in
> memory; do other stuff; indirect branch. Of course, that puts the table
> in dmem, which Mitch doesn't like, or requires a load instruction from
> imem.
>

It is a tradeoff...

My current implementation of switch tables is mostly based on
double-jumping, but this doesn't effect things too much. One calculates
where to jump into the jump table, rather than loading an address from a
table or similar (and adding it against another label used as a
reference point).

>> For small switch one might instead use linear probing or binary
>> subdivision or similar, in which case it is predictable if the
>> individual branches are predictable.
>>
>> Say (number of case labels):
>>    1-3: Linear Probe
>>    4-11: Binary Subdivide
>>    12-511 (and sufficiently dense): Branch Table
>>    Else: Binary Subdivide (1)
>>
>> *1: Binary subdivide happens until either it reaches the conditions
>> for a branch-table, or the number of targets is small enough that it
>> falls back to a linear probe.
>>
>> ...
>
> What matters is the distribution of indices, not the number of targets.
> Think a typical lexer: you want to isolate all alphas with one compare,
> not a four way binary to a particular alpha, because all the alphas go
> to a single label. Once you do that, normal ifconversion will get rid of
> half the internal branches of the decision tree..

It depends a fair bit on the pattern...

If we have a fairly dense table, such as ASCII characters, ideally one
wants a single jump through a table (it is compiled as a single jump
through a single table, if it fits the pattern that allows it to do so).

If it is a sparse distribution, such as TWOCC or FOURCC values, one
doesn't want a big jump table (trying to map a sparse TWOCC space to a
jump-table would waste absurd amounts of space).

Limiting the maximum size of the table also helps limit cases where a
large switch has dense regions and sparse regions, but the average
density falls just over the minimum limit. Splitting may result in the
large sparse regions effectively getting chopped off (and saving a lot
of space overall for large switch blocks).

How to partition the table optimally is non-trivial, and the current
implementation recursively divides the table roughly along the median
value (more likely to chop off sparse regions than splitting the table
at the center).

As noted, the typical worst-case number of branches is ~ log2(n_keys)
for the binary table. For direct jumps it is less, but then the table
has an ~ (key_max-key_min)*4 space overhead, which for sparse tables may
be significant.

So, I mostly fiddled with it to come up with something which seemed
acceptable.

....

On 6/29/2021 4:05 PM, Ivan Godard wrote:
> On 6/29/2021 1:33 PM, MitchAlsup wrote:
>> On Tuesday, June 29, 2021 at 2:27:46 PM UTC-5, Ivan Godard wrote:
>>> On 6/29/2021 9:01 AM, BGB wrote:
>>>> On 6/28/2021 10:45 PM, Andy wrote:
>>>>> On 27/06/21 7:31 am, MitchAlsup wrote:
>>>>>
>>>>>> There are five cases: Switches, Returns, Method calls, Tabulated
>>>>>> Calls, and Longjump.
>>>>>> <
>>>>>> Switches tend to be unpredictable much of the time.
>>>>>> Returns are easily highly predictable
>>>>>> Method calls tend to use few methods more than others
>>>>>> Tabulated calls tend to be indexed tables of entry points
>>>>>> And longjump is a category all by itself.
>>>>>
>>>>> Ummm, so no love for Call Return Tables?, wouldn't they go some way to
>>>>> reducing the number of conditional instructions spent checking for
>>>>> error return codes and having otherwise unneeded instructions situated
>>>>> right after the original call.
>>>>>
>>>>
>>>> A dedicated call-return table probably only really makes sense for
>>>> something like x86, which loads the return address from memory at the
>>>> same time as branching to it.
>>>>
>>>> If you use a link register, or return via some other special register
>>>> (such as treating R1 as a secondary link register), then all one needs
>>>> to do is check is that this register hasn't been modified within the
>>>> pipeline, and if so use the value held in this register as the
>>>> predicted
>>>> branch target.
>>>>
>>>> In this case, typically one can reload the LR or "Secondary LR" several
>>>> cycles before its associated RTS or JMP. If one reloads the link
>>>> register before the others in a function epilog, then (typically) the
>>>> reloaded register will have left the pipeline before the CPU reaches
>>>> the
>>>> return instruction.
>>>>
>>>>
>>>> Meanwhile, switch faces a problem that typically one calculates the
>>>> switch target immediately before branching to it. If one could somehow
>>>> do something like:
>>>> Calculate where the "switch()" will go;
>>>> Put some prior unrelated logic here;
>>>> Do the branch to the switch target.
>>>>
>>>> Then "switch()" could potentially also be made predictable.
>>> You can do exactly that: figure index; index-load from a table in
>>> memory; do other stuff; indirect branch. Of course, that puts the table
>>> in dmem, which Mitch doesn't like, or requires a load instruction
>>> from imem.
>> <
>> Switch is common enough that it should be performed in an instruction
>> (the multiway branch) I added limit checking to this due to how it
>> "worked out" in my ISA.
>> <
>> Also note: the tables in my switches remain program relative, so you
>> fetch
>> from ICache and then add this to the IP for the target address. This
>> saves
>> table size as the majority of all tables fit in 16-bit offsets,
>> retains program
>> relativity.
>> <
>>>> For small switch one might instead use linear probing or binary
>>>> subdivision or similar, in which case it is predictable if the
>>>> individual branches are predictable.
>>>>
>>>> Say (number of case labels):
>>>> 1-3: Linear Probe
>>>> 4-11: Binary Subdivide
>>>> 12-511 (and sufficiently dense): Branch Table
>>>> Else: Binary Subdivide (1)
>>>>
>>>> *1: Binary subdivide happens until either it reaches the conditions for
>>>> a branch-table, or the number of targets is small enough that it falls
>>>> back to a linear probe.
>>>>
>>>> ...
>>> What matters is the distribution of indices, not the number of targets.
>>> Think a typical lexer: you want to isolate all alphas with one compare,
>>> not a four way binary to a particular alpha, because all the alphas go
>>> to a single label. Once you do that, normal ifconversion will get rid of
>>> half the internal branches of the decision tree..
>> <
>> In any event, any HW is going to be able to sort through the situation
>> faster than any string of SW instructions.
>>
>
> Arguable.
>
> Label density matters for the tables too:
> switch (<32 bit>) {
> <cases: 11111, 22222, 33333, 44444, 55555, 66666, 77777, 88888, 99999>
>
> Do you really want 100k labels in your table, or a 3-deep compare tree?
>
> Out of curiosity, what happens when you throw that at Brian's compiler?

Hmm, hand-simulating my algo:
Range is 88888, so split along median 55555;
{11111, 22222, 33333, 44444}
N=4, Range=33333, Median=33333 (avg=27778), So Split:
{11111, 22222}, {33333, 44444}

{55555, 66666, 77777, 88888, 99999}
N=5, Range=44444, Median=77777, So Split:
{55555, 66666}, {77777, 88888, 99999}

No jump tables are used given table density is ~ 0.001%, which is well
below the minimum...

So, in BGBCC, this would compile as if it were, roughly:
if(val>=55555)
{
if(val>=77777)
{
if(val==77777) goto case_77777;
if(val==88888) goto case_88888;
if(val==99999) goto case_99999;
goto case_default;
}else
{
if(val==55555) goto case_55555;
if(val==66666) goto case_66666;
goto case_default;
}
}else
{
if(val>=33333)
{
if(val==33333) goto case_33333;
if(val==44444) goto case_44444;
goto case_default;
}else
{
if(val==11111) goto case_11111;
if(val==22222) goto case_22222;
goto case_default;
}
}

On 6/29/2021 11:09 PM, BGB wrote:
> On 6/29/2021 2:27 PM, Ivan Godard wrote:
>> On 6/29/2021 9:01 AM, BGB wrote:
>>> On 6/28/2021 10:45 PM, Andy wrote:
>>>> On 27/06/21 7:31 am, MitchAlsup wrote:
>>>>
>>>>> There are five cases: Switches, Returns, Method calls, Tabulated
>>>>> Calls, and Longjump.
>>>>> <
>>>>> Switches tend to be unpredictable much of the time.
>>>>> Returns are easily highly predictable
>>>>> Method calls tend to use few methods more than others
>>>>> Tabulated calls tend to be indexed tables of entry points
>>>>> And longjump is a category all by itself.
>>>>
>>>> Ummm, so no love for Call Return Tables?, wouldn't they go some way
>>>> to reducing the number of conditional instructions spent checking
>>>> for error return codes and having otherwise unneeded instructions
>>>> situated right after the original call.
>>>>
>>>
>>> A dedicated call-return table probably only really makes sense for
>>> something like x86, which loads the return address from memory at the
>>> same time as branching to it.
>>>
>>> If you use a link register, or return via some other special register
>>> (such as treating R1 as a secondary link register), then all one
>>> needs to do is check is that this register hasn't been modified
>>> within the pipeline, and if so use the value held in this register as
>>> the predicted branch target.
>>>
>>> In this case, typically one can reload the LR or "Secondary LR"
>>> several cycles before its associated RTS or JMP. If one reloads the
>>> link register before the others in a function epilog, then
>>> (typically) the reloaded register will have left the pipeline before
>>> the CPU reaches the return instruction.
>>>
>>>
>>> Meanwhile, switch faces a problem that typically one calculates the
>>> switch target immediately before branching to it. If one could
>>> somehow do something like:
>>>    Calculate where the "switch()" will go;
>>>    Put some prior unrelated logic here;
>>>    Do the branch to the switch target.
>>>
>>> Then "switch()" could potentially also be made predictable.
>>
>> You can do exactly that: figure index; index-load from a table in
>> memory; do other stuff; indirect branch. Of course, that puts the
>> table in dmem, which Mitch doesn't like, or requires a load
>> instruction from imem.
>>
>
> It is a tradeoff...
>
> My current implementation of switch tables is mostly based on
> double-jumping, but this doesn't effect things too much. One calculates
> where to jump into the jump table, rather than loading an address from a
> table or similar (and adding it against another label used as a
> reference point).
>
>
>>> For small switch one might instead use linear probing or binary
>>> subdivision or similar, in which case it is predictable if the
>>> individual branches are predictable.
>>>
>>> Say (number of case labels):
>>>    1-3: Linear Probe
>>>    4-11: Binary Subdivide
>>>    12-511 (and sufficiently dense): Branch Table
>>>    Else: Binary Subdivide (1)
>>>
>>> *1: Binary subdivide happens until either it reaches the conditions
>>> for a branch-table, or the number of targets is small enough that it
>>> falls back to a linear probe.
>>>
>>> ...
>>
>> What matters is the distribution of indices, not the number of
>> targets. Think a typical lexer: you want to isolate all alphas with
>> one compare, not a four way binary to a particular alpha, because all
>> the alphas go to a single label. Once you do that, normal ifconversion
>> will get rid of half the internal branches of the decision tree..
>
> It depends a fair bit on the pattern...
>
> If we have a fairly dense table, such as ASCII characters, ideally one
> wants a single jump through a table (it is compiled as a single jump
> through a single table, if it fits the pattern that allows it to do so).
>
>
> If it is a sparse distribution, such as TWOCC or FOURCC values, one
> doesn't want a big jump table (trying to map a sparse TWOCC space to a
> jump-table would waste absurd amounts of space).
>
> Limiting the maximum size of the table also helps limit cases where a
> large switch has dense regions and sparse regions, but the average
> density falls just over the minimum limit. Splitting may result in the
> large sparse regions effectively getting chopped off (and saving a lot
> of space overall for large switch blocks).
>
>
> How to partition the table optimally is non-trivial, and the current
> implementation recursively divides the table roughly along the median
> value (more likely to chop off sparse regions than splitting the table
> at the center).
>

Self-correction:
A value chosen from the middle of the range which approximates the
average value.

I realized after posting that the "median" would mean picking the value
from the middle of the table (and dividing it uniformly in half), which
isn't quite right.

Though, looking at it again, did go and tweak the algo used for pivot
selection here.

>
> As noted, the typical worst-case number of branches is ~ log2(n_keys)
> for the binary table. For direct jumps it is less, but then the table
> has an ~ (key_max-key_min)*4 space overhead, which for sparse tables may
> be significant.
>
>
> So, I mostly fiddled with it to come up with something which seemed
> acceptable.
>
>
> ...
>

Stephen Fuld wrote:
> On 6/29/2021 12:27 PM, Ivan Godard wrote:
> I am not a compiler guy, so forgive my ignorance.  What would a compiler
> do in such a situation?  Would it first test for something like if char
> >= "a" and <= "z", etc.?
>
> Just thinking about how I might do it, I think I would have a 256 byte
> array, indexed by the character value, with each entry having an
> indicator value, say 1 for lower case letters, 2 for upper case letters,
> 3 for numbers, 4 for white space characters, etc.  Looking up the value
> shouldn't be costly as most of the table with shortly be in D-cache.
> Then use the indicator value to index a jump or call table (which I
> guess is fairly predictable as most characters are lower case letters.
>
> But what do I know?  :-(

About the same as the standard C lib?

I.e. the classic character classification macros use just such a table.

As I noted previously, it tends to break down a bit with utf8, but you
can at least handle all 7-bit ascii very quickly.

Terje

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

Terje Mathisen <terje.mathisen@tmsw.no> schrieb:
> Stephen Fuld wrote:
>> On 6/29/2021 12:27 PM, Ivan Godard wrote:
>> I am not a compiler guy, so forgive my ignorance.  What would a compiler
>> do in such a situation?  Would it first test for something like if char
>> >= "a" and <= "z", etc.?
>>
>> Just thinking about how I might do it, I think I would have a 256 byte
>> array, indexed by the character value, with each entry having an
>> indicator value, say 1 for lower case letters, 2 for upper case letters,
>> 3 for numbers, 4 for white space characters, etc.  Looking up the value
>> shouldn't be costly as most of the table with shortly be in D-cache.
>> Then use the indicator value to index a jump or call table (which I
>> guess is fairly predictable as most characters are lower case letters.
>>
>> But what do I know?  :-(
>
> About the same as the standard C lib?
>
> I.e. the classic character classification macros use just such a table.
>
> As I noted previously, it tends to break down a bit with utf8, but you
> can at least handle all 7-bit ascii very quickly.

And if you don't sanitize your input, you can get "interesting"
results, such as when the value is negative for a signed char
or when testing if 99999 is printable.

There may be a few CVEs along those lines.

On 6/30/2021 7:19 AM, Terje Mathisen wrote:
> Stephen Fuld wrote:
>> On 6/29/2021 12:27 PM, Ivan Godard wrote:
>> I am not a compiler guy, so forgive my ignorance.  What would a
>> compiler do in such a situation?  Would it first test for something
>> like if char  >= "a" and <= "z", etc.?
>>
>> Just thinking about how I might do it, I think I would have a 256 byte
>> array, indexed by the character value, with each entry having an
>> indicator value, say 1 for lower case letters, 2 for upper case
>> letters, 3 for numbers, 4 for white space characters, etc.  Looking up
>> the value shouldn't be costly as most of the table with shortly be in
>> D-cache. Then use the indicator value to index a jump or call table
>> (which I guess is fairly predictable as most characters are lower case
>> letters.
>>
>> But what do I know?  :-(
>
> About the same as the standard C lib?
>
> I.e. the classic character classification macros use just such a table.
>
> As I noted previously, it tends to break down a bit with utf8, but you
> can at least handle all 7-bit ascii very quickly.
>

Yeah, the "ctype.h" functions in the C library I am using worked this way.

A few functions, like toupper and tolower also used lookup tables.

In a few cases, when I rewrote some of them to have ASM special cases, I
eliminated the lookup tables in favor of direct range checks as direct
range-checks tended to be faster than the use of lookup tables.

Though, this sort of thing is not always the case, for example:
I recently tried experimentally modifying the Doom renderer to use
compressed textures and color modulation in place of 8-bpp textures and
lookups via a colormap table (with things like sprite graphics
effectively using alpha-testing in place of drawing a column in multiple
pieces).

The color-modulated logic tended to be slightly slower than the use of
colormaps (there was an ~ 20% increase in frame-times), I suspect due to
the slightly higher latency of the drawing funcs (and the loops I wrote
only doing one pixel per loop iteration rather than multiple pixels).

Note that flats were in Morton order, whereas wall patches and sprites
were in column order (with effectively 4 pixel columns being merged into
a single compressed-texture column).

Granted, there was also an certain amount of time being spent converting
from Doom's native formats into compressed-texture form, and there were
also some visible artifacts from the conversion process, ...

On 30/06/2021 14:36, Thomas Koenig wrote:
> Terje Mathisen <terje.mathisen@tmsw.no> schrieb:
>> Stephen Fuld wrote:
>>> On 6/29/2021 12:27 PM, Ivan Godard wrote:
>>> I am not a compiler guy, so forgive my ignorance.  What would a compiler
>>> do in such a situation?  Would it first test for something like if char
>>> >= "a" and <= "z", etc.?
>>>
>>> Just thinking about how I might do it, I think I would have a 256 byte
>>> array, indexed by the character value, with each entry having an
>>> indicator value, say 1 for lower case letters, 2 for upper case letters,
>>> 3 for numbers, 4 for white space characters, etc.  Looking up the value
>>> shouldn't be costly as most of the table with shortly be in D-cache.
>>> Then use the indicator value to index a jump or call table (which I
>>> guess is fairly predictable as most characters are lower case letters.
>>>
>>> But what do I know?  :-(
>>
>> About the same as the standard C lib?
>>
>> I.e. the classic character classification macros use just such a table.
>>
>> As I noted previously, it tends to break down a bit with utf8, but you
>> can at least handle all 7-bit ascii very quickly.

It breaks down a /lot/ with UTF-8 - the traditional <ctype.h>
classifications such as "isdigit" or "tolower" collapse pretty quickly
in the face of non-ASCII character sets. Locales can help a bit, but
you don't have to get very exotic before the answer is "it's complicated".

>
> And if you don't sanitize your input, you can get "interesting"
> results, such as when the value is negative for a signed char
> or when testing if 99999 is printable.
>
> There may be a few CVEs along those lines.
>

The C standard library functions here all take "int" parameters, with
the results defined for EOF or a value in the range of unsigned char.
Giving them anything else is undefined behaviour - it is the
programmer's fault, and the programmer's problem.

However, range testing the value is so simple and obvious that I would
not expect any C library implementation to have problems here.

On Tuesday, June 29, 2021 at 10:00:04 PM UTC-5, Stefan Monnier wrote:
> >> >> BTW, what kind of prediction structure do you foresee for your "multiway
> >> >> branch" instructions? Do you foresee predicting the index (and then
> >> >> looking up the corresponding target address in the table), so similar to
> >> >> a taken/nottaken predictor but just returning more than one bit, or do
> >> >> you foresee something more like a BTB (i.e. predict the actual target
> >> >> address of the branch)?
> >> > For narrow machines:: do absolutely nothing
> >> Meaning... stall the pipeline?
> > You need to remember My 66000 ISA has a Jump-through-table instruction
> > that performs dense switch ranges.
> Yes my question is specifically about those instructions.
> > So, it takes a few cycles (on the order of a LD) and then control
> > arrives at case label.
> [...]
> > You can call this stalling of the pipeline, but SW did not have to perform the
> > range compare, and LD through the index, then JMP to the case label. All in
> > all it saves 3-4 instructions and takes (on average) a bit less time than the
> > SW equivalent, so at worst it is break even when compared to std RISC
> > architectures.
> I guess the SW equivalent has typically 2 branches (a conditional one for
> out-of-bounds handling and an indirect one for the actual jump), so it
> likely won't take less than 2 cycles on most systems?
>
> You're probably right that on a narrow enough machine, stalling might be
> about as good. Still, after you fetch&decode the switch instruction,
> you have to:
> - wait for all the data-dependencies to clear in order to get
> your index. For a 10-deep pipeline, that could be what, 2 cycles?
<
The narrow machine is 8 cycles deep::
Fetch:Parse:Decode:Execute:Cache:Align:Wait:Write
<
> - fetch the data from the L1$. Latency would be what? 3 cycles?
<
There is a good chance the offset may be in the instruction buffer
when the index is small, otherwise the ICache access is 1 cycle shorter
than the DCache access. And with 4-word-wide fetch, you are getting 8
offsets per access So, if the index is less than 16, you already have the
offset.
<
> do you think you can shorten that by prefetching the cache line before
> we know the index and then using the index into the cache line to
> reduce this part of the latency to a single cycle?
<
My general guess is that the process is index-bound:: you are more likely
to be waiting for the index before you can get started than the other way
around.
<
> - then finally we have the address of the next instruction and can fetch
> it from L1$.
> If the target is hard to predict, stalling (and working to minimize the
> latency) is the better option, indeed.
>
>
> Stefan

On 6/30/2021 9:21 AM, David Brown wrote:
> On 30/06/2021 14:36, Thomas Koenig wrote:
>> Terje Mathisen <terje.mathisen@tmsw.no> schrieb:
>>> Stephen Fuld wrote:
>>>> On 6/29/2021 12:27 PM, Ivan Godard wrote:
>>>> I am not a compiler guy, so forgive my ignorance.  What would a compiler
>>>> do in such a situation?  Would it first test for something like if char
>>>> >= "a" and <= "z", etc.?
>>>>
>>>> Just thinking about how I might do it, I think I would have a 256 byte
>>>> array, indexed by the character value, with each entry having an
>>>> indicator value, say 1 for lower case letters, 2 for upper case letters,
>>>> 3 for numbers, 4 for white space characters, etc.  Looking up the value
>>>> shouldn't be costly as most of the table with shortly be in D-cache.
>>>> Then use the indicator value to index a jump or call table (which I
>>>> guess is fairly predictable as most characters are lower case letters.
>>>>
>>>> But what do I know?  :-(
>>>
>>> About the same as the standard C lib?
>>>
>>> I.e. the classic character classification macros use just such a table.
>>>
>>> As I noted previously, it tends to break down a bit with utf8, but you
>>> can at least handle all 7-bit ascii very quickly.
>
> It breaks down a /lot/ with UTF-8 - the traditional <ctype.h>
> classifications such as "isdigit" or "tolower" collapse pretty quickly
> in the face of non-ASCII character sets. Locales can help a bit, but
> you don't have to get very exotic before the answer is "it's complicated".
>

If one is feeding raw byte or char values to these functions, and using
UTF-8 or similar, then as soon as one gets outside ASCII range the
answer is basically useless.

Simple case is to ignore everything outside the ASCII range.

Secondary option is to treat everything outside the ASCII range as if it
were Codepage-1252 or Latin-1.

For wider characters, one would likely need some other functions, like
those from 'wctype.h', but then it depends on locale rather than "just
assume it is UTF-16 or something".

Or, at least assuming the locale actually does something (simpler answer
is to hard wire it).

In BGBCC, the patterns I followed are:
Narrow strings (in C) are typically Codepage-1252 by default;
Except when they are UTF-8.
Wide strings are typically UTF-16.

I went with the Windows pattern of using UTF-16 for wide-strings and
wchar_t, rather than the Linux pattern of using UTF-32, partly because
UTF-32 is impractically wasteful, and rarely useful. Similarly, one
still doesn't get "one character, one codepoint" even with UTF-32 when
it comes to things like emojis or similar, so alas...

>>
>> And if you don't sanitize your input, you can get "interesting"
>> results, such as when the value is negative for a signed char
>> or when testing if 99999 is printable.
>>
>> There may be a few CVEs along those lines.
>>
>
> The C standard library functions here all take "int" parameters, with
> the results defined for EOF or a value in the range of unsigned char.
> Giving them anything else is undefined behaviour - it is the
> programmer's fault, and the programmer's problem.
>
> However, range testing the value is so simple and obvious that I would
> not expect any C library implementation to have problems here.
>

Yep.

David Brown <david.brown@hesbynett.no> schrieb:

(ctype.h)

> However, range testing the value is so simple and obvious that I would
> not expect any C library implementation to have problems here.

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=78155 has the non-nice
example

$ cat foo.c
int main (void)
{ __builtin_printf ("%i\n", __builtin_isalpha (999999));
} $ gcc foo.c
$ ./a.out
Segmentation fault (core dumped)

On 30/06/2021 16:59, BGB wrote:
> On 6/30/2021 9:21 AM, David Brown wrote:
>> On 30/06/2021 14:36, Thomas Koenig wrote:
>>> Terje Mathisen <terje.mathisen@tmsw.no> schrieb:
>>>> Stephen Fuld wrote:
>>>>> On 6/29/2021 12:27 PM, Ivan Godard wrote:
>>>>> I am not a compiler guy, so forgive my ignorance.  What would a
>>>>> compiler
>>>>> do in such a situation?  Would it first test for something like if
>>>>> char
>>>>>   >= "a" and <= "z", etc.?
>>>>>
>>>>> Just thinking about how I might do it, I think I would have a 256 byte
>>>>> array, indexed by the character value, with each entry having an
>>>>> indicator value, say 1 for lower case letters, 2 for upper case
>>>>> letters,
>>>>> 3 for numbers, 4 for white space characters, etc.  Looking up the
>>>>> value
>>>>> shouldn't be costly as most of the table with shortly be in D-cache.
>>>>> Then use the indicator value to index a jump or call table (which I
>>>>> guess is fairly predictable as most characters are lower case letters.
>>>>>
>>>>> But what do I know?  :-(
>>>>
>>>> About the same as the standard C lib?
>>>>
>>>> I.e. the classic character classification macros use just such a table.
>>>>
>>>> As I noted previously, it tends to break down a bit with utf8, but you
>>>> can at least handle all 7-bit ascii very quickly.
>>
>> It breaks down a /lot/ with UTF-8 - the traditional <ctype.h>
>> classifications such as "isdigit" or "tolower" collapse pretty quickly
>> in the face of non-ASCII character sets.  Locales can help a bit, but
>> you don't have to get very exotic before the answer is "it's
>> complicated".
>>
>
> If one is feeding raw byte or char values to these functions, and using
> UTF-8 or similar, then as soon as one gets outside ASCII range the
> answer is basically useless.
>
> Simple case is to ignore everything outside the ASCII range.
>
> Secondary option is to treat everything outside the ASCII range as if it
> were Codepage-1252 or Latin-1.
>
>
>
> For wider characters, one would likely need some other functions, like
> those from 'wctype.h', but then it depends on locale rather than "just
> assume it is UTF-16 or something".
>
> Or, at least assuming the locale actually does something (simpler answer
> is to hard wire it).
>
> In BGBCC, the patterns I followed are:
>   Narrow strings (in C) are typically Codepage-1252 by default;
>     Except when they are UTF-8.
>   Wide strings are typically UTF-16.
>
> I went with the Windows pattern of using UTF-16 for wide-strings and
> wchar_t, rather than the Linux pattern of using UTF-32, partly because
> UTF-32 is impractically wasteful, and rarely useful. Similarly, one
> still doesn't get "one character, one codepoint" even with UTF-32 when
> it comes to things like emojis or similar, so alas...
>

I dislike the idea of making things OS specific. Latin-1 is really the
only good choice for an extended 8-bit character set, with wide support.
Anything beyond that (Latin-15, CP-1252, etc.) is going to come out
wrong with some programs.

Using UTF-16 in this day and age is just /wrong/. It is the worst
choice you can have. It doesn't give you a code point per code unit, so
has no advantage over UTF-8. It doesn't have ASCII compatibility and
suffers from endianness choices, giving the disadvantages of UTF-32.
The only possible reason to use it is for interfacing to other code or
API's that are currently UTF-16 - and even Windows is moving to UTF-8.

On 30/06/2021 17:42, Thomas Koenig wrote:
> David Brown <david.brown@hesbynett.no> schrieb:
>
> (ctype.h)
>
>> However, range testing the value is so simple and obvious that I would
>> not expect any C library implementation to have problems here.
>
> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=78155 has the non-nice
> example
>
> $ cat foo.c
> int main (void)
> {
> __builtin_printf ("%i\n", __builtin_isalpha (999999));
> }
> $ gcc foo.c
> $ ./a.out
> Segmentation fault (core dumped)
>

These builtins are a different matter. These are undocumented
functions, used by libraries to implement the documented ones. (There
are plenty of other builtins that /are/ documented.) That is a bug in
the user program, not the compiler, just as derefrencing an invalid
pointer or dividing by zero is a program bug.

Actually, calling standard library "isalpha" with 999999 (assuming you
don't have 32-bit char) and getting a segmentation fault is a programmer
bug too. But it makes sense to have some extra sanity checks on library
functions to help programmers catch their bugs.

David Brown <david.brown@hesbynett.no> schrieb:
> On 30/06/2021 17:42, Thomas Koenig wrote:
>> David Brown <david.brown@hesbynett.no> schrieb:
>>
>> (ctype.h)
>>
>>> However, range testing the value is so simple and obvious that I would
>>> not expect any C library implementation to have problems here.
>>
>> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=78155 has the non-nice
>> example
>>
>> $ cat foo.c
>> int main (void)
>> {
>> __builtin_printf ("%i\n", __builtin_isalpha (999999));
>> }
>> $ gcc foo.c
>> $ ./a.out
>> Segmentation fault (core dumped)
>>
>
> These builtins are a different matter. These are undocumented
> functions, used by libraries to implement the documented ones.

This isn't any better:

$ cat foo.c
#include <ctype.h>
#include <stdio.h>

int main (void)
{ printf ("%i\n", isalpha (999999));
} $ gcc foo.c
$ ./a.out
Segmentation fault (core dumped)

This just serves to illustrate that the arguments to isalpha() and
friends can lead to undefined behavior, and these functions should
not be called on unsanitized data.

On 6/30/2021 10:44 AM, David Brown wrote:
> On 30/06/2021 16:59, BGB wrote:
>> On 6/30/2021 9:21 AM, David Brown wrote:
>>> On 30/06/2021 14:36, Thomas Koenig wrote:
>>>> Terje Mathisen <terje.mathisen@tmsw.no> schrieb:
>>>>> Stephen Fuld wrote:
>>>>>> On 6/29/2021 12:27 PM, Ivan Godard wrote:
>>>>>> I am not a compiler guy, so forgive my ignorance.  What would a
>>>>>> compiler
>>>>>> do in such a situation?  Would it first test for something like if
>>>>>> char
>>>>>>   >= "a" and <= "z", etc.?
>>>>>>
>>>>>> Just thinking about how I might do it, I think I would have a 256 byte
>>>>>> array, indexed by the character value, with each entry having an
>>>>>> indicator value, say 1 for lower case letters, 2 for upper case
>>>>>> letters,
>>>>>> 3 for numbers, 4 for white space characters, etc.  Looking up the
>>>>>> value
>>>>>> shouldn't be costly as most of the table with shortly be in D-cache.
>>>>>> Then use the indicator value to index a jump or call table (which I
>>>>>> guess is fairly predictable as most characters are lower case letters.
>>>>>>
>>>>>> But what do I know?  :-(
>>>>>
>>>>> About the same as the standard C lib?
>>>>>
>>>>> I.e. the classic character classification macros use just such a table.
>>>>>
>>>>> As I noted previously, it tends to break down a bit with utf8, but you
>>>>> can at least handle all 7-bit ascii very quickly.
>>>
>>> It breaks down a /lot/ with UTF-8 - the traditional <ctype.h>
>>> classifications such as "isdigit" or "tolower" collapse pretty quickly
>>> in the face of non-ASCII character sets.  Locales can help a bit, but
>>> you don't have to get very exotic before the answer is "it's
>>> complicated".
>>>
>>
>> If one is feeding raw byte or char values to these functions, and using
>> UTF-8 or similar, then as soon as one gets outside ASCII range the
>> answer is basically useless.
>>
>> Simple case is to ignore everything outside the ASCII range.
>>
>> Secondary option is to treat everything outside the ASCII range as if it
>> were Codepage-1252 or Latin-1.
>>
>>
>>
>> For wider characters, one would likely need some other functions, like
>> those from 'wctype.h', but then it depends on locale rather than "just
>> assume it is UTF-16 or something".
>>
>> Or, at least assuming the locale actually does something (simpler answer
>> is to hard wire it).
>>
>> In BGBCC, the patterns I followed are:
>>   Narrow strings (in C) are typically Codepage-1252 by default;
>>     Except when they are UTF-8.
>>   Wide strings are typically UTF-16.
>>
>> I went with the Windows pattern of using UTF-16 for wide-strings and
>> wchar_t, rather than the Linux pattern of using UTF-32, partly because
>> UTF-32 is impractically wasteful, and rarely useful. Similarly, one
>> still doesn't get "one character, one codepoint" even with UTF-32 when
>> it comes to things like emojis or similar, so alas...
>>
>
> I dislike the idea of making things OS specific. Latin-1 is really the
> only good choice for an extended 8-bit character set, with wide support.
> Anything beyond that (Latin-15, CP-1252, etc.) is going to come out
> wrong with some programs.
>

Pretty much, though Latin-1 and CP-1252 are close enough that the
differences can be mostly fudged over (a few more printable characters
vs a control character space "pretty much no one uses anyways").

> Using UTF-16 in this day and age is just /wrong/. It is the worst
> choice you can have. It doesn't give you a code point per code unit, so
> has no advantage over UTF-8. It doesn't have ASCII compatibility and
> suffers from endianness choices, giving the disadvantages of UTF-32.
> The only possible reason to use it is for interfacing to other code or
> API's that are currently UTF-16 - and even Windows is moving to UTF-8.
>

UTF-8 is generally a good option.

Though in this case it is more a question of what happens when someone
writes something like:
wchar_t *ws0;
...
ws0=L"Something String";

Windows went with UTF-16 here, and Linux went with UTF-32.

I went with UTF-16 as well, because UTF-32 is horribly wasteful as any
sort of default, and because in most regards BGBCC follows similar
patterns as MSVC, with the main exception of 'sizeof(long)' being 8 on
64-bit targets as keeping sizeof(long)==sizeof(void *) seemed like a
more useful property than keeping long being 32 bits.

As can be noted, not even UTF-32 gives one character per code-point,
since many emojis and CJK characters are encoded using combining
characters, so this battle is basically already lost.

And, likewise:
char *s0;
s0="Some String"; //assumes CP-1252 by default

Because, while one could use UTF-8 here, this actually goes horribly
wrong if compiling programs which assume the ability to shove raw binary
data into string literals.

The actual conversion is a little wonky:
ASCII range maps as-is;
0x80 .. 0xFF map through directly;
Any other characters in CP-1252 map to their associated spots;
Any codepoints from CP-437 also map to their associated spots;
Also some amount of PETSCII codepoints and similar (*2);
Pretty much everything else gets dumped off at 0x8F.

So, narrow string literals in C are a little bit lossy in this sense.

Internally, the compiler stores pretty much everything as UTF-8 though,
and emits the strings in their final encoding when the final binary is
produced.

*2: The built in text-mode hardware font in my BJX2 core is capable of
displaying CP-1252, CP-437, and PETSCII glyphs at the same time; though
granted 8-bit strings can't encode these at the same time (using glyphs
outside the ASCII/1252 set effectively requires the use of ANSI escape
codes or similar).

Technically, one can also do this:
char32_t *ls0;
ls0=U"Some UTF-32 String"; //explicit UTF-32
Or:
char16_t *us0;
us0=u"Some UTF-16 String"; //explicit UTF-16

Or:
char *s0;
s0=u8"Some UTF-8 String"; //explicit UTF-8

As for my "TestKern OS", generally most of the other API functions
assume UTF-8 as the default (pretty much anything involving the
filesystem or similar assumes UTF-8 strings).

....

On Wednesday, June 30, 2021 at 12:07:53 PM UTC-5, Thomas Koenig wrote:
> David Brown <david...@hesbynett.no> schrieb:
> > On 30/06/2021 17:42, Thomas Koenig wrote:
> >> David Brown <david...@hesbynett.no> schrieb:
> >>
> >> (ctype.h)
> >>
> >>> However, range testing the value is so simple and obvious that I would
> >>> not expect any C library implementation to have problems here.
> >>
> >> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=78155 has the non-nice
> >> example
> >>
> >> $ cat foo.c
> >> int main (void)
> >> {
> >> __builtin_printf ("%i\n", __builtin_isalpha (999999));
> >> }
> >> $ gcc foo.c
> >> $ ./a.out
> >> Segmentation fault (core dumped)
> >>
> >
> > These builtins are a different matter. These are undocumented
> > functions, used by libraries to implement the documented ones.
> This isn't any better:
>
> $ cat foo.c
> #include <ctype.h>
> #include <stdio.h>
>
> int main (void)
> {
> printf ("%i\n", isalpha (999999));
> }
> $ gcc foo.c
> $ ./a.out
> Segmentation fault (core dumped)
> This just serves to illustrate that the arguments to isalpha() and
> friends can lead to undefined behavior, and these functions should
> not be called on unsanitized data.
<
Why does isalpha NOT check its input argument range ?????

MitchAlsup <MitchAlsup@aol.com> schrieb:

> Why does isalpha NOT check its input argument range ?????

Another of those features of C that did not age well. It made
sense in the 1970s, less so in the 2020s.

A better alternative is to use

#include <safe-ctype.h>

and then ISALPHA etc. This is a gcc extension, not sure
if LLVM has it or not.

On 2021-06-30, BGB wrote:
> On 6/30/2021 9:21 AM, David Brown wrote:
>> On 30/06/2021 14:36, Thomas Koenig wrote:
>>> Terje Mathisen <terje.mathisen@tmsw.no> schrieb:
>>>> Stephen Fuld wrote:
>>>>> On 6/29/2021 12:27 PM, Ivan Godard wrote:
>>>>> I am not a compiler guy, so forgive my ignorance.  What would a
>>>>> compiler
>>>>> do in such a situation?  Would it first test for something like if
>>>>> char
>>>>>   >= "a" and <= "z", etc.?
>>>>>
>>>>> Just thinking about how I might do it, I think I would have a 256 byte
>>>>> array, indexed by the character value, with each entry having an
>>>>> indicator value, say 1 for lower case letters, 2 for upper case
>>>>> letters,
>>>>> 3 for numbers, 4 for white space characters, etc.  Looking up the
>>>>> value
>>>>> shouldn't be costly as most of the table with shortly be in D-cache.
>>>>> Then use the indicator value to index a jump or call table (which I
>>>>> guess is fairly predictable as most characters are lower case letters.
>>>>>
>>>>> But what do I know?  :-(
>>>>
>>>> About the same as the standard C lib?
>>>>
>>>> I.e. the classic character classification macros use just such a table.
>>>>
>>>> As I noted previously, it tends to break down a bit with utf8, but you
>>>> can at least handle all 7-bit ascii very quickly.
>>
>> It breaks down a /lot/ with UTF-8 - the traditional <ctype.h>
>> classifications such as "isdigit" or "tolower" collapse pretty quickly
>> in the face of non-ASCII character sets.  Locales can help a bit, but
>> you don't have to get very exotic before the answer is "it's
>> complicated".
>>
>
> If one is feeding raw byte or char values to these functions, and using
> UTF-8 or similar, then as soon as one gets outside ASCII range the
> answer is basically useless.
>
> Simple case is to ignore everything outside the ASCII range.
>
> Secondary option is to treat everything outside the ASCII range as if it
> were Codepage-1252 or Latin-1.
>
>
>
> For wider characters, one would likely need some other functions, like
> those from 'wctype.h', but then it depends on locale rather than "just
> assume it is UTF-16 or something".
>

There's a clear difference between string encoding (ASCII, Latin-1,
CP-1252, UTF-8, UTF-16, ...) and character encoding. The latter can
usually be safely represented as a 32-bit integer representing a
single Unicode code point.

In my opinion, any function dealing with a single character at a time
should use Unicode code points as input/output (rather than locale
dependent encodings that is just a big source of bugs).

For instance in the GLFW text input API, all input events carry an
unsigned int representing the Unicode code point for a single character:

https://www.glfw.org/docs/latest/input_guide.html#input_char

....whereas functions that deal with text strings use UTF-8 encoding,
like glfwSetWindowTitle():

https://www.glfw.org/docs/latest/window_guide.html#window_title

My personal preference for C/C++ applications is to use UTF-8 strings
everywhere internally, and whenever an external API (e.g. the Win32 API)
is used - do the necessary string translations in conjunction with the
API calls. On POSIX systems you usally do not have to do any
translations since most API:s accept UTF-8 strings.

I successfully used this design philosophy for BuildCache, for instance.

> Or, at least assuming the locale actually does something (simpler answer
> is to hard wire it).
>
> In BGBCC, the patterns I followed are:
>   Narrow strings (in C) are typically Codepage-1252 by default;
>     Except when they are UTF-8.
>   Wide strings are typically UTF-16.
>
> I went with the Windows pattern of using UTF-16 for wide-strings and
> wchar_t, rather than the Linux pattern of using UTF-32, partly because
> UTF-32 is impractically wasteful, and rarely useful. Similarly, one
> still doesn't get "one character, one codepoint" even with UTF-32 when
> it comes to things like emojis or similar, so alas...
>
>
>>>
>>> And if you don't sanitize your input, you can get "interesting"
>>> results, such as when the value is negative for a signed char
>>> or when testing if 99999 is printable.
>>>
>>> There may be a few CVEs along those lines.
>>>
>>
>> The C standard library functions here all take "int" parameters, with
>> the results defined for EOF or a value in the range of unsigned char.
>> Giving them anything else is undefined behaviour - it is the
>> programmer's fault, and the programmer's problem.
>>
>> However, range testing the value is so simple and obvious that I would
>> not expect any C library implementation to have problems here.
>>
>
> Yep.