«

On Aug 24, 11:35*am, Bart van Ingen Schenau <b...@ingen.ddns.info>
wrote:
> On Aug 22, 10:53*am, Kai-Uwe Bux <jkherci...@gmx.net> 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.

Juha Nieminen wrote:
> joe <> 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).

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.

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.

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.

Kai-Uwe Bux wrote:
> Juha Nieminen wrote:
>
>> Kai-Uwe Bux <> 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!).

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).

Goran Pusic wrote:
> On Aug 22, 8:52 pm, Juha Nieminen <nos...@thanks.invalid> wrote:
>> Goran <goran.pu...@gmail.com> 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.

Goran wrote:
> On Aug 21, 11:05 pm, "joe" <jc1...@att.net> 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.

Juha Nieminen wrote:
> Goran Pusic <> 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.