Sign in to follow this  
Followers 0
Misery

C++ array resize

23 posts in this topic

Hi,

I need to resize copy an array as fast as possible. Is it a good way, or there are some dangers I cannot see?
(Lets assume that new size is greater than previous).
[code]
int N=SomeValue, NewSize=SomeValue;
int *array=new int[N];

//making a temporary array:
int *tmp=new int[NewSize];
for (int i=0;i<N;i++) tmp[i]=array[i];
delete[] array;
array=tmp;
[/code]

Or do I need to allocate array again and copy it from tmp to array and then delete tmp?
Will that work fine?

Thanks on advance for help :]
0

Share this post


Link to post
Share on other sites
No need to allocate another new array, that works fine.
But, why not std::vector?
2

Share this post


Link to post
Share on other sites
[quote name='wqking' timestamp='1309770782' post='4830853']
No need to allocate another new array, that works fine.
But, why not std::vector?
[/quote]

Because it would be vector<bool> and i've heard it is not safe to use it.

Thanks gyus for answers :]]
0

Share this post


Link to post
Share on other sites
[quote name='Misery' timestamp='1309770868' post='4830854']
[quote name='wqking' timestamp='1309770782' post='4830853']
No need to allocate another new array, that works fine.
But, why not std::vector?
[/quote]

Because it would be vector<bool> and i've heard it is not safe to use it.

Thanks gyus for answers :]]
[/quote]
vector<bool> is fine to use but I wouldnt have used a loop just memcpy the memory from the old array in to the new one.
3

Share this post


Link to post
Share on other sites
You can often use std::vector<unsigned char> instead of std::vector<bool>. std::vector<bool> is unusual in certain ways, but isn't necessarily unsafe.

What is your usage of the array? Is it resized once, or is it resized multiple times? If multiple, consider over-allocating to amortise the cost of individual resize actions. Also consider wrapping the array in a class, so you can separate the memory management from other code and can directly control when and how much to allocate, while maintaining all the invariants you need.
1

Share this post


Link to post
Share on other sites
[quote name='Misery' timestamp='1309770868' post='4830854']
Because it would be vector<bool> and i've heard it is not safe to use it.
[/quote]
The only potential problem I'm aware of is that you can't just take the address of anything returned by operator[] for an std::vector<bool>. That is something one should be aware of but not something that prohibits the use of the entire class. Could you expand a bit about the safety issues of the bool specialization of std::vector? There are a lot of myths and legends going around, especially from before the time of proper standardization.

That aside, what about Boost's [url="http://www.boost.org/doc/libs/1_46_1/libs/dynamic_bitset/dynamic_bitset.html"]bitset/dynamic_bitset[/url]?
2

Share this post


Link to post
Share on other sites
I will probably use this bit array to store my extended arithmetic numbers for mesh generator, and as a flags container for finite elements properties.
And maybe for iterative corrections of large systems of linear equations.
The problem is that this will be the adaptive mesh for largre tasks (millions of nodes) in partial differential eqs. Now I am playing with different things
just to see possibilities it gives, etc. I needed to have my bitarray as small as possible and as fast as possible. I'm not saying I've done it better
than programming-artists like You gyus or Creators of STL or BOOST, but the thing is that I really need to have absolute control over this project.
I cannot afford to finally find a bug for solving which I will have to wait until next release of some library. That happend to me once
and I almost lost my job. So if it is possible I prefer to use my own code - not so efficient and well made but easy to modify etc.

And the second thing is that I am just learning, and trying to do some things.

to GDNet+: I have wrapped it in class and I will use some of the tips You wrote. However now I am just trying to make a quite good bit array :]

Thank You guys very very much for Your help :]

PS.: If someone wishes to see that class (unfinished yet) I paste it here:

[code]
#ifndef TBITARRAY_H_INCLUDED
#define TBITARRAY_H_INCLUDED
#include <stdlib.h>
#include <string>


class TBitArray
{
class TEightBits; //internal class implementing a byte with access to every bit
private:
TEightBits* Bits;
unsigned int BitsNumber; //number of bits

public:

inline TBitArray() //constructor
{
BitsNumber=0;
Bits=NULL;
}


inline TBitArray(unsigned int NumOfBits) //meritorical nonstructor
{
int NumOfBytes=NumOfBits/8; //jesli NumOfBits nie miesci sie w calkowitej liczbie bajtow
if (NumOfBits%8>0) NumOfBytes++; //trzeba zwiekszyc o 1 liczbe bajtow
BitsNumber=0;
Bits=NULL;
Bits=new TEightBits[NumOfBytes];
BitsNumber=NumOfBits;
}


inline ~TBitArray()
{
BitsNumber=0;
delete[] Bits;
Bits=NULL;
}


inline unsigned int GetNumberOfBytes(void)
{
unsigned int NumOfBytes=BitsNumber/8;
if (BitsNumber%8>0) NumOfBytes++;
return NumOfBytes;
}

inline bool GetBit(unsigned int BitPos)
{
return Bits[BitPos/8].GetBit(BitPos%8);
}

inline void SetBit(bool Bit,unsigned int BitPos)
{
Bits[BitPos/8].SetBit(Bit,BitPos%8);
}

inline void Resize(unsigned int NewSizeInBits)
{
unsigned int NewNumOfBytes=NewSizeInBits/8,
NumOfBytes=BitsNumber/8;
if (NewSizeInBits%8>0) NewNumOfBytes++;
if (BitsNumber%8>0) NumOfBytes++;

if (NewNumOfBytes!=NumOfBytes) //dodac dodatkowe warunki
{
TEightBits *tmp=new TEightBits[NewNumOfBytes];
std::copy(Bits,Bits+Min(NewNumOfBytes,NumOfBytes),tmp); //a faster stuff
delete[] Bits;
Bits=tmp;
BitsNumber=NewSizeInBits;
}
}

inline void Copy(const TBitArray& that)
{
unsigned int NewNumOfBytes=that.BitsNumber/8,
NumOfBytes=BitsNumber/8;
if (that.BitsNumber%8>0) NewNumOfBytes++;
if (BitsNumber%8>0) NumOfBytes++;

if (NewNumOfBytes!=NumOfBytes)
{
delete[] Bits;
Bits=NULL;
Bits=new TEightBits[NewNumOfBytes];
}
std::copy(that.Bits,that.Bits+NewNumOfBytes,Bits);
BitsNumber=that.BitsNumber;
}


inline unsigned int SizeInBytes(void)
{
unsigned int NumOfBytes=BitsNumber/8;
if (BitsNumber%8>0) NumOfBytes++;
return NumOfBytes;
}

inline void Negation(void)
{
for (unsigned int i=0;i<SizeInBytes();i++) Bits[i].Negation();
}

inline void IncByLastBit(void)
{

}

inline void IncByFirstBit(void)
{

}

std::string ToString(void)
{
std::string RetStr(BitsNumber,'0');
for (unsigned int i=0;i<BitsNumber;i++) if(GetBit(i))RetStr[i]='1';
return RetStr;
}

private:

inline unsigned int Min(unsigned int a,unsigned int b)
{
if(a<b) return a; else return b;
}

class TEightBits //internal class implementing a byte with access to every bit
{
private:
unsigned char bits;

public:
TEightBits()
{
bits=0;
}

inline bool GetBit(unsigned short BitPos)
{
return (bits & (1 << BitPos));
}

inline void SetBit(bool Bit, unsigned short BitPos)
{
bits |= Bit << BitPos;
}

inline void NegationBit(unsigned int BitPos)
{
bits ^= 1 << BitPos;
}

inline unsigned int ElementSize(void) const
{
return 8; //bits
}

inline void Negation(void)
{
bits=~bits;
}

inline void operator = (const TEightBits &Byte)
{
bits=Byte.bits;
}

/*
//operators
inline bool operator == (const TEightBits &Byte)
{
return (bits==Byte.bits);
}

inline bool operator != (const TEightBits &Byte)
{
return (bits!=Byte.bits);
}

inline bool operator >= (const TEightBits &Byte)
{
return (bits>=Byte.bits);
}

inline bool operator <= (const TEightBits &Byte)
{
return (bits<=Byte.bits);
}

inline bool operator > (const TEightBits &Byte)
{
return (bits>Byte.bits);
}

inline bool operator < (const TEightBits &Byte)
{
return (bits<Byte.bits);
}
*/
};
};

#endif // TBITARRAY_H_INCLUDED

[/code]
0

Share this post


Link to post
Share on other sites
[quote name='wqking' timestamp='1309770782' post='4830853']
No need to allocate another new array, that works fine.
[/quote]
I'm assuming the existing array is populated and used prior to resizing (else it wouldn't be a resize).
1

Share this post


Link to post
Share on other sites
A couple of things:

First, I would talk out the usage of Boost with my employers. As far as I am concerned, Boost is an integral part of C++ and contains mostly things that should have been in the standard library in the first place (and some of them now are in C++0x). Unless you are working on a compiler with horrible template support, a very embedded platform with limited capabilities or suffer from some weird license issues (extremely weird, considering Boost's rather permissive license) there is not much reason not to use Boost.
In general using well-tested code (and Boost is that) will be much faster than writing it on your own, never mind all those teeny tiny bugs you have to weed out of your own code. Even if Boost contains a bug (not impossible but increasingly unlikely in the well-matured core libraries) I would expect the Boost mailing list could offer a fix for a reproducible bug within a day or two. At worst, you could hack a fix together yourself since the code is all there.

Second, I notice you have a class to grant access to the single bits of a byte. Have you made sure that class is not padded by the compiler to 32/64 bit boundaries? Have you checked in the standard that allocating an array of these classes will never introduce any padding? Because if you didn't, you are wasting memory by a factor of four or eight.

Last, you don't need to specify functions as inline if they are declared in the class body. Neither do you need to specify void for no-argument functions (that's C).
0

Share this post


Link to post
Share on other sites
[quote name='BitMaster' timestamp='1309779357' post='4830901']
A couple of things:

First, I would talk out the usage of Boost with my employers. As far as I am concerned, Boost is an integral part of C++ and contains mostly things that should have been in the standard library in the first place (and some of them now are in C++0x). Unless you are working on a compiler with horrible template support, a very embedded platform with limited capabilities or suffer from some weird license issues (extremely weird, considering Boost's rather permissive license) there is not much reason not to use Boost.
In general using well-tested code (and Boost is that) will be much faster than writing it on your own, never mind all those teeny tiny bugs you have to weed out of your own code. Even if Boost contains a bug (not impossible but increasingly unlikely in the well-matured core libraries) I would expect the Boost mailing list could offer a fix for a reproducible bug within a day or two. At worst, you could hack a fix together yourself since the code is all there.

Second, I notice you have a class to grant access to the single bits of a byte. Have you made sure that class is not padded by the compiler to 32/64 bit boundaries? Have you checked in the standard that allocating an array of these classes will never introduce any padding? Because if you didn't, you are wasting memory by a factor of four or eight.

Last, you don't need to specify functions as inline if they are declared in the class body. Neither do you need to specify void for no-argument functions (that's C).
[/quote]

Bear in mind though that the inline keyword is just a suggestion to the compiler, most optimising compilers are smart enough to figure out that if they find a implementation of a function in a header you meant to inline it. Some functions found in cpp files will be inlined as well when the compiler knows it will provide better speed or according to Optimisation settings in your build environment.

That said however it is nice to still place inline in front of implementations in headers as it gives a heads up to the next programmer that that is what you actually meant to happen.
2

Share this post


Link to post
Share on other sites
That is another can of worms which I did not want to open. Personally, the only place where I ever use inline nowadays is when it is required (for example because a function definition needs to be in a header). But ignoring modern optimizing compilers, things like unnecessary inlines or void parameter list always smell fishy and could very well raise an 'uh oh' when trying to land a job somewhere.
0

Share this post


Link to post
Share on other sites
I checked bitset and it looks cool. Very cool, however it still has capacity of 16 bytes when empty. My class has 8.
And padding? I don't think it should happen here, because I have exactly 8 bytes. Char ptr and integer both have 4 bytes.
0

Share this post


Link to post
Share on other sites
[quote name='Misery' timestamp='1309784853' post='4830939']
And padding? I don't think it should happen here, because I have exactly 8 bytes. Char ptr and integer both have 4 bytes.
[/quote]
I'm not worried about padding of TBitArray. Possible padding of TEightBits worries me and you cannot see that by doing a sizeof(TBitArray).
1

Share this post


Link to post
Share on other sites
Your class doesn't implement the rule of three. Resize() doesn't work if you change the number of bits without changing the number of bytes (e.g. resize 10 to 11 bits). You are implementing "min" yourself for some reason. You've re-implemented the expression for converting #bits into #bytes in a number of places, often multiple times in the same function. Copy() isn't exception safe. There doesn't appear to be much checking for the case where the underlying storage is NULL.

Correctness before speed, always.
1

Share this post


Link to post
Share on other sites
[quote name='BitMaster' timestamp='1309787710' post='4830962']
[quote name='Misery' timestamp='1309784853' post='4830939']
And padding? I don't think it should happen here, because I have exactly 8 bytes. Char ptr and integer both have 4 bytes.
[/quote]
I'm not worried about padding of TBitArray. Possible padding of TEightBits worries me and you cannot see that by doing a sizeof(TBitArray).
[/quote]

Ok. But TEightBits consists only of unsigned char. Why should it cause problem?
0

Share this post


Link to post
Share on other sites
[quote name='rip-off' timestamp='1309789383' post='4830972']
Your class doesn't implement the rule of three. Resize() doesn't work if you change the number of bits without changing the number of bytes (e.g. resize 10 to 11 bits). You are implementing "min" yourself for some reason. You've re-implemented the expression for converting #bits into #bytes in a number of places, often multiple times in the same function. Copy() isn't exception safe. There doesn't appear to be much checking for the case where the underlying storage is NULL.

Correctness before speed, always.
[/quote]

Well, as I said it is unfinished, or rather still at work so I need to do there a lot more.
Thanks for pointing out that mistake with non working resize. The idea was to change the size of array only when number of bytes needed changes and I didn't notice that.
About the NULL - I know :) But I just wanted to discuss the idea itself.
I think that I will think about correctnes, error handling etc when I'll try to make this a part of the larger project.

Thanks once more everybody for wasitng their time to help me :]
0

Share this post


Link to post
Share on other sites
[quote name='Misery' timestamp='1309790051' post='4830985']
[quote name='BitMaster' timestamp='1309787710' post='4830962']
[quote name='Misery' timestamp='1309784853' post='4830939']
And padding? I don't think it should happen here, because I have exactly 8 bytes. Char ptr and integer both have 4 bytes.
[/quote]
I'm not worried about padding of TBitArray. Possible padding of TEightBits worries me and you cannot see that by doing a sizeof(TBitArray).
[/quote]

Ok. But TEightBits consists only of unsigned char. Why should it cause problem?
[/quote]

Because I do not know what the standard says about a class containing only a single char. Usually it would be smart to make sure that the individual members are aligned on 32/64 bit boundaries. That is why a class containing an uint32 and an uint8 will usually be 8 bytes big on 32 bit systems. If the compiler decides to pad you TEightBits class, you waste memory by a factor of four or eight. Even if your compiler does not do it, the question is if the standard promises that or if you can guarantee you will only ever use the code with that one compiler.
0

Share this post


Link to post
Share on other sites
[quote name='BitMaster' timestamp='1309792030' post='4831000']
[quote name='Misery' timestamp='1309790051' post='4830985']
[quote name='BitMaster' timestamp='1309787710' post='4830962']
[quote name='Misery' timestamp='1309784853' post='4830939']
And padding? I don't think it should happen here, because I have exactly 8 bytes. Char ptr and integer both have 4 bytes.
[/quote]
I'm not worried about padding of TBitArray. Possible padding of TEightBits worries me and you cannot see that by doing a sizeof(TBitArray).
[/quote]

Ok. But TEightBits consists only of unsigned char. Why should it cause problem?
[/quote]

Because I do not know what the standard says about a class containing only a single char. Usually it would be smart to make sure that the individual members are aligned on 32/64 bit boundaries. That is why a class containing an uint32 and an uint8 will usually be 8 bytes big on 32 bit systems. If the compiler decides to pad you TEightBits class, you waste memory by a factor of four or eight. Even if your compiler does not do it, the question is if the standard promises that or if you can guarantee you will only ever use the code with that one compiler.
[/quote]

Ok. How do i test it?
0

Share this post


Link to post
Share on other sites
[quote name='Misery' timestamp='1309792192' post='4831003']
Ok. How do i test it?
[/quote]
If it is enough to know no padding is added for *this* compiler with *these exact* settings, checking sizeof(TEightBits) should be enough. Personally, I would add a BOOST_STATIC_ASSERT for that. The check is done at compile time and automatically no matter what changes behind the scenes.

However, even if no padding is done I had the impression you have to be as speed- and time-efficient as possible. Accessing the three (or seven on x64) TEightBit instances which are not perfectly on machine word boundaries will be slower than it could be. Not horribly slower, but slower. If I had to do it with such a helper class, I would suggest
[code]
template <typename BaseType, unsigned BitCount = sizeof(BaseType) * 8>
class TMyBitHelper
{
// fill as appropriate
};

#ifdef WIN32
typedef TMyBitHelper<boost::uint32_t> MyBitHelper;
#else
typedef TMyBitHelper<boost::uint64_t> MyBitHelper;
#endif
[/code]
Not tested, but the basic idea should be clear.
1

Share this post


Link to post
Share on other sites
[quote name='Misery' timestamp='1309775436' post='4830885']
The problem is that this will be the adaptive mesh for largre tasks (millions of nodes) in partial differential eqs.[/quote]

Why do you need to track boolean state for that?

[quote]I needed to have my bitarray as small as possible and as fast as possible.[/quote]
The bottleneck in such homebrewed implementation will be irrelevant compared to the time needed to actually compute the matrices. And those will obviously use some battle-tested third-party library, right? Right?

Nobody today would be insane enough to think they can implement BLAS better than what existing implementations offer. Right? After all, Intel and other similar vendors only put a truckload of math and EE PhDs on the problem, along with myriad of people using that code for billion+ $ and 50+ year projects.

I tried that a while back. I'm smart, I know things, I know SSE, C++, assembly, even some math. After all the tweaking, out-of-box BLAS ran several times faster.

[quote]I cannot afford to finally find a bug for solving which I will have to wait until next release of some library. That happend to me once
and I almost lost my job.[/quote]All such libraries come with source code. STL is headers only.

If the problem was finding the bug, then testing is the real issue. All such software, especially if so crucial that no such failure may occur, will allocate majority (think 90%) of budget and resources to testing and validation over period of several years. Or - it simply doesn't matter and things are fixed as they break.

Whatever your experience was, you are commiting the cardinal sin. You've been frightened into choosing the absolutely worst possible choice without even looking at real problems. The problem you are trying to prevent here is not technical nor was that the cause of original problems. Management, budget, political and social issues cannot be solved using code and attempting to do so is collossal waste of time.

No disrespect intended, but the code posted is not something to put your job on the line for. The number of design issues related to reliability, safety, robustness and long-term aspects is simply inadequate to risk your job for. If it's learning experience then it's fine, tweak it, but if it's for the job, then use vector<bool> or an equivalent class provided by third-party libraries.

[quote]So if it is possible I prefer to use my own code - not so efficient and well made but easy to modify etc.[/quote]
Danger, Will Robinson, Danger. Fatal error C9731: Conflicting requirements: " as small as possible and as fast as possible" and "not so efficient and well made"
1

Share this post


Link to post
Share on other sites
[quote name='BitMaster' timestamp='1309792995' post='4831007']
[quote name='Misery' timestamp='1309792192' post='4831003']
Ok. How do i test it?
[/quote]
If it is enough to know no padding is added for *this* compiler with *these exact* settings, checking sizeof(TEightBits) should be enough. Personally, I would add a BOOST_STATIC_ASSERT for that. The check is done at compile time and automatically no matter what changes behind the scenes.

However, even if no padding is done I had the impression you have to be as speed- and time-efficient as possible. Accessing the three (or seven on x64) TEightBit instances which are not perfectly on machine word boundaries will be slower than it could be. Not horribly slower, but slower. If I had to do it with such a helper class, I would suggest
[code]
template <typename BaseType, unsigned BitCount = sizeof(BaseType) * 8>
class TMyBitHelper
{
// fill as appropriate
};

#ifdef WIN32
typedef TMyBitHelper<boost::uint32_t> MyBitHelper;
#else
typedef TMyBitHelper<boost::uint64_t> MyBitHelper;
#endif
[/code]
Not tested, but the basic idea should be clear.
[/quote]

that is quite cool solution. However I have some issues:
How can I access BitCount specifier from a class using TMyBitHelper? Do I always have to create an instance of MyBitHelper to get to this value?
And one more thing: why does
[code]
MyBitHelper Instance;
sizeof(Instance);
[/code]
sizeof() shows one byte for this Instance variable?
Shouldn't it be 4?

Thanks.
0

Share this post


Link to post
Share on other sites
[quote name='Misery' timestamp='1309800645' post='4831051']
How can I access BitCount specifier from a class using TMyBitHelper? Do I always have to create an instance of MyBitHelper to get to this value?
[/quote]
There are several ways to do that. Static fields, a static function (should decay completely with an optimizing compiler) or maybe
[code]
template <typename BaseType, unsigned BitCount = sizeof(BaseType) * 8>
class TMyBitHelper
{
enum { bits = BitCount };
// fill as appropriate
};
[/code]
I'm not sure how legal anonymous enums are, perhaps it needs a proxy name, after all it will never be used, but MyBitHelper::bits will be the specified bit count.

[quote name='Misery' timestamp='1309800645' post='4831051']
And one more thing: why does
[code]
MyBitHelper Instance;
sizeof(Instance);
[/code]
sizeof() shows one byte for this Instance variable?
Shouldn't it be 4?
[/quote]
The class as I specified it does not yet contain any data (or functions to deal with that data). Most compilers will not make classes of size 0 though and fill them up to a size of 1 byte. You need to add a member of type BaseType to start making the helper useful.
1

Share this post


Link to post
Share on other sites

[b] [url="../../user/7953-bitmaster/"]BitMaster[/url]:[/b]
Thanks a lot!! You really are a Bit Master :]
Your advices helped to solve the entire problem :]

:D
0

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0