Specific reasons to create own array class over using std::array?

Question

What specific conditions or requirements should you create your own array over using std::array?

Here is my background:

I'm developing a small simple library that a small group of people will use and hopefully build upon. The current structure allows for both std::vector and std::array using iterators, however, a lot of the people do not like and cannot seem to use std::array and find the notation confusing to work with the library.

I have attempted to make my library work for better for std::array however, it dawned on me that maybe I should provide my own and adding in the functionality needed?

For example: library::array<int, 2> myArray; myArray.fill(1, 100); and I thought it would be a good project in order for me to develop my skills, particularly in templates and other sorting algorithms.

Answer 1

---

• How many dimensions are needed?
  • C++ Template programming may require some code duplication for each level of higher dimension.
  • Address calculation is the easy part. A simple approach can be used for dimensions up to a dozen.
  • For a 3-dimensional example:
    • Let the size of the array be [m, n, p]
    • For each dimension, we calculate a "weight vector" by successively multiplying terms:
      [p*n, p, 1]
    • To access the element at [i, j, k], its linearized element index can be calculated as:
      [i, j, k] dotproduct [p*n, p, 1]
      or ((((i * n) + j) * p) + k)
  • For higher dimensions, care must be taken to reduce the time spent in multiplications needed for element address calculation.

---

• What are the typical sizes of the array, to the order of magnitude?
  • For small-sized arrays (less than 1000 elements), basically any design and implementation will work, unless proven otherwise by a profiler.
  • For medium-sized arrays (as long as it can still fit entirely in the computer's memory or the application's address space), performance will be an increasingly important concern.
  • For large arrays (which cannot fit as a contiguous piece of memory), architecture concern will dominate.

---

• Architecture / Memory Layout
  • Driving forces:
    • Size / scale
    • Performance
    • Computational platform
    • Interoperability (with other code / libraries)
    • Access semantics
  • Available choices:
    • Contiguous memory (the easiest, most straight-forward choice)
    • Non-contiguous memory (example: tiled array)
    • Memory-mapped file
    • Distributed across multiple machines in a network

---

• Does your implementation need to support high performance?
  • As a ballpark, anything requiring more than one billion elementary operations per second can be considered high-performance for the purpose of choosing a design.
  • Designing for high-performance will impose constraints on:
    • Choice of computational platform
    • Choice of memory layout

---

• Computational platform?
  • If high performance is not needed, scalar C++ code will be sufficient.
  • Otherwise, a high-performance computational platform will be needed.
  • This will impose constraints on:
    • Choice of memory layout
  • Computational choices
    • Scalar C++
    • Multi-core computing
    • Manual threading
    • Concurrent programming library (Intel TBB, Microsoft PPL/AMP)
    • Compiler-assisted (OpenMP)
    • Parallel programming languages. Example: Cilk, Brook
    • Open-soure library (OpenCV)
    • SIMD (Single-Instruction Multiple Data) example: Intel SSE2, AVX, ARM NEON, PowerPC AltiVec
    • GPU programming (CUDA, OpenCL)

---

• Does the array need to be accessible by other libraries, without copying?
  • If so, your array's memory layout must be compatible with that other library you are using.
  • For small array sizes, or for access patterns where writes (modifications) occur infrequently, copying is not an issue.
  • For large arrays which are both read and written very frequently, data copying can become an performance issue.

---

• A story where a bad combination of data copying and access semantics can cause an increasingly disproportionate performance issue:
  • Consider two modules, each of which has its own copy of a 100 MB array, and which they have to keep synchronized at regular intervals.
  • Suppose that one of the modules freely modifies its own copy, without keeping track of which region of the array is being modified.
  • When the time comes to perform synchronization, the first module will have to copy the entire 100 MB array over, because it cannot tell which part needs synchronization.
  • The user of the first module will complain that "if I am only modifying a few elements of this array, why is the library taking so long to synchronize?"
• Lesson: by requiring modifications to go through an API call, access semantics can be used to reduce inefficiency in data copying.

---

• Access semantics.
  • Boils down to three questions:
    • Who computes the memory address of elements? given the subscripts (i, j, k)
    • How is the array's lifetime (ownership) managed?
    • Is the array implementation being notified of which part of the array is modified?
• Choices:
  • Direct access to underlying memory, no API call.
    • The array implementation will not know which part of the array is modified / used.
  • Direct access to underlying memory, requiring a API call to lock/unlock an array view.
    • Known as "advisory locks" because it cannot enforce access control.
    • An advisory lock is still useful, because by locking/unlocking the library is notified of current users of the array, as well as the region being modified.
  • API method for reading and writing one element at a time
    • Easiest to implement and use
    • Slowest
  • API method for copying an array view at a time
    • Copies between a sub-rectangle of your array and a normal C/C++/Java array
    • Good balance between high-performance and safety
    • Allows your array implementation to use a different memory layout

---

• Design of the library interface and syntax
  • ...

If you have made it thus far, congratulations, you can start designing the interface and the syntax!

Answer 2

I think that your library should be generic and not tied to vector/array types unless absolutely necessary. The genericity is provided by the iterators - they are the interface between the algorithm and the container.

Look at what interface C++ algorithms provide. A given algorithm simply requires a couple of iterators with certain properties and that's it. As long as a container provides such an iterator, the algorithm doesn't care about the container per se.

Once you're thinking in terms of iterators, std::array and std::vector behave identically: they both have forward- and backward random access iterators. If the algorithm can use such iterators, you can use it on both std::array and std::vector.

I don't quite believe that you're using iterators as the interface, since if you did, the type of the container the iterator comes from doesn't figure anywhere in your interface. Well, unless you explicitly want std::array<T>::iterator - that'd be very bad style, indeed.

Answer 3

The only reason for providing your own array class from a library is if none of the current offerings (std::array, std::vector and raw arrays) fits your requirements. For example, if you needed an array that does bounds checking without dynamic allocation, you had to write that yourself prior to the introduction of std::array.

As far as accepting array classes in your library goes, you should realize that std::array is a fairly new addition to the C++ language and there are heaps of existing libraries that have their own array classes.
To get your library accepted faster, it should, besides providing useful functionality, accept at least the lowest common denominator of all array-like types, which is the simple pointer.