Beefy Boxes and Bandwidth Generously Provided by pair Networks
Keep It Simple, Stupid
 
PerlMonks  

comment on

( [id://3333]=superdoc: print w/replies, xml ) Need Help??

NOTE: This was orginally a mailing to my local LUG after a Perl vs Python debate and a discussion by one Pythoner about how he's annoyed by the trinary operator.

At a recent LUG meeting, a small debate arose over the trinary operator (so-called because it's the only three-arg operator in most (all?) languages). It was stated that a compiler can create exactly the same code for both the trinary operator and an if-else construct.

It is true that they are functionally identical. In other words, if you create two functions with each construct and give them the same input, they will always return the same output. However, this statement says nothing about the efficiency of the given function.

In programming langauges, there is another kind of identity to keep in mind (and this is the one that I think Python's designers forget a lot): semantic identity. This deals with how the compiler generates the underlieing machine instructions. Optimiziers might seem like they are deep voodoo, but they are actually straightforward mathmatically once you realize how semantics work.

To prove it, I wrote this C program:

#include <stdio.h> int trinary( int var ); int ifelse( int var ); int trinary( int var ) { int to_return = var ? 1 : 0; return to_return; } int ifelse( int var ) { int to_return; if( var ) { to_return = 1; } else { to_return = 0; } return to_return; } int main(int argc, char **argv) { int got_trinary = trinary( 1 ); int got_ifelse = ifelse( 1 ); return 0; }

This was compiled with gcc -fverbose-asm -S trinary_test.c. This will place the generated assembly code in 'trinary_test.s'. The '-fverbose-asm' arg has gcc make the ASM a little more readable.

My gcc is:

$ gcc -v Reading specs from /usr/lib/gcc-lib/i686-pc-linux-gnu/3.3.5-20050130/s +pecs Configured with: /var/tmp/portage/gcc-3.3.5.20050130-r1/work/gcc-3.3.5/configure --enable-version-specific-runtime-libs --prefix=/usr --bindir=/usr/i686-pc-linux-gnu/gcc-bin/3.3.5-20050130 --includedir=/usr/lib/gcc-lib/i686-pc-linux-gnu/3.3.5-20050130/include + --datadir=/usr/share/gcc-data/i686-pc-linux-gnu/3.3.5-20050130 --mandir=/usr/share/gcc-data/i686-pc-linux-gnu/3.3.5-20050130/man --infodir=/usr/share/gcc-data/i686-pc-linux-gnu/3.3.5-20050130/info --with-gxx-include-dir=/usr/lib/gcc-lib/i686-pc-linux-gnu/3.3.5-200501 +30/include/g++-v3 --host=i686-pc-linux-gnu --disable-altivec --enable-nls --without-included-gettext --with-system-zlib --disable-checking --disable-werror --disable-libunwind-exceptions --disable-multilib --disable-libgcj --enable-languages=c,c++,f77 --enable-shared --enable-threads=posix --enable-__cxa_atexit --enable-clocale=gnu Thread model: posix gcc version 3.3.5-20050130 (Gentoo Hardened Linux 3.3.5.20050130-r1, ssp-3.3.5.20050130-1, pie-8.7.7.1)

Below are the outputs for the two functions in question. I've put in comments for where the param-passing sections begin and end, which are the same for both functions, since they have the same function signature.

# trinary function .LC0: .string "trinary" .text .globl trinary .type trinary, @function trinary: # Start param passing pushl %ebp movl %esp, %ebp pushl %ebx subl $52, %esp call __i686.get_pc_thunk.bx addl $_GLOBAL_OFFSET_TABLE_, %ebx movl __guard@GOT(%ebx), %eax movl (%eax), %eax movl %eax, -24(%ebp) # End param passing cmpl $0, 8(%ebp) # var setne %al movzbl %al, %eax movl %eax, -28(%ebp) # to_return movl -28(%ebp), %eax # to_return movl __guard@GOT(%ebx), %edx movl (%edx), %edx cmpl %edx, -24(%ebp) je .L2 movl -24(%ebp), %eax movl %eax, 4(%esp) leal .LC0@GOTOFF(%ebx), %eax movl %eax, (%esp) call __stack_smash_handler@PLT .L2: addl $52, %esp popl %ebx popl %ebp ret .size trinary, .-trinary .globl __stack_smash_handler .section .rodata # ifelse function .LC1: .string "ifelse" .text .globl ifelse .type ifelse, @function ifelse: # Start param passing pushl %ebp movl %esp, %ebp pushl %ebx subl $52, %esp call __i686.get_pc_thunk.bx addl $_GLOBAL_OFFSET_TABLE_, %ebx movl __guard@GOT(%ebx), %eax movl (%eax), %eax movl %eax, -24(%ebp) # End param passing cmpl $0, 8(%ebp) # var je .L4 movl $1, -28(%ebp) # to_return jmp .L5 .L4: movl $0, -28(%ebp) # to_return .L5: movl -28(%ebp), %eax # to_return movl __guard@GOT(%ebx), %edx movl (%edx), %edx cmpl %edx, -24(%ebp) je .L6 movl -24(%ebp), %eax movl %eax, 4(%esp) leal .LC1@GOTOFF(%ebx), %eax movl %eax, (%esp) call __stack_smash_handler@PLT .L6: addl $52, %esp popl %ebx popl %ebp ret .size ifelse, .-ifelse .globl __stack_smash_handler .section .rodata

I warn against trying to make an opcode count. Both Intel and AMD stopped publishing opcode counts years ago, because modern processors have so many optimizations built in that you can no longer get a predictable count. Unlike compiler optimizations, I think processor optimizations actually are deep voodoo, to the point where they are boarderline non-deterministic.

What can be compared is that the ifelse has 3 jumps to trinary's 1. That will be a significant hit on performance, especially if the processor makes a branch mis-prediction.

Also, notice how the two handle the return variable:

# trinary movl %eax, -28(%ebp) # to_return # ifelse movl $1, -28(%ebp) # to_return

The trinary function is handling the variable between registers, whereas ifelse is using a memory location. This is another boost to the trinary operator.

Semantics are basically a way to give the compiler more information about what you're trying to do. In this case, the trinary operator is designed around the idea that you will directly assign to a variable (to_return = var ? 1 : 0;). OTOH, an if-else may or may not be used that way, so it must be compiled in a much more general way.

As it happens, putting -O2 in the compiler args has both functions compile to identical assembly. Apparently, gcc is smart enough to figure out that the if-else's only side effect is modifying the to_return variable. Consider all this a lesson in how semantics work in general, because such smart optimization may not always be possible without introducing different syntax to produce better semantics. Also, it may not be possible for gcc to do so when the operation is placed inside a much more complex function.

All this may not apply to other programming languages. I suspect Perl's implementation isn't very efficient, on the basis that Perl's semantics in general make C look good (it only got constant-folding fairly recently). It isn't so much that Perl's designers ignored good semantics, but that the language wasn't really designed at all. Perl6 should be a great improvement here.

Since the orginal writing, I've been shown output from B::Terse showing that Perl will indeed do optimization of the trinary operator.

Language designers often make a less-general alternative to another statement that has better semantics (particularly the (semi-)functional languages). That's why C's switch() statement is limited in the conditionals it can handle compared to a if-elseif-else. The limitation means switch() can be compiled to a jump table with O(1) efficiency, whereas the if-elseif-else is O(n). (See Re: Perl Idioms Explained: && and || "Short Circuit" operators for an interesting discussion on this).

Functional languages won't generally force a programmer to learn syntax for the sake of learning syntax (i.e., obfuscation), but they freely add (or remove) syntax if it means the compiler can reason about the program more effectively. While this admittedly makes the learning curve harder, it also produces a much more efficient language.

"There is no shame in being self-taught, only in not trying to learn in the first place." -- Atrus, Myst: The Book of D'ni.


In reply to Trinary Operator Semantics by hardburn

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":



  • Are you posting in the right place? Check out Where do I post X? to know for sure.
  • Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
    <code> <a> <b> <big> <blockquote> <br /> <dd> <dl> <dt> <em> <font> <h1> <h2> <h3> <h4> <h5> <h6> <hr /> <i> <li> <nbsp> <ol> <p> <small> <strike> <strong> <sub> <sup> <table> <td> <th> <tr> <tt> <u> <ul>
  • Snippets of code should be wrapped in <code> tags not <pre> tags. In fact, <pre> tags should generally be avoided. If they must be used, extreme care should be taken to ensure that their contents do not have long lines (<70 chars), in order to prevent horizontal scrolling (and possible janitor intervention).
  • Want more info? How to link or How to display code and escape characters are good places to start.
Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others learning in the Monastery: (6)
As of 2024-04-18 01:04 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found