This is the mail archive of the
mailing list for the libstdc++ project.
- From: Christopher Jefferson <caj at cs dot st-andrews dot ac dot uk>
- To: libstdc++ at gcc dot gnu dot org
- Date: Sun, 23 Aug 2009 20:27:26 +0100
- Subject: simplifying _Temporary_buffer
A few algorithms related to sorting and partitioning use a temporary
buffer, allocated on the fly.
I've been trying to transform the algorithms which use
_Temporary_buffer to allow move-only types, but have been finding this
very difficult. The main difficulty comes from the fact that it isn't
possible to setup the buffer by copying values into it at the start,
as happens at present.
I would like to suggest a radical simplification which makes the code
much simpler and shorter.
At the moment _Temporary_buffer begins by trying to allocate enough
room for a copy of the whole input array, if this fails (which
means ::operator new failed), it repeatedly tries to allocate smaller
blocks of memory. I would like to change this, so if allocating all
requested memory fails, we immediately stop. Note in this case the
algorithm still works, but it is slower.
It is very hard to guess what effect this would have -- I would
suggest that if ::operator new fails, we should probably not be trying
to allocate extra bits of memory. I do not know how often this would
effect people in practice -- I had to try very hard to make this code
trigger, and cannot get it to trigger on a 64-bit processor at all.
If we do not make this simplifying assumption, I believe (although
there may be better coders than I) that the stable_sort and
stable_partition code will have to slow down slightly (~8%) on small
Does anyone know they have ever been in a low-memory environment where
this code was useful?
In summation, the current variable-sized _Temporary_buffer code gets
messy and slow with move-only types, there are 3 choices I can see:
1) Have to code paths, some (possibly all) buffer and no buffer
2) Have two code paths, full buffer and no buffer (much simpler,
slower for part-buffer case)
3) Have three code paths, full buffer, some buffer, no buffer. some
buffer would be really messy, and possibly never called.
Apologises for the long mail,