Optimizing Mathematical Expressions For Size

Optimizing Mathematical Expressions For Size

Post by Jaap Sute » Thu, 25 Jul 2002 06:04:28



Hello everyone,

Suppose I have the following class:

class multi_vector
{
    friend Base operator * ( const Base& lhs, const Base& rhs );
    bool is_special_vector() const;

    float v[ some_large_number ];

Quote:}

Very often a multi_vector instance will have the first half of the array
set to zero. Actually there is a subset of all multi_vector instances
which always has the first half of the array set to zero. Let's call
such a vector a special_vector.

Now I am looking for a way so I don't have to store the first half of
the array whenever a multi_vector is actually a special_vector.

Consider the following code:

{
    multi_vector p;
    multi_vector q;
    multi_vector r;

    r = p * q;

    if ( p and q satisfy some criterium )
    {
        assert( sizeof( r ) == sizeof( multi_vector / 2 );
    }
    else
    {
        assert( sizeof( r ) == sizeof( multi_vector );
    }

Quote:}

I have thought about different ways of doing this. I can't use any
runtime polymorphism (it is is a small performance hungry vector class
I'm working on), and I can't use heap-allocations either. I haven't been
able to succeed coming up with a template-meta-programming solution to
solve this problem.

A random brainstorm:

class multi_vector;
class multi_vector_satisfying_criterium : public multi_vector; class
special_vector;

And then write both:

multi_vector       operator * ( const multi_vector&,
const multi_vector& )                                            and
special_vector    operator * ( const multi_vector_satisfying_criterium&,
const multi_vector_satisfying_criterium& )

However, this way the user has to know that p and q satisfy a criterium
(which they might not), and also, special_vector can't derive from
multi_vector.

Any help, suggestions or ideas are greatly appreciated.

Sincerely,

Jaap Suter


      [ about comp.lang.c++.moderated. First time posters: do this! ]

 
 
 

Optimizing Mathematical Expressions For Size

Post by Michiel Salte » Fri, 26 Jul 2002 00:27:29


 > Hello everyone,
 >
 > Suppose I have the following class:
 >
 > class multi_vector
 > {
 >     friend Base operator * ( const Base& lhs, const Base& rhs );
 >     bool is_special_vector() const;
 >
 >     float v[ some_large_number ];
 > }
 >
 > Very often a multi_vector instance will have the first half of the array
 > set to zero. Actually there is a subset of all multi_vector instances
 > which always has the first half of the array set to zero. Let's call
 > such a vector a special_vector.
 >
 > Now I am looking for a way so I don't have to store the first half of
 > the array whenever a multi_vector is actually a special_vector.

Give multivector a std::vector, an integer offset, and an operator[]
which returns 0 if it's argument is smaller than offset and
vector::operator[]( argument-offset) otherwise. is_special_vector
can return ( offset != 0 )

 > Consider the following code:
 >
 > {
 >     multi_vector p;
 >     multi_vector q;
 >     multi_vector r;
 >
 >     r = p * q;
 >
 >     if ( p and q satisfy some criterium )
 >     {
 >         assert( sizeof( r ) == sizeof( multi_vector / 2 );
 >     }
 >     else
 >     {
 >         assert( sizeof( r ) == sizeof( multi_vector );
 >     }
 > }

sizeof(r) == sizeof( multi_vector ) in your design. There is NEVER
an object of type T for which sizeof(object)!=sizeof(T).

 > I have thought about different ways of doing this. I can't use any
 > runtime polymorphism (it is is a small performance hungry vector class
 > I'm working on), and I can't use heap-allocations either. I haven't been
 > able to succeed coming up with a template-meta-programming solution to
 > solve this problem.

Programming is making choices. Either you optimize for size and take the
speed hit of differently-sized objects, or you optimize for speed, give
all objects the same size and live with that waste.

 > A random brainstorm:
 >
 > class multi_vector;
 > class multi_vector_satisfying_criterium : public multi_vector; class
 > special_vector;
 >
 > And then write both:
 >
 > multi_vector       operator * ( const multi_vector&,
 > const multi_vector& )                                            and
 > special_vector    operator * ( const multi_vector_satisfying_criterium&,
 > const multi_vector_satisfying_criterium& )
 >
 > However, this way the user has to know that p and q satisfy a criterium
 > (which they might not), and also, special_vector can't derive from
 > multi_vector.

If I understand the problem correctly, the size of the object returned
by the expression p*q should depend on the values of p and q. This is
impossible in a strongly typed language like C++. The type of p*q depends
on the the types of p and q, never the values. The size of an object which
doesn't use heap allocations is 100% determined by its type.

I suggest you reconsider your priorities. You can't give both size and
speed the top priority. We can't determine for you which one is more
important, what your tradeoffs are, and what the "exchange rate" is on
your system.

Regards,
--
Michiel Salters


      [ about comp.lang.c++.moderated. First time posters: do this! ]

 
 
 

Optimizing Mathematical Expressions For Size

Post by Markus Werl » Sat, 27 Jul 2002 00:47:40



> Programming is making choices. Either you optimize for size and take
> the speed hit of differently-sized objects, or you optimize for speed,
> give all objects the same size and live with that waste.

And in addition to that I made the experience that
- as long as You do not have any memory consumption problem -
the speed penalty due to differently-sized vectors
is much too high a price to pay.

If You use a std::vector-based approach be aware of the fact
that some STL-implementations double the allocated space
during automatic resize (like it may occur during a push_back()) so if
You do not take care (or omit a shrink-to-fit step) You end up with
approximately the same amount of memory consumption
regardless of whether You use a special vector or a stupid one.


> > Very often a multi_vector instance will have the first half of the
> > array set to zero. Actually there is a subset of all multi_vector
> > instances which always has the first half of the array set to zero.

This looks like a design issue to me.
If exactly the first half is empty in a whole subclass of
entities You use, maybe it is time to reorganize/redesign the code. Like
this You may avoid the tradeoff between speed and size.

Markus


      [ about comp.lang.c++.moderated. First time posters: do this! ]

 
 
 

Optimizing Mathematical Expressions For Size

Post by Jaap Sute » Sat, 27 Jul 2002 04:13:44


Quote:> This looks like a design issue to me.
> If exactly the first half is empty in a whole subclass of entities You
> use, maybe it is time to reorganize/redesign the code. Like this You
> may avoid the tradeoff between speed and size.

Okay, with my original post I was trying to avoid the actual details of
my project. Obviously this didn't work, because even though you all
bring up very good points, they don't really apply to my specific
situation (I think). Thus, I will try again, now going into specific
details.

I am working on some code to deal with geometric algebra
(http://modelingnts.la.asu.edu/) concepts. I have written a so called
multi_vector class that directly corresponds with the multivector
concept in geometric algebra. I will try to explain this, so you won't
need any experience with geometric algebra.

Taking three dimensionsal physical space as an example (but the actual
multi_vector class is generic over the dimension) a multi_vector< 3,
float > instantiation will result in a class with 8 floating point
members.

One for the scalar,
Three for the vector,
Three for the bi-vector
One for the pseudo-scalar

However, applications commonly work with vectors, bi-vectors and scalars
directly. So we have two options here.

Option 1: Make everything a multi_vector

{
    multi_vector a, b; // Creates two 0-multivectors;
    a.set_vector( 3, 4, 5 );
    a.set_bi_vector( 3, 4, 5 );

    multi_vector c = a * b;

    // c will now only have the pseudo-scalar part non-zero
    // because a bi-vector * vector == 4-vector == pseudo-scalar
    // in physical space;

    multi_vector d = a + b + c;

Quote:}

Option 2: Write five different classes
               (scalar, vector, bi_vector and pseudo_scalar,
multi_vector);

{
    vector a( 3, 4, 5 );
    bi_vector b( 3, 4, 5 );
    pseudo_scalar c = a * b;

    multi_vector d = a + b + c;

Quote:}

Advantages of option 1:
- Generic, user doesn't need to think about what operator results
   are. However, almost always a user knows what he is doing
   anyway, so this is not a huge advantage.

Disadvantages of option 2:
- Taking up more space.

Advantages of option 2:
- Lean and mean. You only pay for what you use.

Disadvantages of option 2:
- Non-generic. User has to know what he is doing.
- We still have to write a multi_vector class as well, for operators
  that do result in a multi_vector.
- More work, writing out all the classes and different operators,
although
  I do believe  meta-programming can be of assistance here.

Now, getting to the point of my story.

Currently I have option 1 implemented, and it works allright. However,
for geometric algebra to have an advantage over oldskool matrix/vector
algebra we need more than the elegance of a unifiying theory, namely
performance. In this case, both size and speed are important. For
example, we definitely can't expect people to start using multi_vectors
(size = 8 floats) wherever vectors (size = 3 floats) are enough.

Thus, I was looking for a blend of option 1 and 2, in which you can work
with multi_vectors whereever, but that they adapt themselves to the
actual specialization they are. Obviously in C++ this is not possible
without some form of runtime-polymorphism. This involves
heap-allocations, vtables, and the lot. Definitely not something one is
willing to pay for small vector-related geometric calculations.

Thus, I will start working on option 2....

Thanks everybody for the help,

Regards,

Jaap Suter


      [ about comp.lang.c++.moderated. First time posters: do this! ]

 
 
 

Optimizing Mathematical Expressions For Size

Post by Gabriel Dos Rei » Sun, 28 Jul 2002 00:43:50


[...]

| Option 1: Make everything a multi_vector
|
| {
|     multi_vector a, b; // Creates two 0-multivectors;
|     a.set_vector( 3, 4, 5 );
|     a.set_bi_vector( 3, 4, 5 );
|
|     multi_vector c = a * b;
|
|     // c will now only have the pseudo-scalar part non-zero
|     // because a bi-vector * vector == 4-vector == pseudo-scalar
|     // in physical space;
|
|     multi_vector d = a + b + c;
|
| }

This is what youu see in most Computer Algebra System -- which intrepret
your expressions, so mistakes are caught very early.

| Option 2: Write five different classes
|                (scalar, vector, bi_vector and pseudo_scalar,
| multi_vector);
|
| {
|     vector a( 3, 4, 5 );
|     bi_vector b( 3, 4, 5 );
|     pseudo_scalar c = a * b;
|
|     multi_vector d = a + b + c;
| }
|
| Advantages of option 1:
| - Generic, user doesn't need to think about what operator results
|    are. However, almost always a user knows what he is doing
|    anyway, so this is not a huge advantage.

This is like having a class "Number" which implement the concept of
number, and can handle "integer", "real", "complex".  Very quickly you
run into problems where you want to know the exact kind of numbers (here
the degree of your multi-vectors).  In the three dimensional case where
every multivector is a monome, that approach might not be a problem.
However, once you get into higher dimensions you'll have to face
problems involving non-decomposible multi-vector and such.

| Disadvantages of option 2:
| - Taking up more space.

It demands lots of code -- I've been there ;-)

| Advantages of option 2:
| - Lean and mean. You only pay for what you use.

It makes explicit certain operations, like pairing or Hodge operator.

From my experience, this is an instance of things where it is difficult
to find a generic, efficient and effictive representation for all
dimensions.

In implementing Option 1, I used a list of "dynamic" matrices.  That can
be very daunting...

--


      [ about comp.lang.c++.moderated. First time posters: do this! ]

 
 
 

Optimizing Mathematical Expressions For Size

Post by Markus Werl » Sun, 28 Jul 2002 05:18:36



>> This looks like a design issue to me.
>> If exactly the first half is empty in a whole subclass of entities
>> You

>> use, maybe it is time to reorganize/redesign the code. Like this You
>> may avoid the tradeoff between speed and size.

> Okay, with my original post I was trying to avoid the actual details
> of my project. Obviously this didn't work, because even though you all
> bring up very good points, they don't really apply to my specific
> situation (I think). Thus, I will try again, now going into specific
> details.

So You were dissatisfied with the result of Your other thread "The
future of C++'s static language"?  

The techiques proposed in that thread may fit here, too.

Secondly: I do not see You really gain much with
an approach which tries to save the wasted space,
because once the compiler knows that all objects
that interact with each other have the same size,
some rigid optimizations (automatic vectorization)
may apply.

Is size really a problem?
Then go into the shop and buy some additional 512MB chip.
I am not kidding. If I look at the development of
memory available in a standard PC during the last 10 years,
who cares about memory consumption tomorrow, when Your
program has left development state?  

I still think that the best You can do is build
class multi_vector and plug it into
an expression template engine (use PETE or use mine).

--------------

But if You insist on saving space - here is my
brainstorm idea how to achieve it.
What I like most with this approach is the type saftey
for the components.

// This is only a sketch!
// This code will not compile and may have some errors in it.

// some demo TinyVector
template <size_t Size, class T>
struct TinyVector
{
  double Data[Size];
  // Some features missing here like
  // operator()(size_t index)

Quote:};

// The Dummy that helps us to save some space
struct Empty
{}; // empty class optimization is available now

template <bool HasScalar,      
          bool HasPseudoScalar,
          bool HasVector,      
          bool HasBiVector>    
class MultiVector
{
public:
  using Loki::Select; // download loki at sourceforge.net
  // or use boost::mpl::if_ (if You prefer it)

  typedef typename
  Select<HasScalar, double, Empty>::Result ScalarType;    

  typedef typename
  Select<HasPseudoScalar, double, Empty>::Result PseudoScalarType;

  typedef typename
  Select<HasVector, TinyVector<3, double>, Empty>::Result VectorType;

  typedef typename
  Select<HasBiVector, TinyVector<3, double>, Empty>::Result
BiVectorType;

private:
  ScalarType         Scalar_;            
  PseudoScalarType   PseudoScalar_;
  VectorType         Vector_;
  BiVectorType       Bivector_;      

public:
  MultiVector(ScalarType Scalar,            
              PseudoScalarType PseudoScalar,
              VectorType Vector,
              BiVectorType Bivector)
    :
    Scalar_(Scalar),
    PseudoScalar_(PseudoScalar),
    Vector_(Vector),
    Bivector_(Bivector) {}

//   MultiVector() {} // I dislike this one, because here You initialize

//                    // all data with 0 first

  inline void setVector(double d1, double d2, double d3)
  {
    if (HasVector) // known at compile time => optimizer is happy
      {
        Vector_[1] = d1;
        Vector_[2] = d2;
        Vector_[3] = d3;
      }
    else
      {
        // runtime error
      }
  };

  inline VectorType getVector() {
    COMPILE_TIME_ASSERT(!SAME_TYPE(VectorType, Empty));
    return Vector_;
  }

  inline void SetBiVector(double d1, double d2, double d3);
  // etc;

Quote:};

////////////////////////////////////////////////////////////////////////
////
// operator+

template <class C> C operator+(const Empty& E, const C& c)
{
  return c;

Quote:}

template <class C> C operator+(const C& c, const Empty& E)
{
  return c;

Quote:}

// somehwre else
template <size_t Size, class T>
operator+(const TinyVector<Size, T>& V1, const TinyVector<Size, T>& V2);

template <bool LHS_HasScalar,
          bool LHS_HasPseudoScalar,
          bool LHS_HasVector,
          bool LHS_HasBiVector,
          bool RHS_HasScalar,
          bool RHS_HasPseudoScalar,
          bool RHS_HasVector,
          bool RHS_HasBiVector>

MultiVector<
            LHS_HasScalar       || RHS_HasScalar,      
            LHS_HasPseudoScalar || RHS_HasPseudoScalar,
            LHS_HasVector       || RHS_HasVector,      
            LHS_HasBiVector     || RHS_HasBiVector
            >    
operator+
(const MultiVector<LHS_HasScalar
                   LHS_HasPseudoScalar
                   LHS_HasVector      
                   LHS_HasBiVector>& lhs,
 const MultiVector<RHS_HasScalar
                   RHS_HasPseudoScalar
                   RHS_HasVector      
                   RHS_HasBiVector>& rhs)
{
  return MultiVector
    <
    LHS_HasScalar       || RHS_HasScalar,      
    LHS_HasPseudoScalar || RHS_HasPseudoScalar,
    LHS_HasVector       || RHS_HasVector,      
    LHS_HasBiVector     || RHS_HasBiVector
    >
    (
     lhs.getScalar() + rhs.getScalar(),
     //etc.
     );

Quote:}

int main()
{
  MultiVector<true, false, false, true>
    MV1(5.0, Empty(), Empty(), TinyVector<3, double>(1.2, 3.4, 5.0));

  MultiVector<true, false, false, false>
    MV2(5.0, Empty(), Empty(), Empty());

  // this here still is without an expression template engine,
  // but that is pluggable afterwards :-)
  MultiVector<true, false, false, true> MV3 = MV1 + MV2;

Quote:}    


      [ about comp.lang.c++.moderated. First time posters: do this! ]
 
 
 

Optimizing Mathematical Expressions For Size

Post by Jaap Sute » Sun, 28 Jul 2002 20:43:16


 > So You were dissatisfied with the result of Your other thread "The
 > future of C++'s static language"?

No not at all actually. Why do you think so? Having looked over the mpl
recently I was again surprised what was possible with the current mechanism.
Seeing an STL-ish structure where algorithms and containers are seperated
really blowed me away. Simply amazing.

 > The techiques proposed in that thread may fit here, too.

Maybe so. Problem is just that I can be overenthusiastic at times. I just
have this shiny new meta-programming hammer, and suddenly everything is a
nail. Even though I still don't know all the details about how to use the
hammer. Ah well, one can only learn through practice :).

 > Secondly: I do not see You really gain much with
 > an approach which tries to save the wasted space,
 > because once the compiler knows that all objects
 > that interact with each other have the same size,
 > some rigid optimizations (automatic vectorization)
 > may apply.

Wow, this is an optimization I've never heard a compiler do. Are you saying
(taking it to the extreme) that a compiler is allowed (in some cases) to
actually remove attributes from structures if it notices these are never
used?

 > Is size really a problem?

Yes, it is. Maybe premature optimization is the root of all evil [1], but
like I said; we need more than the elegance of a unifying theory if we are
to use it in actual computer science. I'm active in the games industrie,
mostly focusing on graphics. In this world, we need all the speed and size
optimizations we can get. Consoles like the GameCube, PS2 and the XBox are
very limited in memory.

 > Then go into the shop and buy some additional 512MB chip.

Our customers who play on a PC are not going into a shop to buy an
additional 512MB chip. Why? Because my competitor's game doesn't need it.

Even if we had the additional extra 512MB, current bottlenecks are mostly
bandwith related. If I can transfer 4 floats instead of 10 per vector to my
graphics hardware, you bet I'll see a speed increase with nowadays geometry
complexity.

 > I am not kidding. If I look at the development of
 > memory available in a standard PC during the last 10 years,
 > who cares about memory consumption tomorrow, when Your
 > program has left development state?

I don't care about memory-consumption tomorrow, I care about it today. My
game ships today, and it runs on todays hardware.

Computer games, computer graphics and many other fields never advanced it it
weren't for some really sweet optimizations. We can't afford to be lazy.

I prefer stable well written code over some hacked-together fast code
anyday, but if I can write stable well-written fast code at the same time, I
can't afford not to.

 > I still think that the best You can do is build
 > class multi_vector and plug it into
 > an expression template engine (use PETE or use mine).

Cool, I've never knew there were actual 'engines' that generalized
expression templates. I learn something every day. Thanks for the tip!

 > But if You insist on saving space - here is my
 > brainstorm idea how to achieve it.
 > What I like most with this approach is the type saftey
 > for the components.

 > // The Dummy that helps us to save some space
 > struct Empty
 > {}; // empty class optimization is available now

Yeah, the thought about using an Empty type to represent non-components
occured to me as well. However, I probably threw that idea away too quickly.
Because the Empty attributes still need to be addressable they do take up
some size, right? Probably a char (I would have to test that). I mean, take
the following code:

struct Empty {};

class FooA : Empty { float a };

sizeof( FooA ) == sizeof( float a ); // Right, empty class optimization...

However, when Empty is used as an attribute:

class FooB
{
     Empty a;
     Empty b;

Quote:}

sizeof( FooB ) == sizeof( char ) * 2; // Maybe, because char is the smallest
addressable unit? Or does a good compiler detect we're never using a and b,
and therefore optimize them away?

Then again, trading the size of an actual bi_vector for one unsigned char is
pretty cool. Too bad it's not enough for many people to start using
multi_vectors instead of oldskool vector/matrix algebra.

Anyway, thanks very much for the (snipped) code. It is very inspiring, and I
think I can develop this further.

Sincerely,

Jaap Suter


      [ about comp.lang.c++.moderated. First time posters: do this! ]

 
 
 

Optimizing Mathematical Expressions For Size

Post by Markus Werl » Wed, 31 Jul 2002 21:25:40


 > I don't care about memory-consumption tomorrow, I care about it today. My
 > game ships today, and it runs on todays hardware.
 >
 > Computer games, computer graphics and many other fields never advanced it
 > it weren't for some really sweet optimizations. We can't afford to be
 > lazy.

OK. I misguessed You were writing some scientific code, where
code devlopment time is 99% of the "game".
For true games I like to hear at least one guy worries about size,
since my kids cannot play most of the games on the P1-200Mhz 96MB
at home :-)

 >  > But if You insist on saving space - here is my
 >  > brainstorm idea how to achieve it.
 >  > What I like most with this approach is the type saftey
 >  > for the components.
 >
 >  > // The Dummy that helps us to save some space
 >  > struct Empty
 >  > {}; // empty class optimization is available now
 >
 > Yeah, the thought about using an Empty type to represent non-components
 > occured to me as well. However, I probably threw that idea away too
 > quickly. Because the Empty attributes still need to be addressable they do
 > take up some size, right?

I do not bet on optimizers again. They always do more than
I expect them to do.
What I found out with intel's C++ and GNU g++ is:
Expression templates and similar quasi-empty structures
like the above do not exist with their proper names anymore
after some aggressive optimization.
If You use inline wisely (= always) g++ e.g. flattens a
recursive structure with a few dozen levels and leaves You
with code that calls the leaves directly and far too often
one cannot find a breakpoint for debugging or profiling
in huge branches of execution; all stuff gets reordered ...

ET-code in most cases is "99% invisible" for the final executable.

 > [..]
 > However, when Empty is used as an attribute:
 >
 > class FooB
 > {
 >      Empty a;
 >      Empty b;
 > }
 >
 > sizeof( FooB ) == sizeof( char ) * 2; // Maybe, because char is the
 > smallest addressable unit? Or does a good compiler detect we're never
 > using a and b, and therefore optimize them away?

For local objects that live and die in small atomic scopes
the chance is rather high the stuff gets compressed,
especially when You never use it but use it as tag.

 > Then again, trading the size of an actual bi_vector for one unsigned char
 > is pretty cool. Too bad it's not enough for many people to start using
 > multi_vectors instead of oldskool vector/matrix algebra.

There is no one-size-fits-all. I myself use 2 or 3 different
approaches in parallel and - sorry - I do not see where multivector
really helps. Can You point to a paper that shows how and when to use them?

 > Anyway, thanks very much for the (snipped) code. It is very inspiring, and
 > I think I can develop this further.

You're welcome

Markus


      [ about comp.lang.c++.moderated. First time posters: do this! ]

 
 
 

Optimizing Mathematical Expressions For Size

Post by Noah Stei » Thu, 01 Aug 2002 05:42:01



Quote:> Maybe so. Problem is just that I can be overenthusiastic at times. I just
> have this shiny new meta-programming hammer, and suddenly everything is a
> nail. Even though I still don't know all the details about how to use the
> hammer. Ah well, one can only learn through practice :).

You have two antithetical goals in your original post making your request
impossible in C++'s language framework:

"Now I am looking for a way so I don't have to store the first half of
the array whenever a multi_vector is actually a special_vector... I can't
use any
runtime polymorphism..."


"However, this way the user has to know that p and q satisfy a criterium
(which they might not), and also, special_vector can't derive from
multi_vector."

How did you plan on optimizing this?  I don't see where there's a chance to
optimize it from the restrictions you've placed.  How were you planning on
specifying what your optimized layouts and operations are?  If you can't
constrain variables at declaration time, I don't see how you can hope to
optimize anything.

You can make a highly optimized system, but it will require creating special
classes that are a subset of the full geometric algebra.  I don't see why
that would be confusing or surprising.  Since GA represents points, vectors,
and rotations, it seems natural that the subsets are fairly well defined.
Your intermediate results will often be of "unknown" types, but that's
irrelevant.  Declare intermediates as the full GA type and let the compiler
optimize it down.

Quote:> Cool, I've never knew there were actual 'engines' that generalized
> expression templates. I learn something every day. Thanks for the tip!

There's a number of expression engines.  Check out http://oonumerics.org .
It will have plenty of links to systems that have implemented expression
engines.  You might also want to check out Jim Blinn's new book "Jim Blinn's
Corner: Notation, Notation, Notation" for a discussion of a small-scale
expression engine he uses for his graphics development.

Quote:> Yeah, the thought about using an Empty type to represent non-components
> occured to me as well. However, I probably threw that idea away too
quickly.
> Because the Empty attributes still need to be addressable they do take up
> some size, right? Probably a char (I would have to test that). I mean,
take
> the following code:

You are correct about the empty member variables taking up space.  Each is
guaranteed to take up no less than 1 byte.  The compiler is only allowed to
remove the space when it is a base class.  Even then, I think it can only
remove it for one base class in the face of multiple inheritance.  You can
use the system in a modified way by creating an inheritence hierarchy of all
non-empty classes.  It's going to be tricky, though.

-- Noah


      [ about comp.lang.c++.moderated. First time posters: do this! ]

 
 
 

Optimizing Mathematical Expressions For Size

Post by Markus Werl » Sat, 03 Aug 2002 06:51:15



> You are correct about the empty member variables taking up space.

Yes, http://www.cantrip.org/emptyopt.html

Quote:> Each is
> guaranteed to take up no less than 1 byte.  The compiler is only
> allowed to remove the space when it is a base class.

Don't You think that in the global optimization step
(or even earlier) the compiler may find out it never needs
the address of the empty member and reduce the
memory consumption automagically?

At least I do not see a problem with Expression Templates (ET)
or Template Meta-Programming (TMP):
I expect the compiler to look at the ET/TMP structures
figuring out which data goes where and then erase the original
data structures completely.

This really happens: The complete class/object may not exist
in executable code (at least I could not find symbols
with those names during debugging).  
So then the argument with the empty member space waste gets
pointless: No class - no empty member. They are gone.

Example:
In an expression for fixed-sized Matrix A, B, C;
C = A * B;
the compiler "knows" what to do and there is no need
for a run-time object to represent the rhs of this assignment. If the
type of the rhs is something like
BinOp<ConstRef<Matrix>, ConstRef<Matrix>, Mult>,
and if You declare all functions involved in the Assignment inline, You
will not see this structure after modern compilers munched the code.

Quote:> Even then, I think it can only
> remove it for one base class in the face of multiple inheritance.

That was new to me. I do not see any reason for this.
I googled a while but could not find an answer.
Could You please point to a place where this is discussed/explained?

Quote:> You can use the system in a modified way by creating
> an inheritence hierarchy of all
> non-empty classes.  It's going to be tricky, though.

Generic Solution at hand:
Andrei Alexandresou's Loki::GenLinearHierarchy helps alot here (though I
still think we do not need it with modern compilers).

Markus


      [ about comp.lang.c++.moderated. First time posters: do this! ]

 
 
 

Optimizing Mathematical Expressions For Size

Post by Jaap Sute » Sat, 03 Aug 2002 07:01:07


Quote:>  > Computer games, computer graphics and many other fields never
> advanced
it
>  > it weren't for some really sweet optimizations. We can't afford to
> be  > lazy.

> OK. I misguessed You were writing some scientific code, where code
> devlopment time is 99% of the "game". For true games I like to hear at
> least one guy worries about size, since my kids cannot play most of
> the games on the P1-200Mhz 96MB at home :-)

:) hehe.

Honestly though, I must admit that at the moment my purposes are
'scientific', however the idea is to gain insight in the value that
geometric algebra (GA) could have in realtime computer graphics. As far
as elegance goes, GA clearly wins. However, if any other method
(oldskool matrix/vectors for example) has significant performance
benefits, it is no use learning GA. That's why I was looking for ways of
optimizing GA implementations.

Quote:> There is no one-size-fits-all. I myself use 2 or 3 different
> approaches in parallel and - sorry - I do not see where multivector
> really helps. Can You point to a paper that shows how and when to use

them?

[offtopic]

Leo Dorst's paper: Honing geometric algebra for its use in the computer
sciences which can be found at
http://carol.wins.uva.nl/~leo/clifford/sommer.pdf is a good start. After
that, http://modelingnts.la.asu.edu/ has tons of information. All
assuming you don't have any experience with GA yet ofcourse, because if
you would, you probably wouldn't be asking this question :).

Thanks for all the help!

Jaap Suter


      [ about comp.lang.c++.moderated. First time posters: do this! ]

 
 
 

Optimizing Mathematical Expressions For Size

Post by Jaap Sute » Sat, 03 Aug 2002 07:01:32


Quote:> > Maybe so. Problem is just that I can be overenthusiastic at times. I
just
> > have this shiny new meta-programming hammer, and suddenly everything
> > is
a
> > nail. Even though I still don't know all the details about how to
> > use
the
> > hammer. Ah well, one can only learn through practice :).

> You have two antithetical goals in your original post making your
> request impossible in C++'s language framework:

Jup, that's what I found out. But I'd rather be told this by some C++
experts, than to make this conclusion myself only to find out it was
actually possible. My meta-programming skills don't go beyond some
compile-time factorials, power-of-twos, conditional-derivations and some
typelist magic. My experience is not sufficient yet to grasp the scope
and limitations of meta-programming. That's why I came here, because
maybe somebody could come up with something I didn't think of (which
happens all too often :) hehe).

Quote:> Declare intermediates as the full GA type and let the compiler
> optimize it down.

How is that possible? How can my optimizer ever do something like this:

struct A { float m[ 8 ] };

int main()
{
    A a;
    a.m[ 4 ] = 3;
    std::cout << a.m[ 4 ];

Quote:}

I doubt any current optimizer will notice that I'm only using one
element from A, and thus only allocate room for one float on the stack.
And even if it would be possible in the above case, it is certainly not
possible once the usage-information is spread over multiple scopes.

I probably didn't understand what you were actually trying to say
though.

Quote:> There's a number of expression engines.  Check out
> http://oonumerics.org . It will have plenty of links to systems that
> have implemented expression engines.  You might also want to check out
> Jim Blinn's new book "Jim
Blinn's
> Corner: Notation, Notation, Notation" for a discussion of a
> small-scale expression engine he uses for his graphics development.

Added to the Amazon wishlist. Thanks!

Sincerely,

Jaap Suter


      [ about comp.lang.c++.moderated. First time posters: do this! ]

 
 
 

1. Evaluating a Mathematical expression?

Chad,

 > Is there a Windows API call that can evaluate a Mathematical
 > expression that is within a string?

Sorry, no. I would recommend getting a decent lexer/parser generator (my
favorite is Antler).

--

Cheers,

Felix.

If you post a reply, kindly refrain from emailing it, too.

No anti-spam address here. Just one comment: IN YOUR FACE!

2. Changing citations

3. evaluate a string as a mathematical expression

4. Hard discs < 850Mb

5. Mathematical Expression Parser has moved

6. Win programming: Portability ?

7. parser for mathematical evaluation of expressions

8. Help! Datel Express and STe

9. A Class for recording mathematical expressions?

10. Help on parsing Mathematical expression

11. Bit manipulation to optimize size

12. may a compiler optimize x < v.size() ?

13. Binary Expression Tree with an infix expression