V
Vladimir Jovic
thomas said:
Priceless! And people still pay good money for a crap called windows
Priceless! And people still pay good money for a crap called windows
B
Balog Pal
Juha Nieminen said:
You keep stating that, but why on earth would vector do two allocations? Or
use anything but placement new at all, that for in compiles to nothing...
Again, where does that difference come from? Please come up with a fair
comparision of the candidates, that do the same thing on the same types, let
the payload struct be POD and your operation a single resize() from the
empty state... Unless certainly you can show different operations the
'hack' can show.
S
Squeamizh
Agreed, but flexible arrays and VLAs (variable-length arrays) are two
different things. Flexible arrays are just a standardized version of
the struct hack. The OP's struct, using flexible arrays, would look
like this:
struct SvrList {
unsigned int uNum;
GameSvr svr[];
};
J
James Kanze
You're about twenty years too late. It was banned by C90.
Ö
Öö Tiib
Evil things like that _SECURE_SCL defined or not can screw up
statically linked library as well, so one should always compile
everything in a product with same options.
J
Juha Nieminen
Goran Pusic said:
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);
}
Compiling that with "g++ -O3 -march=native" on my Pentium4 system takes
about 10 seconds. So, where do you think all that time is spent? Perhaps
rearranging the binary tree each time a new element is inserted? That sounds
like something which would take its time.
Nope. The majority of that time is spent *allocating memory*. If I
change the above code to use a very fast memory allocator, such as
http://warp.povusers.org/FSBAllocator/ so that the declaration of 'someSet'
becomes:
std::set<int, std::less<int>, FSBAllocator<int> > someSet;
then the running time drops down to about 2.5 seconds.
From the 10 seconds running time of the original program above over
7.5 seconds is spent solely on memory allocation and deallocation.
That's quite a *lot*. (There are many reasons why this is so, one of the
major ones being that the default allocator is thread-safe, which the
FSBAllocator above isn't.)
'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.
Not if the memory is heavily fragmented, which is one major problem here.
J
Juha Nieminen
Öö Tiib said:
Exactly how would boost::array make this any faster? There's no
difference. The issue is not reallocation.
J
Juha Nieminen
Balog Pal said:
How many times does this have to be explained?
If you need to instantiate the struct dynamically, there will be only
one malloc() call if the struct hack is used. However, if the struct hack
is not used, but std::vector or a raw array pointer is used instead, you
will need two allocations: One for the struct and another for the array
inside the struct.
What's so hard to understand in that?
The difference comes from the amount of allocations needed.
If you need to instantiate the struct dynamically one million times,
and the struct hack is used, then one million malloc() calls will suffice.
However, if the struct hack is not used, but std::vector or a raw array
pointer is used instead, you will need two million allocations.
'new' and 'delete' (or malloc() and free()) are quite heavy operations,
so this can have a significant impact in performance. It also increases
memory fragmentation.
I don't even understand that paragraph.
J
Juha Nieminen
Juha Nieminen said:
Of course I meant:
Compiling that with "g++ -O3 -march=native" *and running it* on my
Pentium4 system takes about 10 seconds.
I
Ian Collins
You are cheating. std::set<int> != std::vector<int> and is in no way an
equivalent to a dynamically allocated array.
Try your test with a vector, before and after reserving space (which is
the more realistic comparison).
B
Balog Pal
Juha Nieminen said:
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.
Okay, let's just drop it.
B
Balog Pal
Juha Nieminen said:
Hard to decide that your article is a sour attemt at cheating or just basic
trolling. We discuss performance of vector<int> then you insert a snippet
with set<int> like it had any relevance. :-(((
Different collections have different characteristics wrt performance, memory
footprint, etc, we ALL know that. Now please go back to the original claim
instead of drifting in all directions.
....
And if you allocate a million instances of the struct hack, it will take a
while too. now do you suggest using the struct hack in the *payload*?
Ö
Öö Tiib
What is the issue, then? At some point i start to forget the issue
when all go "blah-blah" and no code is posted. Original 'hack' was
something like that:
// -------
struct SvrList
{
unsigned int uNum;
GameSvr svr[];
};
SvrList* pList = (SvrList*)malloc( sizeof SvrList
+ svrNum * sizeof GameSvr );
int len = pList->uNum;
GameSvr a = pList->svr[0];
pList->svr[1] = a;
// -------
It is simply pile of bad things. Lot better (no pointers, no arrays,
hacks if any in well-tested templates) with boost would look something
like that:
// -------
typedef boost::array<GameSvr, svrNum> SvrList;
typedef boost::shared_ptr<SvrList> SvrListPtr;
SvrListPtr pList = boost::make_shared<SvrList>();
int len = pList->size();
GameSvr a = pList->at(0);
pList->at(1) = a;
// -------
Are you claiming that it is lot less efficient than the original?
Ok ... one additional indirection from shared_ptr and that is all
basically, you won't notice it in profiler. However all hacking
headache has gone away.
J
James Kanze
[...]
Maybe. Alternatively, it's spent because one allocator results
in better locality than the other, with less page faults.
Typically, yes, although some implementations (including VC++!)
do optimize them for "small" allocations---replacing the
allocator for the int's in a shared_ptr, for example, rarely
gains much, since the implementation already picks up the
"small" allocation, and uses a specialized strategy for it
(which isn't that heavy).
[...]
I'm not sure where he got this from. In my experience,
allocators do a good job in allocating similarly sized blocks
close together, but when the sizes are radically different, it
varies considerably.
J
joe
Goran said:
"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". And please note that the
C99 "VLA" (Variable-Length Array) is entirely different that "flexible
array member". Why C++ isn't following suit on this one escapes me. I use
it in C++ using an array dimension of 1, because a struct with a
zero-length array can't be derived from (for no good reason as far as I
can tell, as of course the programmer wouldn't be adding data members to
a class derived from another with flexible array as the last member) and
I forget what the result of trying to use empty brackets is, but you can
try it and see.
J
joe
Juha said:
I don't think performance is the issue at all with this apples-to-oranges
comparison of std::vector and the struct hack: 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. std::vector is a very
specialized container whereas the struct hack is just a down-at-the-metal
technique used in building higher-level abstractions. Note that the OP
had the var-len array as a part of another struct. This isn't about
"array containers".
J
joe
tni said:
Try to derive something from a class that has a zero-length or
undefined-length array as the last member using VC++.
J
joe
Vladimir said:
Undefined by the standard, but DEFINED by all implementations. The "it's
undefined behavior" ranting gets quite annoying. Try compiling something
with the standard instead of an implementation sometime and see how far
you get!
J
Juha Nieminen
Ian Collins said:
How many times does this have to be repeated?
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.
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
};
Then you allocate such structs with
malloc(sizeof(MyStruct) + amount_of_elements * sizeof(int));
Now you have a dynamically allocated instantiation of the struct, where
the size of the 'array' element is decided at runtime.
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.
std::vector::reserve has nothing to do with this.
J
Juha Nieminen
Balog Pal said:
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?