[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index][Old Index]
Re: 64-bit masks
On Mon, 30 Nov 2009 04:03:20 -0000, Steven Bellovin <smb%cs.columbia.edu@localhost>
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
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.
Main Index |
Thread Index |