[Development] submitting a multi-dimensional container class for Qt: QNDArray

[Glen Mabey]

Hello,

For some time, I have been working on a QtCore-based class that would be a container class of arbitrary dimensionality.  I did give a presentation on this topic at DevDays-CA:

http://www.qtdeveloperdays.com/northamerica/sites/default/files/presentation_pdf/QNDArray%20at%20Qt%20Developer%20Days.pdf

There are a couple of fundamental issues that I'd really like to get some feedback on, and it seems like the mailing list might be a better forum for that than just comments on the commit.  I'm going to describe a bunch of issues and design decisions that I've made largely in a closet, and if there's something that seems backward or strange and would make it hard for this code to be fully integrated into an upcoming Qt release or Add-on, please let me know.

Issue 0) I did push a bunch of this code last July, but since then have cleaned things up quite a bit.  I would really like to just abandon that change (from July) but I don't see the "Abandon Change" button where it should be.  I did file a bug report on that (that the button was missing for me) but haven't heard back on it.  If someone could just abandon those for me, the change id's are:  I1fcca761e7459084782f0a45ed2e989d066869fd and  Iacd5dbc94cdccb6c8ec280c7964eecf43a4788b5 .

Issue 1) This class, QNDArray, is templated with two template parameters: one for the number of dimensions and one for the datatype.

template< qint8 N, class DTYPE > class QNDArray;

Most all of the behaviors that QNDArray takes are based on those found in the Numpy project, and the first template parameter (qint8 N) is one example of that.  In Numpy, the maximum number of dimensions is 32.  When I first started working with numpy, I found myself getting confused between the dimensionality of an array and the shape, and limiting N to 7 bits is a reminder of this fact, that it is never intended to be large.

Issue 2) An early challenge I faced was that Q_DECLARE_METATYPE() does not get along with classes with multiple template parameters.  The solution in the forums is to create a typedef and use that in the macro. However, with so many permutations of N and DTYPE, it seemed silly to make a whole bunch of typedefs, so instead I created a new macro that takes two parameters, and puts things back together post-facto:

#define Q_DECLARE_METATYPE_2(h1,h2) \
  QT_BEGIN_NAMESPACE \
  template <> struct QMetaTypeId< h1,h2 > { \
      enum { Defined = 1 }; \
      static int qt_metatype_id() { \
          static QBasicAtomicInt metatype_id = Q_BASIC_ATOMIC_INITIALIZER(0); \
          if (!metatype_id.load()) metatype_id.storeRelease(qRegisterMetaType< h1,h2 >( #h1 "," #h2, reinterpret_cast< h1,h2 *>(quintptr(-1)))); \
          return metatype_id.loadAcquire(); \
      } \
  }; \
  QT_END_NAMESPACE

This seems like a hack to me, but it works great with all of the compilers I've tried it with (32/64-bit g++ on linux and mac; mingw, MSVC 2008, 2010).  Does anyone foresee a big objection to this approach?

Issue 3) QByteArray and other containers seem to be limited to 32-bit indexes, which is probably fine.  This seems short-sighted for arrays, and in fact when I use memmap() on large files I truly need 64-bit indexing, so the implication is that each element of the shape and of the strides needs to be a 64-bit integer.  However, I didn't want to impose that type of requirement on embedded platforms, so as a compromise I use qnda_size_t for them:

  typedef qptrdiff qnda_size_t;

QNDArray is kind of big, as compared to other container classes.  On 64-bit machine:

sizeof(QNDArray<1,int>) =56
sizeof(QNDArray<2,int>) =72
sizeof(QNDArray<3,int>) =88

That's because the layout information (shape and strides) is included directly in the QNDArray class, as opposed to residing in the reference-counted portion.  The original motivation for this was (since the size is relatively limited) to keep these data on the stack instead of having to dereference a pointer in order to access them, even when operating on the instance in a non-method.  As such, the number of items in the shape is identical to N (also for the strides), and hence the sizeof() gets bigger. One of the other data members in the QNDArray class (actually, in QNDArrayBase) was a QExplicitlySharedDataPointer until about six months ago when it became a QNDAMemSourceSharedPointer (functionally much the same) which was necessary in order to properly detach() under certain circumstances.  Thus, actual data is in a separate, reference counted class, while all of the meta-information is in QNDArray proper.  This would be analogous to being able to call QByteArray::mid() and have the new instance refer to the same actual data but with a different offset and length.

However, the sizeof(QNDArray) makes it less palatable for things like emitting it in a signal to many listeners; it's not the sleek sizeof(void*) like all of the other container classes, and I'm kind of embarrassed that it is as big as it is.  As I look forward to including better masked-array support in QNDArray, the size would only increase, which has led me to consider adding another layer of redirection and making QNDArray_p contain all of the meta-info.  However, one of my primary use cases of QNDArray is an instance which is a data member of another, referenced counted class.  Thus, it was the other class that was getting passed around, stored in lists and QVariants, and emitted in a signal, and there was a minimal number of pointers to dereference.  

I also thought that developers could insert a QNDArray instance into a QList before emitting it as a signal, but that sounds way to hackish to actually recommend in the docs.

Issue 4) The issue of unit tests has been central to all of the development I've done, and the intent has always been to use python+numpy to validate the behavior.  However, this implies a new python requirement in that numpy is also needed (I read somewhere -- a long time ago -- that there was already a python requirement in order to run some of the tests?).  There is also some code that is generated from boilerplate -- the methods for QNDArray::operator+(QNDArray) and QNDArray::operator-(QNDArray) are very similar -- that uses a python script for making the substitutions, but it wouldn't be hard to port that to Qt if it would make things more palatable.

Issue 5) One of the motivations for having QNDArray templated in N is for the base case of N=0, which I used via partial specialization to appear as a very minimal class with basically a operator-cast method to get you to the real DTYPE for operations like +-*/.  However, one of the fallouts of this was that certain versions of g++ required some explicit instantiations of the N=0 case.  It appears that these are not necessary when using g++ >= 4.4.3 -- do you think that I will be okay to not include them at all?

Issue 6) I have acutely felt the absence of std::complex data types as I have worked on QNDArray.  I realize that complex data types are not normally used for GUI work (maybe QtCharts will feel that someday), but it has led to some minor infelicities, such as for serializing the data in a QNDArray.  Do you anticipate any improvement to the status of std::complex in Qt?  Perhaps in C++11 some of the awkwardness of dealing with templated types in signals and slots might lead to broader use of std::complex?  

Issue 7) One of the criticisms that I have received from my co-workers is the number of qFatal() calls in my code.  I hope that this is consistent with the behavior of QList and other container classes when parameters provided are out-of-range.  However, because the index data type is either 32- or 64-bits, the UTF8 string passed to qFatal() wants either a %d or something else.  My current way of dealing with that is at the top of QNDArray.h:

/** Used to include 64-bit integers in qFatal() calls -- inttypes.h + PRId64 doesn't work for some strange reason. */
#ifdef Q_OS_WIN32
#define QFI64 "I64d"
#else
#define QFI64 "lld"
#endif

/** Used to include qnda_size_t-sized integers in qFatal() calls. */
#if QT_POINTER_SIZE==4  // 32-bit platforms
#define QNDAST "d"
#else  // 64-bit platforms
#define QNDAST QFI64
#endif

That way I can do this:

  qFatal( "In QNDArray<N,DTYPE>::take(), an out-of-bounds index (%"QNDAST") was found.", idx );

and it works without a compiler warning on all platforms [that I've tried].  Surely there is a better way to do this??

Issue 8)  I did not see any output from the sanity bot when I did a git commit even though I had installed the symlink /.git/hooks/post-commit to git_post_commit_hook … any tips for getting that to run would be appreciated.

Issue 9)  Since the code consists of just .h files, there is no need to have them added to include/QtCore/QtCore .  Is there some way to disable the behavior I've observed that the build seems to add them by default?  Or maybe that indicates that these files don't belong under src/corelib/ ?  Actually, the only files that should be stubbed from include/QtCore/ are qndarray.h, qndarraylist.h, qbytearraylist.h, qndaiteratorstl.h, qndamemsource_cuda.h, qndasort.h, qndamath.h, qndamemsource_fftw.h.  The source is separated into the rest of the files just for manageability (and some of them are auto generated from templates -- not that kind!).

Issue 10)  So, it's not all properly documented, yet.  I do plan to finish the docs, but I anticipate that it will take a while to work through these issues as well as others that developers raise.  So, I guess it's a WIP, and I hope that I'm not too off-base in trying to get this pushed up to gitorious for public consumption, so that this discussion can happen.  However, when I try to push I get this error (I don't really know what I'm doing WRT git/gerritt, but I am trying to learn … ):

homelap:qndarray$ git push ssh://gmabey@codereview.qt-project.org:29418/qt/qtbase HEAD:refs/for/qndarray
Counting objects: 77, done.
Delta compression using up to 8 threads.
Compressing objects: 100% (73/73), done.
Writing objects: 100% (74/74), 104.30 KiB, done.
Total 74 (delta 17), reused 0 (delta 0)
remote: Resolving deltas:  82% (14/17)
To ssh://gmabey@codereview.qt-project.org:29418/qt/qtbase
! [remote rejected] HEAD -> refs/for/qndarray (branch qndarray not found)
error: failed to push some refs to 'ssh://gmabey@codereview.qt-project.org:29418/qt/qtbase'


I have put my contributed files in surely the wrong place, but I certainly won't object to any relocations.


It has taken a long time to get to the point where this code is close to contributing, and I appreciate feedback on these issues.

Best Regards,
Glen Mabey