QString: Allocating more than needed?

[Stefan Heimers]

Am Sonntag, 26. Januar 2003 11.27 schrieb David Faure:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> On Sunday 26 January 2003 11:20, Stefan Heimers wrote:
> > - Is there a way to create qstrings with a fixed length, which
> > won't waste memory in case you know they will never grow?
>
> Yes, setLength().


I just had a look at the sources of Qt 3.1.1. It's in tools/qstring.cpp.

setLength() is not what I am looking for, but what I am complaining 
about. It allocates much more than needed, just in case the string 
might grow.

So memory is wasted on strings you know not to grow at all.

But the allocation has been made more modest since the discussion I 
quoted. SO the situation has improved, thanks to Trolltech!


Here is the function determining how much is allocated if you request a 
length of len with setLength();

static uint computeNewMax( uint len )
{
    uint newMax = 4;
    while ( newMax < len )
	newMax *= 2;  // here the next power of two is requested
    // try to save some memory
    if ( newMax >= 1024 * 1024 && len <= newMax - (newMax >> 2) )
	newMax -= newMax >> 2;
    return newMax;
}

What I would like to see is a function like setAbsLength() which would 
allocate exactly the number of characters you request.

In addition to allocating too much, the above function does waste quite 
a few cpu cycles.

The power of two approach is making allocation more efficient as long as 
you use less than one page of memory. If you have a large chunk of 
data, you just want to allocate a number of pages. The amount of memory 
doesn't need to be a power of two.

What about the following replacement for computeNewMax( uint len )? (not 
tested!)

static uint computeNewMax( uint len )
{
    uint newMax = 4;
    uint pages;

    if (len > (2*PAGE_SIZE) )
     {
      // for large data allocate the next larger number of memory
      // pages, no cpu intense iteration needed to find the
      // next power of two
      pages = len / PAGE_SIZE + 1;
      newMax = PAGE_SIZE * pages;
     }
    else
     {
       // small number, power of two makes sense, not many
       // iterations are needed, so let's go
       while ( newMax < len )
	 newMax *= 2;
      // or does someone know of a faster way to find the next
      // larger power of two?
     }
    return newMax;
}

PAGE_SIZE might be the real memory page size of the operating system, or 
any reasonable power of two, eg. 1024.

You could even do it more fancy by detecting memory installed and cpu 
speed, and then decide to optimize for memory usage (just allocate what 
is requested, not more) or cpu usage (allocate much, using a simple 
algorithm to determine needed size) 


Some pseudo-code:


if (mem < 40MB)
 only_allocate_whats_requested();
else if ( mem < 100MB && cpu > 100MHz)
 do_some_fancy_determining_of_optimal_overallocation();
else
 allocate_generousely();

Stefan