Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > Providing a no-overhead way for a contained class to access its container?

Reply
Thread Tools

Providing a no-overhead way for a contained class to access its container?

 
 
Jerry Coffin
Guest
Posts: n/a
 
      06-17-2008
In article <293706b4-cbee-4cc0-bbe2-0b2c6ba42191
@z72g2000hsb.googlegroups.com>, http://www.velocityreviews.com/forums/(E-Mail Removed) says...

[ ... ]

> What about the case where the contained class must store its data in
> its container?


I'm afraid I don't understand what you're asking.

--
Later,
Jerry.

The universe is a figment of its own imagination.
 
Reply With Quote
 
 
 
 
Puppet_Sock
Guest
Posts: n/a
 
      06-17-2008
On Jun 17, 8:30*am, PeteOlcott <(E-Mail Removed)> wrote:
[snips]
> What about the case where the contained class must store its data in
> its container?


It's not even a little clear what you mean.

Do you mean: The objects in the container stick copies
of themselves into the same container? If so, then you
have a pathological design that should be refactored.

Do you mean: Actual copies of the objects are stored in
the container, as opposed to pointers to the objects?
If that's the issue, and you are concerned about such
things as excess effort involved in swapping copies
instead of pointers, there are many ways of proceeding.

Or do you mean something else?
Socks
 
Reply With Quote
 
 
 
 
PeteOlcott
Guest
Posts: n/a
 
      06-17-2008
On Jun 17, 9:45*am, Puppet_Sock <(E-Mail Removed)> wrote:
> On Jun 17, 8:30*am, PeteOlcott <(E-Mail Removed)> wrote:
> [snips]
>
> > What about the case where the contained class must store its data in
> > its container?

>
> It's not even a little clear what you mean.
>
> Do you mean: The objects in the container stick copies
> of themselves into the same container? If so, then you
> have a pathological design that should be refactored.
>
> Do you mean: Actual copies of the objects are stored in
> the container, as opposed to pointers to the objects?
> If that's the issue, and you are concerned about such
> things as excess effort involved in swapping copies
> instead of pointers, there are many ways of proceeding.
>
> Or do you mean something else?
> Socks


Here is what I mean. For this specific use it is about the highest
performance (space and time) possible. A Large number of Contained
elements can be read in and written to disk as a single block read or
block write. Also all of the extra memory allocation overhead that
would normally be associated with the individual Contained elements
has been reduced to making two large allocations.

#define uint8 unsigned char
#define uint32 unsigned int


ContainedClass {
uint32 Offset;
bool operator<(const ContainedClass& CC);
}


ContainerClass {
uint32 Length; // All ContainedClass elements are the same Length
std::vector<uint8> Bytes;
std::vector<ContainedClass> Contained;
uint8& operator[](uint32 N){ return Bytes[N]; };
void sort(){ std::sort(Contained.begin(), Contained.end()) };
} Container;


bool ContainedClass:perator<(const ContainedClass& CC)
{
uint32 Last = this->Offset + Container.Length;
for (int N = this->Offset, M = CC.Offset; N < Last; N++, M++)
if (Container[N] < Container[M])
return true;
else if (Container[N] > Container[M])
return false;
return false; // They must be Equal, thus Not(LessThan)
}
 
Reply With Quote
 
Puppet_Sock
Guest
Posts: n/a
 
      06-17-2008
On Jun 17, 2:03*pm, PeteOlcott <(E-Mail Removed)> wrote:
> On Jun 17, 9:45*am, Puppet_Sock <(E-Mail Removed)> wrote:
>
> > On Jun 17, 8:30*am, PeteOlcott <(E-Mail Removed)> wrote:
> > [snips]

>
> > > What about the case where the contained class must store its data in
> > > its container?

>
> > It's not even a little clear what you mean.

>
> > Do you mean: The objects in the container stick copies
> > of themselves into the same container? If so, then you
> > have a pathological design that should be refactored.

>
> > Do you mean: Actual copies of the objects are stored in
> > the container, as opposed to pointers to the objects?
> > If that's the issue, and you are concerned about such
> > things as excess effort involved in swapping copies
> > instead of pointers, there are many ways of proceeding.

>
> > Or do you mean something else?
> > Socks

>
> Here is what I mean. For this specific use it is about the highest
> performance (space and time) possible. A Large number of Contained
> elements can be read in and written to disk as a single block read or
> block write. Also all of the extra memory allocation overhead that
> would normally be associated with the individual Contained elements
> has been reduced to making two large allocations.


Ok, I have to say your response had a lot of words in it,
but didn't come near to answering the question. And, after
nearly 30 posts in this thread, we finally illicit some
part of the actual spec. You seem to be talking about
writing stuff to disk, and reading it back, in an efficient
manner, when you have a bunch of objects stored in a
container class of some kind.

> #define uint8 *unsigned char
> #define uint32 unsigned int
>
> ContainedClass {
> * uint32 Offset;
> * bool operator<(const ContainedClass& CC);
>
> }
>
> ContainerClass {
> * *uint32 Length; *// All ContainedClass elements are the same Length
> * *std::vector<uint8> Bytes;
> * *std::vector<ContainedClass> Contained;
> * *uint8& operator[](uint32 N){ return Bytes[N]; };
> * *void sort(){ std::sort(Contained.begin(), Contained.end()) };
>
> } Container;
>
> bool ContainedClass:perator<(const ContainedClass& CC)
> {
> * uint32 Last = this->Offset + Container.Length;
> * for (int N = this->Offset, M = CC.Offset; N < Last; N++, M++)
> * * if (Container[N] < Container[M])
> * * * return true;
> * * else if (Container[N] > Container[M])
> * * * return false;
> return false; *// They must be Equal, thus Not(LessThan)
>
>
> }


Though your sample code does not seem to be related to the
issue of reading from or writing to disk. Plus, what you
posted sure won't compile.

If what you want to do is an efficient read/write of a large
block of data, there are a variety of approaches. None of
them need the object to know it is contained in a container.

Is that what you are on about? Storing and reading back
a std container of objects?
Socks
 
Reply With Quote
 
Peter Olcott
Guest
Posts: n/a
 
      06-18-2008

"Chris Thomasson" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed). ..
>
> "Peter Olcott" <(E-Mail Removed)> wrote in message
> news:Gpc5k.2412$(E-Mail Removed)...
> [...]
>>
>> I have a solution that allows the existence of multiple
>> instances of the container class, the number of such
>> instances can be specified at run-time. These multiple
>> instances would be stored in a single global
>> std::vector<ContainerClass>. Another single instance
>> global integer would be used as the current subscript
>> into this std::vector<ContainerClass>, specifying which
>> ContainerClass is being used. There would be no extra
>> overhead in the use of either the ContainerClass, nor its
>> ContainedClass.

>
> Your diverting the overhead to another area. In order for
> a `ContainedClass' to get at its `ContainerClass' it needs
> to look-up the index of the `ContainerClass' in order to
> perform a lookup in the global vector. This has a cost
> associates with it. AFAICT, your claim that its somehow
> "zero-overhead" is not entirely true. BTW, give some
> pseudo-code to demonstrate your current solution. I am
> probably missing something here... So your saying that you
> have something like:
>
>
> Lets assume that your `ContainerClass' is a `std::list',
> and your `ContainedClass' is a `short'.
>
>
> typedef short ContainedClass;
> typedef std::list<ContainedClass> ContainerClass;
>
>
> You say that your keeping a global container of said
> `ContainerClass':
>
>
> static std::vector<ContainerClass> g_containers;
>
>
> and a global integer:
>
>
> static int g_index = 0;
>
>
>
> How do you dynamically add new `ContainedClass' objects to
> new `ContainerClass' objects? Where am I going wrong?

I said there is no extra cost for the contained class to
access its container, there might be a very slight extra
cost to change from one container to another. In the case of
my actual implementation there is not even this extra cost
because I only need a single container.


 
Reply With Quote
 
PeteOlcott
Guest
Posts: n/a
 
      06-18-2008
On Jun 17, 2:43*pm, Puppet_Sock <(E-Mail Removed)> wrote:
> On Jun 17, 2:03*pm, PeteOlcott <(E-Mail Removed)> wrote:
>
>
>
>
>
> > On Jun 17, 9:45*am, Puppet_Sock <(E-Mail Removed)> wrote:

>
> > > On Jun 17, 8:30*am, PeteOlcott <(E-Mail Removed)> wrote:
> > > [snips]

>
> > > > What about the case where the contained class must store its data in
> > > > its container?

>
> > > It's not even a little clear what you mean.

>
> > > Do you mean: The objects in the container stick copies
> > > of themselves into the same container? If so, then you
> > > have a pathological design that should be refactored.

>
> > > Do you mean: Actual copies of the objects are stored in
> > > the container, as opposed to pointers to the objects?
> > > If that's the issue, and you are concerned about such
> > > things as excess effort involved in swapping copies
> > > instead of pointers, there are many ways of proceeding.

>
> > > Or do you mean something else?
> > > Socks

>
> > Here is what I mean. For this specific use it is about the highest
> > performance (space and time) possible. A Large number of Contained
> > elements can be read in and written to disk as a single block read or
> > block write. Also all of the extra memory allocation overhead that
> > would normally be associated with the individual Contained elements
> > has been reduced to making two large allocations.

>
> Ok, I have to say your response had a lot of words in it,
> but didn't come near to answering the question. And, after
> nearly 30 posts in this thread, we finally illicit some
> part of the actual spec. You seem to be talking about
> writing stuff to disk, and reading it back, in an efficient
> manner, when you have a bunch of objects stored in a
> container class of some kind.
>
>
>
>
>
> > #define uint8 *unsigned char
> > #define uint32 unsigned int

>
> > ContainedClass {
> > * uint32 Offset;
> > * bool operator<(const ContainedClass& CC);

>
> > }

>
> > ContainerClass {
> > * *uint32 Length; *// All ContainedClass elements are the same Length
> > * *std::vector<uint8> Bytes;
> > * *std::vector<ContainedClass> Contained;
> > * *uint8& operator[](uint32 N){ return Bytes[N]; };
> > * *void sort(){ std::sort(Contained.begin(), Contained.end()) };

>
> > } Container;

>
> > bool ContainedClass:perator<(const ContainedClass& CC)
> > {
> > * uint32 Last = this->Offset + Container.Length;
> > * for (int N = this->Offset, M = CC.Offset; N < Last; N++, M++)
> > * * if (Container[N] < Container[M])
> > * * * return true;
> > * * else if (Container[N] > Container[M])
> > * * * return false;
> > return false; *// They must be Equal, thus Not(LessThan)

>
> > }

>
> Though your sample code does not seem to be related to the
> issue of reading from or writing to disk. Plus, what you
> posted sure won't compile.
>
> If what you want to do is an efficient read/write of a large
> block of data, there are a variety of approaches. None of
> them need the object to know it is contained in a container.
>
> Is that what you are on about? Storing and reading back
> a std container of objects?
> Socks- Hide quoted text -
>
> - Show quoted text -- Hide quoted text -
>
> - Show quoted text -


Think about it as storage, retrieval, allocation, access, and
manipulation of strings such that the space and time requirements are
at the current edge of hardware capability. Multiple GB of data stored
in RAM and retrieved from disk. A slight modification to the provided
code, and these strings could vary in length.
 
Reply With Quote
 
Thomas J. Gritzan
Guest
Posts: n/a
 
      06-18-2008
PeteOlcott schrieb:
> Here is what I mean. For this specific use it is about the highest
> performance (space and time) possible. A Large number of Contained
> elements can be read in and written to disk as a single block read or
> block write. Also all of the extra memory allocation overhead that
> would normally be associated with the individual Contained elements
> has been reduced to making two large allocations.
>
> #define uint8 unsigned char
> #define uint32 unsigned int


typedef unsigned char uint8;
typedef unsigned int uint32;

>
>
> ContainedClass {
> uint32 Offset;
> bool operator<(const ContainedClass& CC);
> }
>
>
> ContainerClass {
> uint32 Length; // All ContainedClass elements are the same Length
> std::vector<uint8> Bytes;
> std::vector<ContainedClass> Contained;
> uint8& operator[](uint32 N){ return Bytes[N]; };
> void sort(){ std::sort(Contained.begin(), Contained.end()) };
> } Container;


This code doesn't compile, but assuming a working version of this code,
you could use std::sort with a functor with a pointer to its contained
class (untested! code):

struct ContainedLess
{
ContainedLess(const ContainerClass* container_) :
container(container_) {}

bool operator()(const ContainedClass& c1, const ContainedClass& c2)
const
{
// compare c1 and c2, use member 'container'
// to access container class
const uint8* p1 = &container->Bytes[c1.Offset];
const uint8* p2 = &container->Bytes[c2.Offset];
const uint8* end = p1 + container->Length;
for (; p1 != end; ++p1, ++p2)
{
// ...
}
}

private:
const ContainerClass* container;
};

void ContainerClass::sort()
{
std::sort(Contained.begin(), Contained.end(), ContainedLess(this));
}

It also would be a good idea to make some members of the classes private.

>
>
> bool ContainedClass:perator<(const ContainedClass& CC)
> {
> uint32 Last = this->Offset + Container.Length;
> for (int N = this->Offset, M = CC.Offset; N < Last; N++, M++)
> if (Container[N] < Container[M])
> return true;
> else if (Container[N] > Container[M])
> return false;
> return false; // They must be Equal, thus Not(LessThan)
> }


--
Thomas
 
Reply With Quote
 
Peter Olcott
Guest
Posts: n/a
 
      06-19-2008

"Thomas J. Gritzan" <(E-Mail Removed)> wrote in
message news:g3bvrg$qn9$(E-Mail Removed)...
> PeteOlcott schrieb:
>> Here is what I mean. For this specific use it is about
>> the highest
>> performance (space and time) possible. A Large number of
>> Contained
>> elements can be read in and written to disk as a single
>> block read or
>> block write. Also all of the extra memory allocation
>> overhead that
>> would normally be associated with the individual
>> Contained elements
>> has been reduced to making two large allocations.
>>
>> #define uint8 unsigned char
>> #define uint32 unsigned int

>
> typedef unsigned char uint8;
> typedef unsigned int uint32;
>
>>
>>
>> ContainedClass {
>> uint32 Offset;
>> bool operator<(const ContainedClass& CC);
>> }
>>
>>
>> ContainerClass {
>> uint32 Length; // All ContainedClass elements are the
>> same Length
>> std::vector<uint8> Bytes;
>> std::vector<ContainedClass> Contained;
>> uint8& operator[](uint32 N){ return Bytes[N]; };
>> void sort(){ std::sort(Contained.begin(),
>> Contained.end()) };
>> } Container;

>
> This code doesn't compile, but assuming a working version
> of this code, you could use std::sort with a functor with
> a pointer to its contained class (untested! code):
>
> struct ContainedLess
> {
> ContainedLess(const ContainerClass* container_) :
> container(container_) {}
>
> bool operator()(const ContainedClass& c1, const
> ContainedClass& c2) const
> {
> // compare c1 and c2, use member 'container'
> // to access container class
> const uint8* p1 = &container->Bytes[c1.Offset];
> const uint8* p2 = &container->Bytes[c2.Offset]; const
> uint8* end = p1 + container->Length;
> for (; p1 != end; ++p1, ++p2)
> {
> // ...
> }
> }
>
> private:
> const ContainerClass* container;
> };
>
> void ContainerClass::sort()
> {
> std::sort(Contained.begin(), Contained.end(),
> ContainedLess(this));
> }
>
> It also would be a good idea to make some members of the
> classes private.


That would be the first attempt at actually answering my
original question. I was guessing that the answer might have
something to do with functors. The solution does look pretty
clean, far cleaner than the solution that I derived.

My only question would be whether or not it avoided the
overhead of initializing the pointer to the container upon
every comparison. I would estimate that you would already
know this answer, knowing more clearly the underlying
semantics of the syntax that you specified.

>
>>
>>
>> bool ContainedClass:perator<(const ContainedClass& CC)
>> {
>> uint32 Last = this->Offset + Container.Length;
>> for (int N = this->Offset, M = CC.Offset; N < Last;
>> N++, M++)
>> if (Container[N] < Container[M])
>> return true;
>> else if (Container[N] > Container[M])
>> return false;
>> return false; // They must be Equal, thus Not(LessThan)
>> }

>
> --
> Thomas



 
Reply With Quote
 
PeteOlcott
Guest
Posts: n/a
 
      06-19-2008
On Jun 19, 4:11*am, (E-Mail Removed) (Yannick Tremblay) wrote:
> In article <(E-Mail Removed)>,
>
>
>
>
>
> PeteOlcott *<(E-Mail Removed)> wrote:
> >On Jun 16, 8:27*am, (E-Mail Removed) (Yannick Tremblay) wrote:
> >> In article <QWg5k.5453$(E-Mail Removed)>,
> >> Sorry but you are lying to yourself:
> >> - having globals is overhead. *
> >> - having single instance globals is overhead
> >> - having a global container is overhead.
> >> - having a global container of containers is overhead (vector<ContainerClass>)
> >> - having a global integer that is used as index into a vecotr is
> >> overhead, you need to call vector.at(global_int). *That is not free.

>
> >> So that reduces your statement to: "I have a solution that has no
> >> overhead that I don't ignore nor any that I am not unaware of."

>
> >> Yannick- Hide quoted text -

>
> >> - Show quoted text -

>
> > *http://en.wikipedia.org/wiki/Computational_overhead
> >Overhead is only the EXTRA cost over-and-above providing the basic
> >functionality.

>
> That's correct
>
> >My solution (although clumsy) has no EXTRA cost over and above the
> >normal cost of one class accessing another class.

>
> That's incorrect. *
>
> First, one would need to define "cost". *Typical in software are
> memory, execution and development. *Most of the time, the correct
> solution is a compromise between the three. * Even looking purely at
> memory cost, the optimal solution would depend on lifetime of the
> objects and the way they are used. *For two short lived objects a
> pointer to the other would be the optimal memory minimising solution.
>
> >The most typical solution would require that a pointer to the
> >container be passed to the contained class. This typical solution does
> >require an EXTRA cost over-and-above the basic cost of one class
> >accessing another class. The pointer takes memory, and it must also be
> >copied.

>
> I am sorry but you are ignoring your overhead.
>
> Case 1 that you classify as overhead:
>
> A pointer to the container is passed to the contained class.
> - Memory overhead: 1 pointer per contained object
> Note that this memory overhead only exist for the lifetime of the
> contained object.
> - Access overhead: Access contained pointer and dereference it
>
> Case 2: What you classify as no overhead
>
> a global container of containers of class with global integer
> - Memory overhead: the global container of containers and a global integer *
> These exist for the lifetime of the program. *The global std::vector
> will only ever grow unless you use the swap idiom to shrink it at
> appropriate time. *If you do, then there a computation overhead for
> doing so. *The global integer is also memory overhead.
> - Access overhead: Access the global container, access the global
> integer, call global container.at(global integer), access the
> contained class. *Much more expensive than dereferencing a "pointer to
> parent". *
> - Development overhead: it is generally agreed that global introduce
> development risk and maintenance overhead over well encapsulated
> solutions. *IME, generally speaking, a solution using globals is quick
> and efficient (from a development point of view) for a simple problem
> but as the scope of the problem grows, globals become a liability.
> Regardless of the scope of the problem, globals tend to be a
> maintenance liability.
>
> Look, I am not saying that your solution is wrong. *I am saying that
> it is wrong to ignore the costs of your solution and only highlight
> the memory cost of the pointer-to-parent solution. *In fact, both
> approaches have pros and cons. *One needs to fairly evaluate them in
> order to make the correct choice.
>
> Yannick- Hide quoted text -
>
> - Show quoted text -


My basic singleton solution has no extra cost over-and-above the cost
of one class accessing another, because this solution IS simply one
class accessing another using the typical ways for one class to access
another.
 
Reply With Quote
 
PeteOlcott
Guest
Posts: n/a
 
      06-19-2008
On Jun 19, 4:11*am, (E-Mail Removed) (Yannick Tremblay) wrote:
> In article <(E-Mail Removed)>,
>
>
>
>
>
> PeteOlcott *<(E-Mail Removed)> wrote:
> >On Jun 16, 8:27*am, (E-Mail Removed) (Yannick Tremblay) wrote:
> >> In article <QWg5k.5453$(E-Mail Removed)>,
> >> Sorry but you are lying to yourself:
> >> - having globals is overhead. *
> >> - having single instance globals is overhead
> >> - having a global container is overhead.
> >> - having a global container of containers is overhead (vector<ContainerClass>)
> >> - having a global integer that is used as index into a vecotr is
> >> overhead, you need to call vector.at(global_int). *That is not free.

>
> >> So that reduces your statement to: "I have a solution that has no
> >> overhead that I don't ignore nor any that I am not unaware of."

>
> >> Yannick- Hide quoted text -

>
> >> - Show quoted text -

>
> > *http://en.wikipedia.org/wiki/Computational_overhead
> >Overhead is only the EXTRA cost over-and-above providing the basic
> >functionality.

>
> That's correct
>
> >My solution (although clumsy) has no EXTRA cost over and above the
> >normal cost of one class accessing another class.

>
> That's incorrect. *
>
> First, one would need to define "cost". *Typical in software are
> memory, execution and development. *Most of the time, the correct
> solution is a compromise between the three. * Even looking purely at
> memory cost, the optimal solution would depend on lifetime of the
> objects and the way they are used. *For two short lived objects a
> pointer to the other would be the optimal memory minimising solution.
>
> >The most typical solution would require that a pointer to the
> >container be passed to the contained class. This typical solution does
> >require an EXTRA cost over-and-above the basic cost of one class
> >accessing another class. The pointer takes memory, and it must also be
> >copied.

>
> I am sorry but you are ignoring your overhead.
>
> Case 1 that you classify as overhead:
>
> A pointer to the container is passed to the contained class.
> - Memory overhead: 1 pointer per contained object
> Note that this memory overhead only exist for the lifetime of the
> contained object.
> - Access overhead: Access contained pointer and dereference it
>
> Case 2: What you classify as no overhead
>
> a global container of containers of class with global integer
> - Memory overhead: the global container of containers and a global integer *
> These exist for the lifetime of the program. *The global std::vector
> will only ever grow unless you use the swap idiom to shrink it at
> appropriate time. *If you do, then there a computation overhead for
> doing so. *The global integer is also memory overhead.
> - Access overhead: Access the global container, access the global
> integer, call global container.at(global integer), access the
> contained class. *Much more expensive than dereferencing a "pointer to
> parent". *
> - Development overhead: it is generally agreed that global introduce
> development risk and maintenance overhead over well encapsulated
> solutions. *IME, generally speaking, a solution using globals is quick
> and efficient (from a development point of view) for a simple problem
> but as the scope of the problem grows, globals become a liability.
> Regardless of the scope of the problem, globals tend to be a
> maintenance liability.
>
> Look, I am not saying that your solution is wrong. *I am saying that
> it is wrong to ignore the costs of your solution and only highlight
> the memory cost of the pointer-to-parent solution. *In fact, both
> approaches have pros and cons. *One needs to fairly evaluate them in
> order to make the correct choice.
>
> Yannick- Hide quoted text -
>
> - Show quoted text -


Also my solution for multiple instances of ContainerClasses providing
access to themselves to their ContainedClasses has no additional space
or time cost involved in the specific instance of this provided
access. There is a slight additional space and time cost in providing
multiple instances of the ContainerClass, but, this additional cost
does not directly pertain to providing this access. Instead this
additional cost only pertains to the provision of multiple instances
of the ContainerClass. The singleton case of this ContainerClass has
no additional costs of any kind what-so-ever.
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
"An attempt was made to access a socket in a way forbidden by its access permissions" exiter Computer Support 3 02-27-2012 08:36 PM
Its a bird, its a plane, its.. um, an Attribute based System? thunk Ruby 14 04-03-2010 10:08 AM
Its a bird, its a plane, its.. um, an Attribute based System? thunk Ruby 0 04-01-2010 10:25 PM
Its a bird, its a plane, no ummm, its a Ruide thunk Ruby 1 03-30-2010 11:10 AM
Providing services for 802.11b and 802.11g on the cisco 1200 access points Chris Davies Cisco 6 06-15-2004 01:42 PM



Advertisments