upcoming Switch library review Jan 5th - Jan 9th

The review of the Switch library by Steven Watanabe will begin this
Saturday, Jan 5th.

Description:

The built in C/C++ switch statement is very efficient. Unfortunately,
unlike a chained if/else construct there is no easy way to use it when
the number of cases depends on a template parameter. The Switch
library addresses this issue.


You can download the library from the Boost Vault:
http://tinyurl.com/23qn7w

For convenience, the docs have been uploaded here:
http://tinyurl.com/2h6ut9

... and the source file here:
http://tinyurl.com/2cbfyk

If you are interested, please consider submitting a review of this
library.  I will send more detailed instructions on what to include in
the review on the 5th.

Regards,

Stjepan
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

On 01/02/08 15:08, Stjepan Rajko wrote:
> The review of the Switch library by Steven Watanabe will begin this
> Saturday, Jan 5th.
>
> Description:
>
> The built in C/C++ switch statement is very efficient. Unfortunately,
> unlike a chained if/else construct there is no easy way to use it when
> the number of cases depends on a template parameter. The Switch

The attachment contains an alternative which uses no preprocessing.
It uses more memory because of the static fun_vec in:

   fun_switch_impl::our_vec

However, it would probably use less code because of no preprocessor
generated switch statements.  OTOH, it would be slower because
the function has to be looked up in the vector.

Are there any other comparisons you can think of.  It would be
useful to outline the pro's and cons of alternative implementations
you've considered.

I've done a simple test of the attached by using it in a slightly
modified test_switch.cpp.  I just added the #include and:

     BOOST_CHECK_EQUAL((fun_switch<test_range>(5, f())), 6);

-regards,
Larry

//alternative to switch_
#ifndef FUN_SWITCH_HPP
#define FUN_SWITCH_HPP
#include <boost/mpl/size.hpp>
#include <boost/mpl/for_each.hpp>
template<class Cases, class Int, class F>
struct fun_switch_impl
{
        typedef
        typename
      F::result_type
    result_type
    ;
    template<class Case>
    struct fun_case
    {
            static
          result_type
        _(F f)
        {
            Case arg;
            return f(arg);
        }
    };
    struct fun_vec
    {
            typedef
          result_type
          (*
        fun_type
          )(F)
        ;
            static
          unsigned const
        vec_size
        = boost::mpl::size<Cases>::type::value
        ;
            typedef
          fun_type
        vec_type
          [ vec_size
          ]
        ;
        struct fill_vec
        {
              vec_type&
            my_vec
            ;
            fill_vec(vec_type& a_vec)
            : my_vec(a_vec)
            {}
              template
              < typename Case
              >
              void
            operator()(Case)
            {
                my_vec[Case::value]=fun_case<Case>::_;
            }
        };
          vec_type
        my_vec
        ;
        fun_vec(void)
        {
            boost::mpl::for_each<Cases>(fill_vec(my_vec));
        }
          fun_type
        operator[](Int i)const
        {
            return my_vec[i];
        }
         
    };
        static
      fun_vec const&
    our_vec(void)
    {
        static fun_vec const a_vec;
        return a_vec;
    }
        static
      result_type
    _(Int i, F f)
    {
        return our_vec()[i](f);
    }
};
template<class Cases, class Int, class F>
  typename F::result_type
fun_switch(Int i, F f)
{
    return fun_switch_impl<Cases,Int,F>::_(i,f);
}

#endif


_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

On 01/02/08 23:07, Larry Evans wrote:
> On 01/02/08 15:08, Stjepan Rajko wrote:
>> The review of the Switch library by Steven Watanabe will begin this
>> Saturday, Jan 5th.
[snip]
> The attachment contains an alternative which uses no preprocessing.
> It uses more memory because of the static fun_vec in:
>
>   fun_switch_impl::our_vec
>
OOPS.  I see a flaw in fun_switch.  It doesn't handle missing
numerals. IOW, the CASES could contain a non_sequential_range,
as one of the test_switch.cpp tests shows.

Sorry about that :(


_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

Larry Evans wrote:
We actually very much want a preprocessor-generated 'switch' statement
because it is a special hint for optimization and most compilers
generate very efficient code for it...


Regards,
Tobias

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

Tobias Schwinger <tschwinger <at> isonews2.com> writes:
> We actually very much want a preprocessor-generated 'switch' statement
> because it is a special hint for optimization and most compilers
> generate very efficient code for it...

BTW,
switch_ doesn't implement fall-though and I was worried about performance of
this important case (bzero with Duff's device optimization):

  switch(n % 8)
  {
    case 7: buf[6] = 0;
    case 6: buf[5] = 0;
    case 5: buf[4] = 0;
    case 4: buf[3] = 0;
    case 3: buf[2] = 0;
    case 2: buf[1] = 0;
    case 1: buf[0] = 0;
  }

switch_ would generate this code:

  switch(n % 8)
  {
    case 7:
      buf[6] = 0; buf[5] = 0; buf[4] = 0; buf[3] = 0;
      buf[2] = 0; buf[1] = 0; buf[0] = 0;
      break;
    case 6:
      buf[5] = 0; buf[4] = 0; buf[3] = 0;
      buf[2] = 0; buf[1] = 0; buf[0] = 0;
      break;
    case 5:
      buf[4] = 0; buf[3] = 0; buf[2] = 0; buf[1] = 0; buf[0] = 0;
      break;
    case 4:
      buf[3] = 0; buf[2] = 0; buf[1] = 0; buf[0] = 0;
      break;
    case 3:
      buf[2] = 0; buf[1] = 0; buf[0] = 0;
      break;
    case 2:
      buf[1] = 0; buf[0] = 0;
      break;
    case 1:
      buf[0] = 0;
      break;
    default:
      break;
  }

Below is a program that demonstates a difference of assembly code between hand-
crafted switch and the switch_. The are identical on gcc 3.4.6 x86_64.

#include <iostream>
#include "switch.hpp"
#include <boost/mpl/integral_c.hpp>
#include <boost/mpl/range_c.hpp>
#include <boost/mpl/vector.hpp>

void classic_duff(char* buf, int n)
{
  switch(n % 8)
  {
    case 7: buf[6] = 0;
    case 6: buf[5] = 0;
    case 5: buf[4] = 0;
    case 4: buf[3] = 0;
    case 3: buf[2] = 0;
    case 2: buf[1] = 0;
    case 1: buf[0] = 0;
  }

  // ...
}

template<int N>
struct duff_step;

template<int N>
struct duff_step
{
  static void step(char* buf)
  {
    buf[N-1] = 0;
    duff_step<N-1>::step(buf);
  }
};

template<>
struct duff_step<0>
{
  static void step(char* buf)
  {
  }
};

struct duff_case
{
  char* buf;
  duff_case(char* buf) : buf(buf) {}

  typedef void result_type;
  template<class Case>
  void operator()(Case) const
  {
    duff_step<Case::value>::step(buf);
  }
};

struct ignore
{
  template<class Int>
  void operator()(Int) const {}
};

template<int Mod>
void modern_duff(char* buf, int n)
{
  using namespace boost;
  switch_< mpl::range_c<int,0,Mod> >(n % Mod, duff_case(buf), ignore());

  // ...
}


int main(int argc, char* argv[])
{
  using namespace boost;

  char buf1[7] = { 1, 1, 1, 1, 1, 1, 1 };
  modern_duff<8>(buf1, 7);

  for(int i = 0; i < 8; ++i)
    std::cout << static_cast<int>(buf1[i]) << ", ";
  std::cout << '\n';

  char buf2[7] = { 1, 1, 1, 1, 1, 1, 1 };
  classic_duff(buf2, 7);

  for(int i = 0; i < 8; ++i)
    std::cout << static_cast<int>(buf2[i]) << ", ";
  std::cout << '\n';

}


0000000000400820 <classic_duff(char*, int)>:
  400820:       8d 46 07                lea    0x7(%rsi),%eax
  400823:       83 fe ff                cmp    $0xffffffffffffffff,%esi
  400826:       0f 4f c6                cmovg  %esi,%eax
  400829:       83 e0 f8                and    $0xfffffffffffffff8,%eax
  40082c:       29 c6                   sub    %eax,%esi
  40082e:       83 fe 07                cmp    $0x7,%esi
  400831:       77 24                   ja     400857 <classic_duff(char*, int)
+0x37>
  400833:       89 f0                   mov    %esi,%eax
  400835:       ff 24 c5 50 0b 40 00    jmpq   *0x400b50(,%rax,8)
  40083c:       c6 47 06 00             movb   $0x0,0x6(%rdi)
  400840:       c6 47 05 00             movb   $0x0,0x5(%rdi)
  400844:       c6 47 04 00             movb   $0x0,0x4(%rdi)
  400848:       c6 47 03 00             movb   $0x0,0x3(%rdi)
  40084c:       c6 47 02 00             movb   $0x0,0x2(%rdi)
  400850:       c6 47 01 00             movb   $0x0,0x1(%rdi)
  400854:       c6 07 00                movb   $0x0,(%rdi)
  400857:       f3 c3                   repz retq
  400859:       90                      nop
  40085a:       66                      data16
  40085b:       66                      data16
  40085c:       90                      nop
  40085d:       66                      data16
  40085e:       66                      data16
  40085f:       90                      nop

0000000000400a00 <void modern_duff<8>(char*, int)>:
  400a00:       8d 46 07                lea    0x7(%rsi),%eax
  400a03:       83 fe ff                cmp    $0xffffffffffffffff,%esi
  400a06:       0f 4f c6                cmovg  %esi,%eax
  400a09:       83 e0 f8                and    $0xfffffffffffffff8,%eax
  400a0c:       29 c6                   sub    %eax,%esi
  400a0e:       83 fe 07                cmp    $0x7,%esi
  400a11:       77 24                   ja     400a37 <void modern_duff<8>
(char*, int)+0x37>
  400a13:       89 f0                   mov    %esi,%eax
  400a15:       ff 24 c5 90 0b 40 00    jmpq   *0x400b90(,%rax,8)
  400a1c:       c6 47 06 00             movb   $0x0,0x6(%rdi)
  400a20:       c6 47 05 00             movb   $0x0,0x5(%rdi)
  400a24:       c6 47 04 00             movb   $0x0,0x4(%rdi)
  400a28:       c6 47 03 00             movb   $0x0,0x3(%rdi)
  400a2c:       c6 47 02 00             movb   $0x0,0x2(%rdi)
  400a30:       c6 47 01 00             movb   $0x0,0x1(%rdi)
  400a34:       c6 07 00                movb   $0x0,(%rdi)
  400a37:       f3 c3                   repz retq
  400a39:       c6 47 05 00             movb   $0x0,0x5(%rdi)
  400a3d:       c6 47 04 00             movb   $0x0,0x4(%rdi)
  400a41:       c6 47 03 00             movb   $0x0,0x3(%rdi)
  400a45:       c6 47 02 00             movb   $0x0,0x2(%rdi)
  400a49:       c6 47 01 00             movb   $0x0,0x1(%rdi)
  400a4d:       c6 07 00                movb   $0x0,(%rdi)
  400a50:       c3                      retq
  400a51:       90                      nop
  400a52:       90                      nop
  400a53:       90                      nop
  400a54:       90                      nop
  400a55:       90                      nop
  400a56:       90                      nop
  400a57:       90                      nop
  400a58:       90                      nop
  400a59:       90                      nop
  400a5a:       90                      nop
  400a5b:       90                      nop
  400a5c:       90                      nop
  400a5d:       90                      nop
  400a5e:       90                      nop
  400a5f:       90                      nop



_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

Alexander Nasonov <alnsn <at> yandex.ru> writes:
> BTW,
> switch_ doesn't implement fall-though and I was worried about performance of
> this important case (bzero with Duff's device optimization):

Sorry for typos and errors in code. Assembly are not identical but close.
If I change  modern_duff to throw from switch_, it would change assembly
completely event though the compiler can deduce from n % 8 that all cases
are covered.
So, throwing is good for protecting programmers from accidental errors
but not good for code generation.

I wonder why don't you use none_t or even a special default_t?

struct some_func {
    typedef void result_type;
    template<class Case>
    void operator()(Case c) const {
        std::cout << c << std::endl;
    }

    void operator()(default_t) const {
        throw out_of_range();
    }
};

Though, it may break passing a lambda expression to switch_ but
this case probably is not supported because IIRC there is no
result_type in lambda expression types.

--
Alexander


_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

Forwarding this post from boost.user...

Steven Watanabe wrote:
> AMDG
>
> Tobias Schwinger <tschwinger <at> isonews2.com> writes:
>
>> dan marsden wrote:
>>> Why is the fall through behaviour to throw an exception?
>> I too tripped over this one, yesterday.
>>
>> <snip>

> The other option is an assertion.  Is that any better?

I think the "default default behavior" should be to use the default
constructor. This approach works nice with Any, Variant and Optional.

> Or should a void return type be a special case?

If 'Default's result type is 'void' although something else is expected,
we should assert it never actually returns at runtime (note that it is
possible to detect the result type with an overloaded comma operator and
without requiring 'Default' to work with 'result_of' -- might also be
faster). If assertions are disabled the behavior should be unspecified
in that case.

<snip>

>> Of course there are no pointers to templates, so using a function
>> pointer for anything but the default is pretty pointless. So is trying
>> to handle varying result types -- maybe the result type should be passed
>> in with another template parameter?
>
> I'd rather leave it as result_of<F()>::type.

Actually 'result_of<F()>::type' determines the result of the nullary
call to F. I don't think I like this sort of "result_of abuse"... The
correct usage would be 'result_of<F(MPLConstant)>::type' but it's
pointless since 'MPLConstant' varies and so may the whole type expression.

So, if you insist on deducing the result type from the function object
(instead of having it specified explicitly) my vote is 'F::result_type',
however, I still find another template parameter more appropriate for
the following good reasons:

o The function object can work fine with result_of in a non-'switch_'
    context. The cases can return different things as long as they are
    convertible to the result of 'switch_', and

o there is no way to determine this type with 'result_of.


Regards,
Tobias

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

On Jan 6, 2008 7:34 AM, Tobias Schwinger <tschwinger@...> wrote:
The current implementation seems to use result_type - is it planned to
change to use result_of?

I agree that result_of<F()>::type is slightly abusive, since that's
not what actually gets called.  Would using
result_of<F(boost::mpl::front<Cases>::type)> be an option for a
non-empty case sequence?  As long as the order of the cases doesn't
matter (btw, does it?), the user could put the desired type in the
front of the Cases sequence if the return type differs for different
MPLConstant types.

Stjepan
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

On Jan 6, 2008 12:20 PM, Tobias Schwinger <tschwinger@...> wrote:
> Stjepan Rajko wrote:
> > Would using
> > result_of<F(boost::mpl::front<Cases>::type)> be an option for a
> > non-empty case sequence?
>
> I think it's too complicated: We can't use 'result_of' to determine the
> result of 'switch_', so it should be as simple to determine as possible
> (ideally without deduction at all).
>

Sure - although the library could offer something along the lines of
result_of::switch.

I agree that being able to specify the return type explicitly would be
very useful, precisely because you could use function objects that are
not result_of/result_type compatible, or override the return type even
if one is specified by the function object. I can see overriding it to
boost::any or some other "common denominator" as a frequent use case.

> So what will deducing that type from the function object buy us?
>
> The only answer I can currently see is "nothing but trouble" :-). Please
> tell me if I'm missing something.
>

>From what I can see, it buys simplicity when the use case is not
complicated (the return type is available through result_type or
result_of and does not change), or when you really want to leave it to
the function object to specify what the return type should be.
Granted, all of the proposed solutions for return type deduction seem
slightly imperfect / inelegant, but as long as the behavior is clearly
explained in the documentation they could be useful.

Regards,

Stjepan
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

On Jan 4, 2008 3:31 AM, Alexander Nasonov <alnsn@...> wrote:
Hi Alexander,

Thanks for the example and the assembly analysis.  Off the top of my
head, it doesn't seem like it would be too difficult to add support
for fall-through directly (e.g., by taking an (optional?) sequence of
MPL bool constants to specify whether a case should fall through or
break/return).  Although, the difficult part might be deciding how to
deal with return values in this case.

Steven, what do you think?

Stjepan
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

Stjepan Rajko wrote:
(-: Please excuse my forthright bluntness:

In case of the former it's a minor concern to just pass in that type.
I'm pretty sure the resulting client code will read clearer (that is
without having to dig up the docs).

The latter seems to me as a misguided approach that encourages users
to mess up the result type computation of their function objects.

A user framework might still define its own Concept picking a custom
type member (that will typically be one that does not interfere with
those looked at by result_of) where appropriate.

> Granted, all of the proposed solutions for return type deduction seem
> slightly imperfect / inelegant, but as long as the behavior is clearly
> explained in the documentation they could be useful.

I disagree. Good code is self-explanatory. Good libraries encourage good
style. Weird stuff stays weird and documenting it doesn't change it ;-).

Maybe I'm just blind - but I see absolutely no benefit from attempting
to deduce the result type over having the result type specified by the
user.


Regards,
Tobias


_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

On Jan 7, 2008 2:55 AM, Tobias Schwinger <tschwinger@...> wrote:
I welcome forthright bluntness :-)

I don't think you're blind - for the most part, I'm just throwing out
possible viewpoints to see if anyone else sees any validity behind
them, and to know what to recommend at the end of the review.  Thank
you for providing great arguments for your view - unless the author or
other reviewers feel strongly otherwise it seems like the most
reasonable way to go (and thanks to Joel for joining the discussion!).

Regards,

Stjepan
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

AMDG

"Stjepan Rajko" <stipe@...> wrote:
Of course, we can't use the return value of a case that should fall
through to the
next case...  For non-void return types we could make an actual return
type of void
indicate fallthrough.  Hmmm...   That seems too error prone.  How about
creating a fallthrough_t
for the return type?

In Christ,
Steven Watanabe

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost