Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > Zero-size array as struct member

Reply
Thread Tools

Zero-size array as struct member

 
 
Öö Tiib
Guest
Posts: n/a
 
      08-24-2010
On Aug 24, 11:35*am, Bart van Ingen Schenau <(E-Mail Removed)>
wrote:
> On Aug 22, 10:53*am, Kai-Uwe Bux <(E-Mail Removed)> wrote:
>
>
>
> > Now, you made me curious. Could you present an example? I would try to
> > rewrite that without performance penalty in a "hack free" manner. The
> > reasong is: I have a hard time imagining a use for the struct hack in C++
> > such that doing the same thing in a more idiomatic way comes with a
> > performance hit. On the other hand, I know that sometimes my imagination is
> > just lacking.

>
> > Best

>
> > Kai-Uwe Bux

>
> Here is an example where the struct-hack is extensively used in a real
> production environment.
>
> The system in question uses a message-passing mechanism to communicate
> with both internal and external entities.
> The basic message structure looks like this:
>
> typedef struct
> {
> * * unsigned char *media;
> * * unsigned char *receiver_dev;
> * * unsigned char *sender_dev;
> * * unsigned char *function;
> * * unsigned char *len[2];
> * * unsigned char *receiver_obj;
> * * unsigned char *sender_obj;
> * * unsigned char *data[1];
>
> } MESSAGE_T;
>
> The payload of the message, which is contained in the data array, is
> typically between 4 and 16 bytes, but can be as much as 4000 bytes.
> As said, these messages can be sent both to internal destinations
> (sender_dev == received_dev) and to external devices using a variety
> of (serial) communication mechanisms.


Sent over serial? In C++ i would have "std::vector<uint8_t> message_"
buried into some Message class and done.
 
Reply With Quote
 
 
 
 
joe
Guest
Posts: n/a
 
      08-25-2010
Juha Nieminen wrote:
> joe <(E-Mail Removed)> wrote:
>> I don't think performance is the issue at all with this
>> apples-to-oranges comparison of std::vector and the struct hack:

>
> Exactly how is it an "apples-to-oranges comparison"? The two
> techniques are achieving the same thing: A struct instantiation which
> contains an array whose size is decided at runtime (rather than at
> compile time).
> The difference between them is that the struct hack achieves this with
> one single allocation per struct instance, while the "cleaner" method
> requires two allocations per struct instance (one for the struct
> itself and another for the vector).


Apples and oranges. One is contiguous and one is not. You're "turning it
inside out": performance comes as a side effect of the contiguity and the
contiguity is the important part of the technique, not the side effect.

>
> Performance will not be an issue if you need to allocate just a few
> instances of the struct. However, it can become an issue if you need
> to allocate millions of instances.
>
>> it's contiguity of the
>> var-len array with the other members of the struct that is the
>> reason for the struct hack's usefulness and popularity.

>
> That may be so, but you can't dismiss the efficiency benefit in cases
> where huge amounts of instantiations need to be done.
>
>> std::vector is a very specialized container

>
> Why are people here so obsessed about the specifics of std::vector
> here? It's only being used here as a substitute for a raw array. In
> terms of efficiency it doesn't make any difference compared to one.
> It's just easier to use.
>
>> Note that the OP
>> had the var-len array as a part of another struct. This isn't about
>> "array containers".

>
> There seems to be some kind of failure at communication here.
>
> I am not talking about the efficiency of allocating an array. I am
> talking *precisely* about the efficiency of allocating a struct which
> has an array as the last member, comparing the struct hack to a more
> regular solution (which has a pointer or a std::vector as the last
> struct element).


I was just pointing out that I don't think that performance is hardly the
reason that the struct hack came to be. As such, I find the discussion
about performance tangential to the OP. Performance is, of course, the
proverbial low-hanging-fruit of discussion in programming groups. (I
think that's what prompted me to ask in another post what is more
worthwhile to know, "Big O" science or Assembly language. Obviously, I
think the latter).


 
Reply With Quote
 
 
 
 
joe
Guest
Posts: n/a
 
      08-25-2010
Juha Nieminen wrote:

struct Apple
> {
> // Some other member variables here.
> int size;
> int array[0];
> };



struct Orange
> {
> // Some other member variables here.
> std::vector<int> array;
>
> MyStruct(int size): array(size) {}
> };


That the performance is different is a non-issue at best or a clouding of
the purpose of the struct hack worst. I'd like to see C++ support the
technique better than using a one-element array, which of course is
syntactically hackish.



 
Reply With Quote
 
joe
Guest
Posts: n/a
 
      08-25-2010
Ian Collins wrote:

> The struct hack is a C idiom which is seldom used in C++.


It's definitely a missing piece in C++, but at least the hack still
works.

> In C++ we have other techniques.


Show me.


 
Reply With Quote
 
joe
Guest
Posts: n/a
 
      08-25-2010
Juha Nieminen wrote:

> The struct hack is
> about a struct which, besides any other members it may have, also has
> an array as its
> last element, the size of which is determined at runtime.
>


Which, of course is incorrect. At least it is lax or unknowing by only
giving one example usage (using dynamic mem with the struct hack) and
presenting it as a definition of the struct hack. Again though,
performance is hardly the point of the struct hack and std:vector is not
a substitute for the struct hack. C was right in standardizing it and C++
would do good to follow suit. While there are more issues to address in
developing an "alternative" to the struct hack in C++, they are not
unsurmountable I think.


 
Reply With Quote
 
joe
Guest
Posts: n/a
 
      08-25-2010
Kai-Uwe Bux wrote:
> Juha Nieminen wrote:
>
>> Kai-Uwe Bux <(E-Mail Removed)> wrote:
>>> Nothing. However, _why_ would you use a vector _member_ in the
>>> struct? The natural thing is to use a vector _instead_ of the
>>> struct. After all, the struct as it stands just serves the same
>>> purpose as a vector. It has no other members than the length and
>>> the array of elements.

>>
>> The struct in the examples is simplified for the sake of being an
>> example.
>> The struct can have (and often has) other members besides the size
>> of the array.
>>
>> The struct hack is not necessarily about making a struct which
>> acts as an
>> array which contains the size of the array. The struct hack is about
>> a struct which, besides any other members it may have, also has an
>> array as its last element, the size of which is determined at
>> runtime.
>>
>> But yes: If a C program is using the struct hack solely for the
>> same purpose as you would normally use std::vector (in other words,
>> the struct only contains the array size plus the array itself), then
>> std::vector would definitely be the better choice in the equivalent
>> C++ program.
>>
>> However, as said, the struct hack can be used for more than that.

>
> Now, you made me curious. Could you present an example? I would try to
> rewrite that without performance penalty in a "hack free" manner. The
> reasong is: I have a hard time imagining a use for the struct hack in
> C++ such that doing the same thing in a more idiomatic way comes with
> a performance hit. On the other hand, I know that sometimes my
> imagination is just lacking.


There is no alternative to the struct hack in C++. One has to use the
hack if one needs/wants the characteristics of it because C++ has not
formalized or accepted any form of the technique. A hole in the C++ spec
(or worse) if you ask me. I'm fine with using the one-element array
version of the technique, but I do feel like that is unnecessarily (for
lack of formal C++ recognition and support of the technique) hackish (but
not in comparison to how I use/abuse the preprocessor!).



 
Reply With Quote
 
joe
Guest
Posts: n/a
 
      08-25-2010
tni wrote:
> On 2010-08-22 10:53, Kai-Uwe Bux wrote:
>> Juha Nieminen wrote:
>>
>>> But yes: If a C program is using the struct hack solely for the
>>> same purpose as you would normally use std::vector (in other words,
>>> the struct only contains the array size plus the array itself),
>>> then std::vector would definitely be the better choice in the
>>> equivalent C++ program. However, as said, the struct hack can be used
>>> for more than that.

>>
>> Now, you made me curious. Could you present an example? I would try
>> to rewrite that without performance penalty in a "hack free" manner.
>> The reasong is: I have a hard time imagining a use for the struct
>> hack in C++ such that doing the same thing in a more idiomatic way
>> comes with a performance hit. On the other hand, I know that
>> sometimes my imagination is just lacking.

>
> How about this:
>
> #include <boost/intrusive/bs_set_hook.hpp>
> #include <boost/intrusive/treap.hpp>
>
> struct Message : public boost::intrusive::bs_set_base_hook<> {
> uint16_t priority;
> uint16_t length;
> uint8_t payload[];
> };
>
> // Message comparison for treap is based on payload
> boost::intrusive::treap<Message> mtreap;
>
> Let's assume, you have to use a treap-like data structure, but you are
> free to distribute the data any way you like. "bs_set_base_hook<>" is
> basically a set of 3 pointers (to other messages). Whenever you
> access a message, you typically use priority, length, payload and a
> random pointer from "bs_set_base_hook<>".
>
> The messages are small, lets say on average 16 bytes. Let's assume on
> a 32-bit platform, sizeof(Message) will be 16 without payload and
> pointers are 4 bytes each, so messages will typically fit into a
> single cache line.
> Let's assume for the purposes of this example, access to the messages
> is random and memory usage is more than 100x the CPU cache size.
>
> Given these constraints, the only choice you have, is to locate all
> the data for a message in one place. You could of course use a vector
> with something like the small string optimization (instead of the
> flexible array). That would result in higher memory usage and more
> complex code but a much cleaner design/interface and re-usability.
>
> \\
>
> That being said, I'll happily admit that you can usually
> hide/eliminate the extra indirection 'proper' C++ requires and that
> the struct hack should be used very, very rarely.


Those selective placements though are very, very important. Perhaps
having come from a C originally I still have an appreciation for
programming close to the metal whereas that concept escapes those that
started out with the decidely higher-level C++ (or buy into it, lock,
stock and barrel).


 
Reply With Quote
 
joe
Guest
Posts: n/a
 
      08-25-2010
Goran Pusic wrote:
> On Aug 22, 8:52 pm, Juha Nieminen <(E-Mail Removed)> wrote:
>> Goran <(E-Mail Removed)> wrote:
>>>> "OP's hack"? The technique is very well-known from C and C99
>>>> standardized it (C99 uses empty brackets rather than a array
>>>> dimension of 0 or 1). Do a web search on "struct hack" for all the
>>>> details. In addition, you can search on "C99", and "flexible array
>>>> member".

>>
>>> I shall do no such thing.

>>
>> Yeah, way to go. Don't even try to understand what the struct hack
>> technique is all about, and then scream loudly how you know these
>> things better than anybody else. That's the way to discuss and to
>> learn things.

>
> Please read my very first post in this thread and __then__ tell me I
> don't understand what struct hack technique is all about.
>
> But flames aside, I think we ultimately disagree only about one thing:
> how often will one benefit from employing it.
>
> My contention is: in practice, almost never. In practice, other
> processing will swamp the cost of that one allocation. And if actual
> number of elements needs to change (and in what I write, that's almost
> always), vector beats struct hack, because struck hack has horrible
> reallocation performance.
>


Performance never was the issue.


 
Reply With Quote
 
joe
Guest
Posts: n/a
 
      08-25-2010
Goran wrote:
> On Aug 21, 11:05 pm, "joe" <(E-Mail Removed)> wrote:
>> Goran Pusic wrote:
>>> I am speaking about locality because on current hardware, and in a
>>> running system, it easily makes more difference than allocation. (I
>>> am speaking abut a case where there's not too create-use-destroy
>>> cycles, of course; and IME(xperience), best course of action when
>>> there is a lot of that, are algorithmic changes; OPs hack comes in
>>> dead last, when other options are explored).

>>
>> "OP's hack"? The technique is very well-known from C and C99
>> standardized it (C99 uses empty brackets rather than a array
>> dimension of 0 or 1). Do a web search on "struct hack" for all the
>> details. In addition, you can search on "C99", and "flexible array
>> member".

>
> I shall do no such thing. Did you take a look at hbvla class from my
> first post in this thread? I can implement this thing, in C++, with
> the best here. And I certainly did it better than a random C hack like
> OP's.
>
> And I still know it's a hack that has very limited usefulness in real-
> world code, because performance aspect is a massive case of
> prematureoptimizationitis.


Performance is not the issue. You are missing the whole point behind the
struct hack. You and Juha.

>
> Then, hack has peformance worse than vector as soon as of elements
> needs to change, as you can't do it at all without a complete
> reallocation. Then, it's a question of standard-compliance.
>
> There's no need to be condescending.
>
> Goran.



 
Reply With Quote
 
joe
Guest
Posts: n/a
 
      08-25-2010
Juha Nieminen wrote:
> Goran Pusic <(E-Mail Removed)> wrote:
>> But flames aside, I think we ultimately disagree only about one
>> thing: how often will one benefit from employing it.

>
> Who is "we"? At least I am not claiming that the struct hack should
> be used frequently, if at all. In fact, if I had such a situation in
> some project of mine where using the struct hack would potentially
> bring efficiency benefits, I would nevertheless try to think if the
> program could be redesigned in such way that the benefit is
> achievable without the struct hack.


Before you can use a tool, you must understand what its purpose is. The
struct hack is not a performance optimization. You have categorized it
incorrectly.


 
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
Can *common* struct-members of 2 different struct-types, that are thesame for the first common members, be accessed via pointer cast to either struct-type? John Reye C Programming 28 05-08-2012 12:24 AM
Using an instance of a struct as a member of that struct dutchgoldtony C Programming 15 11-16-2005 11:24 PM
length of an array in a struct in an array of structs in a struct in an array of structs Tuan Bui Perl Misc 14 07-29-2005 02:39 PM
struct my_struct *p = (struct my_struct *)malloc(sizeof(struct my_struct)); Chris Fogelklou C Programming 36 04-20-2004 08:27 AM
How would I use qsort to sort a struct with a char* member and a long member - I want to sort in order of the long member Angus Comber C Programming 7 02-05-2004 06:41 PM



Advertisments