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

[Glen Mabey]

On Jan 11, 2013, at 2:03 AM, Samuel Rødal wrote:

> On 12/28/2012 03:36 PM, Glen Mabey wrote:
>> 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
> 
> I see that you've specialized on bools to store one bool per bit. Is 
> that wise, considering that it's generally agreed that std::vector<bool> 
> doing the same was a mistake? 
> http://www.informit.com/guides/content.aspx?g=cplusplus&seqNum=98

Great question!

I actually had no knowledge of std:vector's bit-packed implementation, and that article does make some very pertinent points, most of which I don't think apply to my experiences with multi-dimensional arrays -- let's see how well I can make that case.

First, bit-packed QNDArray's was not premature optimization, but rather post-facto optimization.  I had planned to make this change, but hadn't ever needed it, until I had an application (that runs in an HPC system) that was not running in real time, and used lots of QNDArray<2,quint8> instances.  I didn't ever even measure by what factor it was too slow -- it was really bad.  Without any algorithmic changes, QNDArray<2,bool> with the bit-packed partial specialization implementation made the algorithm run (barely!) in real-time.  I know that's more detail than you needed to hear, but it was really exciting to see the power of the L2 cache grow with such a small code change in the application (there were lots of random accesses in some rather large arrays).

And just as the article indicates, QNDArray<2,quint8> is still an option, but I don't think that most programmers will feel a need to substitute with it.  That's because (in my experience) most of the time I find myself *operating* on an array instead of iterating over it.  I don't know whether logical operators (!,~,&,|,^,&=,|=,^=) for std::vector<bool> instances are supported (somehow I doubt it), but that's a fundamental aspect of QNDArray.  And those logical operators (in QNDArray) all operate on the two instances whole words at a time.  (and incidentally, studying the DTYPE=bool case is easier because of a reduced number of operators)

It turns out that std::vector<bool> and QNDArray<N,bool> both took the same approach to "addressing" a single bit (the separate class that is instantiated when indexing a single element) but IMHO the QNDArray's class is a natural extension and base case to the process of dimensional reduction from any value of N.  That is, for 

QNDArray<3,bool> a3( T3(4,5,6) );
a3 = true;
QNDArray<3,bool> a2 = a3[1];  // shape is (5,6)
QNDArray<1,bool> a1 = a2[3];  // shape is (6,)
bool a0 = a1[2];

the N=0 case has the same mechanics as the N=1 and N=2 cases.  I won't elaborate here, but this is true for all DTYPEs.  However, the bool partial specialization has a little bit of extra magic foo to support these maneuvers:

a3[ T3(0,4,2) ] = false;
a1[ 3 ] = false;

which is precisely the "reference" class the article referred to.

So, I am very happy with the numerical (well, logical) usage of bit-packed QNDArray's that I have had experience with -- I hope yours is just as good!

Best Regards,
Glen