2
\$\begingroup\$

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;
    }
  };
\$\endgroup\$
  • \$\begingroup\$ I have rolled back the last edit. Please see What to do when someone answers. \$\endgroup\$ – Mast Feb 25 '16 at 0:16
  • \$\begingroup\$ @Mast Oh. Sorry about that. Rather new to this site. I'm sure you could tell. \$\endgroup\$ – user64704 Feb 25 '16 at 1:01
  • \$\begingroup\$ Don't worry about it. It's a common mistake for new users. Feel free to post a follow-up question once you've refactored your code and don't forget to add a link to this question for clarity. \$\endgroup\$ – Mast Feb 25 '16 at 1:54
4
\$\begingroup\$

Unused

#define ARRAYLIST_DEBUG_OUTPUT 0

Even if this is used I would be careful. I hate putting conditional code into functions. But rather build macros that either plant the correct code or nothing based on this macro.

C casts. STOP doing this:

    _buffer = (T*)(::operator new(sizeof(T) * size));
    ::new(&data[i]) T((T&&)_buffer[i]);

C++ has it own syntax for casting. It documents the type of cast more accurately and prevents errors much better than the C style. Also when converting to r-value referrece the std::move() documents much better your intent.

    _buffer = static_cast<T*>(::operator new(sizeof(T) * size));
    ::new(&data[i]) T(std::move(_buffer[i]));

Stop using this

this->_InitBuffer(1);

If you need to use this it is usually an indication that you are doing something else wrong (like shadowing local variables). The reason to use this is to disambiguify a context. If you need to disambiguify this means your code is not as clear and concise as it should be.

This means reviewers start to dig in deeper. Here you just don't even need it.

Looks like a bug

The buffer is all about _buffer and _capacity. Why are you refferring to _length in this function?

  void _IncreaseBuffer(ulong newSize){
    if(_length == 0){

Releasing resources

When releasing resource try and make sure your object is in a completely valid state so that if something goes wrong you are protected.

I don't think in this case it is a problem. But if you changed this code to use a custom allocator then a problem may crop up and therefore in general it is a good hobbit to get into.

I would change

      ::operator delete(_buffer);
      _buffer = data;
      _capacity = newSize;

into:

      std::swap(_buffer, data);
      _capacity = newSize;
      // Now the object is a good valid state.
      // If things go wrong in the delete then the object will be OK.
      ::operator delete(data);
      // It also makes the new/delete operations symmetrical
      // and symmetry appeals to me in coding.

There is also the opportunity of the constructor/destroctor of T failing so you should take that into account. You will not damage your object but you may leave dangling objects.

      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();
      }

Into:

      T* data = (T*)(::operator new(sizeof(T) * newSize));
      int i;
      try
      {
          for(i = 0;i < _length;i++){
             ::new(&data[i]) T((T&&)_buffer[i]);
             _buffer[i].~T();
          }
       }
       catch(...) {
          for(;i > 0;--i) {
               _buffer[i].~T();
          }
          ::operator delete(_buffer)
          throw;                     // don't forget to re-throw after
                                     // you have tidied up all the stuff.
       }

Copy and Swap idiom.

Now all the above seems like a lot of work for some unlikely situations. And you are correct that is a lot of work. And there is a standard technique for doing it more simply. Its called Copy/Swap/

       void _IncreaseBuffer(ulong newSize){

           ArrayList<T> tmp(newSize);    // safely allocate a new buffer
                                         // that will be deleted at the end.

           // Move the data to the new buffer.
           for(i = 0;i < _length;i++){
             ::new(tmp._buffer[i]) T(std::move(_buffer[i]));
             ++tmp._length;
           }

           // Swap the content of the tmp with the current object.
           // Swap should be exception safe.
           tmp.swap(*this);

           // destructor of tmp is now called as it goes out of scope.
           // will tidy up all the allocation and destroy all the members.
       } 

Premature optimization

    ArrayList() : _buffer(NULL),
                  _length(0),
                  _capacity(0){}

    ArrayList(ulong initCap) : _length(0),
                               _capacity(initCap)
    {
      _buffer = (initCap == 0) ? NULL : (T*)(::operator new(sizeof(T) * initCap));
    }

Not sure I would optimize for a zero capacity array. It just makes the rest of the code more complex. I would treat it just like a normal constructor and call ::operator new but ask for zero sized object (that's perfectly legal). You will get a non NULL pointer back (with zero elements). Now you don't need to special case the rest of your code which makes it easier to read/maintain.

Copy and Swap again.

    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]);
      }
    }

Here you fail to deal with construction failure in T. You will leak the objects in the new buffer because the destructor will never be called on this object.

Easier to write as

    ArrayList(const ArrayList& a)
        : _length(0)
        , _capacity(0)
        , _buffer(nullptr)
    {
        ArrayList<T> tmp(a._capacity);

        for(int i = 0;i < _length;i++){
          ::new(&tmp._buffer[i]) T(a._buffer[i]);
          ++tmp._length;
        }
        tmp.swap(*this);
    }
    // On exit tmp is destroyed and all members in tmp cleaned up.
    // So if there is an unexpected exception all data will be cleaned
    // up correctly.

Implement move as a swap.

This implementation has a bug that in the moved object still has a capacity. Will that not affect your object if somebody tries to call other methods.

    ArrayList(ArrayList&& a)noexcept : _buffer(a._buffer),
                                       _length(a._length),
                                       _capacity(a._capacity)
    { 
      a._buffer = NULL;
      a._length = 0;
    }

I would write as:

    ArrayList(ArrayList&& a)  noexcept
        : _buffer(nullptr),
        , _length(0),
        , _capacity(0)
    { 
       a.swap(*this);
    }

Make sure the _buffer is deleted even if there are exceptions.

    ~ArrayList(){
      for(int i = 0;i < _length;i++){
        _buffer[i].~T();
      }
      ::operator delete(_buffer);
    }

Operator[]

Normally operator[] is optimized for speed. Which mean it does not validate the index parameter. Usually an implementation provides the at() method that does the same operation but validates the input.

    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];
    }

Assignment operator use copy/swap.

    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;
    }

Much easier to write as:

Also no chance of accidentally leaking.

    ArrayList& operator=(const ArrayList a){
        a.swap(*this);
        return *this;
    }

Implement move as swap.

Definitely a bug in here. You are leaking the current _buffer and all its members.

    ArrayList& operator=(ArrayList&& a)noexcept{
      _buffer = a._buffer;    // Overwritting the current value (thus it leaks)
      a._buffer = NULL;
      _length = a._length;
      a._length = 0;
      _capacity = a._capacity;
      return *this;
    }

Much easier to write as:

    ArrayList& operator=(ArrayList&& a)noexcept{
        a.swap(*this);
        return *this;
    }

Capacity increase.

Sure 2 is a good number.

        this->_IncreaseBuffer(_length * 2);

I believe the current common implementations of the standard library use something between 1.5 and 2. But its a long time since I looked. They did a lot of maths to come up with the perfect ratio increase. But note they multiple by _capacity not _length. Also you should beware when your length and capacity is zero. This will not change the size.

\$\endgroup\$
  • \$\begingroup\$ I'll work on adding a swap function. It really does make it look nicer. And yeah I didn't even think about ensuring no errors interfered with memory deallocation. As for the initializing with (T*)(::operator new(sizeof(T) * 0);, I read that it would still allocate memory so I thought I should prevent that if a zero was passed. Does it not call for allocation and just return a pointer to nothing? And doesn't std::move just return a cast of the input? Is there an advantage to it I missed? The unused macro was just leftover, forgot to delete it. I'll work on my C-style casts, just used to C. \$\endgroup\$ – user64704 Feb 24 '16 at 23:24
  • \$\begingroup\$ The standard doesn't specify whether to use 1.5, 2, or some other value for the capacity increase. It just requires that the increases follow a geometric progression. 1.5 is pretty common. The heavily mathematical solution is to use the golden mean (~1.62) or smaller. This guarantees that if your discarded blocks are contiguous with each other, they'll eventually form a block big enough for the next allocation. \$\endgroup\$ – Jerry Coffin Feb 25 '16 at 5:29
  • \$\begingroup\$ @rexy712 Does it not call for allocation and just return a pointer to nothing? It returns a pointer. I am sure there is some overhead associated with that. But since you have specified 0 there is nothing you can actually use. \$\endgroup\$ – Martin York Feb 25 '16 at 17:51
  • \$\begingroup\$ @rexy712 And doesn't std::move just return a cast of the input? The return value of a function is an r-value reference. That's basically all it does. BUT for a human it does much more. It shows intent on what you are trying to do. Using the C cast to achieve this does not show your intent. And thus you should prefer std::move to make the code more easy to read. \$\endgroup\$ – Martin York Feb 25 '16 at 17:53
  • \$\begingroup\$ @rexy712 Is there an advantage to it I missed? Yes. It makes the code easier to read because it shows what you are trying to achieve. This is also the standard way of doing it so doing it another way is going to confuse humans. \$\endgroup\$ – Martin York Feb 25 '16 at 17:54
1
\$\begingroup\$

First of all, I suggest using a pre-rolled benchmarking library. Microbenchmarking is very difficult to get right. Try something like google/benchmark. Your method of measurement is very noisy. It would be far better to have a loop with your code (calling clock twice instead of 2*LOOP times) and a loop with the vector code to reduce the noise that comes in the call to clock, for example.

Second, in order to answer questions like this it's impossible to be at all accurate unless we know which compiler, compiler options, and standard library you're using.

Third, I can imagine several effects that may cause this:

  • You may not be compiling at the same optimization level that the shared libc++ you're linking to was compiled at.
  • Your emplace_back code has an additional indirection compared to the llvm version, which stores a begin and end pointer rather than a pointer and an offset.
  • You are running your code before the vector code for each i. It's possible that branch prediction is better the second time around.
  • std::allocator may be more efficient than operator new (this seems unlikely).

By the way, you are using reserved names (e.g. _IncreaseBuffer); see the rules for identifiers.

\$\endgroup\$
  • \$\begingroup\$ As to the changing of how I call clock(), your's is a much better solution. I will definitely change that. The compilers I've tested with are gcc 4.9.3 and clang 3.5.0. The same result comes from both resulting outputs. My compiler options are -g -std=c++14 -O2. It's just a test program so that's all for compiler options as of right now. Everything on my system is compiled with -O2 optimization level. \$\endgroup\$ – user64704 Feb 24 '16 at 23:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.