Jump to content

  • Log In with Google      Sign In   
  • Create Account

We're offering banner ads on our site from just $5!

1. Details HERE. 2. GDNet+ Subscriptions HERE. 3. Ad upload HERE.


C++ array resize


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
23 replies to this topic

#1 Misery   Members   -  Reputation: 317

Like
0Likes
Like

Posted 04 July 2011 - 02:47 AM

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

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 :]

Sponsor:

#2 BitMaster   Crossbones+   -  Reputation: 4261

Like
1Likes
Like

Posted 04 July 2011 - 02:56 AM

I would use std::copy instead of a homemade loop.

#3 wqking   Members   -  Reputation: 756

Like
2Likes
Like

Posted 04 July 2011 - 03:13 AM

No need to allocate another new array, that works fine.
But, why not std::vector?

http://www.cpgf.org/
cpgf library -- free C++ open source library for reflection, serialization, script binding, callbacks, and meta data for OpenGL Box2D, SFML and Irrlicht.
v1.5.5 was released. Now supports tween and timeline for ease animation.


#4 Misery   Members   -  Reputation: 317

Like
0Likes
Like

Posted 04 July 2011 - 03:14 AM

No need to allocate another new array, that works fine.
But, why not std::vector?


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

Thanks gyus for answers :]]

#5 NightCreature83   Crossbones+   -  Reputation: 2935

Like
3Likes
Like

Posted 04 July 2011 - 04:02 AM


No need to allocate another new array, that works fine.
But, why not std::vector?


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

Thanks gyus for answers :]]

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.
Worked on titles: CMR:DiRT2, DiRT 3, DiRT: Showdown, GRID 2, Mad Max

#6 rip-off   Moderators   -  Reputation: 8527

Like
1Likes
Like

Posted 04 July 2011 - 04:07 AM

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.

#7 BitMaster   Crossbones+   -  Reputation: 4261

Like
2Likes
Like

Posted 04 July 2011 - 04:11 AM

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

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 bitset/dynamic_bitset?

#8 Misery   Members   -  Reputation: 317

Like
0Likes
Like

Posted 04 July 2011 - 04:30 AM

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:

#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



#9 King Joffrey   Members   -  Reputation: 150

Like
1Likes
Like

Posted 04 July 2011 - 04:46 AM

No need to allocate another new array, that works fine.

I'm assuming the existing array is populated and used prior to resizing (else it wouldn't be a resize).

#10 BitMaster   Crossbones+   -  Reputation: 4261

Like
0Likes
Like

Posted 04 July 2011 - 05:35 AM

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

#11 NightCreature83   Crossbones+   -  Reputation: 2935

Like
2Likes
Like

Posted 04 July 2011 - 06:58 AM

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


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.
Worked on titles: CMR:DiRT2, DiRT 3, DiRT: Showdown, GRID 2, Mad Max

#12 BitMaster   Crossbones+   -  Reputation: 4261

Like
0Likes
Like

Posted 04 July 2011 - 07:04 AM

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.

#13 Misery   Members   -  Reputation: 317

Like
0Likes
Like

Posted 04 July 2011 - 07:07 AM

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.

#14 BitMaster   Crossbones+   -  Reputation: 4261

Like
1Likes
Like

Posted 04 July 2011 - 07:55 AM

And padding? I don't think it should happen here, because I have exactly 8 bytes. Char ptr and integer both have 4 bytes.

I'm not worried about padding of TBitArray. Possible padding of TEightBits worries me and you cannot see that by doing a sizeof(TBitArray).

#15 rip-off   Moderators   -  Reputation: 8527

Like
1Likes
Like

Posted 04 July 2011 - 08:23 AM

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.

#16 Misery   Members   -  Reputation: 317

Like
0Likes
Like

Posted 04 July 2011 - 08:34 AM


And padding? I don't think it should happen here, because I have exactly 8 bytes. Char ptr and integer both have 4 bytes.

I'm not worried about padding of TBitArray. Possible padding of TEightBits worries me and you cannot see that by doing a sizeof(TBitArray).


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

#17 Misery   Members   -  Reputation: 317

Like
0Likes
Like

Posted 04 July 2011 - 08:41 AM

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.


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 :]

#18 BitMaster   Crossbones+   -  Reputation: 4261

Like
0Likes
Like

Posted 04 July 2011 - 09:07 AM



And padding? I don't think it should happen here, because I have exactly 8 bytes. Char ptr and integer both have 4 bytes.

I'm not worried about padding of TBitArray. Possible padding of TEightBits worries me and you cannot see that by doing a sizeof(TBitArray).


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


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.

#19 Misery   Members   -  Reputation: 317

Like
0Likes
Like

Posted 04 July 2011 - 09:09 AM




And padding? I don't think it should happen here, because I have exactly 8 bytes. Char ptr and integer both have 4 bytes.

I'm not worried about padding of TBitArray. Possible padding of TEightBits worries me and you cannot see that by doing a sizeof(TBitArray).


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


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.


Ok. How do i test it?

#20 BitMaster   Crossbones+   -  Reputation: 4261

Like
1Likes
Like

Posted 04 July 2011 - 09:23 AM

Ok. How do i test it?

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
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
Not tested, but the basic idea should be clear.




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS