----- Original Message ----- From: "Toon Knapen" <[EMAIL PROTECTED]> To: "Boost mailing list" <[EMAIL PROTECTED]>; "Maarten Hilferink" <[EMAIL PROTECTED]> Sent: Wednesday, May 28, 2003 12:59 PM Subject: Re: [boost] sequence_array contribution
On Thursday 22 May 2003 12:51, Maarten Hilferink wrote: > template<typename T> struct sequence_array<T>; > which has an interface that is almost compatible with > std::vector<std::vector<T> >; > but faster. Toon wrote>and more compact I presume. AFAICT the drawback will be that the sequece is not as dynamic anymore as a vector-of-vectors (vov) Well, sequences of a sequence_array can be resized, for example: sequence_array<std::pair<double, double> polygons(10); // 10 polygons. polygons[1].resize(50); // 50 points in second polygon. polygons[0].resize(20); // 20 points in first polygon. I have made the sequence_arry.hpp a bit more self contained (see attachment) and will continue to integrate the stuff into the boost-style. I have done some time testing (see attached: sequenceTest.cpp) and it looks promising Inserting 1000 points in each of 5000 polygons and then destructing it takes 13 secs on my computer with a vector of vectors (vov) and 3 second with a sequene_array. (this is in debug mode in which MVC adds stuff to heap allocations and does an expensive check for de-allocations; nevertheless, a saving of more than 75%). > template<typename T> struct sequence_array<T>; > that uses an internal > std::vector<T> m_Data; > for sequencial storage of sequences of T > and an additional > std::vector<std::pair<T*, T*> > m_Seqs; > for identifying allocated sequences. Toon wrote>But isn't always gauranteed : m_seqs[i].second == m_seqs[i+1].first ? In this case you could shrink the memory footprrint with another pointer per innter vector. No, Sequences can be reallocated in m_Data (see example above), and therefore this equation is not guaranteed. > sequence_array offers typedef iterator, const_iterator, reference, and > const_reference > with interfaces nearly compatibe with > std::vector<T>*, const std::vector<T>*, vector<T>&, resp. const vector<T>&. > (the sequences however don't have a reserve() member function, Toon wrote>Why not ? I have something similar as you and definitly need reserve. But my reserve takes two arguments : the number of internal vectors (will reserve m_seqs) and the storage consumed by all internal vectors (will reserve m_data). Yes, you can reserve data for the sequence_array, but not for each sequence separately, I made the design decision to have only 2 pointers (not 3) per sequence, so I can resize, but not reserve for, a sequence, for example: sequence_array<std::pair<double, double> polygons; polygons.resize(2) // make room for 2 polygons polygons.data_reserve(70); // to occupy a total of 70 points. polygons[1].resize(50); // 50 points in second polygon. polygons[0].resize(20); // 20 points in first polygon. // polygons[0].reserve(x); // illegal: with only 2 pointers per sequence I cannot identify uninitialized data. > I specifically would like to hear from you on the following design issues: > - I am considering to change the definition of the above mentioned m_Seqs > to: > std::vector<std::pair<size_t, size_t> > m_Seqs; > where m_Seqs[i].first and second are offsets of the start and end of > sequence i relative to m_Data.begin(). > This avoids adjustment when m_Data grows, for a small const access-time > penalty. Toon wrote>In my implementation, I allways recalculate m_seqs when m_data grows. But you would need to perform profiling to know what's best actually. Actually, the recalculation works quite well, so I think I keep the direct pointers to favour access speed. > 1. Arye you interested in such contribution? Toon wrote>I am but need to make sure it provides enough performance for my specific case. See the above testing results, and more details in the enclosed files. I am still very interested in your feedback, especially about how to integrate sequence_arrays into boost, but will not respond to email during my holiday (10-June - 8- July). When cc'd to my email account, I will respond on the 9-th of June or after 8-July. Greetings, Maarten.
SequenceArray.hpp
Description: Binary data
SequenceArrayTest.cpp
Description: Binary data
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
