(Sorry, reply above was to Ujl, post #47)
Printable View
(Sorry, reply above was to Ujl, post #47)
Only if the objects allocated with new are non-POD types should you not use memcpy().Quote:
Originally Posted by Mitsukai
With POD types, memcpy() is safe.
Regards,
Paul McKenzie
i know but with an array object you do not know if it is a POD or not.Quote:
Originally Posted by Paul McKenzie
That's the problem.Quote:
Originally Posted by Graham
Assume you have to connect your program with an old unsafe C library and you have to call a function which "return" a string, in that way:
The C++ programmer passes a big amount of memory (16KB for example), because he wants to avoid buffer overflows.Code:void OldUglyCFunction(char* UserAllocatedBuffer); /* the buffer must be LARGE enough... and there is no way to know how many bytes must be allocated */
Here, using an initialized std::vector<char>(16384) may reduce performances by a HUGE factor!
Using a static buffer for the first copy, is not an option in multithreaded environments... And, using TLS would consume much memory if there are a lot of threads, and be overcomplicated...
It may be negligible... But when it is not, there should be a not-too-ugly mean to avoid this overhead...Quote:
Originally Posted by dcjr84
I think Mitsukai's point here is that zero or default initialised elements may not necessarily be any better than garbage values from uninitialised elements when one does such calculations. For the calculations to be correct, the input values have to correct, and so one must either initialise or assign (directly or indirectly) the correct values to the elements used in calculation.Quote:
And even if it did reduce performance; I would rather
have a program that runs at 50% speed but is guaranteed to
an extremely high percentage to never make a mistake
in calculation because it might at some point use an unintialized
garbage value from an array or vector, than have one that runs
at 100% speed but the results might be incorrect at some point
because there is the possibility it might use an uninitialized element
from an array or vector.
However, I think that std::vector is flexible enough such that Mitsukai's worries are unfounded.
Does the performance bottleneck in your code lie in this part of the code?Quote:
Do you see any way to make that faster using vector?
In the end, you guys are going to do whatever you feel is right and soQuote:
Then, you should not program in C++.
There are lots of much safer languages (at the cost of a small performance overhead).
will I. For me, that means always initializing an array to some known
value to promote determinism. Unless, for some extreme reason which I
highly doubt would arise, I had to write a program which absolutely
could not spare the extra CPU cycles to initialize what I needed.
Cheers :)
By the way, no bad blood here. I always enjoy a good
constructive criticism conversation :)
Too much, too fast!
I guess I should have made this more clear in my code:
//use pointers instead of classes when using malloc.
I put that there because I knew that my class could not handle aArr<class1> arr;
but can handle aArr<class1*> arr;
That's just something you have to remember when using it.
Keep in mind that the code is not finished yet and I should have mentioned that when I posted it.
But it costs later when POD gets substituted with non-POD. IMHO it's simplier to write code which handles both cases.Quote:
Originally Posted by Paul McKenzie
Right, you should always assume that when you code these things to assume that you are working with both non-POD and POD types.Quote:
Originally Posted by RoboTact
Regards,
Paul McKenzie
The sentence "Then, you should not program in C++." was not to be taken too litterally...Quote:
Originally Posted by dcjr84
You know, nowadays determinism can really be a Good Thing(TM).
I meant that there are really very good determinist languages, having performances very close to C++ (unlike in 1985).
OCaml is probably the language having the best performances after C and C++.
So, OCaml is better than C++ except for:
- A few percents of performances...
- The (perhaps) unreachable level of expressivity and power of C++...
- A few other Good Things of C++ which makes it suitable for system programmation (such as an efficient and natural to use RAII).
- Really usable for embedded systems
But, if the point is stability and determinism... C++ is not the ideal tool.
C, C++ and Fortran are not good for that.
IMHO, it is a Good Idea to improve C++ determinism... But, if there is any performance tradeoff, there must be an explicit way to avoid the penalty, at the cost of safety.
For instance, it could be a good idea to default-initialize *all* variables, provided that there is a mean to create uninitialized data:
For instance:
C++ must be able to replace C in any and each way... Otherwise, we would see programs containing C modules (for critical code) and C++ modules (for higher level code).Code:class C {
public:
int a; /* a would be initialized to zero, even if constructors doesn't initialize it explicitly */
C():a(?) /* except when a special "constructor" would be invoked */
{
}
};
Until now, I think that C++ can fully replace old C.
Instead of writing a new class from scratch... It could be much easier to modify existing code (there are good Open Source STLs).Quote:
Originally Posted by aewarnick
It would avoid the pain of debugging, and the fear of the last(s) bug(s)...
0 is garbage. just like an unitialised variable, thus C++ saw no logic for this superkoko
So I guess I should modify my stance on the subject just a tiny bit.Quote:
IMHO, it is a Good Idea to improve C++ determinism... But, if there is any performance tradeoff, there must be an explicit way to avoid the penalty, at the cost of safety.
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 think you'll be much happier with this. Although, now I remember why I never coded a copy constructor or assignment operator: Because I couldn't, and still can't without sacrificing speed. I have now handled the copy constructor and assignment operator by coding an error message if it is used. Ideally, I'd like to have the compiler halt if that section of code is needed...Is that possible?
The const thing you were talking about, I don't know what you mean.
The public members that should be protected are still public. I'll change that later. I knew when I coded it that way that I should not have...but I did it anyway.
PHP Code://About 1.5 times faster than vector
//USE POINTERS instead of classes.
//NEVER do this: aArr<class1> arr. Do this: aArr<class1*> arr
//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
//over.
//NEVER assign another aArr to this class with =. Copy the data by looping instead.
template < typename T >
class aArr
{
protected:
uint capacity;
public:
//Both should be protected:
T* _Items;
uint Count;
aArr()
{
Reset();
}
aArr(uint initCapacity)
{
Reset();
capacity= initCapacity;
_Items= (T*)malloc(initCapacity*sizeof(T));
}
aArr(aArr &arr)
{
*this= arr;
}
/*aArr(const T &item) //ambiguous when item is uint
{
Reset();
Add(item);
}*/
~aArr()
{
Del();
}
void Del(uint initCapacity= 0)
{
if(_Items)
{
free(_Items); //free is 2x faster than delete[]
_Items= 0;
}
Count= 0; capacity= 0;
}
void Reset()
{
_Items= 0;
Count= 0;
capacity= 0;
}
//Unsafe to code this because data that class pointers point to would need memcpy'd.
void operator=(aArr& arr)
{
MB("Fatal Error!\n\naArr: cannot assign directly (arr1=arr2). Copy Manually.");
throw "aArr=";
}
T& operator[](uint ind)
{
return _Items[ind];
}
T& Ind(uint ind)
{
return _Items[ind];
}
void Add(const T& d)
{
if(Count >= capacity)
Resize(Count < 10 ? 20 : Count*1.5f);
memcpy(&_Items[Count], &d, sizeof(T));
++Count;
}
void Ins(uint where, aArr < T* > &arr)
{
if(!arr.Count) return;
if(!Count || where >= Count)
{
for(uint i= 0; i < arr.Count; ++i)
Add(arr[i]);
return;
}
if(Count+arr.Count >= capacity)
Resize(Count < 10 ? 20+arr.Count : Count*1.5f +arr.Count);
uint sT= sizeof(T), sTemp= (Count-where)*sT;
aBuffer buf(sTemp);
//T* temp= (T*)malloc(sTemp);
memcpy(buf.Ptr(), &_Items[where], sTemp);
memcpy(&_Items[where], arr[0], sT*arr.Count);
memcpy(&_Items[where+arr.Count], buf.Ptr(), sTemp);
//free(temp);
Count += arr.Count;
}
void Ins(uint where, const T& d)
{
//aArr<T*> arr; arr.Add(&d);
//Ins(where, arr);
//return;
if(!Count || where >= Count)
{
Add(d);
return;
}
if(Count >= capacity)
Resize(Count < 10 ? 20 : Count*1.5f);
uint sT= sizeof(T), sTemp= (Count-where)*sT;
aBuffer buf(sTemp);
//T* temp= (T*)malloc(sTemp);
memcpy(buf.Ptr(), &_Items[where], sTemp);
memcpy(&_Items[where], &d, sT);
memcpy(&_Items[where+1], buf.Ptr(), sTemp);
//free(temp);
++Count;
}
void Rem(aArr < uint > & arr)
{
T* temp= _Items;
capacity= Count;
_Items= (T*)malloc(capacity*sizeof(T));
uint count= Count;
Count= 0;
uint removed= -1;
for(uint i= 0; i < count; ++i)
{
for(uint j= 0; j < arr.Count; ++j)
{
if(i == arr[j])
{
removed= i;
break;
}
}
if(removed == -1)
{
Add(temp[i]);
}
else
{
removed= -1;
}
}
free(temp);
}
void Rem(uint ind)
{
aArr < uint > arr(1);
arr.Add(ind);
Rem(arr);
}
void RemAll()
{
Del();
}
void Resize(uint newSize)
{
capacity= newSize;
_Items= (T*)realloc(_Items, newSize*sizeof(T));
if(capacity < Count)
Count= capacity;
}
private:
static int _ascending(const void *v1, const void *v2)
{
if(*((T*)v1) > *((T*)v2)) return 1;
if(*((T*)v1) < *((T*)v2)) return -1;
return 0;
}
static int _descending(const void *v1, const void *v2)
{
if(*((T*)v1) > *((T*)v2)) return -1;
if(*((T*)v1) < *((T*)v2)) return 1;
return 0;
}
public:
void Sort(char A_D= 'A')
{
if(A_D == 'A') qsort(&_Items[0], Count, sizeof(T), &_ascending);
else qsort(&_Items[0], Count, sizeof(T), &_descending);
return;
const int tSize= sizeof(T);
void* hold[tSize];
for(int i= 0; i < Count; ++i)
{
for(int j= 0; j < Count-1; ++j)
{
if((A_D == 'A' && _Items[j] > _Items[j+1]) || (A_D == 'D' && _Items[j] < _Items[j+1]))
{
Swap(&_Items[j], &_Items[j+1], tSize, &hold);
}
}
}
}
aStr ToStr()
{
aStr s;
for(uint i= 0; i < Count; ++i)
{
s= s << _Items[i] << "\n";
}
return s;
}
};
Not really. Much happier using vector.Quote:
Originally Posted by aewarnick
What does a copy constructor have to do with speed? If a class never gets copied, the copy constructor doesn't get called.Quote:
Although, now I remember why I never coded a copy constructor or assignment operator: Because I couldn't, and still can't without sacrificing speed.
You make the copy constructor and assignment operator private. Also, you have the wrong prototype for your assignment operator:Quote:
I have now handled the copy constructor and assignment operator by coding an error message if it is used. Ideally, I'd like to have the compiler halt if that section of code is needed...Is that possible?
and I don't see a copy constructor in what you posted.Code:aArr& operator = (const aArr& arr)
Const-correctness should be known by any programmer attempting to code a class such as this.Quote:
The const thing you were talking about, I don't know what you mean.
All you did was attempt to simulate a vector<T*>. Never quote numbers without showing what you did to test.Quote:
About 1.5 times faster than vector
Any competent C++ programmer who knows how to use vector will judge for themself whether to use objects or pointers in a vector. What if I wanted to use your class and I want to make copies? It isn't unreasonable for this to occur.Quote:
//reasons such as removing, inserting, resizing...classes would be created and then all the members copied
What if the class is tiny, say two char members? Why shouldn't the programmer not make copies of these? It isn't large and should not have a performance penalty.
It is not a good idea to force what you think is good on a programmer -- let the programmer decide what they want to do.
Why don't you provide a function to do this instead of making the user have to code their own function?Quote:
//NEVER assign another aArr to this class with =. Copy the data by looping instead.
Also, unless you use some template magic, you cannot use non-POD types such as aArr<std::string>, and have your code not have undefined behavior due to the memcpy().
Basically, you're attempting to reinvent the wheel of a vector<T*> (note the T*, not T) where T is non-POD, or a vector<T> where T is a POD type. If a C++ programmer wants an array of pointers, they have vector<T*>.
Also, you still are missing the second operator[] prototype I mentioned. It has everything to do with the const thing you do not know about.
Bottom line -- there are just too many things wrong and other issues with the class you posted. If you wanted to write a class that uses only pointers in the array, you could have written a wrapper around vector<T*> instead of creating your own class from scratch.
Also, what is Sort() doing in the class?
I'll be honest with you:
It takes a seasoned C++ programmer to write classes such as this correctly. Just because it seems "in your skill set" to do something like this, it really isn't unless you are an experienced C++ programmer (and the standard library implementation is more than likely written by ace C++ programmers).
Regards,
Paul McKenzie
"What does a copy constructor have to do with speed?"
Nothing. But I cannot code it unless I stop using memcpy and do the whole class the C++ way rather than C.
"Why don't you provide a function to do this instead of making the user have to code their own function?"
See first response.
"Also, what is Sort() doing in the class?"
Convenience. If the user want to sort data, they can. Say they have an array of integers.
"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.
"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.
"I don't see a copy constructor in what you posted"
It is there.
"make the copy constructor and assignment operator private"
Why? The user can't access them directly.
I don't understand. You are mixing the 'C' way with C++ classes? What's wrong with using the proper C++ techniques? i.e. operator new[], or use placement-new(), not malloc() and memcpy(). Please don't say "they're slower" -- they are not. Mixing 'C' techniques in C++ is a recipe for disaster.Quote:
Originally Posted by aewarnick
No. Provide a function that the user must call themselves to do the copy. Look at the MFC CArray for example. There is a CopyData() function that is never called by the CArray class. It is only a convenience function provided to the user of the class if they want to copy the data.Quote:
"Why don't you provide a function to do this instead of making the user have to code their own function?"
See first response.
And what is wrong with std::sort() to do this? That's what std::sort() is there for. Also, the sort is totally useless if they provided pointers. It won't sort their data, only the pointers. Also std::sort() on many implemetations outperforms qsort().Quote:
"Also, what is Sort() doing in the class?"
Convenience. If the user want to sort data, they can. Say they have an array of integers.
And how do you enforce that? This is the restriction that I'm referring to. Your code will exhibit undefined behavior.Quote:
"If you wanted to write a class that uses only pointers in the array"
Pointers ONLY need to be used for classes.
That still doesn't answer how you enforce this, except to write in a comment that it can't be used.Quote:
"you cannot use non-POD types such as aArr<std::string>"
See former response.
Again, you are stating what will slow things down without any concrete evidence. And I don't want to go into the "binary size" issue. I've proven a few times in this forum and in other forums that this is a myth, at least for the Visual C++ 6.0 compilers.Quote:
"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.
But the big picture is why can't someone just use a vector<T*> instead of your class? It works already and doesn't have all of these problems, and they are using pointers.
The prototype is incorrect, just as the assignment operator is.Quote:
"I don't see a copy constructor in what you posted"
It is there.
You asked how to make sure that copies and assignments are not done, and how do you make the compiler catch these operations. The answer is to make these functions private. This is explained in any good C++ book on class design -- if you don't want copies or assignment, make these functions private.Quote:
"make the copy constructor and assignment operator private"
Why? The user can't access them directly.
And your current implementations, save for the wrong prototype, can be accessed by the user. Their public, so of course the user has access to them. The copy constructor is also faulty. What do you think happens here?:
It calls your assignment operator. But your assingment operator doesn't assign -- it throws an exception.Code:aArr(aArr &arr)
{
*this= arr;
}
Regards,
Paul McKenzie
aewarnick, you code is really buggy, and alo your not using an allocater, basicly meaning users cannot make their own allocation methods. i have written an array class and i have learn alot from poeple on codeguru.
Your sort function is very slow. Your insert function is very slow. Standards are doing this faster than you. Though imho insert programming is very bad. an array should be resized respectivly.
Zero is not garbage. Consider this case - you have several new bank accounts - they all start with the same account balance - that is 0. But they may change at different relative rates. It is significant. It signals the "beginning" in many practical cases.Quote:
Originally Posted by Mitsukai
than the user initializes it to 0 not the vector.Quote:
Originally Posted by exterminator
The Sort funk uses qsort and then returns. How is that very slow?
std::sort is parameterized on comparison function, so comparison may be inlined in sort algorithm.Quote:
Originally Posted by aewarnick
Read the comments again. The std::sort() outperforms qsort() due to the compiler having better optimization strategies with std::sort() than qsort().
Also, usage of qsort() is discouraged in a C++ program, just like memcpy() is discouraged for doing copies of T. The qsort() knows nothing about C++ non-POD types, therefore dangerous to use -- same thing with memcpy().
If you want to code in 'C', then you can do that. The issue is that you want to code in C++ (i.e. use templates, create classes, etc.) and use 'C' techniqes to accomplish this. This is wrong in many respects already pointed out here.
Regards,
Paul McKenzie
"The copy constructor is also faulty. What do you think happens here?:
Code:
aArr(aArr &arr)
{
*this= arr;
}
It calls your assignment operator. But your assingment operator doesn't assign -- it throws an exception"
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. I guess the best thing to do would be to code an array that is used strictly for pointer types in this case.
I agree that my Ins function is a little slow and can easily be optimized, but I wouldn't say it's very slow.
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).Quote:
Originally Posted by Mitsukai
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.Quote:
Originally Posted by aewarnick
If you don't want copying, then you make these functions private.
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:
I guess the best thing to do would be to code an array that is used strictly for pointer types in this case.
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++.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
Regards,
Paul McKenzie
I agree. Premature optimization is the root of evil.Quote:
Originally Posted by dcjr84
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!
It is a premature pessimization...Quote:
Originally Posted by aewarnick
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.
0 is often a garbage, but not always.Quote:
Originally Posted by Mitsukai
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...
False!Quote:
Originally Posted by aewarnick
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:
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.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);}
// ...
};
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!
It is not always possible... For example, if you have to pass it to a C-style function...Quote:
Originally Posted by exterminator
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.
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.Quote:
Originally Posted by SuperKoko
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.
Less maintainability and bugs are the two things that immediately come to mind.Quote:
Pointers can have a very high cost!
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.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.
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:
should do the trick.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>() );
The initialisation to 0 can be useful for word-counting.Quote:
Originally Posted by Mitsukai
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.
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.Quote:
Originally Posted by aewarnick
malloc cannot be compared with new.
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:
Originally Posted by aewarnick
This is false, or at the very least, based on faulty reasoning.Quote:
malloc may not be much faster than new, but malloc/realloc is much faster than new.
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:
thinking that they have created 10 foo objects when in fact they haven't.Code:#include <stdlib.h>
struct foo
{
std::string s;
};
int main()
{
foo *pf = (foo *)malloc(10 *sizeof(foo));
free(pf);
}
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:
loops==1000000PHP 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();
}
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.
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:
Originally Posted by aewarnick
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.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.
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
Not quite, aewarnick, it should be more like:Quote:
The original comment about const was made about the operator[]. Does he mean this:
T& operator[](uint ind) const;
Code:const T& operator[](uint ind) const;
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:
In my case, it's not necessary because I'm not even thinking about modifying members there.
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.Quote:
I know what const is, in fact, I used it at least twice in the original code.
For example, you write your copy constructor as:
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(aArr &arr)
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
int* a=new int[100000000];
Are you sure that the os allocate 100000000 integer for you?
if not it will take about 0.000 s
and I test that it takes 0.5s if the os(winxp,vc 6.0) allocate so many space.
Your code will refuse to compile if you did this:Quote:
Originally Posted by aewarnick
That's why you need the other overload.Code:#include <iostream>
//...
void foo( const aArr<int>& a )
{
std::cout << a[0]; // error -- operator [] is non-const
}
Regards,
Paul McKenzie
If if returns without throwing bad_alloc then yes, I am sure.Quote:
Originally Posted by sunshinesky
In release mode?Quote:
if not it will take about 0.000 s
and I test that it takes 0.5s if the os(winxp,vc 6.0) allocate so many space.
Paul, you are absolutely right about this:
void foo( const aArr<int>& a )
{
std::cout << a[0]; // error -- operator [] is non-const
}
And now I understand why. Thanks! I learned something today!
Someone mentioned that the Ins function was very slow and they are right. I was under the impression that memcpy copied data from begin to end but I did some tests and it LOOKS like it copies from end to begin.
Am I correct about this?
Should it matter? It may copy all data or part of data. Reverce order is most natural algorithm to move part of array in-place...
It does matter. Think about it in terms of how inserting data works. I need to move memory to the right to accomodate for inserted data:
stringy v("abcd");
v.Insert(0, "C");
I'm inserting one character which means all the data must move right one.
From begin to end bcd would all become a's because they would be over-written.
From end to begin, there is an empty spot at the end and therefore, not data is over-written.
*Do you imagine how complex your cardiovascular system is?* :lol:
There is a problem. It does not work correctly unless sizeof(T) is 1 or 2. It would seem that memcpy is not copying backward if T is an int (size 4) because the data is over-written just like I said above. Why is this?
PHP Code:void Ins(uint where, const T& d)
{
if(!Count || where >= Count)
{
Add(d);
return;
}
if(Count >= capacity)
Resize(Count < 10 ? 20 : Count*1.5f);
memcpy(&_Items[where+1], &_Items[where], (Count-where)*sizeof(T));
memcpy(&_Items[where], &d, sizeof(T));
/*aBuffer buf(sTemp);
//T* temp= (T*)malloc(sTemp);
memcpy(buf.Ptr(), &_Items[where], sTemp);
memcpy(&_Items[where], &d, sT);
memcpy(&_Items[where+1], buf.Ptr(), sTemp);
//free(temp);*/
++Count;
}
aArr<short> arr(4);
arr.Add('a'); arr.Add('b'); arr.Add('c'); arr.Add('d');
arr.Ins(0, 'C');
MB(arr.ToStr());
//Output: 67, 97, 98, 99, 100
//When short is int: 67, 97, 97, 97, 97
I found the solution: memmove.
I still don't understand why char and short worked fine though. Can anyone explain that?