Re: 64-bit masks

[Sad Clouds <cryintothebluesky%googlemail.com@localhost>]

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.

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.