This is the mail archive of the 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]

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 arrays.

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 (current status)
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,


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