I've written a vector-like class in C++ and I'm trying to figure out issues in efficiency. When I use clock() to measure the time taken to emplace objects, std::vector outperforms this class until emplacing more than 1000 objects. For simple types, the performance is much more evenly matched.
The test I've been running is:
#include <time.h>
#include <vector>
#include <stdio.h>
#include "TestObject.h"
//TestObject is a barebones class I used to test for memory leaks.
//It is move constructable, copy constructable, and has equivalent
//operator= overloads
#include "ArrayList.h"
#define LOOP 1000
#define OUTERLOOP 1
//if OUTERLOOP > 1, the measured efficiency of Array is much better
//than std::vector for some reason. As long as it is equal to 1,
//ArrayList is measured as much slower than std::vector until enough
//objects are emplaced. ie LOOP is a big enough number
int main(){
int x = 0, w = 0, xAvg = 0, wAvg = 0;
for(int j = 0;j < OUTERLOOP;j++){
ArrayList<Obj> a;
std::vector<Obj> v;
x = clock();
for(int i = 0;i < LOOP;i++){
a.Emplace(i);
}
x = clock() - x;
w = clock();
for(int i = 0;i < LOOP;i++){
v.emplace_back(i);
}
w = clock() - w;
xAvg += x;
wAvg += w;
}
xAvg /= OUTERLOOP;
wAvg /= OUTERLOOP;
printf("Array: %d\nVector: %d\n", xAvg, wAvg);
}
Now here's the ArrayList class. It doesn't conform to container requirements, I know. I'm just wondering where the efficiency issue is.
#ifndef ARRAYLIST_3_H
#define ARRAYLIST_3_H
#define ARRAYLIST_DEBUG_OUTPUT 0
#include <stdio.h>
#include <new>
#include "Exceptions.h"
typedef unsigned int uint;
typedef unsigned long ulong;
template<class T>
class ArrayList
{
private:
T* _buffer;
ulong _length; //keeps track of num elements
ulong _capacity; //keeps track of allocated memory
void _InitBuffer(ulong size){
_buffer = (T*)(::operator new(sizeof(T) * size));
_capacity = size;
}
void _IncreaseBuffer(ulong newSize){
if(_length == 0){
this->_InitBuffer(1);
}
else{
T* data = (T*)(::operator new(sizeof(T) * newSize));
for(int i = 0;i < _length;i++){
::new(&data[i]) T((T&&)_buffer[i]);
_buffer[i].~T();
}
::operator delete(_buffer);
_buffer = data;
_capacity = newSize;
}
}
public:
ArrayList() : _buffer(NULL),
_length(0),
_capacity(0){}
ArrayList(ulong initCap) : _length(0),
_capacity(initCap)
{
_buffer = (initCap == 0) ? NULL : (T*)(::operator new(sizeof(T) * initCap));
}
ArrayList(const ArrayList& a) : _length(a._length),
_capacity(a._capacity)
{
_buffer = (a._capacity == 0) ? NULL : (T*)(::operator new(sizeof(T) * a._capacity));
for(int i = 0;i < _length;i++){
::new(&_buffer[i]) T(a._buffer[i]);
}
}
ArrayList(ArrayList&& a)noexcept : _buffer(a._buffer),
_length(a._length),
_capacity(a._capacity)
{
a._buffer = NULL;
a._length = 0;
}
~ArrayList(){
for(int i = 0;i < _length;i++){
_buffer[i].~T();
}
::operator delete(_buffer);
}
T& operator[](ulong index){
if(index >= _length){
fprintf(stderr, "%-18pIndex Out of Bounds Exception thrown in ArrayList::operator[](ulong index)!\n", this);
fprintf(stderr, "_length = %lu\nRequest = %lu\n", _length, index);
throw IndexOutOfBoundsException();
}
return _buffer[index];
}
ArrayList& operator=(const ArrayList& a){
T* data = (a._capacity == 0) ? NULL : (T*)(::operator new(sizeof(T) * a._capacity));
for(int i = 0;i < a._length;i++){
::new(&data[i]) T(a._buffer[i]);
}
for(int i = 0;i < _length;i++){
_buffer[i].~T();
}
::operator delete(_buffer);
_buffer = data;
_length = a._length;
_capacity = a._capacity;
return *this;
}
ArrayList& operator=(ArrayList&& a)noexcept{
_buffer = a._buffer;
a._buffer = NULL;
_length = a._length;
a._length = 0;
_capacity = a._capacity;
return *this;
}
template<class U>
void Push(U&& u){
if(_length == _capacity){
this->_IncreaseBuffer(_length * 2);
}
::new(&_buffer[_length++]) T((U&&)u);
}
template<class... Args>
void Emplace(Args&&... args){
if(_length == _capacity){
this->_IncreaseBuffer(_length * 2);
}
::new(&_buffer[_length++]) T((Args&&)args...);
}
template<class... Args>
void EmplaceAt(ulong pos, Args&&... args){
if(pos > _length){
fprintf(stderr, "%-18pIndex Out of Bounds Exception thrown in ArrayList::EmplaceAt(ulong pos, Args&&... args)!\n", this);
fprintf(stderr, "_length = %lu\nRequest = %lu\n", _length, pos);
throw IndexOutOfBoundsException();
}
else if(_length == _capacity){
this->_IncreaseBuffer(_length * 2);
}
if(pos == _length){
::new(&_buffer[_length++]) T((Args&&)args...);
}
else{
::new(&_buffer[_length]) T((T&&)_buffer[_length - 1]);
for(int i = _length - 1;i > pos;i--){
_buffer[i] = (T&&)_buffer[i - 1];
}
_buffer[pos] = (T&&)T((Args&&)args...);
_length++;
}
}
template<class U>
void Insert(ulong pos, U&& u){
if(pos > _length){
fprintf(stderr, "%-18pIndex Out of Bounds Exception thrown in ArrayList::Insert(ulong pos, U&& u)!\n", this);
fprintf(stderr, "_length = %lu\nRequest = %lu\n", _length, pos);
throw IndexOutOfBoundsException();
}
else if(_length == _capacity){
this->_IncreaseBuffer(_length * 2);
}
if(pos == _length){
::new(&_buffer[_length++]) T((U&&)u);
}
else{
::new(&_buffer[_length]) T((T&&)_buffer[_length - 1]);
for(int i = _length - 1;i > pos;i--){
_buffer[i] = (T&&)_buffer[i - 1];
}
_buffer[pos] = (U&&)u;
_length++;
}
}
void Pop(){
if(_length > 0){
_buffer[--_length].~T();
}
}
void Delete(ulong pos){
//yet to be implemented
}
void ResizeBuffer(ulong newCap){
T* t = (T*)(::operator new(sizeof(T) * newCap));
if(newCap > _length){
for(int i = 0;i < _length;i++){
::new(&t[i]) T((T&&)_buffer[i]);
_buffer[i].~T();
}
}
else{
for(int i = 0;i < newCap;i++){
::new(&t[i]) T((T&&)_buffer[i]);
_buffer[i].~T();
}
for(int i = newCap;i < _length;i++){
_buffer[i].~T();
}
_length = newCap;
}
::operator delete(_buffer);
_buffer = t;
_capacity = newCap;
}
int Capacity()const{
return _capacity;
}
int Length()const{
return _length;
}
};
