Standard C++ way to generate a Jump Table ???
Peter Olcott
of an assembly language jump table:
switch(N)
{
case 0:
case 1:
case 2:
case 3:
case 4:
case 5:
case 6:
case 7:
}
mov eax, DWORD PTR _N$[esp-4]
cmp eax, 7
ja SHORT $LN1_TestSpeed
jmp DWORD PTR $LN14_TestSpeed[eax*4]
I am looking for a way to be able to specify C++ code such
that the second and third line of the assembly language
would not be generated. The only way that I can think to do
this is to delete the two lines and compile it as assembly
language.
Are there any possible standard C++ ways to do this?
Sam
Well, if I understood you correctly:
The only possible way you can hope to have the C++ compiler optimize away
the comparison, with you still using standard C++ as your source, is for you
replace your literal integer values with an enum type that contains only
eight values, something like
enum something {
firstval=0,
…
lastval=7
};
Then, if you switch to an instance of the enumerated type, the C++ compiler
might be smart enough to realize that, technically, the switch specifies all
possible values, so the boundary check is not needed. You may have to
specify a fairly aggressive optimization level, for you C++ compiler, in
order for it to make that assumption.
blargg
> lastval=7
> };
[...]
Couldn't a compiler also make use of undefined behavior? For example,
switch(N)
{
case 0: ... break;
case 1: ... break;
case 2: ... break;
case 3: ... break;
case 4: ... break;
case 5: ... break;
case 6: ... break;
case 7: ... break;
default:
*(int*) 0 = 0; // undefined behavior
}
Since the statement under the default case results in undefined
behavior, the compiler would be free to eliminate the range check, such
that instead of N<0||N>7 causing a dereference of null, it would read
outside the jump table. This would be an interesting general way of
telling the compiler that some situation can never occur. For example,
#define IMPOSSIBLE() (*(int*) 0 = 0)
if ( n < 0 || n > 7 )
IMPOSSIBLE();
would be a concise, clear way to tell the compiler that n was never
outside the range 0...7 when execution passes this line.
Ivan A. Kosarev
If it's known there are only these eight different values of N possible,
then one of the case labels can be replaced with the default label so
that your compiler will have no need to handle the default case implicitly.
> Are there any possible standard C++ ways to do this?
There is no a standard way to specify a statement to be a jump table. A
call table, however, can be implemented with a table of function pointers.
--
Ivan A. Kosarev
> Peter Olcott writes:
>
>> This is as close as I could get to generating the equivalent of an
>> assembly language jump table:
>>
>> switch(N)
>> {
>> case 0:
>> case 1:
>> case 2:
>> case 3:
>> case 4:
>> case 5:
>> case 6:
>> case 7:
>> }
> The only possible way you can hope to have the C++ compiler optimize
> away the comparison, with you still using standard C++ as your source,
> is for you replace your literal integer values with an enum type that
> contains only eight values, something like
>
> enum something {
> firstval=0,
> …
> lastval=7
> };
>
> Then, if you switch to an instance of the enumerated type, the C++
> compiler might be smart enough to realize that, technically, the switch
> specifies all possible values, so the boundary check is not needed. You
> may have to specify a fairly aggressive optimization level, for you C++
> compiler, in order for it to make that assumption.
A couple of notes:
a) the extra comparison in the assembly code is not actually "a boundary
check" and implements a bypass for the body of the switch statement due
to the default label is omitted and
b) the set of values of the enumeration defined is not limited to values
of the enumerators specified. A enumeration is able to represent any
value from the range of values of its underlying type; see C++ 7.2 #6.
--
Paavo Helde
Out of curiosity - have you measured how much effect deleting these two
lines would give you? (Presuming of course there are some non-empty cases,
otherwise the compiler should optimize the whole construction away.)
> Are there any possible standard C++ ways to do this?
>
Standard C++ requires the code to work also if N is outside of [0,7], so it
cannot strip away the code for that. You could try to declare N as unsigned
char and provide all 256 cases.
FWIW, MSVC++ provides the __assume keyword as an extension, letting one to
tell the optimizer things like that. The example in the MSDN documentation
is exactly about optimizing out the default branch of a switch.
Paavo
Paavo Helde
Note that the enum values are required to accommodate any number fitting
into the same number of bits as the declared enum values. So the
optimization would be possible only if the enum provides dense values
from 0 up to some 2^N-1. This is the case here, indeed, so in principle,
the compiler ought to be able to strip out the boundary check, but I
would not bet my money on any existing compiler actually doing that.
Paavo
Paavo Helde
>
> b) the set of values of the enumeration defined is not limited to values
> of the enumerators specified. A enumeration is able to represent any
> value from the range of values of its underlying type; see C++ 7.2 #6.
Not exactly - the clause you cite talks about bitfields:
<quote>
For an enumeration where emin is the smallest enumerator and emax is the
largest, the values of the enumeration
are the values of the underlying type in the range bmin to bmax, where bmin
and bmax are, respectively,
the smallest and largest values of the smallest bit-field that can store
emin and emax. It is possible to
define an enumeration that has values not defined by any of its
enumerators.
</quote>
Thus, for the example in OP post the underlying type could well be some 32-
bit int, whereas the valid values would be only those in range 0..7.
Paavo
Peter Olcott
"Ivan A. Kosarev" <i...@unicals.com> wrote in message
news:NG_yl.124252$C87....@newsfe30.ams2...
I am shooting for maximum speed, thus function call overhead
is not acceptable.
Peter Olcott
"Paavo Helde" <pa...@nospam.please.ee> wrote in message
news:Xns9BDB5D92C2...@216.196.109.131...
Both suggestions are extremely helpful, thanks.
PeteOlcott
When I attempt to optimize my code, I do not take the term "optimize"
figuratively like compiler optimizers do. When I optimize my code I
make every attempt to make the code as fast as possible within the
binding constraint of the semantic requirements. Also I carefully
select the set of semantic requirements from a categorically
exhaustive set of every combination that provides the desired end-
result. This process works exceptionally well for all development
where the desired end-result can be specified in a mathematically
rigorous way.
> > Are there any possible standard C++ ways to do this?
>
> Standard C++ requires the code to work also if N is outside of [0,7], so it
> cannot strip away the code for that. You could try to declare N as unsigned
> char and provide all 256 cases.
>
> FWIW, MSVC++ provides the __assume keyword as an extension, letting one to
> tell the optimizer things like that. The example in the MSDN documentation
> is exactly about optimizing out the default branch of a switch.
>
> Paavo- Hide quoted text -
>
> - Show quoted text -
Paavo Helde
>
> When I attempt to optimize my code, I do not take the term "optimize"
> figuratively like compiler optimizers do. When I optimize my code I
> make every attempt to make the code as fast as possible within the
> binding constraint of the semantic requirements. Also I carefully
> select the set of semantic requirements from a categorically
> exhaustive set of every combination that provides the desired end-
> result. This process works exceptionally well for all development
> where the desired end-result can be specified in a mathematically
> rigorous way.
Sounds like you should really program in assembler, then. However, even
this can't guarantee full control nowadays, with microcode, branch
prediction, virtual machines, multi-core cache syncing, etc. I believe
there is no need to mention a well-known cite from a well-known 70-era
computer scientist.
Best regards
Paavo
Peter Olcott
Donald Knuth made the following statement on optimization:
"We should forget about small efficiencies, say about 97% of
the time: premature optimization is the root of all evil."
Although he may have been right for most of software
development (application programming) I would go so far as
to say that he was flat out wrong for systems programming.
With the process that I have created, the ballpark of the
best possible system** can be created for about the same
cost as mediocrity, because the cost break down is 70%
design 20% coding and 10% debugging and testing. ** Maximum
speed, ease of use, maintainability and reliability.
No, actually with your great suggestion that eliminated the
extra code in the C++ switch statement I can finally produce
the quality of code that I have been striving for all along.
I can tell from the quality of the generated assembly
language that there is no possible further improvement of
this fundamental control flow construct. (Within the binding
constraint of the machine architecture).
Paavo Helde
> No, actually with your great suggestion that eliminated the
> extra code in the C++ switch statement I can finally produce
> the quality of code that I have been striving for all along.
Out of interest, which suggestion do you refer to? unsigned char, __assume
or enum N^2? And how many percents of speed increase in typical usage?
Don't get me wrong, I'm a big fan of (program) performance myself. But I
usually stop much earlier. I would just like to know what I'm losing.
Best regards
Paavo
Peter Olcott
> "Peter Olcott" <NoS...@SeeScreen.com> kirjutas:
>
>> No, actually with your great suggestion that eliminated
>> the
>> extra code in the C++ switch statement I can finally
>> produce
>> the quality of code that I have been striving for all
>> along.
>
> Out of interest, which suggestion do you refer to?
> unsigned char, __assume
> or enum N^2? And how many percents of speed increase in
> typical usage?
I missed the last one. The first one was enlightening, and I
used the second one. I estimate that the speed of the
critical loop will be between 20% to 30% faster.
Your suggestion can be applied to four different places in
this tight loop.
The reason that I am optimizing by this degree is that it
only takes me a few extra days for a year long project, and
it is good to know in advance that no one will be able to
beat my system's performance. I estimate that it will be at
least 100-fold faster than the next best alternative system.
>
> Don't get me wrong, I'm a big fan of (program) performance
> myself. But I
> usually stop much earlier. I would just like to know what
> I'm losing.
When one very tiny portion of the system represents 98% of
the CPU cycles it is probably always worth extreme levels of
optimization. My heuristic was to stop just short of actual
assembly language programming. The rest of the system might
take about twice as long as the fastest possible code.
I may eventually optimize this code too. My goal is to make
a product of the same quality as Turbo Pascal 3.0. In my
opinion this product was an example of the epitome of the
best possible quality.
>
> Best regards
> Paavo
blargg
[...]
> No, actually with your great suggestion that eliminated the
> extra code in the C++ switch statement I can finally produce
> the quality of code that I have been striving for all along.
> I can tell from the quality of the generated assembly
> language that there is no possible further improvement of
> this fundamental control flow construct. (Within the binding
> constraint of the machine architecture).
I doubt it. What about eliminating the jump table and calculating the
destination as PC+(N<<shift), so that each case statement is some power of
2 from the previous? There's always room for improvement, and the
micro-improvements are generally beyond a compiler.
Peter Olcott
"blargg" <blarg...@gishpuppy.com> wrote in message
news:blargg.ei3-27...@192.168.1.4...
Infeasible, more cases than bits, and memory use would grow
absurdly fast.
There is no feasible improvement within the binding
constraints.
Ivan A. Kosarev
> "Ivan A. Kosarev" <i...@unicals.com> kirjutas:
>> b) the set of values of the enumeration defined is not limited to values
>> of the enumerators specified. A enumeration is able to represent any
>> value from the range of values of its underlying type; see C++ 7.2 #6.
>
> Not exactly - the clause you cite talks about bitfields:
OK, good point. Let's make four more points then:
a) The wordings of the Standard about values of enumerations are
currently not self-consistent: the verse cited talks about bit fields
while 7.2 #5 requires all values of underlying type be preserved during
integral promotion; see issue #172 of Stroustrup;
> Thus, for the example in OP post the underlying type could well be some 32-
> bit int, whereas the valid values would be only those in range 0..7.
b) The underlying type of the enumeration can be a signed type so the
values of the bit field are, at least, in range -7...7;
c) The values that are out of the range are not valid nor invalid. They
are, being converted to the enumeration type, unspecified. That allows a
given implementation remain them unchanged during the conversion;
d) OP asks about things related to optimization so the current practice
does matter here. The current practice about enumeration values is that
the enumeration has a signed underlying type and the range of values of
the enumeration is at least is that of type int.
--
Peter Olcott
The way that standard C++ could handle my issue without
having to resort to vendor specific extensions to the
language would be if all enumeration type values could only
be specified in terms of their enumeration names. Specifying
an enumeration value as any integer would be caught as a
syntax error.
The compiler would be free to map these names to a
contiguous set of integer values beginning with zero.
Whenever a switch statement would be specified using an
enumeration, the compiler would know that it would not have
to insert the extra code to test for out-of-range values,
because all out-of-range values would be reported as syntax
errors at compile time.
Puppet_Sock
[snip]
> I am shooting for maximum speed, thus function call overhead
> is not acceptable.
I've seen the name Peter Olcott about this group, so likely
all I've got to say is old news to you. This is mostly for
newbies who may be lurking.
Maybe what you need is to do this small portion in assembler then.
Also, before you go to that effort, I'd suggest you want to
get some good profiling tools and measure performance. Make
sure you really are losing time at the call, and that it would
gain you a path to a "win" by decreasing it.
And before you do *that* you should define, with numeric values,
what a "win" woould be. "Maximum speed" is rarely a reasonable
spec. For example, does speed over-ride correct results? In some
cases it might, but certainly not every case. If you line up
your spec requirements, you may then find that instead of
"maximum" speed, you have "total program execuation time is
less than <so many> seconds" or "time the user waits for a
response in this case is less than <so much time>" etc.
If you line up your specs that way, you may find that using a
profiling tool tells you that you can't possibly get to a win
by optimizing this call sequence. Or you may find that you
can get the required values with a less nasty optimization
in some other part of the code. Maybe you can even re-factor
something so this call goes away, or becomes something else
that is easier, in context, to optimize.
Or possibly all I've said is irrelevant due to other constraints.
Maybe you must use this call form due to existitng libraries
or legacy code or some such. Software is usually written under
such constraints.
Socks
blargg
> blarg wrote:
> > Peter Olcott wrote:
[...]
> >> I can tell from the quality of the generated assembly
> >> language that there is no possible further improvement of
> >> this fundamental control flow construct. (Within the
> >> binding constraint of the machine architecture).
> >
> > I doubt it. What about eliminating the jump table and
> > calculating the destination as PC+(N<<shift), so that
> > each case statement is some power of 2 from the previous?
> > There's always room for improvement, and the
> > micro-improvements are generally beyond a compiler.
>
> Infeasible, more cases than bits, and memory use would grow
> absurdly fast. There is no feasible improvement within the
> binding constraints.
No human can reliably claim that there is "no feasible improvement". I
don't care what the software; there's always some improvement that some
other person can see that you can't.
If the more common cases only use a few lines of code, while the
less-common ones use more, you can use a small shift and have branches to
the larger code for the less-common cases. But you've been so secretive
about the code, that it's no fun to play such a hypothetical game (I'm
interested in offering more ideas, in private if you like).
blargg
[...]
> The way that standard C++ could handle my issue without
> having to resort to vendor specific extensions to the
> language would be if all enumeration type values could only
> be specified in terms of their enumeration names. Specifying
> an enumeration value as any integer would be caught as a
> syntax error.
That's the way it is, only one can cast from an integer to an enmueration:
enum E { min = 0, max = 15 };
E e = 0; // error
E e = (E) 0; // OK
This is necessary when type information is lost, particularly when saving
enumeration values to disk and later loading them. Unforfunately, the
current wording also allows use of values for which there is no named
constant, for example
E e = (E) 7; // OK, and well-defined
assert( e == 7 ); // passes
> The compiler would be free to map these names to a
> contiguous set of integer values beginning with zero.
> Whenever a switch statement would be specified using an
> enumeration, the compiler would know that it would not have
> to insert the extra code to test for out-of-range values,
> because all out-of-range values would be reported as syntax
> errors at compile time.
This seems a round-about way of achieving a more general
constraint-specification system. I like my solution, as it doesn't require
any new language mechanisms:
if ( n < 0 || n > 7 ) // tell compiler that n is never outside this range
Peter Olcott
the problem, eliminating the
extra code.
A broader solution would be to redefine standard C++ such
that enumeration values could only be specified by using the
enumeration name, thus the extra out-of-range checking could
be done at compile time rather than run-time.
"Puppet_Sock" <puppe...@hotmail.com> wrote in m
essage
news:59aee258-d741-47f3...@l22g2000vba.googlegroups.com...
Peter Olcott
Categorically exhaustive reasoning within 100% completely
precise specifications proves otherwise. There can not
possibly be a faster form of control flow than a jump-table
within the boundaries of my requirements, and currently
existing and commonly available machine architectures.
Specialized machines could derive slight improvements for
infeasibly higher costs.
> If the more common cases only use a few lines of code,
> while the
> less-common ones use more, you can use a small shift and
> have branches to
> the larger code for the less-common cases. But you've been
> so secretive
> about the code, that it's no fun to play such a
> hypothetical game (I'm
> interested in offering more ideas, in private if you
> like).
Just limit the discussion to the jump-table form of control
flow construct, and I can discuss any details.
Peter Olcott
> [...]
>> The way that standard C++ could handle my issue without
>> having to resort to vendor specific extensions to the
>> language would be if all enumeration type values could
>> only
>> be specified in terms of their enumeration names.
>> Specifying
>> an enumeration value as any integer would be caught as a
>> syntax error.
>
> That's the way it is, only one can cast from an integer to
> an enmueration:
>
> enum E { min = 0, max = 15 };
>
> E e = 0; // error
> E e = (E) 0; // OK
>
> This is necessary when type information is lost,
> particularly when saving
> enumeration values to disk and later loading them.
> Unforfunately, the
> current wording also allows use of values for which there
> is no named
> constant, for example
This is exactly the problem, if it was defined as a syntax
error, then I could get what I need form standard C++.
>
> E e = (E) 7; // OK, and well-defined
> assert( e == 7 ); // passes
>
>> The compiler would be free to map these names to a
>> contiguous set of integer values beginning with zero.
>> Whenever a switch statement would be specified using an
>> enumeration, the compiler would know that it would not
>> have
>> to insert the extra code to test for out-of-range values,
>> because all out-of-range values would be reported as
>> syntax
>> errors at compile time.
>
> This seems a round-about way of achieving a more general
> constraint-specification system. I like my solution, as it
> doesn't require
> any new language mechanisms:
I thought that it would be the most direct approach in terms
of mapping the precise syntax the exactly the desire
semantics.
Peter Olcott
I did not get to complete my prior typo corrections and
complete my post because my annoying extra <enter> key
bumped the mouse pad again, and sent the message before I
was done. That key no longer exists.
I thought that it would be the most direct approach in terms
of mapping the precise syntax specified to exactly the
desired semantics required. It is probably a design flaw of
the C++ language to allow values to be specified outside of
the values specified within the enumeration.
This can be easily corrected as a type mismatch compile time
error. Only enumeration names would be allowed as specified
enumeration values. These names could be cast to integers,
but, the reverse cast would be disallowed.
> if ( n < 0 || n > 7 ) // tell compiler that n is never
> outside this range
> *(int*) 0 = 0; // undefined behavior
I did not understand the above suggestion, it looks like a
syntax error. I just tested it and it did not work.
Paavo Helde
>
> This can be easily corrected as a type mismatch compile time
> error. Only enumeration names would be allowed as specified
> enumeration values. These names could be cast to integers,
> but, the reverse cast would be disallowed.
Except that this would probably break lots of existing code, and introduce
a serious discrepancy with C. The current standard is carefully worded to
allow using enum values composed from bit flags, and I believe there are
many programs using that feature. Also deserialization of enum values from
an external source would become much more complicated.
For helping the compiler to optize away impossible branches, I would prefer
to mark them explicitly, e.g.
switch(x) {
case a: break;
case b: break;
default: std::never();
}
This would work the same as MSVC __assume(0), but avoiding the logical
ping-pong of first assuming falsehood and then deriving something out of
it.
Paavo
Peter Olcott
Okay, that sounds like an improvement over what I said. I
don't think that referring to it as a part of the standard
template library is ideal, some other equivalent syntax may
provide the next increment of additional improvement.
Peter Olcott
By keeping optimization in sharp focus throughout every
aspect of the detailed design the final performance will be
at least 10-fold faster than if the speed of every
alternative was not carefully weighed when selecting
detailed design alternatives.
Jerry Coffin
NoS...@SeeScreen.com says...
[ ... ]
> A broader solution would be to redefine standard C++ such
> that enumeration values could only be specified by using the
> enumeration name, thus the extra out-of-range checking could
> be done at compile time rather than run-time.
If this ever happens, it won't be for a very long time. The shortest
time in which I'd consider it even as a remote possibility would be
around 20 years. Roughly 10 years from now would be the first
opportunity to officially deprecate assigning arbitrary integers to enum
values. Roughly 10 years after that would be the first opportunity to
officially remove the possibility from the language.
IMO, this is unlikely to ever happen at all. The closest you can
reasonably hope for is a new type that's otherwise vaguely similar to an
enum, but which can only be assigned values from the defined group. Even
then, it's open to some question whether the compiler is at all likely
to eliminate range checking, unless other changes are made to eliminate
the possibility of doing such an assignment with a cast (and without
that possibility, serializing such a type could be difficult).
--
Later,
Jerry.
The universe is a figment of its own imagination.
Peter Olcott
"Jerry Coffin" <jco...@taeus.com> wrote in message
news:MPG.2439a55fa...@news.sunsite.dk...
"Paavo Helde" came up with this great improvement to my
idea, and explained exactly why the above would not work:
switch(x) {
case a: break;
case b: break;
default: std::never();
}
The big advantage with this improvement to my suggestion is
that it could optionally provide the kind of functionality
that I am looking for without breaking any existing code.
Peter Olcott
std:: namespace would probably be a good idea, it is always
available and never collides with any pre-existing names. It
might be better to make it into a flag instead of a
function: std::NEVER_OCCURS. This flag would be considered
as a compiler hint that compiler vendors would be free to
ignore.
blargg
> Paavo Helde wrote:
[...]
> > For helping the compiler to optize away impossible
> > branches, I would prefer to mark them explicitly, e.g.
> >
> > switch(x) {
> > case a: break;
> > case b: break;
> > default: std::never();
> > }
> >
> > This would work the same as MSVC __assume(0), but avoiding
> > the logical ping-pong of first assuming falsehood and then
> > deriving something out of it.
>
> std:: namespace would probably be a good idea, it is always
> available and never collides with any pre-existing names.
Don't worry about the dust when you're still deciding whether to put in
carpet or hardwood floors.
> It might be better to make it into a flag instead of a
> function: std::NEVER_OCCURS.
What's a flag in this context?
> This flag would be considered as a compiler hint that
> compiler vendors would be free to ignore.
The point of using a function call is that it is a standard semantic
structure which occurs at a particular point in execution. This allows its
invocation to mark that line of execution as never occurring.
Peter Olcott
Using a flag to generally mean a point in the execution
trace that is never reached may be more conventional than
specifying this with a function call. Putting this flag in
the std:: namespace prevents name collisions and this
namespace is probably as intuitive as possible. I think that
your idea is a substantial incremental improvement to my
original idea (prevents breaking exisitng code) and that my
next suggestion (possibly slightly more conventional) is a
tiny improvement to yours.
Jorgen Grahn
...
> That's the way it is, only one can cast from an integer to an enmueration:
>
> enum E { min = 0, max = 15 };
>
> E e = 0; // error
> E e = (E) 0; // OK
>
> This is necessary when type information is lost, particularly when saving
> enumeration values to disk and later loading them. Unforfunately, the
> current wording also allows use of values for which there is no named
> constant, for example
>
> E e = (E) 7; // OK, and well-defined
> assert( e == 7 ); // passes
You make that sound as a loophole or mistake in the standard,
something which may be fixed in the future. But it is a feature of
C++, and is very unlikely to ever change. See TC++PL 4.8.
...
> This seems a round-about way of achieving a more general
> constraint-specification system. I like my solution, as it doesn't require
> any new language mechanisms:
>
> if ( n < 0 || n > 7 ) // tell compiler that n is never outside this range
> *(int*) 0 = 0; // undefined behavior
I like that idea too.
/Jorgen
--
// Jorgen Grahn <grahn@ Ph'nglui mglw'nafh Cthulhu
\X/ snipabacken.se> R'lyeh wgah'nagl fhtagn!
Jorgen Grahn
> On Sat, 28 Mar 2009 16:46:20 -0500, blargg <blarg...@gishpuppy.com> wrote:
...
>> enumeration values to disk and later loading them. Unforfunately, the
>> current wording also allows use of values for which there is no named
>> constant, for example
>>
>> E e = (E) 7; // OK, and well-defined
>> assert( e == 7 ); // passes
>
> You make that sound as a loophole or mistake in the standard,
> something which may be fixed in the future. But it is a feature of
> C++, and is very unlikely to ever change. See TC++PL 4.8.
And *then* I read Paavo Helde's posting which said it better. Oh
well.