Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #66580

Re: Possibly better stringobject allocator

Show all headers | View raw

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/
> 
> Cool.  I read your description and am very pleased with your
> 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));
}
> 
> --Guido van Rossum (home page: http://www.python.org/~guido/)

Back to comp.lang.python | Previous | Next | Find similar | Unroll thread

Thread

Re: Possibly better stringobject allocator anish198519851985@gmail.com - 2014-02-16 19:27 -0800

csiph-web