Zero-size array as struct member

[Juha Nieminen]

What is the issue, then?

How many times does this have to be repeated?

The issue is that with a member vector (or boost::array or whatever you
want to use), there will be *two* memory allocations (one for the struct
itself and another for the member array), while with the struct hack
there will be only *one* memory allocation.

Why is that so hard to understand?

If your argument is that it doesn't matter efficiency-wise, then you
are simply wrong if the amount of struct instantiations is significantly
large because memory allocation is a heavy operation in most systems.

 

[Juha Nieminen]

Nothimg, it is just hard to believe that you actually meant to drag that
gremlin in an expert group and hope to get away with it.
We certainly do NOT do stuff like
new vector<int>
in real life, but have the vector as direct member, or it passed in, or
returned -- such code would hardly pass any review. So your "if"
situation only works on "paper" not reality.

How many times does this have to be explained? I just can't think how
I would explain it more clearly.

Ok, let me try once more. Assume you have this:

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

Then you need to allocate an instance of that struct dynamically (because
it has to survive the scope where it is being created). You do it like:

malloc(sizeof(MyStruct) + elements_amount * sizeof(int));

Please count the number of allocations being made. It's 1. Follow me so
far?

Ok, now consider the alternative:

struct MyStruct
{
// Some other member variables here.
std::vector<int> array;

MyStruct(int size): array(size) {}
};

Then when you need to allocate an instance of that struct dynamically,
you do it like:

new MyStruct(elements_amount);

Please count the number of allocations being made. It's 2 (one for the
struct itself, and one performed by std::vector).

Understand now?

 

[Juha Nieminen]

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

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

 

[Ian Collins]

How many times does this have to be repeated?

What, that you cheated?

The so-called struct hack is a technique for allocating a variable-length
struct. It's struct which has an array as the last element, and the size
of this array is determined at runtime by "overallocating" memory using
malloc(). When this last element is then indexed, this will access that
allocated memory.

I discovered that 30 odd years ago, no news there.

So using the struct hack you would have:

struct MyStruct
{
int size; // or whatever
int array[0]; // or int array[1] if the compiler demands it
};

or int array[] if you have a conforming C compiler.

Then you allocate such structs with

malloc(sizeof(MyStruct) + amount_of_elements * sizeof(int));

In the C world, yes.

Now you have a dynamically allocated instantiation of the struct, where
the size of the 'array' element is decided at runtime.

The struct hack is a C idiom which is seldom used in C++. In C++ we
have other techniques.

The other option is to do it like:

struct MyStruct
{
std::vector<int> array;

MyStruct(int size): array(size) {}
};

Then you allocate the struct like:

new MyStruct(amount_of_elements);

(It has to be allocated dynamically if the struct instantiation needs to
survive the scope where it was created.)

In the latter case there will be *two* allocations: One for the struct
and another for the std::vector. In the former case there will be only
one allocation.

Big deal.

std::vector::reserve has nothing to do with this.

neither has std::set.

 

[Juha Nieminen]

What, that you cheated?

Cheated exactly how? I was demonstrating the speed of memory allocations.
Allocating a million std::set nodes and allocating a million instances of
(non-zero-sized) std::vector instances both cause a million memory
allocations. The point was to demonstrate the speed of memory allocation,
not the speed of std::vector vs. std::set. I could just as well have used
std::list, std::map or outright raw 'new' calls for the same purpose.

In other words, I was demonstrating the significance of the amount of
times that 'new' and 'delete' are executed.

The struct hack is a C idiom which is seldom used in C++. In C++ we
have other techniques.

And this has what to do with my original point, namely that 'new' and
'delete' are heavy operations?

Big deal.

So you *do* understand my point, finally? In other words, that with the
struct hack the total amount of memory allocations will be halved compared
to the cleaner solution (using a dynamically allocated array as the member
of the struct).

If you are making a huge amount of such allocations, it *will* be a big
deal because 'new' and 'delete' (or malloc() and free() if you like) are
quite heavy operations. That's what my example with the std::set was
demonstrating.

neither has std::set.

The point was to demonstrate how heavy 'new' and 'delete' are.

 

[Juha Nieminen]

The point was to demonstrate the speed of memory allocation,
not the speed of std::vector vs. std::set. I could just as well have used
std::list, std::map or outright raw 'new' calls for the same purpose.

Btw, to delve more into why I used std::set in the example:

The point was to demonstrate that 'new' and 'delete' are heavy
operations. But how heavy? It's clear that if you do nothing else in
a program other than N allocations or 2*N allocations, the latter will
take about twice the time compared to the former. However, that tells
little about how heavy the allocation is compared to other operations
that the program might be doing. If 'new' and 'delete' take one clock
cycle then it's rather irrelevant.

std::set does quite a lot of things when elements are inserted. It's
a balanced binary tree, and every time an element is inserted, especially
if there is already a big amount of elements, it will perform quite many
operations, mainly to re-balance the tree. It will traverse the tree and
update pointers and flags, etc. (It does this to about O(log n) elements
of the tree, but we are still talking about dozens of operations needed
to re-balance the tree.)

So inserting an element to a std::set is a relatively heavy operation
because of all the operations it needs to do internally to re-balance the
tree. Thus one would easily think that when inserting 10 million elements
to a std::set, the vast majority of the time is being spent on these
operations.

However, rather surprisingly, over 75% of the time is actually being
used by 'new'. In other words, 'new' is at least three times slower than
re-balancing a binary tree with millions of elements in it.

This goes to demonstrate how heavy 'new' is, and why it may be a good
idea to minimize how many times it's called in a program, if possible.

If you want to directly measure the speed difference between the struct
hack allocation and the more regular solution, doing that is rather easy
with a program like:

#if(1)
//--------------------------------------------------------------
#include <cstdlib>

struct MyStruct
{
int someData;
int size;
int array[0];
};

int main()
{
for(int i = 0; i < 100000000; ++i)
{
const int arraySize = 10 + i % 10;
MyStruct* p = (MyStruct*) std::malloc
(sizeof(MyStruct) + arraySize * sizeof(int));
std::free(p);
}
}
//--------------------------------------------------------------
#else
//--------------------------------------------------------------
#include <vector>

struct MyStruct
{
int someData;
std::vector<int> array;

MyStruct(int size): array(size) {}
};

int main()
{
for(int i = 0; i < 100000000; ++i)
{
const int arraySize = 10 + i % 10;
MyStruct* p = new MyStruct(arraySize);
delete p;
}
}
//--------------------------------------------------------------
#endif

For example in my computer the first version of the program, which uses
the struct hack, takes 10 seconds to run, while the latter version takes
20 seconds to run.

Of course given the attitude that some people seem to have formed in
this thread, I'm pretty sure someone will come up with some reason why
I "cheated" there as well (most probably by ignoring the original premise
that the struct needs to be allocated dynamically in cases where it has
to outlive the scope where it's being created).

 

[Öö Tiib]

  How many times does this have to be repeated?

  The issue is that with a member vector (or boost::array or whatever you
want to use), there will be *two* memory allocations (one for the struct
itself and another for the member array), while with the struct hack
there will be only *one* memory allocation.

No. boost::array does usually allocate together with struct that
contains it. It is like any usual non dynamic array. Since i used
boost::make_shared<> in my example it did exactly one allocation
(allocating room both for svrlist and for shared_ptr pointing at it at
once).

  Why is that so hard to understand?

  If your argument is that it doesn't matter efficiency-wise, then you
are simply wrong if the amount of struct instantiations is significantly
large because memory allocation is a heavy operation in most systems.

No. My argument is that there is always a way to write it in C++. That
struct hack is there since C provides you no much other ways. If the
already existing things do not suit you then fine, but that hack is
ugly don't you see?

 

[Juha Nieminen]

No. boost::array does usually allocate together with struct that
contains it. It is like any usual non dynamic array. Since i used
boost::make_shared<> in my example it did exactly one allocation
(allocating room both for svrlist and for shared_ptr pointing at it at
once).

There's a failure at communication here. You are creating an array of
struct objects. That's not the issue here. The issue is the array which
is inside the struct, as its last member, which size is determined at
runtime (rather than at compile time).

No. My argument is that there is always a way to write it in C++.

There's always a way to write *what* in C++?

That
struct hack is there since C provides you no much other ways.

Of course C provides you other ways. You could do this in C:

struct MyStruct
{
int size;
int* array; // instead of int array[0];
};

However, now you need to allocate the array separately. Thus you end
up with two allocations: One for the struct instantiation itself, and
another for the array inside it. The struct hack avoids the latter
allocation by making the array be in the same memory block as the
struct instantiation itself.

In C++ you can use std::vector instead of int*, but that changes nothing
(it only makes it easier and safer to use, but it still causes the same
amount of memory allocations to be performed).

If the
already existing things do not suit you then fine, but that hack is
ugly don't you see?

I am not questioning the ugliness, safety or anything else. Of course
using std::vector instead of the struct hack (or a raw array with int*)
is easier and safer. The only thing I'm arguing is allocation efficiency.

 

[Bo Persson]

Of course C provides you other ways. You could do this in C:

struct MyStruct
{
int size;
int* array; // instead of int array[0];
};

However, now you need to allocate the array separately. Thus you
end
up with two allocations: One for the struct instantiation itself,
and another for the array inside it. The struct hack avoids the
latter allocation by making the array be in the same memory block
as the
struct instantiation itself.

In C++ you can use std::vector instead of int*, but that changes
nothing (it only makes it easier and safer to use, but it still
causes the same amount of memory allocations to be performed).

No, in C++ you would use a std::vector in place of the MyStruct, not
in place of the buffer pointer. That is what people have been trying
to tell you here.

C and C++ are two different languages, and you do things differently.


Bo Persson

 

[Juha Nieminen]

No, in C++ you would use a std::vector in place of the MyStruct, not
in place of the buffer pointer. That is what people have been trying
to tell you here.

Care to show me how it would be done?

The idea in the original post, in other words, the idea with the so-called
"struct hack", is that you have an object which has an array as member, the
size of this array being determined at runtime. In other words, what you
would normally write like this:

struct MyStruct
{
int someData, someOtherData;
std::vector<int> anArray;
};

That's a struct which has an array as member. Its minor "problem" is
that the array is allocated separately from the struct itself. The struct
just contains a pointer to that array (which is what std::vector really is,
internally). This usually doesn't matter much. However, if you need to
instantiate MyStruct dynamically, and you need to do a lot, then you are
effectively doubling the amount of allocations being performed (each
allocation of MyStruct also causes an additional allocation performed
by std::vector).

The C struct hack is a low-level optimization of this, where the array
is allocated alongside the struct itself. Due to how C (and C++) works,
this is technically possible and feasible. Thus you write the above as:

struct MyStruct
{
int someData, someOtherData;
int anArray[0];
};

and then when allocating an instance of MyStruct, you "overallocate" memory
for it. The additional memory is used as the memory needed by the 'anArray'
member, which can then be accessed normally with operator[].

This way only one allocation is needed, even though the size of 'anArray'
is determined at runtime.

Now, would you kindly show me how std::vector<MyStruct> achieves this
same result?

I think you are confused about what the struct hack is all about. Please
try to understand what is it that the struct hack is doing. I have tried
to explain it as well as I can.

 

[Kai-Uwe Bux]

No, we were discussing the efficiency of memory allocation.

If you are instantiating a million std::vector instances (initialized
with a non-zero size), there will be a million allocations.


The discussion was about the efficiency of memory allocation. 'new' and
'delete' are heavy operations.


If you allocate a million instances of the struct using the struct hack,
you will be making one million memory allocations.

If you allocate a million instances of the struct without the struct
hack
(ie. it has a std::vector as an element instead), you will be making *two*
million memory allocations.

What is so hard to understand in that?

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.

So, instead of:

struct SvrList{
unsigned int uNum;
GameSvr svr[0];
};
....
SvrList* pList =
(SvrList*)malloc(sizeof( SvrList) + svrNum*sizeof(GameSvr));
for ( int i = 0; i < svrNum; ++i ) {
pList->svr = GameSvr();
}

you would do:

std::vector< GameSvr > svr_seq ( svrNum );


If you use std::vector instead of the struct, you have just as many dynamic
memory allocations. There still are technical differences: (a) the size
variable could be stored in a different place, (b) vector also manages a
capacity, (c) std::vector initializes the elements, and (d) you can only use
it if (d) GameSvr satisfies the CopyConstructible and Assignable concept.
However, the number of allocations would be the same.


Best

Kai-Uwe Bux

 

[Juha Nieminen]

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.

 

[Ian Collins]

So you *do* understand my point, finally? In other words, that with the
struct hack the total amount of memory allocations will be halved compared
to the cleaner solution (using a dynamically allocated array as the member
of the struct).

If you are making a huge amount of such allocations, it *will* be a big
deal because 'new' and 'delete' (or malloc() and free() if you like) are
quite heavy operations. That's what my example with the std::set was
demonstrating.

If you are allocating a large number of vectors *and* those allocations
are a performance bottleneck, you would use a custom allocator (possibly
by utilising std::vector's allocator template parameter) so new is no
longer be a heavy operation.

 

[Kai-Uwe Bux]

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.


Best

Kai-Uwe Bux

 

[Juha Nieminen]

If you are allocating a large number of vectors *and* those allocations
are a performance bottleneck, you would use a custom allocator (possibly
by utilising std::vector's allocator template parameter) so new is no
longer be a heavy operation.

That would indeed be a cleaner C++ solution to the problem. Of course
creating such an allocator is quite complicated (and quite hard to make
it any more efficient than the default allocator if you need it to be
thread-safe).

Of course the best solution would be to see if the program could be
designed in such way that you don't need so many individual allocations
in the first place... (Naturally this is not always possible, but it's
always a good option to consider.)

 

[Juha Nieminen]

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.

Ok, off the top of my head (iow. I haven't checked if there's a much
better way of doing this equally efficiently):

An array (which size is determined at runtime) which has the size
of the array, a reference count (so that the array can have shared
ownership) and a lock data structure so that the reference counting
can be done in a thread-safe manner.

 

[tni]

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.

 

[Öö Tiib]

  There's a failure at communication here. You are creating an array of
struct objects. That's not the issue here. The issue is the array which
is inside the struct, as its last member, which size is determined at
runtime (rather than at compile time).

You may allocate sufficient memory for several things (some of what
may be arrays with run-time decided sice) at once in C++ as well. You
have to manage it and use placement new to put all things into same
storage.

There may be some issues with alignment and padding, but some rules
help with it:
1) Structs can be used as members of arrays.
2) Arrays can be used as members of structs.
3) Arrays do not have padding between their members.
4) There is no padding before the first member of a structure, but
there may be padding between structure elements and at the end.

When you create things with placement new then you have to wrap
creation and destruction of it anyway to avoid bugs ... so i do not
see problems there too.

  I am not questioning the ugliness, safety or anything else. Of course
using std::vector instead of the struct hack (or a raw array with int*)
is easier and safer. The only thing I'm arguing is allocation efficiency.

POD structure members are arranged in memory in the order they are
defined, C++ relaxes that requirement for classes in situations.
Perhaps best is to have pointers to such (allocated at once) arrays
anyway.

 

[Goran]

  You are basing your claims on your personal *opinion*? Rather than,
you know, actually testing it in practice?


  It's quite well founded. For example, take this short piece of code:

    int main()
    {
        std::set<int> someSet;
        for(int i = 0; i < 10000000; ++i) someSet.insert(i);
    }

Oh, come on! set is not a vector. That's a MAJOR flaw in your example
and example is therefore completely of the mark.

  'new' and 'delete' are significantly heavy operations.



  If you are allocating a million instances of the struct, each such
instance having an std::vector object inside, reserve() would do nothing
to alleviate the memory fragmentation.

What!? Reserve would cause exactly 0 memory fragmentation, at least
until code starts reallocating or freeing these vectors, at which
point, there would be, fragmentation-wise, little, if any, difference
between a vector and discussed struct hack.

  Not if the memory is heavily fragmented, which is one major problem here.

You're still to prove how memory is fragmented. Until you reach
reserved size in a vector, there's no fragmentation.

All you have is one allocation more with a vector. That's easily
swamped by the rest of the code, especially if you have millions of
elements in it.

You need to have _a lot_ of vectors, all with a _small_ number of
elements in it for your complaint to be relevant. And for that,
there's no need to use contortions until one can measurein running
code, that performance hit is indeed relevant. You are trying to do it
backwards, and especially because programmers are proven time and time
over to be poor judges of performance problems.

Goran.

 

[Goran]

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

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.