maximum cases in a switch ?

J

Juha Nieminen

Paul said:
The implementation of the switch case is irrellevant to what I said. The
worst case scenaio would be approx 3x 525.
Obviously a compiler will optimise this , I don't really give a toss how it
does this and I don't give a toss whether you or any other idiot thinks it
will be implemented as a jump table or a binary search becuase you are just
speculating and if you idiots had any clue about this you would have
followed that branch of the thread that was discussing jump tables and
answered the questions there.


It's irrellevant if you or any other idiot can do it in 1 clock cycle. Now
stop trying to twist what I say.

You are just digging a deeper and deeper hole, trying to weasel yourself
out of the pinch.

I know how it is, from personal experience. Been there, done that. Once
you have started to defend your mistake, you simply can't stop anymore.
You have to continue. But it's a vicious circle: The more you try to avoid
admitting the error, the more you prolong the facade, the more it would hurt
to stop and admit your error. So you just can't stop. You try to come up
with some rationalization, some explanation of how you didn't actually make
a mistake, how your behavior and claims were justified. You might even
convince yourself that you didn't make a mistake (even though deep inside
you know you did, you just can't admit it even to yourself, much less to
others).

I know how hard it is to break the vicious cycle, and how hard it is
to avoid doing the same thing again and again in the future. You write
a response too hastily, without thinking, without having the proper
knowledge and experience on the subject, and suddenly you once again find
yourself in the pinch: You made a mistake and now it's very hard to admit
it and move on. You have to start defending yourself once again. Which,
unfortunately, just makes things worse. But you just can't stop. I know
this feeling, and I know how hard it is to overcome.

However, your problem is even worse than just that. Your problem is
aggravated even more by the fact that you resort very easily to insults,
denigrating namecalling and belittling other people, sometimes even without
any kind of provocation. Maybe it's a defense mechanism, a semi-subconscious
attempt to compensate your own insecurities. After all, if everybody else
is an idiot and a moron, you yourself cannot be that bad, can you? This is
a form of psychological projection.

I know this post will not change anything at all, and it will be a
complete waste of time, but maybe, just maybe, if you read it, it might
plant a small seed in you that will perhaps grow in a few years and make
you learn something about how to interact with other people, even when
doing so behind the anonymity of the internet.

I know you are going to dismiss this, but for your own sake, please do
three things:

1) Stop insulting people. Simply don't do it. There's no reason to do it.

2) atop posting hasty replies on subjects you do not have much experience
and knowledge about (especially if that reply is in disagreement with what
somebody else has said).

3) When you make a mistake, don't be afraid to admit it. Just write
something like "ah, you are right, I didn't know that", no matter how
much it might hurt your pride at that moment, and move on. You will be
glad later that you did that instead of engaging in yet another detrimental
and useless flamewar that will only give you a shitty reputation.

You are not going to do this now, but I'm hoping something of this will
make you think in the following years.
 
L

Larry Evans

On Wed, 17 Aug 2011 10:54:13 -0500, Larry Evans



That's correct, the shorter example just does a linear search (via a
series of compares) through the possible cases. A switch with three
cases is so short that a linear search is probably the most reasonable
approach (and is what is being used). IOW, generating either a binary
search or a table lookup is likely to be worse than just doing the
three compares (OK, two compares, and a test to check for zero in this
case). If that program were changed to have more cases, I'd expect a
jump table as in the other example (which has ten cases) if the values
are consecutive, or a binary search (usually coded with a bunch of
compares, but I've seen it done with a table as well) if they aren't.
[snip]
Thanks Robert.

Now I'm wondering why, given a contiguous set of tag values, a vector
of function pointers wouldn't work just as well as a switch. So, I
changed the .mk file to include another macro, FUN_VEC, and added
another macro with the same name to the .cpp file to chose between
the switch or vector of function pointers implementation. The two .s
output files are attached. It appears, in the case of:

switch.U.10.s

the the jump table stores a vector of labels, and the switch jumps to
the label and then calls the function; whereas in:

switch.D.10.s

the function pointers are stored in fun_vec and then an index into
fun_vec is made and then the call is made:

movq fun_vec(,%rax,8), %rax
call *%rax

This seems to me to be about the same speed. I would even
think that the fun_vec implementation would be a bit faster
since indexing into an array, then jumping to an instruction
address would seem to me faster than jumping to a instruction
address and then calling a function at that instruction.
Of course, I admit I know very little about how assembly works :(
I'd appreciate any insights you might have.

My system is a pc and the g++ -v shows:

g++ -v
Using built-in specs.
Target: x86_64-linux-gnu
Configured with: ../src/configure -v --with-pkgversion='Ubuntu
4.4.3-4ubuntu5' --with-bugurl=file:///usr/share/doc/gcc-4.4/README.Bugs
--enable-languages=c,c++,fortran,objc,obj-c++ --prefix=/usr
--enable-shared --enable-multiarch --enable-linker-build-id
--with-system-zlib --libexecdir=/usr/lib --without-included-gettext
--enable-threads=posix --with-gxx-include-dir=/usr/include/c++/4.4
--program-suffix=-4.4 --enable-nls --enable-clocale=gnu
--enable-libstdcxx-debug --enable-plugin --enable-objc-gc
--disable-werror --with-arch-32=i486 --with-tune=generic
--enable-checking=release --build=x86_64-linux-gnu
--host=x86_64-linux-gnu --target=x86_64-linux-gnu
Thread model: posix
gcc version 4.4.3 (Ubuntu 4.4.3-4ubuntu5)


TIA.

-Larry
 
A

Alain Ketterlin

Larry Evans said:
Now I'm wondering why, given a contiguous set of tag values, a vector
of function pointers wouldn't work just as well as a switch. So, I
changed the .mk file to include another macro, FUN_VEC, and added
another macro with the same name to the .cpp file to chose between
the switch or vector of function pointers implementation. The two .s
output files are attached. It appears, in the case of:

switch.U.10.s

the the jump table stores a vector of labels, and the switch jumps to
the label and then calls the function; whereas in:

switch.D.10.s

the function pointers are stored in fun_vec and then an index into
fun_vec is made and then the call is made:

movq fun_vec(,%rax,8), %rax
call *%rax

This seems to me to be about the same speed. I would even
think that the fun_vec implementation would be a bit faster
since indexing into an array, then jumping to an instruction
address would seem to me faster than jumping to a instruction
address and then calling a function at that instruction.

There is no reason why one should perform significantly better than the
other. However, in your switch, I seem to remember that all cases fall
through (i.e., the first value executes all the calls because there is
no break). But that's a detail of your example.

In general, an indirect jump followed by a call is almost identical to
an indirect call (a call is basically push+jump, so you get one more
jump in the case of the jump table). Since you save a jump in the
func_vec version, you put less pressure on your instruction cache. I
doubt this will make a difference in your tests, but who knows...

-- Alain.
 
L

Larry Evans

There is no reason why one should perform significantly better than the
other. However, in your switch, I seem to remember that all cases fall
through (i.e., the first value executes all the calls because there is
no break). But that's a detail of your example.

In general, an indirect jump followed by a call is almost identical to
an indirect call (a call is basically push+jump, so you get one more
jump in the case of the jump table). Since you save a jump in the
func_vec version, you put less pressure on your instruction cache. I
doubt this will make a difference in your tests, but who knows...

-- Alain.

Thanks very much Alain.

One reason I asked the question is a post to the boost list:

http://article.gmane.org/gmane.comp.lib.boost.devel/169739

hinted that there might be a significant difference and I
couldn't really understand why. I guess I should have
asked Tobias back then in 2008 instead of waiting till now
to get another opinion.

-regards,
Larry
 
J

James Kanze

On 8/9/2011 12:03 PM, Lynn McGuire wrote:
You have your answer, I'm not going to repeat it. Remember that it's
not normative, though.

The actual answer is implementation defined, so it should be in
the documentation of your compiler. The numeric answer given
earlier is just a recommendation (and, as you say,
non-normative).

C has a normative requirement, although I forget the value (not
very large, however). Practically, no C++ compiler will do less
than what C requires.
I have a different question. How easy do you think it is going to be to
maintain the code with more than 1000 cases in a single switch
statement?

I don't know if its his case, but I could easily see such cases
occuring in machine generated code.
 
N

Nick Keighley

--hence my "estimate" is in clock cycles (instructions actually)

making it independent of the clock speed
If you think you are so smart

I never claimed to be smart
[...] lets see the C++ and the assembly and tell me
which compiler produced it.

I was using an imaginary (but representative) machine. See MIX.
You cannot do it in 6 instructions(as you say).

My original post said "we're talking half a dozen instructions and a
couple of memory accesses". In my world "half a dozen" is /about/ 6 or
so.

5, 6, 7. It makes no odds. Because your number was out by a factor of
a hundred or so.

And an instruction is not
the same thing as a clock cycle.

there's usually a straightforward relationship between them on risc
processors. I thought some machines did actually do one instruction
per cycle.
So lets see the code or [shutup] and go have a group hug with Leigh and the rest
of the gayboys who seem to have just leared what a jump table is.
Code in C++ please , not your own language.

the HLL isn't too important either.
 
V

Victor Bazarov

FWIW, the C++98 requirement

A "requirement"? Care to give the chapter/verse?
(16384 case labels in a switch) is
considerable larger than the C requirements (257 in C89, 1023 in C99).
I don't know if that's changed in C++11.

That particular number seems to be the same. And the status of their
being *not* normative hasn't changed either.

V
 
J

James Kanze

On Aug 9, 8:42 pm, Victor Bazarov <[email protected]> wrote:
[...]
The actual answer is implementation defined, so it should be in
the documentation of your compiler. The numeric answer given
earlier is just a recommendation (and, as you say,
non-normative).
C has a normative requirement, although I forget the value (not
very large, however). Practically, no C++ compiler will do less
than what C requires.
FWIW, the C++98 requirement (16384 case labels in a switch) is
considerable larger than the C requirements (257 in C89, 1023 in C99).
I don't know if that's changed in C++11.

Except that, as has been pointed out, C++98 has no
"requirement", only a non-normative recommendation.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,744
Messages
2,569,482
Members
44,901
Latest member
Noble71S45

Latest Threads

Top