Possible with templates?
wizo...@hotmail.com
worthwhile challenge" sort of query!
Basically, I'm working on data structure design whereby all the objects
in my data structure have their properties referenced by integer ids.
Property values are also always integral. The naive implementation
would be to store all properties in an int-to-int map, and let any
object hold any value for any property.
Unfortunately, maps are problematic for two simple reasons: size and
speed. The application needs to work with 100s of 1000s of objects,
and each object can have up to 12 properties (although most only have 4
or 5). It needs to be able to very very rapidly access basically every
property of every object, and not impose unreasonable memory
requirements. The performance testing I did basically ruled out maps
on this basis.
Now much of the time the properties required are known at compile time.
That is, I might have code like:
int color = object.property(property_color);
Basically, I need this to compile to code that isn't measurably slower
than a direct reference to a data member, e.g.:
int color = object.color;
Furthermore, in order to reduce memory requirements, I've worked out
how pack all the possible properties into either 16 or 8 bit integers,
some of them signed, some of them unsigned.
I also know that each object has a key property - "type" - that
determines which other properties make sense for an object. So an
object of type, say, "sound" doesn't have a color, whereas an object of
type "car" would.
With this in mind I came up with a system of macros that allows me to
do the following:
template <bool get>
inline void getset(Object& obj, int prop, int& value, int type = 0)
{
if (type == 0) type = obj.props[0];
switch (type)
{
case objectSound:
GETSETPROP3(
int16_t, propPitch,
uint16_t, propDuration,
uint16_t, propVolume);
case objectCar:
GETSETPROP4(
uint16_t, propColor,
uint8_t, propCylinders,
uint8_t, propDoors,
uint16_t, propEngineSize);
// etc.etc.;
}
}
I've comfirmed by looking at the disassembly and some performance
testing that this does exactly what I want for cases where both the
object type and property id are known at compile time, and for cases
where one or the other or both are not (in fact, it's damn impressive
the sort of optimizations compilers can do in this regard!). The 'both
unknown at compile time' scenario pretty much only occurs when
serializing, but even this can't afford to be as slow as a std::map
lookup.
The part I don't like about it is the GETSETPROP# macros, which need to
be defined for every number between 1 and 12, and use some slightly
ugly casting, e.g.:
#define SPROP(P, N) case P: assign<get>(p->m##N, value); return;
#define GETSETPROP4(t1, p1, t2, p2, t3, p3, t4, p4) \
{ \
struct p_ { int16_t pad; t1 m1; t2 m2; t3 m3; t4 m4; }; \
p_* p = reinterpret_cast<p_*>(&obj); \
switch (prop) { SPROP(p1, 1) SPROP(p2, 2) SPROP(p3, 3) SPROP(p4, 4)
}; \
return; \
};
I accept the casting will be necessary one way or another (or you could
cheat and use a union), but this is really just a method of packing as
much data as possible into a limited block of space.
The obvious question is how much of this can be done with just template
meta-programming? I know you can define type chains and the like, but
I couldn't really see how it would help me here.
If I can scrap the macros entirely I would be very happy, but
everything I've tried so far has failed to get me anywhere.
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
Ian McCulloch
> Ok, this is really just a "is there anyone who thinks this is a
> worthwhile challenge" sort of query!
>
> Basically, I'm working on data structure design whereby all the objects
> in my data structure have their properties referenced by integer ids.
> Property values are also always integral. The naive implementation
> would be to store all properties in an int-to-int map, and let any
> object hold any value for any property.
>
> Unfortunately, maps are problematic for two simple reasons: size and
> speed. The application needs to work with 100s of 1000s of objects,
> and each object can have up to 12 properties (although most only have 4
> or 5). It needs to be able to very very rapidly access basically every
> property of every object, and not impose unreasonable memory
> requirements. The performance testing I did basically ruled out maps
> on this basis.
100,000 * 12 * sizeof(int) = 4.5MB (assuming int is 4 bytes). If efficiency
is so important, why not just put all the properties into an array and
directly access them? With the space overhead of a map, there probably
isn't much difference in memory use. Indeed, it may well take less memory.
Do you know in advance which properties are pertinent to each object?
Cheers,
Ian McCulloch
Udo Stenzel
> Ok, this is really just a "is there anyone who thinks this is a
> worthwhile challenge" sort of query!
>
> Basically, I'm working on data structure design whereby all the objects
> in my data structure have their properties referenced by integer ids.
This is actually the quite uninteresting challenge of educating you
about proper use of C or C++. What you describe are structures, plain
and simple. "properties" are just fields, you aren't keying them by
integers, but by symbolic names, and that's the same as field labels.
You also describe simple static typing, which is built-in to C++. Your
structures may also form an inheritance hierarchy or you may need to
build a union of (some of) them, but the need for that is not clear from
your description.
> The performance testing I did [...]
> and some performance testing [...]
Way too much performance testing and way too little design. If you
worked out what your program is actually supposed to do, the right data
structure would come naturally. Instead you "designed" a final solution
to all conceivable problems by modelling everything in terms of
"properties" and "objects", both of which are just hollow phrases. If
you follow this path, you just end up with an ugly and ill-designed
programming language, but still no application. (You may have a genuine
need for a language different from C++. If so, don't invent one, _use_
one instead.)
Udo.
wizo...@hotmail.com
Udo Stenzel wrote:
> wizo...@hotmail.com <wizo...@hotmail.com> schrieb:
> > Ok, this is really just a "is there anyone who thinks this is a
> > worthwhile challenge" sort of query!
> >
> > Basically, I'm working on data structure design whereby all the objects
> > in my data structure have their properties referenced by integer ids.
>
> This is actually the quite uninteresting challenge of educating you
> about proper use of C or C++. What you describe are structures, plain
> and simple. "properties" are just fields, you aren't keying them by
> integers, but by symbolic names, and that's the same as field labels.
> You also describe simple static typing, which is built-in to C++. Your
> structures may also form an inheritance hierarchy or you may need to
> build a union of (some of) them, but the need for that is not clear from
> your description.
>
nearly 15 years of C/C++ programming, I've seend and used almost every
conceivable data structure in existence. I'm quite happy with the
solution I have, I'm just curious if there's a slightly neater way to
implement it.
>
> > The performance testing I did [...]
> > and some performance testing [...]
>
> Way too much performance testing and way too little design.
I initially spent 12 months (on and off) designing the basic data
structure - working out what object types are required and what
properties each type requires.
But I have some real performance requirements that just are not
satisfied but any other option I've tried out so far.
> Instead you "designed" a final solution
> to all conceivable problems by modelling everything in terms of
> "properties" and "objects", both of which are just hollow phrases.
True, but they adequately and accurately represent all the data I
require and the concepts I am modelling. What I need is a compact and
efficient way to store them in memory, that allows very rapid
iteration.
The reason C++ is ideal for what I want is that I can entirely separate
the code that requires access to the objects and their properties from
the data structures used to store them - in the performance testing I
did, I never had to change the application code - only the data
definitions and the accessor functions. Few other languages would make
that straightforward.
wizo...@hotmail.com
> wizo...@hotmail.com wrote:
>
> > Ok, this is really just a "is there anyone who thinks this is a
> > worthwhile challenge" sort of query!
> >
> > Basically, I'm working on data structure design whereby all the objects
> > in my data structure have their properties referenced by integer ids.
> > Property values are also always integral. The naive implementation
> > would be to store all properties in an int-to-int map, and let any
> > object hold any value for any property.
> >
> > Unfortunately, maps are problematic for two simple reasons: size and
> > speed. The application needs to work with 100s of 1000s of objects,
> > and each object can have up to 12 properties (although most only have 4
> > or 5). It needs to be able to very very rapidly access basically every
> > property of every object, and not impose unreasonable memory
> > requirements. The performance testing I did basically ruled out maps
> > on this basis.
>
> 100,000 * 12 * sizeof(int) = 4.5MB (assuming int is 4 bytes). If efficiency
> is so important, why not just put all the properties into an array and
> directly access them? With the space overhead of a map, there probably
> isn't much difference in memory use. Indeed, it may well take less memory.
> Do you know in advance which properties are pertinent to each object?
>
across all objects, and I want my code to be able to generically
attempt to access any property from any value, even though, in the
current design, every object type only requires a small subset of the
total available property types.
And even 4.5 Mb is more than I'd like to use, given that this will not
represent the entire memory footprint, and I would like to be able to
run several instances of the same application. Currently I'm at ~2 Mb,
and I'd like to keep it that way.
kanze
> wizo...@hotmail.com wrote:
> > Ok, this is really just a "is there anyone who thinks this
> > is a worthwhile challenge" sort of query!
> > Basically, I'm working on data structure design whereby all
> > the objects in my data structure have their properties
> > referenced by integer ids. Property values are also always
> > integral. The naive implementation would be to store all
> > properties in an int-to-int map, and let any object hold any
> > value for any property.
> > Unfortunately, maps are problematic for two simple reasons:
> > size and speed. The application needs to work with 100s of
> > 1000s of objects, and each object can have up to 12
> > properties (although most only have 4 or 5). It needs to be
> > able to very very rapidly access basically every property of
> > every object, and not impose unreasonable memory
> > requirements. The performance testing I did basically ruled
> > out maps on this basis.
> 100,000 * 12 * sizeof(int) = 4.5MB (assuming int is 4 bytes).
> If efficiency is so important, why not just put all the
> properties into an array and directly access them? With the
> space overhead of a map, there probably isn't much difference
> in memory use. Indeed, it may well take less memory. Do you
> know in advance which properties are pertinent to each object?
If I understand correctly, he wants some sort of generic access;
given a (variable) property id, he wants to access the correct
property.
The most direct way of implementing this is to just use virtual
functions get and set:
class Object
{
public:
virtual ~Object() {}
virtual int get( int propertyId ) const = 0 ;
virtual void set( int propertyId, int newValue ) = 0 ;
} ;
Each concrete type then derives from Object, defines whatever
properties it needs as data members, and provides an
implementation of get and set to access the correct member; a
naíve implementation might use a switch, but double dispatch
through an object in a map could also be used:
struct AbstractGetterSetter
{
virtual ~GetterSetter() {}
vitual int get( Object const* obj ) const = 0 ;
virtual void set( Object * obj, int newValue ) const = 0 ;
} ;
template< typename Derived, int propertyId >
struct GetterSetter : public AbstractGetterSetter
{
virtual int get( Object const* obj ) const
{
return static_cast< Derived const* >( obj )->get<
propertyId >() ;
}
virtual void set( Object* obj, int newValue ) const
{
static_cast< Derived* >( obj )->set< propertyId >( newValue
) ;
}
} ;
with for each object type:
std::map< int, AbstractGetterSetter const* >
ourPropertyMap ;
It would still be necessary in each derived object to define the
template specializations for the relevant properties. And to
initialize the static maps. It should be relatively easy to
generate this code automatically, however. (Some form of
indirection is probably needed, as I don't think you can
explicitly specialize a member function template of a
non-template class. Or perhaps you define the derived class as
a template specialization, templated on the propertyId.)
An alternative solution would be to declare virtual getters and
setters for all of the possible attributes in the base class,
with a default implementation of generating an error. When
generic access is needed (which is probably the exception --
when getting or setting a color, the code knows that it is
dealing with color), a simple vector of pointers to abstract
getter/setter objects like the above could be used. This would
be the fastest solution, but it results in an extremely heavy
base class interface.
--
James Kanze GABI Software
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
Calum Grant
> Ok, this is really just a "is there anyone who thinks this is a
> worthwhile challenge" sort of query!
>
> Basically, I'm working on data structure design whereby all the
> objects
> in my data structure have their properties referenced by integer ids.
> Property values are also always integral. The naive implementation
> would be to store all properties in an int-to-int map, and let any
> object hold any value for any property.
Some ideas to try:
1) Use virtual functions
class object
{
public:
virtual int get_property(int key)
{
throw no_such_property();
}
};
class vehicle : public object
{
int m_colour, m_cylinders;
public:
...
int get_property(int key)
{
switch(key)
{
case colour: return m_colour;
case cylinders: return m_cylinders;
default: return object::get_property(key);
}
};
};
class car : public vehicle
{
public:
...
int get_property(int key)
{
switch(key)
{
case wheels: return 4;
default: return vehicle::get_property(key);
};
}
};
2) Store an array of std::pair<int,int> for each object. Use a binary
search to locate the property you want and read off the value.
3) Have a hash_map<std::pair<object,property>, value> Would be much
faster than a map.
4) The template solution sounds a little hairy, but I think could be
done.
Calum
wka...@yahoo.com
...
> Basically, I'm working on data structure design whereby all the objects
> in my data structure have their properties referenced by integer ids.
> Property values are also always integral. The naive implementation
> would be to store all properties in an int-to-int map, and let any
> object hold any value for any property.
Resist not the power of the Dark Side...
packaux.hpp
-----------------------
class P__OBJECT_NAME
{
private:
#undef B1
#undef B2
#define B1(PROP) unsigned char PROP##_;
#define B2(PROP) unsigned char PROP##_[2];
P__PROPERTIES
public:
unsigned short get_prop(int prop)
{
switch (prop)
{
#undef B1
#undef B2
#define B1(PROP) case PROP : return(PROP##_);
#define B2(PROP) \
case PROP : return(PROP##_[0] << 8 | PROP##_[1]);
P__PROPERTIES
}
return(0);
}
void set_prop(int prop, unsigned short val)
{
switch (prop)
{
#undef B1
#undef B2
#define B1(PROP) \
case PROP : \
PROP##_ = static_cast<unsigned short>(val); break;
#define B2(PROP) \
case PROP : \
PROP##_[0] = static_cast<unsigned short>(val >> 8); \
PROP##_[1] = static_cast<unsigned short>(val & 0xFF); \
break;
P__PROPERTIES
}
}
};
#undef B1
#undef B2
-------------------------
The header file(s) to define the classes would contain bits like this:
#undef P__OBJECT
#undef P__PROPERTIES
#define P__OBJECT_NAME Car
#define P__PROPERTIES B1(Color) B2(Weight) B1(Age)
#include "packaux.hpp"
#undef P__OBJECT
#undef P__PROPERTIES
#define P__OBJECT_NAME Person
#define P__PROPERTIES B1(Age) B1(Sex) B2(ZipCode)
#include "packaux.hpp"
...
#undef P__OBJECT
#undef P__PROPERTIES
Usage would look like:
Car car;
car.set_prop(Color, Blue);
car.set_prop(Weight, 2345);
std::cout << "Age = " << car.get_prop(Age) << endl;
You could avoid being dependent on the compiler to inline
optimally, but it would be significanly more complicated.
wizo...@hotmail.com
> Ian McCulloch wrote:
>
> > 100,000 * 12 * sizeof(int) = 4.5MB (assuming int is 4 bytes).
> > If efficiency is so important, why not just put all the
> > properties into an array and directly access them? With the
> > space overhead of a map, there probably isn't much difference
> > in memory use. Indeed, it may well take less memory. Do you
> > know in advance which properties are pertinent to each object?
>
> If I understand correctly, he wants some sort of generic access;
> given a (variable) property id, he wants to access the correct
> property.
>
> The most direct way of implementing this is to just use virtual
> functions get and set:
>
any unnecessary indirection or memory allocation/deallocation. My
"objects" are just lumps of data really - they don't have any behaviour
per se (this is basically because determining what to do with one
particular object depends heavily on the surrounding objects, so the
logic has to be handled by the container, not the objects themselves).
I really can't afford a solution that's any slower than my current one,
so I was just hoping maybe there was a cleaner way of the defining how
to pack the properties into each object.
Dave Harris
> The obvious question is how much of this can be done with just template
> meta-programming?
It sounds like you have nested switch statements, the first testing the
object's type and the second the property. The tests need to be dynamic
because the tested values aren't always known at compile time.
I don't see how to make a switch with templates. I expect it is possible
to synthesis a linear search using type chains and the like. Probably it
is possible to synthesis a binary search, too. The big question is whether
the compiler will be able to optimise it when the values are known. You
could end up with a recursive search, eg:
int Child::get( int property ) {
if (property < c_property) ?
return Base1::get( property );
else
return Base2::get( property );
}
where c_property is a compile time constant. It might be worth trying. A
good compiler could inline everything into a big if-else tree, and when
property is known at compile time it could do all the comparisons at
compile time too, leaving a simple return statement.
Whether the binary search is slower than the switch statement if the
property is not a compile time constant I don't know. You'd need to
measure. The number of cases is small, and a direct jump can be much
faster than an indirect jump, and a switch statement will need a few tests
to ensure the argument is in range anyway. Some compilers might implement
the switch with a linear or binary search anyway.
It sounds to me like it would be worth a try, at least for the second
switch. For the first switch I gather you have more cases, so a
switch+cast may be better. As James Kanze says you could also use a
virtual function call, but I suspect that would be harder for the compiler
to optimise.
I'm not going to write real code, but ideally a declaration would look
like:
struct ObjectCar :
Child<propPitch,
Child<propPitch,
Base<propPitch,int16_t>,
Base<propCylinders,int8_t> >,
Child<propDoors,
Base<propDoors,int8_t>,
Base<propEngineSize,int16_t> > > {
};
only with some means to disambiguate the base classes. I suppose there's a
danger this would be less space efficient than your version.
-- Dave Harris, Nottingham, UK.
kwikius
wizo...@hotmail.com wrote:
[cut]
> I accept the casting will be necessary one way or another (or you could
> cheat and use a union), but this is really just a method of packing as
> much data as possible into a limited block of space.
>
> The obvious question is how much of this can be done with just template
> meta-programming? I know you can define type chains and the like, but
> I couldn't really see how it would help me here.
The following uses multiple inheritance to solve the problem. Only
compile time properties are available, but looking through your
original function this seems to be confirmed by the type parameter
anyway.
#include <iostream>
template <int ID>
struct property{
property() : value(0){}
int value;
int get() const
{
return value;
}
void set ( int v)
{
value = v;
}
};
// for how both functions work see below
template <int ID,typename Object>
int get_property (Object const & in)
{
property<ID> const & t = static_cast<property<ID> const & >(in);
return t.get() ;
}
template <int ID,typename Object>
void set_property (Object & in, int value)
{
property<ID> & t = static_cast<property<ID> & >(in);
t.set(value) ;
}
// some 'objects' comprised of various properties
struct my_object1 : property<1>,property<2>{};
struct my_object2 : property<5>,property<6>,property<7>{};
int main()
{
my_object1 object1;
std::cout << get_property<1>(object1)<<'\n';
set_property<1>(object1,2);
std::cout << get_property<1>(object1)<<'\n';
my_object2 object2;
std::cout << get_property<5>(object2)<<'\n';
set_property<5>(object2,100);
std::cout << get_property<5>(object2)<<'\n';
// regards
// Andy Little
Calum Grant
> Ok, this is really just a "is there anyone who thinks this is a
> worthwhile challenge" sort of query!
>
> Basically, I'm working on data structure design whereby all the objects
> in my data structure have their properties referenced by integer ids.
> Property values are also always integral. The naive implementation
> would be to store all properties in an int-to-int map, and let any
> object hold any value for any property.
<snip>
> With this in mind I came up with a system of macros that allows me to
> do the following:
>
> template <bool get>
> inline void getset(Object& obj, int prop, int& value, int type = 0)
> {
> if (type == 0) type = obj.props[0];
> switch (type)
> {
> case objectSound:
> GETSETPROP3(
> int16_t, propPitch,
> uint16_t, propDuration,
> uint16_t, propVolume);
> case objectCar:
> GETSETPROP4(
> uint16_t, propColor,
> uint8_t, propCylinders,
> uint8_t, propDoors,
> uint16_t, propEngineSize);
> // etc.etc.;
> }
> }
I think I would prefer virtual functions to switching based upon a type
enumeration. This makes the object-model extensible, and I think more
efficient (though, you should check that on your particular compiler).
Also watch out for alignment issues: you may not necessarily get a
speed/space improvement just because you use 8 bits instead of 16.
The answer to your question is yes, you can use templates, and I think
they are a preferable solution to macros. Here is a complete solution
based upon virtual functions, that uses templates to construct
property-lists:
#include <cassert>
#include <stdexcept>
class NoSuchProperty : public std::out_of_range
{
public:
NoSuchProperty() : std::out_of_range("NoSuchProperty") { }
};
class object
{
public:
virtual short &operator[](int x)=0;
virtual short operator[](int x) const=0;
};
class empty { };
template<int I, class Tail=empty>
struct int_list
{
static int const value = I;
typedef Tail tail_type;
};
template<class Value, class List>
class property_list
{
Value value;
property_list<Value, typename List::tail_type> tail;
public:
Value &property(int k)
{
return k == List::value ? value :
tail.property(k);
}
const Value &property(int k) const
{
return k == List::value ? value :
tail.property(k);
}
};
template<class Value>
class property_list<Value,empty>
{
public:
Value &property(int i)
{
throw NoSuchProperty(); // Maybe return 0 instead?
}
const Value &property(int i) const
{
throw NoSuchProperty(); // Maybe return 0 instead?
}
};
template<typename IntList>
class property_object : public object
{
property_list<short, IntList> m_property_list;
public:
short &operator[](int k) { return m_property_list.property(k); }
short operator[](int k) const { return m_property_list.property(k); }
};
template<int I1> class int_list_1 : public int_list<I1> { };
template<int I1, int I2> class int_list_2 : public int_list<I1,
int_list<I2> > { };
template<int I1, int I2, int I3> class int_list_3 : public int_list<I1,
int_list_2<I2, I3> > { };
// etc
namespace properties
{
enum { colour, wheels, cylinders, engine_capacity, legs };
}
namespace objects
{
typedef property_object<int_list_3<properties::colour,
properties::wheels, properties::cylinders> > Vehicle;
typedef property_object<int_list_2<properties::legs,
properties::colour> > Animal;
}
int main(int argc, char* argv[])
{
objects::Vehicle car, bike;
car[properties::wheels] = 4;
bike[properties::wheels] = 2;
car[properties::colour] = 10;
objects::Animal horse, centipede;
horse[properties::legs] = 4;
centipede[properties::legs] = 100;
horse[properties::colour] = 4;
object &horseRef(horse);
assert(horseRef[properties::legs] == 4);
bool caught = false;
try
{
horseRef[properties::wheels];
}
catch(NoSuchProperty&)
{
caught = true;
}
assert(caught);
return 0;
kwikius
kwikius wrote:
> wizo...@hotmail.com wrote:
>
> [cut]
>
> > I accept the casting will be necessary one way or another (or you could
> > cheat and use a union), but this is really just a method of packing as
> > much data as possible into a limited block of space.
> >
> > The obvious question is how much of this can be done with just template
> > meta-programming? I know you can define type chains and the like, but
> > I couldn't really see how it would help me here.
>
> The following uses multiple inheritance to solve the problem. Only
> compile time properties are available, but looking through your
> original function this seems to be confirmed by the type parameter
[cut]
The previous code couldnt be used in a list of objects. The following
code (needs http://www.boost.org libs) extended from the code above
allows this:
#include <boost/utility/enable_if.hpp>
#include <boost/type_traits/is_base_of.hpp>
#include <vector>
#include <iostream>
// use MI to inherit your object
// from required properties
template <int ID>
struct property{
static const int id = ID;
property() : value(0){}
int value;
int get() const
{
return value;
}
void set(int v)
{
value = v;
}
};
// error function
struct invalid_property : std::out_of_range{
invalid_property()
: std::out_of_range(
"property out of range"
){}
};
// check if a particular Object-type has property N
template <typename Object, int ID>
struct has_property : boost::is_base_of<
property<ID>,Object
>{};
// get_property is called on various Objects
// this overload for valid objects
template <int ID,typename Object>
inline
typename boost::enable_if<
has_property<Object, ID>,
int
>::type
get_property (Object const & in)
{
property<ID> const& t
= static_cast<property<ID> const&>(in);
return t.get() ;
}
// get_property needs to be instantiated
// for Objects that cant be cast to property<ID>
// in object_impl below
// but will fail if actually called
template <int ID,typename Object>
inline
typename boost::disable_if<
has_property<Object,ID>,
int
>::type
get_property (Object const & in)
{
throw invalid_property();
}
template <int ID,typename Object>
inline
typename boost::enable_if<
has_property<Object,ID>,
void
>::type
set_property (Object & in, int value)
{
property<ID>& t
= static_cast<property<ID>&>(in);
t.set(value) ;
}
// needs to be instantiated
// by object_impl below,
// but will fail if called
template <int ID,typename Object>
inline
typename boost::disable_if<
has_property<Object,ID>,
void
>::type
set_property (Object & in, int value)
{
throw invalid_property();
}
// base class for containerable objects
struct object{
virtual int get(int property_id)const =0;
virtual void set(int property_id,int value) =0;
virtual ~object(){}
// some 'properties'
enum {
prop1 = 1,
prop2,
prop3,
prop4,
prop5,
prop6,
prop7
};
};
// object implementation,
// derive class with properties from here
// usin CRTP
// so derived class can be
// used in object* containers
// (Theoretically CRTP removes
// some virtual function call overhead)
template <typename D>
struct object_impl : object{
// allow D to create more efficient
// get_impl function as in my_object3 below
int get(int property_id)const{
D const & d
= static_cast<D const &>(*this);
return d.get_impl(property_id);
}
// this version needs a case for all potential properties
// (Actually if all cases are in step then lookup implementation
// is constant time [just jump offset]
// irrespective of number of values in VC7.1 at least)
int get_impl(int property_id) const
{
D const & d
= static_cast<D const &>(*this);
int result =0;
switch (property_id){
case object::prop1:
result = get_property<object::prop1>(d);
break;
case object::prop2:
result = get_property<object::prop2>(d);
break;
case object::prop3:
result = get_property<object::prop3>(d);
break;
case object::prop4:
result = get_property<object::prop4>(d);
break;
case object::prop5:
result = get_property<object::prop5>(d);
break;
case object::prop6:
result = get_property<object::prop6>(d);
break;
case object::prop7:
return get_property<object::prop7>(d);
default:
throw invalid_property();
}
return result;
}
// allow derived to create more efficient
// set_impl function as in object3 below
void set(int property_id,int value)
{
D & d = static_cast<D &>(*this);
d.set_impl(property_id,value);
}
// this version needs statements for
// all properties
void set_impl(int property_id,int value)
{
D& d = static_cast<D&>(*this);
switch (property_id){
case object::prop1:
set_property<object::prop1>(d,value);
break;
case object::prop2:
set_property<object::prop2>(d,value);
break;
case object::prop3:
set_property<object::prop3>(d,value);
break;
case object::prop4:
set_property<object::prop4>(d,value);
// throw invalid_property();
break;
case object::prop5:
set_property<object::prop5>(d,value);
break;
case object::prop6:
set_property<object::prop6>(d,value);
break;
case object::prop7:
set_property<object::prop7>(d,value);
break;
default:
throw invalid_property();
}
}
};
// some example 'objects' comprised of various properties
// They also need to be derived from object_impl<T>
//if they are meant to be 'objects'
struct my_object1 :
property<object::prop1>,
property<object::prop2>,
object_impl<my_object1>{};
struct my_object2 :
property<object::prop5>,
property<object::prop6>,
property<object::prop7>,
object_impl<my_object2>{};
// One obvious refinement. In my_object3 smaller
// size of lookup for get_impl is achieved by
// over-riding get_impl, set_impl functions
// because Only look up of PA, PB,PC is required
// Would need to add versions of the class
// for different numbers of properties
// No speed up expected but maybe smaller size
// assuming object_impl functions not instantiated
// for these versions. Actually
// I think ths may be slower than the version in
// object_impl though!
template <int PA,int PB, int PC>
struct my_object3 :
property<PA>,
property<PB>,
property<PC>,
object_impl<my_object3>{
int get_impl(int property_id) const
{
int result=0;
switch (property_id){
case PA:
result = get_property<PA>(*this);
break;
case PB:
result = get_property<PB>(*this);
break;
case PC:
result =get_property<PC>(*this);
break;
default:
throw invalid_property();
}
return result;
}
void set_impl(int property_id, int value)
{
switch (property_id){
case PA:
set_property<PA>(*this,value);
break;
case PB:
set_property<PB>(*this,value);
break;
case PC:
set_property<PC>(*this,value);
break;
default:
throw invalid_property();
}
}
};
// further encapsulation is cheap and easy
struct my_object4 :
my_object3<object::prop4,object::prop1,object::prop7>{};
int main()
{
try{
my_object1 object1;
int p1 = get_property<object::prop1>(object1);
std::cout << p1 <<'\n';
set_property<object::prop1>(object1,2);
p1 = get_property<object::prop1>(object1);
std::cout << p1<<'\n';
my_object2 object2;
int p2 = get_property<object::prop5>(object2);
std::cout << p2 <<'\n';
set_property<object::prop5>(object2,100);
p2 = get_property<object::prop5>(object2);
std::cout << p2<<'\n';
// check objects work ok in container
std::vector<object*> vect;
vect.push_back(&object1);
vect.push_back(&object2);
std::cout << vect[0]->get(object::prop1) <<'\n';
vect[0]->set(object::prop1,-999) ;
std::cout << vect[0]->get(object::prop1) <<'\n';
my_object3<object::prop3,object::prop4,object::prop1> object3;
vect.push_back(&object3);
std::cout << vect[2]->get(object::prop4) <<'\n';
vect[2]->set(object::prop4,-888) ;
std::cout << vect[2]->get(object::prop4) <<'\n';
my_object4 object4;
vect.push_back(&object4);
std::cout << vect[3]->get(object::prop7) <<'\n';
vect[3]->set(object::prop7,-777) ;
std::cout << vect[3]->get(object::prop7) <<'\n';
}
catch (invalid_property & e){
std::cout << e.what() <<'\n';
}
}
regards
kwikius
> If I can scrap the macros entirely I would be very happy, but
> everything I've tried so far has failed to get me anywhere.
Having looked into it a bit more ( via my two previous posts in this
thread), I reckon that your current solution is pretty well optimal. It
seems to work at least 2x as fast as my polymorphic code at least where
constants are known at compile time (otoh my rt non-polymorpic code
works as fast), so if it works for you, I guess you should ignore the
stylists and live with it. ;-). I think that you could do pretty much
the same by slicing a class built up in parts, at least for the code in
your post. Also I wonder whether a design in which one 'object' may
have a sound property but no sound option and another a colour but no
sound option couldnt be improved...
cheers
Andy Little
kanze
I'm not sure I understand your current solution. I had the
impression that you were using a switch -- depending on the
underlying hardware, a virtual function may be just as fast, or
even faster (or a lot slower -- it depends on the hardware).
That doesn't necessarily mean that it is the "correct" solution
in every case. What you are basically doing is using
discriminate unions, and there are cases where that is an
appropriate solution, even if there is no direct support for it
in C++ (except for the special guarantee in §9.2/16). While
it's rare that the choice between discriminate unions and an
inheritance hierarchy will make a significant difference in
terms of run-time, your statement that "what to do with one
particular object depends heavily on the surrounding objects"
suggests very strongly that discriminate unions are the
appropriate solution, or at least a solution which should be
considered.
--
James Kanze GABI Software
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
Larry
went I posted from my newsreader.)
On 11/07/2005 03:32 AM, Calum Grant wrote:
[snip]
> The answer to your question is yes, you can use templates, and I think they are a preferable solution to macros. Here is a complete solution based upon virtual functions, that uses templates to construct property-lists:
[snip]
> template<class Value, class List>
> class property_list
> {
> Value value;
> property_list<Value, typename List::tail_type> tail;
> public:
> Value &property(int k)
> {
> return k == List::value ? value :
> tail.property(k);
> }
>
> const Value &property(int k) const
> {
> return k == List::value ? value :
> tail.property(k);
> }
> };
>
Although the OP number of properties was small, and consequently
the time taken to do the k==List::value tests would likewise
be small, it might be faster to calculate a vector of methods
indexed by List::value. The method above was used in:
the proposed method is used here:
in file acceptor_complete.zip. Basicly, a vector
of function pointers indexed by List::value is
used to directly jump to the appropriate
function. This vector is built in acceptor_complete.hpp.
kwikius
Calum Grant wrote:
Calum Grant wrote:
> The answer to your question is yes, you can use templates, and I think
> they are a preferable solution to macros. Here is a complete solution
> based upon virtual functions, that uses templates to construct
> property-lists:
FWIW I decide to do some tests of a write on these various efforts.
Dont take it too seriously ;-)
source files used are at :
http://www.servocomm.freeserve.co.uk/Cpp/template_quest/
(I renamed the objects to prevent clashes)
object1 is Wizof
object2 is Andy Little (me)
object3 is Calum Grant
unoptimised in VC7.1
Object1 time = 0.39
Object2 time = 0.86
Object3 time = 0.5
optimised, using VC7.1 with /O2
Object1 time = 0
Object2 time = 0.187
Object3 time = 0.078
Mine didnt do too well :-O
regards
Andy Little
kwikius
I believe that the reason for the speed of the OP's code is that there
is no function call whatever once the function has been optimised,
which compiler obviously finds trivial too. Function call overhead is
the problem in the other versions, In mine two function calls, and as
you point out dependent on the property parameter in Calums. IOW in the
quest for speed function pointers are out. The code following is IMO
equivalent to Op's code and seems to run as fast as OP's code. It does
seem to demonstrate that the c-style stuff is faster (Unless of course
anyone can come up with C++ style way to beat it!) . Note that the
obvious modification of making the type a member of a base class causes
a large slow down, which is why it hasnt been done here. Its also
noticeably 'orrible to use. With all these int parameters one needs to
find what each int parameter means and errors in parameter order will
be hard to find. Nevertheless it is fast!
struct one {
int v1;
};
struct two : one{
int v2;
};
struct three : two{
int v3;
};
inline void set(void* in, int prop, int value, int type)
{
switch (type){
case 1:{
one * t = reinterpret_cast<one*>(in);
switch(prop){
case 1:
t->v1 = value;
break;
default:
;
}
return;
}
case 2: {
two * t = reinterpret_cast<two *>(in);
switch(prop){
case 1:
t->v1 = value;
break;
case 2:
t->v2 = value;
break;
default:
;
}
}
case 3: {
three* t = reinterpret_cast<three*>(in);
switch(prop){
case 1:
t->v1 = value;
break;
case 2:
t->v2 = value;
break;
case 3:
t->v3 = value;
break;
default:
;
}
}
default:
;
}
}
regards
Andy Little
wizo...@hotmail.com
kwikius wrote:
> wizo...@hotmail.com wrote:
>
> > If I can scrap the macros entirely I would be very happy, but
> > everything I've tried so far has failed to get me anywhere.
>
> Having looked into it a bit more ( via my two previous posts in this
> thread), I reckon that your current solution is pretty well optimal. It
> seems to work at least 2x as fast as my polymorphic code at least where
> constants are known at compile time (otoh my rt non-polymorpic code
> works as fast), so if it works for you, I guess you should ignore the
> stylists and live with it. ;-). I think that you could do pretty much
> the same by slicing a class built up in parts, at least for the code in
> your post. Also I wonder whether a design in which one 'object' may
> have a sound property but no sound option and another a colour but no
> sound option couldnt be improved...
>
have
one particular set of properties, others of which have rather different
properties.
My example was actually that an object of type "sound" would not
logically have
a property 'color', whereas a car would. Of course, these aren't
actual
object types in my application, but there's no question that my
application
does need to deal with a large number of heterogenous objects for which
there
is no real need for every object to be capable of storing a value for
every possible
property type.
But yes, I know my solution is highly optimized, and most definitely
worth it
(your 2x was nothing compared to some of the results I was seeing - I
had to
seriously fine tune the map-based implementation to get it down to even
a
quarter of the speed and about 8 times the memory usage!).
I just thought there might be a nicer alternative to the macros.
wizo...@hotmail.com
> wizo...@hotmail.com wrote:
> > kanze wrote:
>
> > > If I understand correctly, he wants some sort of generic
> > > access; given a (variable) property id, he wants to access
> > > the correct property.
>
> > I really can't afford a solution that's any slower than my
> > current one, so I was just hoping maybe there was a cleaner
> > way of the defining how to pack the properties into each
> > object.
>
> I'm not sure I understand your current solution. I had the
> impression that you were using a switch -- depending on the
> underlying hardware, a virtual function may be just as fast, or
> even faster (or a lot slower -- it depends on the hardware).
Actually it's more a matter of the compiler than the hardware.
Compilers can optimize away entire functions if all the
arguments are known at compile time. They tend to do far less
well with virtual functions. And using virtual functions requires that
each object essentially be allocated separately and referred to via
a pointer.
>
> That doesn't necessarily mean that it is the "correct" solution
> in every case. What you are basically doing is using
> discriminate unions, and there are cases where that is an
> appropriate solution, even if there is no direct support for it
> in C++ (except for the special guarantee in §9.2/16). While
> it's rare that the choice between discriminate unions and an
> inheritance hierarchy will make a significant difference in
> terms of run-time, your statement that "what to do with one
> particular object depends heavily on the surrounding objects"
> suggests very strongly that discriminate unions are the
> appropriate solution, or at least a solution which should be
> considered.
>
If I understand what you mean by "discriminate unions" then yes,
I think that's basically the technique I'm using, except that it's
using casts rather than unions, as I couldn't see any way to
combine the declaring of the unions with the access - that is, I
want one piece of code that simultaneously declares how each
property is packed into each type of object, and generates the
necessary code to access those properties. With unions, I'd
end up with
struct sound_properties
{
int16_t pitch;
uint16_t duration,
uint16_t volume;
};
struct car_properties
{
uint16_t color;
uint8_t cylinders;
//etc.etc.
};
struct Object
{
int type;
union properties
{
sound_properties sound;
car_properties car;
// etc. etc.
};
};
template <bool get>
inline void getset(Object& obj, int prop, int& value, int type = 0)
{
if (type == 0) type = obj.type;
switch (type)
{
case objectSound:
switch (prop)
{
case propPitch: access<get>(obj.sound.pitch, value);
return;
case propDuration: access<get>(obj.sound.duration,
value); return;
case propVolume: access<get>(obj.sound.volume, value);
return;
};
break;
case objectCar:
switch (prop)
{
case propColor: access<get>(obj.car.color, value);
return;
case propCylinders: access<get>(obj.sound.cylinders,
value); return;
// etc. etc.
};
// etc. etc.
};
}
...which is too much to maintain for my taste.
Unless I'm misunderstanding what you mean by discriminate unions.
Btw, it should be obvious, but the extra parameter to pass in the type
is necessary to cause the compiler to optimize out the switch statement
completely when both the object type and property are known at compile
time. It would require full program analysis for a compiler to be
smart enough to do it automatically based on the fact that the calling
function could only have been called given a particular object type.
Larry
> Larry wrote:
[snip]
> I believe that the reason for the speed of the OP's code is that there
> is no function call whatever once the function has been optimised,
> which compiler obviously finds trivial too. Function call overhead is
> the problem in the other versions, In mine two function calls, and as
> you point out dependent on the property parameter in Calums. IOW in the
> quest for speed function pointers are out. The code following is IMO
> equivalent to Op's code and seems to run as fast as OP's code. It does
> regards
> Andy Little
Hi Andy,
Your answer made me wonder if the function pointer dereferencing
can be eliminated if the contents of the function pointer vector
is constant, and the pointed-to functions are all inline.
Consequently,
I've uploaded little.switch.cpp to http://boost-consulting.com/vault/
under 'Template Metaprogramming'. It compiles with my gcc (3.3.5)
but not my intel (8.1). Any compiler experts know of any compilers
that do this?
Le Chaud Lapin
> Yes, but there are nearly 100 different properties that are possible
> across all objects, and I want my code to be able to generically
> attempt to access any property from any value, even though, in the
> current design, every object type only requires a small subset of the
> total available property types.
I started a thread in comp.lang.c++.moderated a while back about using
prime numbers for taxonomic indication. I have not had time to
evaluate this idea thoroughly, but if each combination of properties
includes only a few primitive properties, as in your case, then this
technique might be what you need.
With the prime number method, you encode each simple property as a
prime number, then synthesize complex properties from the simple
properties using enum's and multiplication, hoping to pack all
properties in a typical, 4-byte word. You check if a property includes
a simple propery using the % operator. If you multiply the prime
numbers from 2-29, inclusive, you stay under 2^32 (31 causes overflow).
That gives you 10 prime numbers to work with. However, there are well
over 100,000,000 primes less than 2^32. See Pi(x) function.
Even though I haven't done a thorough evaluation, I have been using
this technique for several months now for a very large "mostly defined"
taxonomy and it "feels ok". The only sugguestion I have is that you
leave out one of the lower prime numbers for safety, and use the number
1 to represent your equivalent of "thing", because everything is a
thing, and it is very convenient to be able to write ((x % THING) == 0)
to see anything is a thing.
Red_Black::Associative_Set<unsigned long int, unsigned long int> as;
enum {INGESTIBLE = 2, LIQUID = 5, EXPLOSIVE = 7, CAUSTIC = 13, H2S04 =
CAUSTIC * LIQUID, GASOLINE = EXPLOSIVE * LIQUID, LEMONADE = INGESTIBLE
* LIQUID};
unsigned long int object_id;
if ((as.mapping(object_id) % INGESTIBLE) == 0)
; // The object is ingestible
-Le Chaud Lapin-
kwikius
wizo...@hotmail.com wrote:
> kwikius wrote:
> > your post. Also I wonder whether a design in which one 'object' may
> > have a sound property but no sound option and another a colour but no
> > sound option couldnt be improved...
> >
> How so? The real world is full of examples of objects, some of which
> have
> one particular set of properties, others of which have rather different
> properties.
> My example was actually that an object of type "sound" would not
> logically have
> a property 'color', whereas a car would. Of course, these aren't
> actual
> object types in my application, but there's no question that my
> application
> does need to deal with a large number of heterogenous objects for which
> there
> is no real need for every object to be capable of storing a value for
> every possible
> property type.
I find it difficult to see a good reason for listing a sound and a car
together in the same container. It sounds like your property lists have
complicated interdependencies. This suggests to me that they might
benefit from being grouped as different types of object. I would be
intrigued to know more details of the actual design you are talking
about. Perhaps then the above description would make more sense ;-)
> But yes, I know my solution is highly optimized, and most definitely
> worth it
> (your 2x was nothing compared to some of the results I was seeing - I
> had to
> seriously fine tune the map-based implementation to get it down to even
> a
> quarter of the speed and about 8 times the memory usage!).
> I just thought there might be a nicer alternative to the macros.
Hmm...you need to write a lot of macros? The functionality of object
is exposed in every function invoked on it? When you change, add or
remove an object you need to change every dependent function too?.
Though your code is certainly fastest it is also the least elegant,
most high maintenance and most error prone. Nevertheless its an
interesting optimisation. It highlights that compiler optimisation
can bridge the metaprogramming - runtime programming states. Maybe
there are ways to apply the method in a more elegant way.
regards
Andy Little
wizo...@hotmail.com
kwikius wrote:
> wizo...@hotmail.com wrote:
> > Of course, these aren't
> > actual
> > object types in my application, but there's no question that my
> > application
> > does need to deal with a large number of heterogenous objects for which
> > there
> > is no real need for every object to be capable of storing a value for
> > every possible
> > property type.
>
> I find it difficult to see a good reason for listing a sound and a car
> together in the same container.
True, but even the average graphics application has things like
circles, that have a radius , and rectangles, that don't, but might
have a "rounded corners" property instead.
> It sounds like your property lists have
> complicated interdependencies. This suggests to me that they might
> benefit from being grouped as different types of object.
Not really. In fact, relatively few of the properties are shared at
all. I just want the ability to be able to access the properties
efficiently via an integer id, mainly in order to simpifly
serialization and parts of the user interface. In particular, defining
new properties has to be as low-maintenance as possible. I don't want
to have to change all of the object class definition, the serialization
code, the UI and the program logic every time (which, in my experience,
is the usual requirement. And usually the UI changes are the most
involved!)
>I would be
> intrigued to know more details of the actual design you are talking
> about. Perhaps then the above description would make more sense ;-)
>
It may, but while not commercially confidential, I'd prefer not to
reveal any more about my application than necessary. And the actual
details would likely distract from the particular problem I was looking
for advice on.
> > I just thought there might be a nicer alternative to the macros.
>
> Hmm...you need to write a lot of macros?
Only the ones I described in the original post.
> The functionality of object
> is exposed in every function invoked on it?
Actually, the objects have no instrinsic "functionality". They either
represent particular items that are displayed to the user, and/or
represent a change in document state that affects how other objects are
displayed. In fact, the closest approximation is a word processing
application: a "word" might be one object, and a "paragraph formatting
tag" might another. The primary objects are actually converted into
secondary object types suitable for direct display and interaction with
the user as needed (e.g. a "word" object in its primary state has no
need for x/y coordinates, but once the text is all laid out, this
object is represented by a secondary object that does have these
coordinates.)
> When you change, add or
> remove an object you need to change every dependent function too?.
Um, no...changing adding or removing *objects* doesn't affect the code
at all...do you mean object *types* (classes)? Even then, this
wouldn't affect the definitions or most of the existing logic for the
current object types, but obviously in some cases, I might be adding a
new object type in order to allow additional fine tuning of how
existing object types should behave.
> Though your code is certainly fastest it is also the least elegant,
> most high maintenance and most error prone.
Now that I have all the macros in place, it's actually almost 0
maintenance.
As far as error prone, I don't see why - I have both compile-time and
run-time asserts to catch attempts to access properties on objects that
don't exist, or to pack more properties into any particular object type
than they is space for etc. etc.
> Nevertheless its an
> interesting optimisation. It highlights that compiler optimisation
> can bridge the metaprogramming - runtime programming states. Maybe
> there are ways to apply the method in a more elegant way.
>
That's what I was hoping for.
James Kanze
> kanze wrote:
[...]
> If I understand what you mean by "discriminate unions" then
> yes, I think that's basically the technique I'm using, except
> that it's using casts rather than unions, as I couldn't see
> any way to combine the declaring of the unions with the access
> - that is, I want one piece of code that simultaneously
> declares how each property is packed into each type of object,
> and generates the necessary code to access those properties.
Yes, I meant discriminate unions as a concept, not as an
implementation technique.
> With unions, I'd end up with
> struct sound_properties
> {
> int16_t pitch;
> uint16_t duration,
> uint16_t volume;
> };
> struct car_properties
> {
> uint16_t color;
> uint8_t cylinders;
> //etc.etc.
> };
> struct Object
> {
> int type;
> union properties
> {
> sound_properties sound;
> car_properties car;
> // etc. etc.
> };
> };
Sort of. Another possibility would be:
struct Base
{
int type ;
} ;
struct SoundProperties
{
int type ;
int16_t pitch ;
uint16_t duration ;
uint16_t volume ;
} ;
struct CarProperties
{
int type ;
uint16_t color ;
uint8_t cylinders ;
} ;
// ...
union UnknownObject
{
Base object ;
SoundProperties sound ;
CarProperties car ;
} ;
void
f( UnknownObject* pObj )
{
switch ( p->object.type ) {
case typeSound :
p->sound...
break ;
// ...
}
}
This is the motivation for allowing access to common initial
parts of structures in a union, regardless of which element it
really contains.
[...]
> Btw, it should be obvious, but the extra parameter to pass in
> the type is necessary to cause the compiler to optimize out
> the switch statement completely when both the object type and
> property are known at compile time. It would require full
> program analysis for a compiler to be smart enough to do it
> automatically based on the fact that the calling function
> could only have been called given a particular object type.
Of course, you're not likely to get the optimization unless the
function is inline anyway. But if you know the type, and it is
a compile time constant, then why not have a specialized
function for that type, and just call it directly?
--
James Kanze mailto: james...@free.fr
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 pl. Pierre Sémard, 78210 St.-Cyr-l'École, France +33 (0)1 30 23 00 34
Larry
[snip]
Or, derive each of the struct XXXProperties from Base and just
use:
union UnknownObject
{
SoundProperties sound ;
CarProperties car ;
} ;
this is what Rafal wanted here:
http://groups.google.com/group/comp.std.c++/msg/8a90765a6e61ce82
the only difference being the virtual function instead of the
switch statement on the index (i.e. Base::type) of the
discriminated union.
BTW, an adaptation of the code mentioned in my previous post:
was used to accomplish Rafal's purpose, AFAICT. Also, a similar
adaptation could be used to accomplish wizofaus' purpose, although
at the cost of using function pointers instead of switch statements.
These adaptations would be part of the "policy_composite" proposed
here:
http://groups.google.com/group/comp.std.c++/msg/27e41e693228c6c7
, but which didn't elicit any interest :( Is there still no
interest in a "policy_composite"?
>
>> Btw, it should be obvious, but the extra parameter to pass in
>> the type is necessary to cause the compiler to optimize out
>> the switch statement completely when both the object type and
>> property are known at compile time. It would require full
>> program analysis for a compiler to be smart enough to do it
>> automatically based on the fact that the calling function
>> could only have been called given a particular object type.
>
>
>
> Of course, you're not likely to get the optimization unless the
> function is inline anyway. But if you know the type, and it is
> a compile time constant, then why not have a specialized
> function for that type, and just call it directly?
>
Which "sortof" answers the question posed here:
http://groups.google.com/group/comp.lang.c++.moderated/msg/b97b8b7cb59739a6
about whether a static vector of const pointers to functions, indexed
by a runtime value would be as fast as a switch statement.
More specifically, there's the 'int type' index into the:
'discriminated_union_function_vector'
our_rec_vec
;
and the 'int prop' index into the
'cartesion_product_function_vector'
dispatcher_rec<rid_two>::our_prp_vec
;
, where, obviously, the single quoted identifiers are descriptive
rather that actual identifiers in the code.
IOW. current compiler's probably wouldn't generate code from the
function pointer version of the code vs. the switch statement
version of the code :( . I can't help think that it's possible
though I remeber hearing that some compilers translate switch
statments into an index into a vector of jumps, or something
like that, and it seems something similar could be done
with a vector of pointers to inline functions.
kwikius
Larry wrote:
> Your answer made me wonder if the function pointer dereferencing
> can be eliminated if the contents of the function pointer vector
> is constant, and the pointed-to functions are all inline.
> Consequently,
> I've uploaded little.switch.cpp to http://boost-consulting.com/vault/
> under 'Template Metaprogramming'. It compiles with my gcc (3.3.5)
> but not my intel (8.1). Any compiler experts know of any compilers
> that do this?
Hi . I added your code into my tests and It seemed to do quite well. It
came out 2nd fastest, so it appears that there is some optimisation
going on. I'll post the code and results when I have time.
regards
Andy L:ittle
wizo...@hotmail.com
> wizo...@hotmail.com wrote:
>
> > Btw, it should be obvious, but the extra parameter to pass in
> > the type is necessary to cause the compiler to optimize out
> > the switch statement completely when both the object type and
> > property are known at compile time. It would require full
> > program analysis for a compiler to be smart enough to do it
> > automatically based on the fact that the calling function
> > could only have been called given a particular object type.
>
> Of course, you're not likely to get the optimization unless the
> function is inline anyway. But if you know the type, and it is
> a compile time constant, then why not have a specialized
> function for that type, and just call it directly?
>
type/property type combination that it was worth the optimization for
(which could be 100's).
I could just access the internal struct/union member directly, but I
want to be able to change the implementation easily without breaking
the code that uses the objects. The current implementation makes sense
now, but in 5 or 10 years time when compilers and/or computers are that
much more powerful, it may not be worth the hassle.
And surely having a consistent interface regardless of object type
and/or property type counts for something!
Anyway, other than having to define a whole bunch of macros, I'm really
quite happy with the current solution. Maybe the BOOST preprocessor
library would be able to give me a way of defining a whole bunch of
similar macros with variable numbers of parameters, but I couldn't get
it working unver VC 7.1 after a brief play.
Larry
> Larry wrote:
[snip]
>> I've uploaded little.switch.cpp to http://boost-consulting.com/vault/
>> under 'Template Metaprogramming'. It compiles with my gcc (3.3.5)
[snip]
> Hi . I added your code into my tests and It seemed to do quite well. It
> came out 2nd fastest, so it appears that there is some optimisation
> going on. I'll post the code and results when I have time.
Great! I've replaced that vault file with little.funvec_.zip. That
zip contains a reformatting and rename of little.switch.cpp to
little.funvec_constcvec.cpp. In addition, the file,
little.funvec_foreach.cpp is "essentially" the same except it used
mpl::for_each to fill the vector of function pointers instead
of the simpler "const c vector" (hence the suffix) method of
initializing the pointers. The foreach method, I believe, makes it
easier to add methods, but probably slows down execution since the
compiler probably can't see that it's doing essentially the
same thing as in the constcvec method.
I'd hope to write a benchmark somewhat like yours, but haven't gotten
around to it. I also had ambitions to write a boost pp version
to emulate the OP code, but not yet.
-regards,
Larry
kwikius
Larry wrote:
> I'd hope to write a benchmark somewhat like yours, but haven't gotten
> around to it. I also had ambitions to write a boost pp version
> to emulate the OP code, but not yet.
FWIW I posted the latest version of the test(I havent incorporated your
latest code). Again please dont take it too seriously, except in this
version I loaded the data from file to suppress some optimisations. (to
run the test for the first time needs the data file. uncomment the
save_data function in main to write that file).
http://www.servocomm.freeserve.co.uk/Cpp/template_quest/
Here are some timings. In the unoptimised case I dont think there is in
reality much to choose so I selected the one that put me first ;-) ,
which just goes to show that you should be very careful with these
statistics. To do this seriously I would recommend doing your own
tests). I also suspect that the order the tests are done in affects the
result. The first in the programme seems to get an advantage. In the
optimised case there is in reality no difference in timing between the
top two
unoptimised VC7.1
1. test4() (Andy Little 2) time = 2.109
2. test2() (Andy Little) time = 2.27
3. test5() (Larry) time = 2.311
4. test3() (Calum Grant) time = 2.327
5. test1() (Wizof) time = 2.343
optimised VC7.1 /O2
1 test4() time = Andy Little 2 time = 0.234
2 test1() time = Wizof time = 0.235
3 test5() time = Larry time = 0.313
4 test3() time = Calum Grant time = 0.359
5 test2() time = Andy Little time = 0.437
regards
Andy Little
Larry
[snip]
> Anyway, other than having to define a whole bunch of macros, I'm really
> quite happy with the current solution. Maybe the BOOST preprocessor
> library would be able to give me a way of defining a whole bunch of
> similar macros with variable numbers of parameters, but I couldn't get
> it working unver VC 7.1 after a brief play.
I took more than a "brief play" (and I wouldn't call it play ;) ) at
using BOOST preprocessor. The results are in:
http://boost-consulting.com/vault
/Template Metaprogramming/PP_RECFLD.zip
All the objects and properties are specified with something like:
#define objects ( Sound )( Car )
#define properties_Sound \
(( type_i<0>, propPitch ))\
(( type_i<1>, propDuration ))\
(( type_i<2>, propVolume ))\
/**/
#define properties_Car \
(( type_i<3>, propColor )) \
(( type_i<4>, propCylinders )) \
(( type_i<5>, propDoors )) \
(( type_i<6>, propEngineSize)) \
/**/
IOW, for each element, E, in objects, there's a sequence, properties_E,
which defines the structure for E. The reason for type_i<X> instead of
something like uint16 is explained in code.