Vector resizing algorithm #
I had heard that the vector class in C++ STL doesn't double every time it needs to resize (as we were taught to do in data structures class), but instead it multiplies the size by 1.5. In a recent article on comp.lang.c++.moderated, Andrew Koenig explains why. It's related to the golden ratio and the Fibonacci sequence:
From: "Andrew Koenig" <ark@acm.org>
Subject: Re: vector growth factor of 1.5
Newsgroups: comp.lang.c++.moderated
Date: 5 Nov 2003 17:26:10 -0500
Organization: AT&T Worldnet
There is a technical reason to prefer 1.5 to 2 -- more specifically, to
prefer values less than 1+sqrt(5)/2.
Suppose you are using a first-fit memory allocator, and you're progressively
appending to a vector. Then each time you reallocate, you allocate new
memory, copy the elements, then free the old memory. That leaves a gap, and
it would be nice to be able to use that memory eventually. If the vector
grows too rapidly, it will always be too big for the available memory.
It turns out that if the growth factor is >= 1+sqrt(5)/2, the new memory
will always be too big for the hole that has been left sofar; if it is
<1+sqrt(5)/2, the new memory will eventually fit. So 1.5 is small enough to
allow the memory to be recycled.
Anti-aliased XEmacs #
I've been wanting an anti-aliased XEmacs for years. There had been a patch a few years ago but it wasn't maintained. There's a new patch out now! The announcement was on the xemacs-beta list.
The authors have been having some trouble getting the patches accepted into the CVS version. I guess I'll just keep applying their patches.
Subscribe to:
Posts (Atom)