array vs vector

Quote:

---

Originally Posted by aewarnick

I coded it that way because my if arr is an array of class pointers, I have no way to safely copy the data because the code supports pointer and non-pointer data types.

---

And if it is an array of int, it will also fail. So your code doesn't accomplish anything except potentially corrupt memory. An object is still created and/or assigned to, and will corrupt memory if any operations are done on it.

If you don't want copying, then you make these functions private.

Quote:

---

I guess the best thing to do would be to code an array that is used strictly for pointer types in this case.

---

If you just used new[] instead of malloc(), then you don't worry about POD versus non-POD, since new[] will construct x objects correctly. But ultimately, the best thing to do is just to use vector<T*>. I mean look at your own comment:

Quote:

---

//The reason I created it this way is for speed. Otherwise, every time the array needs copied for
//reasons such as removing, inserting, resizing...classes would be created and then all the members copied

---

There is absolutely no reason to code your own class given this. All you needed to do is use vector<T*> if there was a degradation in speed using a vector<T>. I'm starting to wonder if you were even using the vector<T> correctly, i.e. passing it as a parameter or returning it, since you made it clear you didn't know what const was, which is a fundamental concept in C++.

Regards,

Paul McKenzie

Quote:

---

Originally Posted by dcjr84

So I guess I should modify my stance on the subject just a tiny bit.
I definitely agree with this statement. If such a huge performance
penalty DID exist, then there should be a way to avoid it definitely.
However, as you pointed out this will be at the cost of safety.

But as a general rule of thumb, unless such a situation explicity
existed, the majority ( like 99%) of the time I believe you should always
initialize an array or vector

---

I agree. Premature optimization is the root of evil.
That's why, initialization to zero should be the default behavior.
And once, the programmer has profiled his program, he can modify his code for removing initialization, only in the critical part of the code, if, and only if, there is a vector whose initialization is critical in his code. And only that vector initialization!

Quote:

---

Originally Posted by aewarnick

"If you wanted to write a class that uses only pointers in the array"
Pointers ONLY need to be used for classes.
"you cannot use non-POD types such as aArr<std::string>"
See former response.

---

It is a premature pessimization...
In projects I wrote (I agree that no two projects are identical), usually vectors are initialized once, and accesses A LOT of times.
In that case, value semantics really speed up significantly.
And, as optimizers are better and better, this speed up is more and more significant.

Pointers can have a very high cost!

memcpy is evil... In fact, instead of using memcpy on POD types, it should be better to use a good implementation of std::copy, which calls memmove for POD types registred by a traits class template.

Quote:

---

Originally Posted by Mitsukai

0 is garbage. just like an unitialised variable, thus C++ saw no logic for this superkoko

---

0 is often a garbage, but not always.

But, the point here, is that 0 is always zero! 0==0
It is reproductible on all platforms and all the time...
That's why, if the program is perfectly determinist and runs without crashing, it will work on all platforms, in debug & release mode!
But, if it is not initialized to zero... It may work sometimes, on some platforms, not all, and crash only for some set of data, not others.... That's much harder to debug...

Quote:

---

Originally Posted by aewarnick

"If you wanted to write a class that uses only pointers in the array, you could have written a wrapper around vector<T*> instead"
Wrappers slow things down and increase binary size.

---

False!
That's the whole point of C++!
C++, unlike many other OO languages, has the principle of zero-overhead:
Mainly, encapsulation must have no cost!
That's why Bjarne Stroustrup created inline functions.
Bjarne Stroustrup wanted that nobody would ever break (or avoid) encapsluation for performance reasons... That's probably the primary aim of C with Classes.

If a compiler has no zero-overhead for an extremely simple wrapper such as:

Code:

---

class A
{
B value;
inline void Method1(int x) {value.Method1(x);}
inline float Method2(float x, float y) const {return value.Method2(x,y);}
// ...
};

---

Then (after having checked that debug mode is off, and that optimizations are turned on), you should drop your compiler, and use a better one.
Even Turbo C++ 1 had zero-overhead for inline functions... But I know that some modern compilers are not able to inline correctly a very very simple wrapper function... Don't use such stupid compiler!

Quote:

---

Originally Posted by exterminator

What is your argument? What are your points that you want to prove? To me the whole comparison between an array and a vector is meaningless. It's like comparing two people who basically have the same role (and that is storage of a collection of data) but do it quite differently with difference in ease of usability and extra services that they provide above their basic functionality. But before going any forward with this argument I would like to know what exactly are you arguing about? If you don't want initialization use std::vector::reserve (which is even suggested while using vectors and knowing approximate count of objects that you would be storing in them and doing push_backs).

---

It is not always possible... For example, if you have to pass it to a C-style function...
And, push_back are very difficult to optimize efficiently by the compiler (because there is at least one comparison, and one modification of an instance variable of the vector)...
The cost, of push_back is greater than the cost of bound checking when accessing array elements.
That's why, for vectors of POD types, std::copy(source, source_end, &v[0]) is usually faster than the same thing for a vector whose space has been reserved, and with a back inserter.

Quote:

---

Originally Posted by SuperKoko

It is a premature pessimization...
In projects I wrote (I agree that no two projects are identical), usually vectors are initialized once, and accesses A LOT of times.
In that case, value semantics really speed up significantly.
And, as optimizers are better and better, this speed up is more and more significant.

---

You're correct. What is bad is the coder who without any real measurements, writes a convoluted solution (almost usually containing pointers) that makes the code not only buggy and/or very hard to maintain, but may even be slower than if they just stuck with the original design using standard library. If there is any performance gain from this hand-optimization, it is so minimal that it is insignificant.

Optimizing code should be about using better algorithms. Of course, spotting things such as passing big objects by value, are those exceptions where a change in coding is usually done. Changes such as these are still in the context of a C++ change, which is much better than utilizing buggy 'C' techniques and pointers.

Quote:

---

Pointers can have a very high cost!

---

Less maintainability and bugs are the two things that immediately come to mind.

Quote:

---

memcpy is evil... In fact, instead of using memcpy on POD types, it should be better to use a good implementation of std::copy, which calls memmove for POD types registred by a traits class template.

---

It's amazing that if you dig a little, most, if not all of these bottlenecks that are claimed by programmers can be solved with a little judicious use of the standard library. There is very little reason to go to the low-level of pointers because of bottleneck issues -- all it needs is more education on those things in the standard library that can speed up performance.

I guess it comes down to what a programmer is used to doing to solve problems. A lot of C programmers who use C++ use (mostly ill-advised) 'C' techniques to supposedly solve problems, since they have not been exposed to what the C++ library has to offer.

Regards,

Paul McKenzie

We've had this discussion before.

In that situation you wanted to read from a file.

The point is that vector<char> buf( SOME_BIG_NUMBER ) has two flaws- one is that it will initialise all the char values to 0 and secondly because it does not know that char is a POD it is likely to set each one in turn. Of course, a clever vendor could check if the type is char and use memset on such an occasion. I don't know if any do - you'll have to look at the detail.

As for the first issue, you don't need to set the buffer because you are about to fill it. And you cannot use std::string either because it doesn't guarantee a contiguous buffer so &s[0] is not safe (might not even be of type char, it could be some nested class with operator= overloaded, often used when string is implemented COW).

So you can't use vector if that's what you want but you don't have to write your own wrapper either. You can use boost::shared_array<char> or boost::scoped_array<char>. These do nothing particularly special except handle the memory management (like shared_ptr, scoped_ptr). By "anything special" I mean you can't resize them, but in this case you probably don't want to.

boost::array is of no use here unless know the size at compile-time (and I'm assuming you don't).

Actually, boost::shared_array can be replaced by boost::shared_ptr with a custom deleter (that uses delete[]). If you don't have boost but have tr1 then use tr1::shared_ptr<char> with a deleter thus:

Code:

---

template < typename T >
struct array_deleter
{
  void operator() ( T* t ) const
  {
    (void)sizeof( T ); // check it's complete
    delete [] t;
  }
};

tr1::shared_ptr< char > ( new char[BIG_SIZE], array_deleter<char>() );

---

should do the trick.

Quote:

---

Originally Posted by Mitsukai

than the user initializes it to 0 not the vector.

---

The initialisation to 0 can be useful for word-counting.

Code:

---

typedef std::map< std::string, int > map_type;
map_type aMap;
std::string word;
std::istream & is = getStream(); // gets a valid istream reference
while ( is >> word )
{
  ++aMap[ word ];
}

---

in my own array class is unitialized unless specified.

Code:

---

                Array(const SizeT p_Size): m_Size(p_Size)
                {
                        MAlloc::Alloc(m_Data, p_Size);
                }
                       
                Array(const SizeT p_Size, const TypeT& p_Init): m_Size(p_Size)
                {
                        MAlloc::Alloc(m_Data, p_Size);
                        MAlloc::Set(m_Data, p_Size, p_Init);
                }

---

1) When modifying your code, you accidentally deleted the
initialization for Count in the "aArr(uint initCapacity)"
constructor.

2) Reset() will leak memory in some cases
(see code below for example).

3) As mentioned earlier, if you want to disable copying, you
should make the copy constructor and assignment operator
private with no implementation. That way, if a client tries to use
them, a COMPILE/LINK error will occur, instead of a RUN-TIME error.


4) You should use std::sort instead of qsort. Also, you should allow
passing a predicate to the Sort function. The Sort() function will
not work for a container of pointers.

5) Here is a sample code you can use to "benchmark" your class versus
vector. (Once you correct the Count problem)

I call a number of member fucntions for aArr and the corresponding
ones for vector. (uncomment the appropriate section and time). I did not
run it myself (your Ins() function uses aBuffer class). I would guess that
the vector version will be as faster and probably faster no matter what
compiler you use. Having said that, I wrote the code more to warn of the
dangers of simple benchmarks and then stating that one class is faster
than another. Although the code below calls a number of member functions
for aArr/vector, it is doubtful that a real application will have the
same mix of function calls as this one does. The only way to make a
comparison is to try both in a real application. In some applications aArr
will be faster, in others vector.

Code:

---

#include <vector>
#include <iostream>
#include <cmath>
#include <algorithm>

using namespace std;


int main()
{
    const int N = 250000;

    int i;

   
    /* 

                      // aArr code
    aArr<int> a(N);
    aArr<int> b(N);
    aArr<int> c(N);

    for (i=0; i<N; ++i)
    {
        a[i] = i;
        b[i] = N-i;
        c[i] = a[i] + b[i];
    }

    for (i=0; i<500; ++i)
    {
        a.Ins(100,i);
        b.Ins(100,i);
        c.Ins(100,i);
    }

    for (i=0; i<500; ++i)
    {
        a.Rem(N/10);
    }

    a.Resize(N/3);
    b.Resize(2*N);
    c.Resize(N+1000);

    a.Reset(); // memory leak
    for (i=0; i<N; ++i) a.Add(i);


    aArr<double> d(N);

    double factor =  3.14159 / d.Count;
    int cc = 0;
    for (i=0; i<N; ++i)
    {
        d[i] = sin(cc*factor);
        cc++;
    }

    d.Sort();

    */

   
    /*
   
                      // vector code
    vector<int> a(N);
    vector<int> b(N);
    vector<int> c(N);

    for (int i=0; i<N; ++i)
    {
        a[i] = i;
        b[i] = N-i;
        c[i] = a[i] + b[i];
    }

    for (i=0; i<500; ++i)
    {
        a.insert(a.begin()+100,i);
        b.insert(b.begin()+100,i);
        c.insert(c.begin()+100,i);
    }

    for (i=0; i<500; ++i)
    {
        a.erase(a.begin()+N/10);
    }

    a.resize(N/3);
    b.resize(2*N);
    c.resize(N+1000);

    a.clear();
    for (i=0; i<N; ++i) a.push_back(i);

    vector<double> d(N);

    double factor =  3.14159 / d.size();
    int cc = 0;
    for (i=0; i<N; ++i)
    {
        d[i] = sin(cc*factor);
        cc++;
    }

    sort(d.begin(),d.end());

  */
   


    return 0;
}

---

You guys post too fast. This was supposed to be a few posts up.

"since you made it clear you didn't know what const was"
I know what const is, in fact, I used it at least twice in the original code.
The original comment about const was made about the operator[]. Does he mean this:
T& operator[](uint ind) const;
In my case, it's not necessary because I'm not even thinking about modifying members there. But I'll put it in there to be thorough.

"If you don't want copying, then you make these functions private"
I did change that from that last time someone mentioned it. Thank you though.

It is of my opinion that users should not get in the habit of creating arrays of classes, rather than pointers to classes, because of the potential overhead of copying the entire object when inserting or removing items rather than a small pointer (which is the fastest data type). Sure, there are disadvantages to enforcing this, but it forces you to write faster code and code that moves less memory around.

malloc may not be much faster than new, but malloc/realloc is much faster than new.

Quote:

---

Originally Posted by aewarnick

malloc may not be much faster than new, but malloc/realloc is much faster than new.

---

untrue, malloc is only faster if new allocates objects. using new wisely makes it almost as fast as realloc or maybe in some cases faster. malloc cannot be used to allocate objects, new does that. though imho its wiser to use malloc for PODs but this shuld be written by an allocator not by the array class.
malloc cannot be compared with new.

Quote:

---

Originally Posted by aewarnick

It is of my opinion that users should not get in the habit of creating arrays of classes, rather than pointers to classes, because of the potential overhead of copying the entire object when inserting or removing items rather than a small pointer (which is the fastest data type). Sure, there are disadvantages to enforcing this, but it forces you to write faster code and code that moves less memory around.

---

But that is a vector<T*>, as I've been pointing out. There is no need to code something from scratch when all of this is available.

Quote:

---

malloc may not be much faster than new, but malloc/realloc is much faster than new.

---

This is false, or at the very least, based on faulty reasoning.

What if new is written in terms of malloc()? How could malloc be faster()?

What if the malloc() uses a poor heap manager, and operator new() does not use this poor heap manager, but some other allocator? new does not have to use the same memory manager as malloc(). You can overload operator new to get memory from an already allocated pool of memory at the beginning of the program, and all a call to "new" needs to do is return a pointer to the user, and not physically have to allocate anything.

So operator new[] can be adjusted, changed, etc., by the programmer to suit their needs, something that doesn't exist in the 'C' world for malloc() (unless of course you physically replace the compiler's heap manager by linking in your own heap manager).

And add to the fact that there is no way to create non-POD objects just with malloc(). Hopefully you aren't the ones doing this, because I have seen some surprised C programmers scratch their heads wondering why their C++ program blows up when they use malloc on things like this:

Code:

---

#include <stdlib.h>
struct foo
{
  std::string s;
};

int main()
{
    foo *pf = (foo *)malloc(10 *sizeof(foo));
    free(pf);
}

---

thinking that they have created 10 foo objects when in fact they haven't.

So saying that malloc() is faster than new or comparing malloc to new is not valid.

Regards,

Paul McKenzie

malloc is ONLY normally a little faster than new. realloc however blows new out of the water. I just did a bench marking test to prove it. A little code:

PHP Code:

---

void NewDelete_Realloc()
{
    char* p;
    p= 0;
    ResetAndStartTimer("Realloc");
    for(uint i= 0; i < loops; ++i)
    {
        //p=(char*)malloc(i*sizeof(char)); free(p);
        p= (char*)realloc(p, i*sizeof(char));
    }
    free(p);
    StopAndLog();
    p= 0;
    ResetAndStartTimer("NewDelete");
    for(uint i= 0; i < loops; ++i)
    {
        p= new char[i];
        delete[]p;
    }
    StopAndLog();
} 


---

loops==1000000
All optimisations on, building with gcc
realloc: .375
new/delete: 4.25

There is no way new can be faster than realloc because new will always allocate "new" memory and then copy the old to the "new". realloc only copies when it can't resize.

You can simulate the same with placement new.

Quote:

---

Originally Posted by aewarnick

malloc is ONLY normally a little faster than new. realloc however blows new out of the water. I just did a bench marking test to prove it.

---

How are you going to use realloc() on non-POD types? In the real world of C++, these are the types that exist. Unless you use placement-new, realloc() is not to be used in a C++ class that can potentially contain non-POD types.

Quote:

---

There is no way new can be faster than realloc because new will always allocate "new" memory and then copy the old to the "new". realloc only copies when it can't resize.

---

Wrong. You are only assuming how realloc() and new[] are supposed to work -- it depends on the implementation that you're using. For gcc it is one thing -- for Visual C++ it may be another, for C++ Builder it could be another, etc.

Nowhere in the 'C' or C++ specification does it state how realloc() or new[] are supposed to work with respect to the memory allocation scheme. It is perfectly viable for realloc() to always physically get memory each and every time it's called.

Answer this question -- how does realloc() know it doesn't need to resize()? It doesn't. What does know is the heap manager. Again, it all depends on the implementation of the free-store for new[] and the heap manager for malloc and realloc as to how fast allocations are done.

You can have an optimized free-store implementation for new[] that is very fast, and a god-awful heap manager implementation for malloc() or realloc(). that is very slow. Again, the big difference is that with new[], you have the freedom of changing the allocation scheme by overloading, with malloc() or realloc(), you're stuck. Someone could rewrite the allocator for new[] to take advantage of the fact that resizing will be done.

Regards,

Paul McKenzie

Quote:

---

The original comment about const was made about the operator[]. Does he mean this:
T& operator[](uint ind) const;

---

Not quite, aewarnick, it should be more like:

Code:

---

const T& operator[](uint ind) const;

---

Quote:

---

In my case, it's not necessary because I'm not even thinking about modifying members there.

---

By providing a non-const version of operator[], you provide an interface by which the data in the array may be modified. This can be a Good Thing, unless you did it without even realising what you have done.

Quote:

---

I know what const is, in fact, I used it at least twice in the original code.

---

You might know what it is, but I find it hard to believe that you know how (or how important it is) to be const correct.

For example, you write your copy constructor as:

Code:

---

aArr(aArr &arr)

---

In view that the object being copied from may be const, and since the copying here does not change what is being copied from, you should write it as:

Code:

---

aArr(const aArr &arr)

---

declaring a variable to be static initializes it to zero doesn't it, then what happens if declare an array to be static... that would be possible at compile time but can i declare a dynamic array to be static??

i know it would be easier to try... but right now i don't have access to a compiler..

regards