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

Samuel Rødal samuel.rodal at digia.com
Fri Jan 11 15:19:05 CET 2013


On 01/11/2013 02:41 PM, Glen Mabey wrote:
>
> 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)

Yep, very good points. In the cases when doing bit operations on large 
data sets your representation will both use less space and perform a lot 
better.

> 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!

Ok, I guess QNDArray is also meant to represent data sets that are 
potentially a lot larger as well, compared to the average 
std::vector<bool> use case. And as you say there's always quint8 if 
someone has different requirements.

--
Samuel



More information about the Development mailing list