# Possibly better stringobject allocator

anish198519851985 at gmail.com anish198519851985 at gmail.com
Mon Feb 17 04:27:43 CET 2014

```On Saturday, February 8, 1997 12:00:00 AM UTC-8, Guido van Rossum wrote:
> > I installed modified versions of stringobject.c and stropmodule.c on our web
> > server.  They are accessible via
> >
> > 	http://www.automatrix.com/~skip/python/
>
> approach.  Did you benchmark it with pystone yet?  (I'm still waiting
> for a better benchmark, but nobody has given me one yet... ;-)
>
> > Warning: This is just a first attempt.  I've done some testing, but not a
> > bunch.  Use this on an experimental basis only.  The code isn't yet properly
> > packaged, and there are some definite warts on it.  Feedback is welcome.
>
> I immediately went to resizestring (to check that you'd taken care of
> it properly -- you have) and noticed that there's one easy
> optimization there: when the new and old sizes fall in the same
> bucket, you don't need to do anything except change the ob_size field.
>
> > One thing I haven't yet figured out is this:  Given an arbitrary number, n,
> > return the power of two that is equal to or greater than n *without writing
> > a loop*.  I can clearly do something like:
> >
> >     for (i = 1; i < n; i <<= 1);
> >
> > Can it be done using a single bit-twiddling expression though?
>
> For numbers < 256 you can do it with a single table lookup, if you can
> spare 256 bytes for the table.  For larger numbers you can quickly
> find the highest byte in the number that's non-zero and use that to
> index the table and add 8* the byte number (if you count from the
> right end ;_)

Below is the code for this idea.

#include <stdio.h>
int log[256];
int next_power_of_two(int no)
{
int t, tt, r;
if(tt = no>> 16) {
r = (t = tt >> 8)?24+log[tt]:16+log[t];
} else {
r = (t = no >> 8)?8+log[t]:log[no];
}
return r;
}

void make_table()
{
int i;

log[0] = 0;
log[1] = 1;
for(i=2;i<256;i++) {
log[i] = 1 + log[i/2];
}
}

int main()
{
int no = 512;
make_table();
printf ("%d\n", next_power_of_two(no));
}
>