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]

Re: Patch 2: speeding up the basic_string modifications

First of all, I understand and support Ryszard's patch as better than
the one I posted but have not personally tested his yet.  His patch
addresses the O() run-time requirements imposed by the C++98 standard.

>1) will string::capacity() return the exact same value as passed to
>   _Rep::_S_create?

I believe so.

>2) wasn't the consensus that the growth should be such that it would be a
>   a power of two *minus* the malloc administration overhead for
>   sizes under the page size, and a multiple of the page size above
>   that?  It seems to me that this patch might -say- try to allocate
>   a capacity of 512 bytes, resulting in a memory allocation of 1024
>   bytes (512 bytes + 4 bytes of malloc administration), which is a
>   waste of memory.

There was no final consensus on this issue of avoiding possible
fragmentation (and/or wasted space) in the memory pool.  Various
people weighed in on how to handle the issue of mapping request sizes
to match internal malloc implementations.  But, this is indeed an
independent issue and may be handled by further upward refinement of
the new memory request size after it has been rounded to handle
run-time requirements.

I think any code to further refine memory block request sizes should
happen at the lowest point of contact to the allocator yet still at a
point that may control capacity...  Under the current library
architecture of basic_string<> that would be _Rep::_S_create().
Unfortunately, no one has posted an algorithm that will be good for
all malloc implementations.  I have one that I believe is good for
systems whose malloc implementation's are known to always round-up and
align memory requests in a certain manner thus wasting space in many
cases (this technique is know to reduce fragmentation).  malloc
implementations that have other tradeoffs in this area will want other
round-up algorithms.

I'm not sure a patch for this issue should go in FSF sources unless we
can make it general.

Loren J. Rittle
Senior Staff Software Engineer, Distributed Object Technology Lab
Networks and Infrastructure Research Lab (IL02/2240), Motorola Labs, KeyID: 2048/ADCE34A5, FDC0292446937F2A240BC07D42763672

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