This is the mail archive of the libstdc++@gcc.gnu.org mailing list for the libstdc++ project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: Extending Temporary buffer for rvalues



On 27 Aug 2009, at 11:15, Paolo Carlini wrote:


.. if we don't have better ideas and we want anyway to complete the
algorithms for C++0x, I think it would make sense for now to just avoid
buffering when std::uninitialized_fill_n would be called in the
_Temporary_buffer constructor.

Unfortunately there are two main problems with that:


1) It's quite a bit slower (around 3 times slower to sort an array of vector<int>s of length 1000).
2) It violates the standard. The algorithm with no buffer is O(n. log n. log n), we are supposed to achieve O(n log n) if there is "enough extra memory available".


While I still don't like it much, I've substantially simplified and cleaned my earlier patch and added some description to it. I'm sure this is correct, as I'm careful to put *__first back when I've initialised the temporary buffer.

I tried just insansating the buffer on first use, the problem is that in the case where the buffer isn't as big as the range we are trying to sort, different amounts of it get used at each call, making it very tricky to ensure each element gets constructed exactly once.

Attachment: tempbuf_diff_2
Description: Binary data








Paolo.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]