Re: 64-bit masks

[Steven Bellovin <smb%cs.columbia.edu@localhost>]

On Nov 30, 2009, at 5:50 AM, Sad Clouds wrote:

> On Mon, 30 Nov 2009 04:03:20 -0000, Steven Bellovin 
> <smb%cs.columbia.edu@localhost> wrote:
> 
>> Let me be heretical: if you don't need a lot of these 64-item selections, 
>> why not use an array of 64 ints (or maybe chars or shorts, set up as a 
>> linked list?  Allocating the first free one is basically a single array 
>> index.  Freeing them if you don't need to maintain the order is just as fast.
>> 
>> This is a classic space-time tradeoff; you say you need the speed and RAM is 
>> quite cheap.  That doesn't mean waste it, of course, but you can certainly 
>> spend a bit of RAM to buy CPU cycles in many situations.
> 
> How would this work? Basically the two states I need to keep track of (busy 
> and free) represent waiting threads. Current multicore hardware supports up 
> to 256 parallel threads (Sun UltraSparc T2), and this number will grow in the 
> future.
> 
> When I assign a job to a thread, I mark it busy, then I look for the next 
> free thread. I don't want to step through all 256 threads one at a time, 
> trying to find a free one. I divide threads into groups, from 1 up to 64, 
> using 64-bit masks allows me to look at the state of up to 64 threads at a 
> time.

The simplest way, then, is just to use a linked list.  Assuming you have
some per-thread structure, just add a pointer to that structure and use
it to keep free threads on a free list.  Just pull the first one off the list.

        struct per_thread {
                struct per_thread *next;
                /* everything else you need */
        } threadlist[256];
        struct per_thread *freelist;

        struct per_thread *findfree()
        {
                struct per_thread *p;

                /* Lock the free list */
                p = freelist;
                if (p) freelist = p->next;
                /* Unlock free list */
                return p;
        }

Returning to the freelist and initializing it are left as exercises for the
reader...  You can also make that code inline if you choose.  I know nothing
of your application, so I've said nothing about what to do if there are no
free threads.


> 
> If I keep a list of free threads as an array, then I would have to step 
> through each array element to find a free thread, because different threads 
> might finish jobs at random times and mark themselves free, this will result 
> in fragmentation of the free list.
> 
It's possible to implement linked lists using arrays instead of pointers,
but don't worry about that here.

                --Steve Bellovin, http://www.cs.columbia.edu/~smb