4
\$\begingroup\$

The problem

We want to use a very large array for some computations. When created, all the elements of this array have to be initialized to some value. We'll only use a few values from the array1, so we don't want the runtime of the algorithm to be dominated by the initialization time.

In other words, we want to create and access an initialized array in constant time2.

How can this be done ? (Hint: we may use extra memory)

After reading about the rule of three I decided to take this implementation and make it a little bit better. So here is what I came up with ...

The source code is also available here

#pragma once

#include <algorithm>

#ifndef NDEBUG
  #include <iostream>
#endif

template <typename T>
class InitializedArray {
public:
  InitializedArray() = default;
  InitializedArray(size_t length, T initial) : mInitial(initial), mTop(0), mLength(length) {
    #ifndef NDEBUG
      std::cout << "[InitializedArray] Constructor" << std::endl;
    #endif
    // Allocate Arrays
    mFrom     = new size_t[mLength];
    mTo       = new size_t[mLength];
    mElements = new T[mLength];
  }
  InitializedArray(const InitializedArray & other) {
    #ifndef NDEBUG
      std::cout << "[InitializedArray] Copy Constructor" << std::endl;
    #endif
    if (mLength == 0) {
      // Allocate Arrays
      mFrom     = new size_t[other.mLength];
      mTo       = new size_t[other.mLength];
      mElements = new T[other.mLength];
      // Copy Arrays
      std::copy(other.mFrom    , other.mFrom     + other.mLength, mFrom    );
      std::copy(other.mTo      , other.mTo       + other.mLength, mTo      );
      std::copy(other.mElements, other.mElements + other.mLength, mElements);

      mInitial = other.mInitial;
      mTop = other.mTop;
      mLength = other.mLength;
    } else if (mLength >= other.mLength) {
      // Copy Arrays
      std::copy(other.mFrom    , other.mFrom     + other.mLength, mFrom    );
      std::copy(other.mTo      , other.mTo       + other.mLength, mTo      );
      std::copy(other.mElements, other.mElements + other.mLength, mElements);

      mInitial = other.mInitial;
      mTop = other.mTop;
      mLength = other.mLength;
    }
  }
  ~InitializedArray() {
    #ifndef NDEBUG
      std::cout << "[InitializedArray] Destructor" << std::endl;
    #endif
    // Free Arrays
    delete[] mFrom;
    delete[] mTo;
    delete[] mElements;
  }
  InitializedArray & operator=(const InitializedArray & other) {
    #ifndef NDEBUG
      std::cout << "[InitializedArray] Copy Assignment Operator" << std::endl;
    #endif
    if (&other != this) {
      if (mLength == 0) {
        // Allocate Arrays
        mFrom     = new size_t[other.mLength];
        mTo       = new size_t[other.mLength];
        mElements = new T[other.mLength];
    // Copy Arrays
    std::copy(other.mFrom    , other.mFrom     + other.mLength, mFrom    );
    std::copy(other.mTo      , other.mTo       + other.mLength, mTo      );
    std::copy(other.mElements, other.mElements + other.mLength, mElements);

    mInitial = other.mInitial;
    mTop = other.mTop;
    mLength = other.mLength;
      } else if (mLength >= other.mLength) {
        // Copy Arrays
        std::copy(other.mFrom    , other.mFrom     + other.mLength, mFrom    );
        std::copy(other.mTo      , other.mTo       + other.mLength, mTo      );
        std::copy(other.mElements, other.mElements + other.mLength, mElements);

    mInitial = other.mInitial;
    mTop = other.mTop;
    mLength = other.mLength;
      }
    }
    return *this;
  }
  T & operator[](size_t index) {
    #ifndef NDEBUG
      std::cout << "[InitializedArray] Subscript Operator" << std::endl;
    #endif
    if (mFrom[index] < mTop && mTo[mFrom[index]] == index) {
      return mElements[index];
    } else {
      mFrom[index] = mTop;
      mTo[mTop] = index;
      mElements[index] = mInitial;
      mTop++;
      return mElements[index];
    }
  }
  size_t size() {
    return mLength;
  }
private:
  size_t * mFrom = nullptr;
  size_t * mTo = nullptr;
  T      * mElements = nullptr;
  T        mInitial;
  size_t   mTop = 0;
  size_t   mLength = 0;
};
\$\endgroup\$
  • \$\begingroup\$ I guess the default constructor can lead to problems :/ \$\endgroup\$ – xorz57 Aug 5 '18 at 0:17
3
\$\begingroup\$
#pragma once

Be aware that you are giving up portability here as this is, while common, a non-standard compiler extension. For nearly all applications, as long as you use implementations that support it, neither physically nor logically copy files around, and the filesystem doesn't trigger a false-positive, then #pragma once is fine. Otherwise, stick with standard include guards and give some effort to differentiate the guard name.


  InitializedArray() = default;

Not sure you need this. You can greatly simplify the logic of your functions as you won't need the existence checking. The lifetime of member arrays would be guaranteed to exist for the lifetime of the object.


  InitializedArray(size_t length, T initial)
      : mInitial(initial), mTop(0), mLength(length) {
    mFrom = new size_t[mLength];
    mTo = new size_t[mLength];
    mElements = new T[mLength];
  }

For portability reasons, size_t needs to be qualified with its namespace (std::size_t) and it requires <cstddef>. C++ makes no guarantee that size_t will be available in the global namespace, but it doesn't guarantee that the symbols are available in namespace std.

Is T guaranteed to be cheap to copy? Pass by-reference to-const. What if T is not copyable?

For data members dependent on the user to provide values to initialize with, prefer the constructor initializer list to assignment in the body of the constructor.

Avoid explicit new/delete. If one of those allocations fails, any allocation that has already completed will not be cleaned up. Use std::make_unique<T|std::size_t[]>. Abusing std::vector will probably only allow for simple buffer lifetime management, but I wouldn't rely on the behavior in the buffer region beyond the size of the vector.

You have the same three copy expressions that appear multiple times. Consider writing a helper to reduce the replication.

    // Exposition-only
    void copy_thrice(const InitializedArray& other) {
        std::copy(...);
        std::copy(...);
        std::copy(...);
    }

    InitializedArray(const InitializedArray& other)
    : mFrom{std::make_unique<std::size_t[]>(other.size())}
    , ... {
        copy_thrice(other); // Give this an appropriate name?
    }

  InitializedArray & operator=(const InitializedArray & other) { ... }

If other was default constructed (has not initialized array data members), should the copy constructor initialize the array data members?

What happens when mLength is non-zero and less than other.mLength?

The logic can be simplified. Read up on the copy-and-swap idiom.


  T & operator[](size_t index)

This is fine for a mutable InitializedArray, but what about a const-qualified (immutable) InitializedArray?

    if (mFrom[index] < mTop && mTo[mFrom[index]] == index) {
      return mElements[index];
    } else {
      mFrom[index] = mTop;

You don't need an else after a control structure like return, break, continue, etc.

    if (already_initialized(index)) {
      return mElements[index];
    }
    return initialize_at(index);

  size_t size() {
    return mLength;
  }

No reason this function cannot be used in a const context.

\$\endgroup\$
7
\$\begingroup\$

Now that you know the Rule of Three, and have been pointed by 1201ProgramAlarm to study the Rule of Five... you should also be aware of the Rule of Zero. Try rewriting your code to eliminate all manual memory management. Use unique_ptr<T[]> or vector<T> instead of a manually managed T*.

template <class T>
class InitializedArray {
public:
    explicit InitializedArray(size_t length, T initial) :
        mInitial(std::move(initial)),
        mFrom(length), mTo(length), mElements(length)
    {}

    InitializedArray(InitializedArray&&) = default;
    InitializedArray(const InitializedArray&) = default;
    InitializedArray& operator=(InitializedArray&&) = default;
    InitializedArray& operator=(const InitializedArray&) = default;
    ~InitializedArray() = default;

    // YOUR CODE HERE

    std::vector<size_t> mFrom;
    std::vector<size_t> mTo;
    std::vector<T> mElements;
};

Things to notice in passing:

  • I removed the debugging printfs that you'd placed under NDEBUG. I strongly recommend not to reuse NDEBUG to control anything of your own code; its intended purpose is to control the expansion of the standard assert macro. If you must use a debugging macro, make up your own name for it; I recommend #if DEBUGGING. (Notice that #if does the right thing with -DDEBUGGING=0, whereas your #ifdef does not.)

  • Since we're using std::vector, we can follow the Rule of Zero. We don't have to write out the =defaulted members — we could have just omitted them — but I wrote them out just to show that they're all really still there.

  • Your class doesn't need, and therefore probably shouldn't have, a zero-argument constructor.

  • What constructors you do have (except for the copy and move constructors) should always be marked explicit.

  • Your original code, and also this "Rule of Zero" code, both rely on being able to default-construct length copies of T at construction time. This is likely to be slow for large values of length, and anyway it defeats your stated purpose, and anyway there's no reason T should even need to be default-constructible. Keywords for further study: "placement new", "std::optional".


Your size() member function should be const-qualified, since it doesn't need to modify the *this object.

Your operator[](size_t) should have const and non-const versions.


Consider whether it would make philosophical sense to permit something like InitializedArray<std::unique_ptr<int>>. Think about what you'd have to change in order to make that work. (Hint: mInitial couldn't be a T. What could it be?)

\$\endgroup\$
  • 1
    \$\begingroup\$ std::vector isn't going to do exactly what this problem is trying to solve. The purpose is to avoid the cost of initializing an expensively large contiguous array. Think unordered map subscript access for a dense uninitialized array. For uninitialized areas of a vector, you are at the whim of the implementation since there is no defined behavior mandated by the standard. \$\endgroup\$ – Snowhawk Aug 5 '18 at 4:41
  • \$\begingroup\$ @Snowhawk: "The purpose is to avoid the cost of initializing an expensively large contiguous array..." Yet OP's code does exactly that (new T[mLength]). So using vector wouldn't make it any worse. But yeah, to make it better the OP should look into "placement new" etc. \$\endgroup\$ – Quuxplusone Aug 5 '18 at 7:45
  • \$\begingroup\$ new T[mLength] is just a block of uninitialized values. A vector seems worse as the standard doesn't really say much about capacity beyond capacity will be equal to or greater than size. On copy, implementations are free to shrink the capacity to size, which slices any value set in what vector believes is uninitialized values and meaningless. \$\endgroup\$ – Snowhawk Aug 5 '18 at 8:04
4
\$\begingroup\$

The default constructor is almost OK, since most members of the class have default values specified. If the type T has a default construtor there are no problems. If it is a type without one (like int), then mInitial will be uninitialized.

Your copy constructor is written more like a copy assignment operator. Since the object being constructed is empty, there is no point in checking if mLength == 0, since it will be 0. Get rid of the if statement completely, including the else code, but keep the compound statement between the if and else. In addition, you may want to take the initial value by const reference (const T &initial) to avoid making copies of large types.

Your copy assignment is flawed, because it does nothing if the existing length is shorter than the length of the InitializedArray being copied.

You should have a const version of your array element access, const T & operator[](size_t index) const. This version would not support adding a new element.

You should also look at the Rule of Five.

\$\endgroup\$
2
\$\begingroup\$

Preface: this may be off-topic since I am really reviewing the code in the linked blog post rather than what the user posted. However, since the two are linked, I think this may be helpful.


Part of a code review (IMO) is to check assumptions. Here you're assuming that initializing a vector takes a long time.

The simplest check is to first compile a just the initialization and see how long it take. Using a vector with 134217728 elements, it takes 2.5 seconds. Yeah, I'd say that's worth optimizing!


Since we're optimizing performance, let's check to see how fast this new method really is. Ideally I'd use perf to check, but I'm on a Mac so I'm going to use Instruments. Also, I commented out all the IO from the code you posted. As another user mentioned, it was annoying that you used DNDEBUG to control std::cout because if I defined DNDEBUG my assert wouldn't work and the test would be invalid.

enter image description here

This report is for 1099511627776 elements in the vector and 10000 accesses. This is a very short sample which sort of skews the results. Since the number of accesses directly sways the percents, the percents are not really important. If you knew what kinds of parameters you'd have in production, then obviously you should test with those. Still, it shows some slow sections.

I've highlighted two lines which take a long time. These are the calls to new/delete for the underlying vectors. They take about 0.15 seconds alone.

There is another algorithm to solve this problem with no expensive memory operations in the constructors or destructors. Use a map! Store index as key and value as value. I made a quick and dirty implementation and ran it against this implementation. Below are some timed graphs. I used -O3 for all versions.

enter image description here

When you're only looking at the data 1000 times, std::vector is really slow as we knew from the first test. It spends too long in the constructor. So long that I stopped running it after a few values...

The submitted code is fast but the operator[] has too much going on. Yes, it is O(1), but a big constant. It may be surprising that map::operator[] is still faster despite being log(n). I think (unverified) this may be because for a really big array, the InitializedArray::operator[] will have cache misses. The map, on the other hand, is really small. It only has the 1000 elements in it.

enter image description here

When doing 100000 elements on a big array, InitializedArray::operator[] is almost slow enough to offset the vector. I didn't test this, but it looks like with only a few more accesses or a few more array elements the std::vector will be faster again. This should give you a sense of what range of values InitializedArray is worth using.


There's a line in the linked blog post:

In principle, we could make read accesses a bit more efficient, by skipping the complex initialization and just returning init_val. In this C++ implementation this isn't possible, however, because when you overload operator [], you can't discriminate between read and write accesses to the element.

I believe this is true, but you could abandon operator[] and have separate functions for lvalues and rvalues. However, I'm not sure how that would help rewrite operator[] (perhaps move constructor code to after the first write?).


If you would like to see the test scripts/map version, let me know in the comments.

\$\endgroup\$

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.