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 _______________________________________________ Development mailing list Development@qt-project.org http://lists.qt-project.org/mailman/listinfo/development
