tech-userlevel archive

[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 <> 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.

Home | Main Index | Thread Index | Old Index